[antlr-interest] LL(k) vs LALL(k) vs SLL(k) (was Nondeterminism
problem)
Oliver Zeigermann
oliver at zeigermann.de
Fri Dec 19 16:38:13 PST 2003
Have a look at Terence's lectures:
http://nexus.cs.usfca.edu/~parrt/course/652/lectures/formal.language.pdf
Oliver
Greg Lindholm wrote:
> Could someone post a definition and explaination of the differences of
> these:
>
> LL(k) vs LALL(k) vs SLL(k)
>
> It's been kinda hard to follow this tennis match :)
>
> */Terence Parr <parrt at cs.usfca.edu>/* wrote:
>
>
> On Friday, December 19, 2003, at 12:09 PM, sarah2geller wrote:
> > Since t is not on the right side of a production, the t production is
> > not reachable in the grammar.
> >
> > As I said before, LL(1), SLL(1), and LALL(1) are all the same grammar
> > class. This is a well-known fact that you can find in any text book.
>
> I think you'll find it says more precisely that LL(1) can be rewritten
> as SLL(1) but they are not the same class of grammars. Same class of
> languages, though. :)
>
> > So when I said the grammar above was LL(1), that means that it is
> > also SLL(1) because they are the same class. Saying "strong LL(1)" is
> > redundant because all LL(1) grammars are strong.
>
> I just posted an LL(1) grammar that is not LALL(1) nor SLL(1). You
> have to do the transformation I showed. The difference between same
> and equivalent gets kinda murky. ;)
>
> > LL(k) is more
> > powerful than LALL(k) and SLL(k) only for k>1.
>
> And for k=1 grammars, but not languages; just to harp on it for a
> second ;)
>
> Terence
> --
> Professor Comp. Sci., University of San Francisco
> Creator, ANTLR Parser Generator, http://www.antlr.org
> Co-founder, http://www.jguru.com
> Co-founder, http://www.knowspam.net enjoy email again!
> Co-founder, http://www.peerscope.com pure link sharing
>
>
>
>
>
>
> Yahoo! Groups Links
>
> To visit your group on the web, go to:
> http://groups.yahoo.com/group/antlr-interest/
>
> To unsubscribe from this group, send an email to:
> antlr-interest-unsubscribe at yahoogroups.com
>
> Your use of Yahoo! Groups is subject to:
> http://docs.yahoo.com/info/terms/
>
> ------------------------------------------------------------------------
> Do you Yahoo!?
> New Yahoo! Photos - easier uploading and sharing
> <http://pa.yahoo.com/*http://us.rd.yahoo.com/evt=21260/*http://photos.yahoo.com>
>
> ------------------------------------------------------------------------
> *Yahoo! Groups Links*
>
> * To visit your group on the web, go to:
> http://groups.yahoo.com/group/antlr-interest/
>
> * To unsubscribe from this group, send an email to:
> antlr-interest-unsubscribe at yahoogroups.com
> <mailto:antlr-interest-unsubscribe at yahoogroups.com?subject=Unsubscribe>
>
> * Your use of Yahoo! Groups is subject to the Yahoo! Terms of
> Service <http://docs.yahoo.com/info/terms/>.
>
>
Yahoo! Groups Links
To visit your group on the web, go to:
http://groups.yahoo.com/group/antlr-interest/
To unsubscribe from this group, send an email to:
antlr-interest-unsubscribe at yahoogroups.com
Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list