Left recursion

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
   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.

Next topic: Lexical tie-ins
Previous topic: Input style

© 2003 Caldera International, Inc. All rights reserved.
SCO OpenServer Release 5.0.7 -- 11 February 2003