Re: tail recursion

[Akim Demaille]

| I knew about the bottom-up parsing technique used by bison.  It just never
| occurred to me that I could get away with left recursion in the grammar.
| And I can't find ANY reference to it in any of the bison docs I have.

FYI:

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


But I'm installing this in Bison.texi:

Index: ChangeLog
from  Akim Demaille  <address@hidden>

        * doc/bison.texinfo (Stack Overflow): xref to Recursion.
        (Frequently Asked Questions, Parser Stack Overflow): New.

Index: doc/bison.texinfo
===================================================================
RCS file: /cvsroot/bison/bison/doc/bison.texinfo,v
retrieving revision 1.68
diff -u -u -r1.68 bison.texinfo
--- doc/bison.texinfo 7 Sep 2002 06:33:29 -0000 1.68
+++ doc/bison.texinfo 24 Sep 2002 12:30:02 -0000
@@ -114,6 +114,7 @@
 * Invocation::        How to run Bison (to produce the parser source file).
 * Table of Symbols::  All the keywords of the Bison language are explained.
 * Glossary::          Basic concepts are explained.
+* FAQ::               Frequently Asked Questions
 * Copying This Manual::  License for copying this manual.
 * Index::             Cross-references to the text.
 
@@ -268,6 +269,10 @@
 * Option Cross Key::  Alphabetical list of long options.
 * VMS Invocation::    Bison command syntax on VMS.
 
+Frequently Asked Questions
+
+* Parser Stack Overflow::      Breaking the Stack Limits
+
 Copying This Manual
 
 * GNU Free Documentation License::  License for copying this manual.
@@ -4888,6 +4893,10 @@
 returns a nonzero value, pausing only to call @code{yyerror} to report
 the overflow.
 
+Becaue Bison parsers have growing stacks, hitting the upper limit
+usually results from using a right recursion instead of a left
+recursion, @xref{Recursion, ,Recursive Rules}.
+
 @vindex YYMAXDEPTH
 By defining the macro @code{YYMAXDEPTH}, you can control how deep the
 parser stack can become before a stack overflow occurs.  Define the
@@ -4911,6 +4920,13 @@
 macro @code{YYINITDEPTH}.  This value too must be a compile-time
 constant integer.  The default is 200.
 
address@hidden FIXME: C++ output.
+Because of semantical differences between C and C++, the LALR(1) parsers
+in C produced by Bison by compiled as C++ cannot grow.  In this precise
+case (compiling a C parser as C++) you are suggested to grow
address@hidden  In the near future, a C++ output output will be
+provided which addresses this issue.
+
 @node Error Recovery
 @chapter Error Recovery
 @cindex error recovery
@@ -5788,7 +5804,6 @@
 @noindent
 will produce @file{output.c++} and @file{outfile.h++}.
 
-
 @menu
 * Bison Options::     All the options described in detail,
                        in alphabetical order by short options.
@@ -6011,6 +6026,33 @@
 The VMS file system does not permit filenames such as
 @file{foo.tab.c}.  In the above example, the output file
 would instead be named @file{foo_tab.c}.
+
address@hidden ================================================= Invoking Bison
+
address@hidden FAQ
address@hidden Frequently Asked Questions
address@hidden frequently asked questions
address@hidden questions
+
+Several questions about Bison come up occasionally.  Here some of them
+are addressed.
+
address@hidden
+* Parser Stack Overflow::      Breaking the Stack Limits
address@hidden menu
+
address@hidden Parser Stack Overflow
address@hidden Parser Stack Overflow
+
address@hidden
+My parser returns with error with a @samp{parser stack overflow}
+message.  What can I do?
address@hidden display
+
+This question is already addressed elsewhere, @xref{Recursion,
+,Recursive Rules}.
+
address@hidden ================================================= Table of 
Symbols
 
 @node Table of Symbols
 @appendix Bison Symbols