Next: Semantics Prev: Rules Up: Grammar File

Recursive Rules

   A rule is called "recursive" when its RESULT nonterminal appears
also on its right hand side.  Nearly all Bison grammars need to use
recursion, because that is the only way to define a sequence of any
number of somethings.  Consider this recursive definition of a
comma-separated sequence of one or more expressions:

     expseq1:  exp
             | expseq1 ',' exp

Since the recursive use of `expseq1' is the leftmost symbol in the
right hand side, we call this "left recursion".  By contrast, here the
same construct is defined using "right recursion":

     expseq1:  exp
             | exp ',' expseq1

Any kind of sequence can be defined using either left recursion or
right recursion, but you should always use left recursion, because it
can parse a sequence of any number of elements with bounded stack
space.  Right recursion uses up space on the Bison stack in proportion
to the number of elements in the sequence, because all the elements
must be shifted onto the stack before the rule can be applied even
once.  Note: The Bison Parser Algorithm, for further
explanation of this.

   "Indirect" or "mutual" recursion occurs when the result of the rule
does not appear directly on its right hand side, but does appear in
rules for other nonterminals which do appear on its right hand side.

   For example:

     expr:     primary
             | primary '+' primary
     primary:  constant
             | '(' expr ')'

defines two mutually-recursive nonterminals, since each refers to the

automatically generated by info2www