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.