The algorithm used by the Yacc parser encourages so called ``left recursive'' grammar rules: rules of the form
name : name rest_of_rule ;These rules frequently arise when writing specifications of sequences and lists:
list : item | list ',' item ;and
seq : item | seq item ;In each of these cases, the first rule 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
seq : item | item seq ;the parser would be a bit bigger, and the items would be seen, and reduced, from right to left. More seriously, an internal stack in the parser would be in danger of overflowing if a very long sequence were read. Thus, the user should use left recursion wherever reasonable.
It is worth considering whether a sequence with zero elements has any meaning, and if so, consider writing the sequence specification with an empty rule:
seq : /* empty */ | seq item ;Once again, the first rule would always be reduced exactly once, before the first item was read, and then the second rule would be reduced once for each item read. Permitting empty sequences often leads to increased generality. However, conflicts might arise if Yacc is asked to decide which empty sequence it has seen, when it hasn't seen enough to know!