Contents    Page-10    Prev    Next    Page+10    Index   

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:

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.