Ambiguous grammar and Right Most Derivative

1.3k views Asked by At

Ambiguous grammar is defined as, "An ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree."

My doubt is,

1) If the grammar has more than one Right Most Derivatives, does that make the grammar ambiguous?

2) If the grammar has more than one Right Most Derivatives, does that mean it will have more than one Left Most Derivative?

And having more than one Right Most Derivatives has any effect on parsing capability of LL(1), LR(0) parsers, LR(1) parsers etc., why?

Everything is defined and approached based on Left Most Derivatives. This is probably because we move from left to right. But can we gain any insight from Right Most Derivatives?

1

There are 1 answers

0
rici On BEST ANSWER

The choice of left or right is entirely arbitrary. A sentence which has more than one leftmost derivation for a given grammar will also have more than one rightmost derivation and vice versa. So the two possible definitions of ambiguity are equivalent.

This is probably clearer if you consider the derivation to generate a tree rather than a series of derivation steps. The two derivation orders correspond to two different procedures for walking the tree. (Both are depth-first but one visits nodes left-to-right and the other right-to-left.) A grammar is ambiguous if some sentence (that is, the fringe of the tree) appears in two different parse trees. Two different trees will have different walk sequences for both walk procedures, so the traverse can be used to compare trees. (Other walk procedures with this property are also possible.)