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.