Ambiguity and Left Recursion

Many derivations could correspond to a single parse tree. A grammar for which some sentence has more than one parse tree is ambiguous. An ambiguous grammar can be dealt with in two ways:

• Rewrite the grammar to be one that generates the same language but is unambiguous. For example, the if-then-else ambiguity can be eliminated.

• Use disambiguating rules to guide the parser. LEX and YACC have defaults that handle many common cases correctly. Operator precedence parsing is a form of disambiguating rules.

A grammar is left recursive iff A +⇒ A α for some nonterminal A . A left recursive grammar can cause a top-down recursive descent parser to go into an infinite loop. Left recursion can be eliminated by left factoring to obtain an equivalent grammar.