(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().
