Search code examples
parsingambiguityderiving

Can I consider this derivation as Leftmost or/and Rightmost?

For example I would like to derive the string 'aabbccdd' from the given set of production:

S -> AB  | C
A -> aAb | ab
B -> cBd | cd
C -> aCd | aDd
D -> bDc | bc

I can derive the string from AB using the leftmost and rightmost derivation.

But how about from C? Upon deriving the string, I am always having one variable only.

Derivation from C:

S -> C
S -> aCd
S -> aaDdd
S -> aabDcdd
S -> aabbccdd

What kind of derivation was used and can I consider this grammar ambiguous?

Solution

    1. In a rightmost derivation, the rightmost non-terminal is derived. In a leftmost derivation, the leftmost non-terminal is derived. If there is only one non-terminal, the derivation is both leftmost and rightmost. This is not a contradiction.

    2. Since there are two derivations for the target string starting with S, the grammar is ambiguous.