Right Recursion versus Left Recursion

Input to yacc mentioned left and right recursion. For example, if a program consists of a number of statements separated by semicolons, you might define it with right recursion as:

program : statement
        │ statement ';' program ;

or with left recursion as:

program : statement
        │ program ';' statement ;

If you think about the way that the state stack works, you can see that the second way is much to be preferred. Consider, for example, the way something like:

S1 ; S2 ; S3 ; S4

is handled (where all the Sn's are statements).

With right recursion, the parser gathers S1; and then go looking for a program. To gather this program, it gathers S2. It then looks at the lookahead symbol ; and sees that this program has the form:

statement ';' program

The parser then gathers the program after the semicolon. But after S3, it finds another semicolon, so it begins gathering yet another program. If you work the process through, you find that the state stack grows to seven entries (one for each Sn: and one for each ;) before the first Reduce takes place.

On the other hand, if you have the left recursion:

program : program ';' statement

and the same input, the parser performs a Reduce as soon as it sees:

S1 ; S2

This is reduced to a single state corresponding to the nonterminal symbol program. The parser reads ;S3 and reduces:

program ; S3

to program again. The process repeats for the last statement. If you follow it through, the state stack never grows longer than three states, as compared with the seven that are required for the right recursive rule. With right recursion, no reduction takes place until the entire list of elements has been read; with left recursion, a reduction takes place as each new list element is encountered. Left recursion can therefore save a lot of stack space.

The choice of left or right recursion can also affect the order that recognition actions are performed in. Suppose T is a token. If you define:

x : /* null */
  │ y ',' x {a1} ;
y : T {a2} ;

then the input:

T , T , T

performs recognition actions in the order:

{a2} {a2} {a2} {a1} {a1} {a1}

The {a2} actions are performed each time a T is reduced to y. The {a1} actions do not happen until the entire list has been read, because right recursion reads the entire list before any Reduce actions take place.

On the other hand, if you define:

x : /* null */
  │ x ',' y {a1} ;
y : T {a2};

the recognition actions for the same input take place in the order:

{a2} {a1} {a2} {a1} {a2} {a1}

With left recursion, Reduce actions take place every time a new element is read in for the list.

This means that if you want the action order:

{a2} {a2} {a2} {a1} {a1} {a1}

you must use right recursion even though it takes more stack space.