In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?
migrated from cstheory.stackexchange.com Feb 20 at 10:22
This question came from our site for theoretical computer scientists and researchers in related fields.
Recall that a left recursive rule of a CF grammar $G = (V,\Sigma,R,S)$ is of the form:
$\alpha \rightarrow \alpha \beta$
with $\alpha$ an element of $V$ and $\beta$ an element of $V \cup \Sigma$.
Usually, $\beta$ is actually a sequence of terminals and non terminals, and there is an other rule for $\alpha$ where $\alpha$ does not appear in the right hand side.
Whenever a new terminal is being received by the grammar parser (from the lexer), this terminal is pushed atop the stack: this operation is called a shift.
Each time the right hand side of a rule is matched by a group of consecutive elements at the top of the stack, this group is replaced by a single element representing the phrase newly matched. This replacement is called a reduction.
With right recursive grammars, the stack may grow indefinitely until a reduction occurs, thus limiting rather dramatically the parsing possibilities. However, left recursive ones will let the compiler generate reductions earlier (in fact, as soon as possible). See the wikipedia entry for more information.
Consider this rule:
Now consider a LL parser trying to match a non-matching string like
In order to prevent that, you'd either have to parse from the right (which is quite uncommon, as far as i've seen, and would make right recursion the problem instead), artificially limit the amount of nesting allowed, or match a token before the recursion starts so there's always a base case (namely, where all the tokens have been consumed and there's still no complete match). Since a right-recursive rule already does the third, it doesn't have the same problem.