Programming Languages – What is Left Recursion in Layman’s Terms

definitionparsingprogramming-languages

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:

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.

"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?

Best Answer

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.

Related Solutions

What imperative programming languages do not support recursion

I'm not sure COBOL does (it certainly didn't at one time), but I can't quite imagine anybody caring much either.

Fortran has since Fortran 90, but requires that you use the recursive keyword to tell it that a subroutine is recursive.

PL/I was pretty much the same -- recursion was supported, but you had to explicitly tell it what procedures were recursive.

I doubt there are many more than that though. When you get down to it, prohibiting recursion was mostly something IBM did in their language designs, for the simple reason that IBM (360/370/3090/...) mainframes don't support a stack in hardware. When most languages came from IBM, they mostly prohibited recursion. Now that they all come from other places, recursion is always allowed (though I should add that a few other machines, notably the original Cray 1, didn't have hardware support for a stack either).

Programming Languages – Advantages of Left-to-Right Language Syntax

The basic advantage is that parsing is simpler and unique. Note that after the line is parsed, the compiler will know what the exact type is, so from there on, how the type was defined is irrelevant.

Any function that returns an argument of array type, or function pointer type are hard to read currently:

// common way of obtaining the static size in elements of an array:
template <typename T, int N>
char (&array_size_impl( T (&)[N] ))[N];
// alternative parser:
template <typename T, int N>               // this would probably be changed also
array_simple_impl function( T [N] & ) char [N] &;

And there would be less chance for misunderstanding (as the most-vexing-parse):

// Current C++
type x( another_type() );      // create an instance x of type passing a
                               // default constructed another_type temporary?
                               // or declare a function x that returns type and takes as argument
                               // a function that has no arguments and returns another_type
// How the compiler reads it:
x function( function() another_type ) type;

// What many people mean:
x type { another_type{} };

Using a similar approach to uniform initialization in C++0x (i.e. {} to identify initialization). Note that with a left to right approach it is much clearer what we are defining. Many people (me for sure) have been bitten at any point by this parsing error in the past (more than once), and that would not be the case with a left-to-right syntax.

Best Answer

Related Solutions

What imperative programming languages do not support recursion

Programming Languages – Advantages of Left-to-Right Language Syntax

Related Topic