|
|
The algorithm used by the yacc parser encourages left-recursive grammar rules. Rules of the following form match this algorithm:
name : name rest_of_rule ;Rules like this arise frequently during the writing of specifications for sequences and lists. For example:
list : item
| list ',' item
;
and:
seq : item
| seq item
;
The first rule in each group
will be reduced for the first item only,
and the second rule
will be reduced for the second and all succeeding items.
With right recursive rules such as the following, the parser is somewhat bigger, and the items are seen and reduced from right to left:
seq : item
| item seq
;
A more serious problem is that an internal stack in the parser
is in danger of overflowing if a very long sequence is read.
Thus, the user should use left recursion whenever possible.
It is worth considering whether a sequence with zero elements has any meaning; if it has, consider writing the sequence specification using an empty rule:
seq : /* empty */
| seq item
;
Once again, the first rule is always reduced
exactly once before the first item is read,
and then the second rule is reduced once for each item read.
Permitting empty sequences often leads to increased generality.
However, conflicts may arise if the parser is asked to decide
between empty sequences that can satisfy more than one rule,
when not enough input has been seen to know which one is appropriate.