In layman's terms, what is left recursion?

Question

According to one page on code.google.com, "left recursion" is defined as follows:

Left recursion just refers to any recursive nonterminal that, when it produces a sentential form containing itself, that new copy of itself appears on the left of the production rule.

Wikipedia offers two different definitions:

1. In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s productions (‘alternatives’) either immediately (direct/immediate left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites to r again.

2. "A grammar is left-recursive if we can find some non-terminal A which will eventually derive a sentential form with itself as the left-symbol."

I'm just barely starting out with language creation here, and I'm doing it in my spare time. However when it comes down to selecting a language parser, whether left recursion is supported by this parser or that parser is an issue that immediately comes up front and center. Looking up terms like "sentential form" only leads to further lists of jargon, but the distinction of "left" recursion almost has to be something very simple. Translation please?

Answer 1

A rule R is left-recursive if, in order to find out whether R matches, you first have to find out whether R matches. This happens when R appears, directly or indirectly, as the first term in some production of itself.

Imagine a toy version of the grammar for mathematical expressions, with only addition and multiplication to avoid distraction:

Expression ::= Multiplication '+' Expression
            || Multiplication

Multiplication ::= Term '*' Term
                 || Term

Term ::= Number | Variable

As written, there's no left-recursion here — we could pass this grammar to a recursive-descent parser.

But suppose you tried to write it this way:

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

This is a grammar, and some parsers can cope with it, but recursive descent parsers and LL parsers can't — because the rule for Expression begins with Expression itself. It should be obvious why in a recursive-descent parser this leads to unbounded recursion without actually consuming any input.

It doesn't matter whether the rule refers to itself directly or indirectly; if A has an alternative that starts with B, and B has an alternative that starts with A, then A and B are both indirectly left-recursive, and in a recursive-descent parser their matching functions would lead to endless mutual recursion.

Answer 2

I'll take a stab at putting it into layman's terms.

If you think in terms of the parse tree (not the AST, but the parser's visitation and expansion of the input), left recursion results in a tree that grows left and downwards. Right recursion is exactly the opposite.

As an example, a common grammar in a compiler is a list of items. Lets take a list of strings ("red", "green", "blue") and parse it. I could write the grammar a few ways. The following examples are directly left or right recursive, respectively:

arg_list:                           arg_list:
      STRING                              STRING
    | arg_list ',' STRING               | STRING ',' arg_list 

The trees for these parse:

         (arg_list)                       (arg_list)
          /      \                         /      \
      (arg_list)  BLUE                  RED     (arg_list)
       /       \                                 /      \
   (arg_list) GREEN                          GREEN    (arg_list)
    /                                                  /
 RED                                                BLUE

Note how it grows in the direction of the recursion.

This isn't really a problem, it is ok to want to write a left recursive grammar...if your parser tool can handle it. Bottom up parsers handle it just fine. So can more modern LL parsers. The problem with recursive grammars isn't recursion, it is recursion without advancing the parser, or, recursing without consuming a token. If we always consume at least 1 token when we recurse, we eventually reach the end of the parse. Left recursion is defined as recursing without consuming, which is an infinite loop.

This limitation is purely an implementation detail of implementing a grammar with a naive top-down LL parser (recursive descent parser). If you want to stick with left recursive grammars, you can deal with it by rewriting the production to consume at least 1 token before recursing, so this ensures we never get stuck in non-productive loop. For any grammar rule that is left-recursive, we can rewrite it by adding an intermediate rule that flattens out the grammar to just one level of lookahead, consuming a token between the recursive productions. (NOTE: I'm not saying this is the only way or the preferred way to rewrite the grammar, just pointing out the generalized rule. IN this simple example, the best option is to use the right-recursive form). Since this approach is generalized, a parser generator can implement it without involving the programmer (theoretically). In practice, I believe ANTLR 4 now does just that.

For the grammar above, the LL implementation displaying left recursion would look like this. The parser would start with predicting a list...

bool match_list()
{
    if(lookahead-predicts-something-besides-comma) {
       match_STRING();
    } else if(lookahead-is-comma) {
       match_list();   // left-recursion, infinite loop/stack overflow
       match(',');
       match_STRING();
    } else {
       throw new ParseException();
    }
}

In reality, what we are really dealing with is "naive implementation", ie. we initially predicated a given sentence, then recursively called the function for that prediction, and that function naively calls the same prediction again.

Bottom up parsers do not have the problem of recursive rules in either direction, because they don't reparse the beginning of a sentence, they work by putting the sentence back together.

Recursion in a grammar is only a problem if we produce from top down, ie. our parser works by "expanding" our predictions as we consume tokens. If instead of expanding, we collapse (productions are "reduced"), as in a LALR (Yacc/Bison) bottom up parser, then recursion of either side isn't a problem.