Re: Parser question

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.


DoDi

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