Parsing with yacc

Left recursion

The algorithm used by the yacc parser encourages so called left recursive grammar rules. Rules of the form

   name   :   name  rest_of_rule  ;

match this algorithm. Rules such as

   list   :   item
          |   list  ','  item
          ;

and

   seq    :   item
          |   seq  item
          ;

frequently arise when writing specifications of sequences and lists. 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 is a bit bigger; and the items are seen and reduced from right to left. More seriously, an internal stack in the parser is in danger of overflowing if an extremely long sequence is read (although yacc can process very large stacks). Thus, you should use left recursion wherever reasonable.

It is worth considering if a sequence with zero elements has any meaning, and if so, consider writing the sequence specification as

   seq   :   / empty /
         |   seq  item
         ;

using an empty rule. 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 has not seen enough to know!