[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: tail recursion
From: |
Akim Demaille |
Subject: |
Re: tail recursion |
Date: |
24 Sep 2002 14:32:08 +0200 |
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Honest Recruiter) |
| 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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: tail recursion,
Akim Demaille <=