Left Recursion

The algorithm used by the yacc parser encourages so-called left recursive grammar rules. Rules of the following form match this algorithm:

name : name rest_of_rule ;

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 is reduced for the first item only; and the second rule is reduced for the second and all succeeding items.

With right-recursive rules, such as:

seq	   	: item 
       	| item seq 
       	;

the parser is somewhat larger; 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 now 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 is always reduced exactly once before the first item is read, and the second rule is 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.