A grammar can have more than one parse tree generating a given string of terminals. Such a grammar is said to beambiguous. A grammar is called ambiguous if, It permits a terminal string to have more than one parse tree. This means also more than one leftmost derivation for a given string Also, more than one rightmost derivation for same string.
To show that a grammar is ambiguous, all we need to do is find a terminal string that is the yield of more than one parse tree. Since a string with more than one parse tree usually has more than one meaning, we need to design unambiguous grammars for compiling applications, or to use ambiguous grammars with additional rules to resolve the ambiguities.
The grammar for expressions used so far is ambiguous. Two parse trees for id id * id
Ambiguous grammars should be avoided
- Do not guarantee unique parsing and translation
- Expression evaluation is not clearly defined in the above grammar
To eliminate ambiguity of else in if statements ...
- We distinguish matched if statements from unmatched ones
- We insist on having a matched statement between then and else
- Unambiguous grammar for if statements is given below
stmt -> matched | unmatched
matched ->if expr then matched else matched | other-stmt
unmatched -> if expr then stmt
unmatched -> if expr then matched else unmatched