CODEWITHSUNDEEP
parsingcompiler-construction
Taha Jiruwala
Taha Jiruwala

Reputation: 11

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.

Upvotes: 0

Views: 738

Answers (1)

rici
rici

Reputation: 241931

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.

Upvotes: 1

Related Questions