Left-Recursion
The grammar for assignment statements from Modules 1 and 2 is left-recursive; that is, in the process of expanding the first nonterminal, that nonterminal is generated again:
Parsing, here initiated by the driver program, proceeds by expanding productions until a terminal (token) is finally generated. Then that terminal is read from the input and the procedure continues. If the first nonterminal is the same as that being expanded, as in the production for an expression above, it will be continually and indefinitely expand without ever generating a terminal that can be matched in the grammar.
Generation of top-down parsers may require a preprocessing step that eliminates left-recursion.
Common Prefix
A second problem is caused by two productions for the same nonterminal whose right-hand side begins with the same symbol:
S --> a 
S --> a 
These two productions contain a common prefix, and once again the parser, as initiated by the driver looking at only the next symbol in the input, does not know which of these productions to choose. Fortunately, grammars can be changed to eliminate these problems. We will show algorithms for changing the grammars to eliminate both left-recursion and common prefixes.
