Re: tail recursion

[by way of Hans Aberg]

Hans Aberg <address@hidden> wrote:

>At 21:52 -0400 2002/09/15, address@hidden wrote:
>
<snip>
>
>>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.
>
<snip>
>
>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
>

Thanks, Hans - it worked :)

You have no idea how much I appreciate your help.  I was getting ready to
dust off an old hand-made parser that I once built in a compiler design
course.  You've saved me LOTS of work.

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.

Anyway, thanks again.

Graham

__________________________________________________________________
The NEW Netscape 7.0 browser is now available. Upgrade now!
http://channels.netscape.com/ns/browsers/download.jsp

Get your own FREE, personal Netscape Mail account today at
http://webmail.netscape.com/