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

Andru Luvisi <luvisi@andru.sonoma.edu>
21 Jul 2006 16:01:39 -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)
Re: Why LL(1) Parsers do not support left recursion? egagnon@sablevm.org (Etienne Gagnon) (2006-07-22)
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-07-23)
Re: Why LL(1) Parsers do not support left recursion? max@gustavus.edu (Max Hailperin) (2006-07-23)
[22 later articles]
| List of all articles for this month |

From: Andru Luvisi <luvisi@andru.sonoma.edu>
Newsgroups: comp.compilers
Date: 21 Jul 2006 16:01:39 -0400
Organization: Compilers Central
References: 06-07-024
Keywords: parse, LL(1)

>>>>> "DevInstinct" == DevInstinct <martin_lapierre@videotron.ca> writes:


        DevInstinct> My question: why is that? In which case a LL(1)
        DevInstinct> parser can enter infinite recursivity?


        DevInstinct> I can't find a good example that demonstrates that.


Consider the grammar


term ::= '[0-9]+';
expr ::= expr '+' term |
                  term;


and the expression


    1 + 2 + 3 + 3 + 5


Ideally, this should be parsed into an abstract syntax tree that looks
something like:


    add(add(add(add(1, 2), 3), 4), 5)


Here's the problem. When you're handling the 1, you don't know
whether to recurse into the "expr '+' term" or terminate on the
"term". You actually should recurse four times and then terminate,
but you can't know that without looking way ahead to the end of the
expression, which can be arbitrarily far away, and you're only allowed
one token of lookahead in LL(1).


Andru
--
Andru Luvisi


Quote Of The Moment:
    "If you give someone Fortran, he has Fortran.
      If you give someone Lisp, he has any language he pleases."
     -- Guy Steele


Post a followup to this message

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