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

"Rahul Chaudhry" <rahul.chaudhry@gmail.com>
18 Jul 2006 14:06:05 -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? 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)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-22)
Re: Why LL(1) Parsers do not support left recursion? max@gustavus.edu (Max Hailperin) (2006-07-22)
[25 later articles]
| List of all articles for this month |

From: "Rahul Chaudhry" <rahul.chaudhry@gmail.com>
Newsgroups: comp.compilers
Date: 18 Jul 2006 14:06:05 -0400
Organization: http://groups.google.com
References: 06-07-02406-07-039
Keywords: parse, LL(1)
Posted-Date: 18 Jul 2006 14:06:05 EDT

I think the real problem here can be appreciated with a slightly more
complex example:


S ::= Ab | Ac
A ::= Aa | <epsilon>


Here, the grammar cannot be parsed by a LL(k) parser for any finite k,
as I can always construct a sentence in the language that needs more
than k lookahead to make that decision on the first production from
'S'.


A sentence beginning with k a's needs to look at at least (k+1) symbols
to make the decision on which rule to use to expand 'S'. And expanding
'S' to one of the alternatives is the first step a top down parser has
to do.


The grammar above is just the regular expression a*(b|c). It can easily
be re-written to make it friendly to LL parsing.


An LR (or LALR) parser does bottom up parsing. The reduction to 'S'
from one of the alternatives is that last step for it, and hence it can
handle such a grammar just fine. (Try it with yacc).


Hope this helps,
Rahul




SM Ryan wrote:
> "DevInstinct" <martin_lapierre@videotron.ca> wrote:
> # Hi, first of all, I'm not an expert in the theory of computation.
> #
> # I've read about LL(1) parsers and I have seen that they do not support
> # left recursion, because it is said that it would lead to infinite
> # recursivity.
>
> LL(k) grammars make parsing decisions based on the first k symbols.
>
> For
> S ::= Sb | a
> FIRST(Sb,1) = FIRST(S,1) + FIRST(a,1) = {a}
> FIRST(a,1) = {a}
>
> So both alternatives have the same FIRST(1) sets, and you can't decide
> which alternative to use. It's not an LL(1) grammar.


Post a followup to this message

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