[antlr-interest] LL(k) vs LALL(k) vs SLL(k) (was Nondeterminism problem)

[Greg Lindholm]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20031219/40bdd8ab/attachment.html