Re: Parser question

Hans-Peter Diettrich <>
Tue, 15 Jul 2008 12:42:11 +0200

          From comp.compilers

Related articles
Parser question (Mike \(News\)) (2008-07-11)
Re: Parser question (Aeran) (2008-07-13)
Re: Parser question (Max Hailperin) (2008-07-13)
Re: Parser question (Hans-Peter Diettrich) (2008-07-15)
Re: Parser question (Mikael =?ISO-8859-1?Q?Str=F6m?=) (2008-07-17)
Re: Parser question (Max Hailperin) (2008-07-19)
| List of all articles for this month |

From: Hans-Peter Diettrich <>
Newsgroups: comp.compilers
Date: Tue, 15 Jul 2008 12:42:11 +0200
Organization: Compilers Central
References: 08-07-024
Keywords: parse
Posted-Date: 19 Jul 2008 14:43:15 EDT

Mike (News) schrieb:

> The implementation is a predictive parser that construct a syntax tree
> holding both expression and statements. As the grammar is recursive,
> so is the implementation. However, i wish to find some shortcuts to
> rewrite (at least some of) the recursive functions to be
> iterative. Are there any well known algorithms of doing this?

> For instance the grammar for:
> expr -> term moreterms
> moreterms -> + term | - term | N5
> Is inherently recursive. How would I write iterative code for this using
> my tree function makenode_op(operand, left, right)?

One method would "flatten" the operator hierarchy, to essentially only
one unary and binary operator class, covering all operators:

      moreterms -> binop term | epsilon

Then something like an internal list (usually stack) of operators and
terms is produced by moreterms, that is "folded" into an tree before
exit, based on the operator precedence, grouping etc.

Otherwise indirect recursion may not be eliminated, by tail recursion or
a conversion of distinct productions.


Post a followup to this message

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