enter image description here

I would really appreciate if someone can explain the syntax diagram itself and can help to build the parsing tree.


That diagram describes a language, a set of words over some alphabet.

Intuitively, this language contains all the words that can be obtained traveling over the diagram from the beginning (on the left) and following the arrows.

If we take the upper route, we build a word starting with $x$, then continuing with any string (or at least that's how I read that "String" box), and then ending with another $x$.

If we take the lower route, we form the word $x$, only.

To solve the exercise, you have to find a route which can generate the given string $xxyxx$. When doing so, you have to note down what parts of your string correspond to the nodes in the diagram (e.g. what correspond to the "String" box).

Note that this diagram is somewhat simple, in that it has no loops, so the parse tree is also simple. With loops, it could be more complex.

The last part of the exercise asks you to find a word which can not be generated following the diagram.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.