Re: Why LL(1) Parsers do not support left recursion?

On Sun, 2006-07-16 at 10:44 -0400, Quinn Tyler Jackson wrote:
> * Factoring gets you around the issue in a known and legitimate way, but
> produces parse trees with many intermediate nodes that must be traversed
> before you get to the node type of the actual expression. Something like:
>
> expr
> power
> mult
> div
> add
> number
> integer
>
> Where what you really only need is:
>
> expr
> integer
>
> I have found that trimming the junk intermediate nodes "sooner rather than
> later" makes for easier traversal during tree interpretation. YMMV.


JJTree (comes with JavaCC) uses a notation for doing this called
conditional node descriptors, e.g. the "#AdditiveExpression(>1)" below:


void AdditiveExpression() #AdditiveExpression(>1):
{}
{
MultiplicativeExpression() (( "+" | "-" ) MultiplicativeExpression())*
}


ensures that AdditiveExpression nodes will only be created if they have
more than one child node.


I wrote a fair bit of ugly AST trimming code - which I shamefacedly
deleted after re-reading the documentation and discovering this
feature :-)


Yours,


Tom

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