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

>>>>> "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

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