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

Tom Copeland <tom@infoether.com>
18 Jul 2006 01:17:24 -0400

          From comp.compilers

Related articles
Why LL(1) Parsers do not support left recursion? martin_lapierre@videotron.ca (DevInstinct) (2006-07-16)
RE: Why LL(1) Parsers do not support left recursion? qtj-query@shaw.ca (Quinn Tyler Jackson) (2006-07-16)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-18)
Re: Why LL(1) Parsers do not support left recursion? tom@infoether.com (Tom Copeland) (2006-07-18)
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-07-18)
Re: Why LL(1) Parsers do not support left recursion? rahul.chaudhry@gmail.com (Rahul Chaudhry) (2006-07-18)
Re: Why LL(1) Parsers do not support left recursion? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-19)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-21)
Re: Why LL(1) Parsers do not support left recursion? luvisi@andru.sonoma.edu (Andru Luvisi) (2006-07-21)
Re: Why LL(1) Parsers do not support left recursion? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-21)
[27 later articles]
| List of all articles for this month |

From: Tom Copeland <tom@infoether.com>
Newsgroups: comp.compilers
Date: 18 Jul 2006 01:17:24 -0400
Organization: Compilers Central
References: 06-07-024 06-07-027
Keywords: parse, LL(1)
Posted-Date: 18 Jul 2006 01:17:24 EDT

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


Post a followup to this message

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