Re: inling/tail recursion, recursive decent parser

Lefteris Keftedopoulos <spam@disney.com> wrote:
>Would inlining / tail recursion have significant effect on the amount
>of call stack space used by a recursive decent parser?


Tail recursion unfortunately isn't common in recursive-descent parsers.
Much more usual are structures like:


start()
while (there's more)
more()


which unfortunately don't lend themselves to that kind of optimization.


Inlining could help substantially, if you're willing to accept some
increase in code size. In a straightforward recursive-descent parser,
many procedures are called from only one or two places. Inlining
won't reduce the space used for variables very much, but it will cut
out a lot of per-call stack-frame overhead. (Caveat: the benefits
will be reduced substantially if operator precedence in expressions is
handled by some specialized trick rather than by having a level of
procedures per level of precedence.)
--
"Think outside the box -- the box isn't our friend." | Henry Spencer
                                                                -- George Herbert | henry@spsystems.net

Return to the comp.compilers page.
Search the comp.compilers archives again.