when do we say a grammar to be unambiguous with respect to parse tree and derivation tree?

1.4k Views Asked by At

In normal terminology we say that both the parse and derivation trees are same in meaning so if a grammar derives one string with left derivation as well as right derivation then it is ambiguous , if both left and right derivation correspond to 2 different parse trees.

Now what if I have the left-most derivation tree to be similar to right-most derivation tree ,and they both correspond to 1 parse tree so can I conclude that the grammar is unambiguous ?

1

There are 1 best solutions below

0
On

An unambiguous grammar has same leftmost and rightmost derivation:


Ambiguous Grammars


Definitions:


  • If a grammar has more than one leftmost derivation for a single sentential form, the grammar is $\color{Blue}{\text{ambiguous}.}$

  • If a grammar has more than one rightmost derivation for a single sentential form, the grammar is $\color{Blue}{\text{ambiguous}.}$

  • The leftmost and rightmost derivations for a sentential form $\color{Red}{\text{may differ,}}$ even in an $\color{Green}{\text{unambiguous}}$ grammar.

Ref@https://www.eecis.udel.edu/~cavazos/cisc471-672/lectures/Lecture-08.pdf


Comment : Here, last point says an unambiguous grammar has same (or may not be) leftmost and rightmost derivation.

On the other hand, if a grammar has more than one parse tree for any string in given language, then grammar said to be ambiguous.