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?

• Typically, compilers use top-down parsing. If you have left-recursion, then the parser goes into an infinite recursion. However, in right-recursion, the parser can see the prefix of the string that it has so far. Thus, it can check whether the derivation went "too far". You can, of course, swap the roles and interpret expressions from the right, making right-recursion bad, and left-recursion fine. Feb 20, 2013 at 10:20
• Left recursion is bad because in the old days when computers had 16 KB of RAM the most commonly used parser generator could not cope with it. Feb 20, 2013 at 13:38

Left recursive grammars are not necessarily a bad thing. These grammars are easily parsed using a stack to keep track of the already parsed phrases, as it is the case in LR parser.

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$. (See the complete formal definition for the tuple $(V,\Sigma,R,S)$ there).

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.

• It would help if you defined your variables. Mar 29, 2014 at 19:58

Consider this rule:

example : 'a' | example 'b' ;


Now consider a LL parser trying to match a non-matching string like 'b' to this rule. Since 'a' doesn't match, it'll try to match example 'b'. But in order to do so, it has to match example...which is what it was trying to do in the first place. It could get stuck trying forever to see whether it can match, because it's always trying to match the same stream of tokens to the same rule.

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.

• You are sort of blindly assuming that parsing is necessarily naive top-down parsing. Feb 21, 2013 at 13:17
• I'm highlighting a pitfall of a rather common method of parsing -- a problem that can easily be avoided. It's certainly possible to handle left-recursion, but retaining it creates an almost-always-unnecessary limitation on the type of parser that can use it.
– cHao
Feb 21, 2013 at 19:10
• Yes, that's a more constructive and useful way of putting it. Feb 22, 2013 at 19:43

(I know this question's pretty old by now, but in case other people have the same question...)

Are you asking in the context of recursive descent parsers? For example, for the grammar expr:: = expr + term | term, why something like this (left recursive):

// expr:: = expr + term
expr() {
expr();
if (token == '+') {
getNextToken();
}
term();
}


is problematic, but not this (right recursive)?

// expr:: = term + expr
expr() {
term();
if (token == '+') {
getNextToken();
expr();
}
}


It looks like both versions of expr() call themselves. But the important difference is the context -- i.e. the current token when that recursive call is made.

In the left recursive case, expr() continually calls itself with the same token and no progress is made. In the right recursive case, it consumes some of the input in the call to term() and the PLUS token before reaching the call to expr(). So at this point, the recursive call may call term and then terminate before reaching the if test again.

For example, consider parsing 2 + 3 + 4. The left recursive parser calls expr() infinitely while stuck on the first token, while the right recursive parser consumes "2 +" before calling expr() again. The second call to expr() matches "3 +" and calls expr() with only the 4 left. The 4 matches to a term and the parsing terminates without any more calls to expr().

From Bison manual:

"Any kind of sequence can be defined using either left recursion or right recursion, but you should always use left recursion, because it can parse a sequence of any number of elements with bounded stack space. Right recursion uses up space on the Bison stack in proportion to the number of elements in the sequence, because all the elements must be shifted onto the stack before the rule can be applied even once. See The Bison Parser Algorithm, for further explanation of this."

http://www.gnu.org/software/bison/manual/html_node/Recursion.html

So it depends on the parser's algorithm, but as stated in other answers, some parsers may simply not work with left recursion