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

[Oliver Zeigermann]

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/