(bison) Recursion

Info Catalog

(bison) Rules

(bison) Grammar File

(bison) Semantics

 
 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 a particular thing.  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.  
 The Bison Parser Algorithm 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
 other.
 

Info Catalog

(bison) Rules

(bison) Grammar File

(bison) Semantics