Re: tail recursion

[Hans Aberg]

At 21:52 -0400 2002/09/15, address@hidden wrote:
>I've been fooling around with flex and bison for a while now, and I'm
>currently trying to put together a VRML file parser.  I want it to create
>and initialize C++ objects in a scene graph, so the parser needs to
>understand C++.
>
>My problems started when I began to read in non-trivial files and I
>encountered a parser stack overflow.  The problem seems to have two parts.
>
>First, I discovered that the stack depth was not being updated in
>accordance with the YYMAXDEPTH constant.

These are well known problems with older versions and C++: These versions
did not really support C++, but merely made it possible to compile it. For
example, the C stacks that were implemented will not respect the C++ copy
constructors when reallocating.

Use the latest Bison beta: ftp://alpha.gnu.org/gnu/bison/  (bison-1.49x.tar.gz)

Compile with -S C++.bison (or bison.c++ or something).

>The more serious problem is with right recursion in the syntactical
>definitions of the grammar.  I want to parse a list of vertices that could
>be arbitrarily long (depending on the file used for input).  The
>production is typical:
>
>       vertex_list : vertex ',' vertex_list ;
>
>No matter how big I make the stack, some file will eventually make it
>overflow.

If you use the correct C++ support the problem will go away, as the stack
will properly reallocated.

But due to the bottom up nature of the algorithm LALR(1) that Bison uses,
recursion rules should be written
    vertex_list : vertex_list ',' vertex;
if you want to avoid parser stack growth. -- It's in the Bison manual
somewhere.

  Hans Aberg