in Compiler Design retagged by
1,408 views
2 votes
2 votes
If a grammar( $CFG$ ) has more than one Right most derivation, Can it be called ambiguous ?

Or we say a grammar is ambiguous only when it has more than one left most derivation ?
in Compiler Design retagged by
1.4k views

3 Answers

6 votes
6 votes
Best answer
If any CFG $G$ has at least one String such that for that String, we have either

1. Two or more Right Most Derivation then $G$ is ambiguous.

or

2. Two or more left most Derivation then $G$ is ambiguous

or

3. Two or more Parse Tress (Derivation Trees) then $G$ is ambiguous.
selected by
3 votes
3 votes

A grammar is called ambiguous grammar if it has

  1. 2 or more Left most derivation (LMD)
  2. 2 or more Right most derivation (RMD)

Why grammar becomes ambiguous?  Its because whenever the compiler sees 2 or more possibilities to derive the same string(either via LMD or RMD) then it gets confused which one to choose to derive the string.

0 votes
0 votes
For , proving a grammar to be ambiguous , we should have at least one string generated by the grammar such that the string has:

1-> more than one parse tree.

2-> 2 or more than 2 right most derivations .

3-> 2 or more than 2 left most derivations.

 Any of  the three would suffice.