Search code examples
parsingcompiler-construction

Parse trees in ambiguous and unambiguous grammar


In an unambiguous grammar, do left and right derivation both produce the same parse tree? Because I have read that grammar having more than one parse tree is said to be ambiguous.


Solution

  • If the grammar is unambiguous, there is only one parse tree. (By definition.) So the leftmost and rightmost derivations generate the same tree.

    You can think of a derivation as a tree walk. For a given tree, there are many different possible ways of traversing it. Leftmost and rightmost derivations are pre- and post-order depth-first traverses, respectively.