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

SM Ryan <wyrmwif@tsoft.org>
18 Jul 2006 01:18:40 -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)
[26 later articles]
| List of all articles for this month |
From: SM Ryan <wyrmwif@tsoft.org>
Newsgroups: comp.compilers
Date: 18 Jul 2006 01:18:40 -0400
Organization: Quick STOP Groceries
References: 06-07-024
Keywords: parse, LL(1)
Posted-Date: 18 Jul 2006 01:18:40 EDT

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


--
SM Ryan http://www.rawbw.com/~wyrmwif/
I'm not even supposed to be here today.

Post a followup to this message

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