# [antlr-interest] Re: SLL(1) grammar subset LL(1) grammar: proof by existence?

Terence Parr parrt at cs.usfca.edu
Thu Dec 25 11:19:24 PST 2003

```On Wednesday, December 24, 2003, at 02:37 PM, sarah2geller wrote:

> Now I feel bad. This is unfair if you do not have your books handy.
> Please believe me when I say that LL(1)==SLL(1), at least until you
> can check for yourself. The grammar you gave is SLL(1).

Thanks!  Wow...my memory sucks.  That's SLL(1), eh?  Strange.  Oh well.
I better go back and read my thesis.  I think I understood things 10
years ago. ;)   What must be the difference then between LALL and SLL
lookahead computations?  Perhaps you are actually building LALL
parsers?  I thought I was doing SLL until I read these wacky parsing
books and then decided I was doing LALL. ;)

> What you may be thinking of is that cannonical LL(1) parsers are
> sometimes able to detect errors slightly sooner than SLL(1) parsers.

Yeah, i remember that part.

> But the classes of grammars are identical.

Hmm...still something is bothering me.  I'll have to dig thru the
parsing books when I get back.  i've got some really scary dense
parsing books that made it all clear to me 10 years ago.   Perhaps it's
an EBNF vs BNF thing.  The following should be SLL(1) too, though,
right?

s : (a|C) B t ;

a : A|;

t : a C ;

More likely my confusion is that I'm so used to k>1 that my brain just
improperly back extrapolated to k=1.

BTW, what are your thoughts on a strict ordering for SLL(k) vs
LALL'(k)?  I don't think there is a strict ordering.  SLL(k) has the
vs global FOLLOW accuracy.  The only trouble is that, taking your word
that the above grammar is SLL(1), what could possibly distinguish LALL
from SLL?  For certain they have the same parsing states and therefore
following grammar, which I believe is LALL(2), but not SLL(2):

A -> aBc
A -> C
B -> b
B ->
C -> cBd

According to my prior understanding of SLL(2), the problem is that
the prediction of production 2.  LALL(2) sees the lookahead as {ab,ac}
for production one, hence, has no collision.  Can you confirm/correct
the SLL(2) lookahead computations for me?  Now that I think about it
though, SLL(2) should be able to see the correct lookahead too.  Seems
that LOOK_2(aBc) should be FIRST_2(aBc) which is {ab,ac}, the only
strings generated by aBc.  Hmm...I'll just wait to hear back from you

Anyway, if the above is not SLL(2), then (because LALL'(2) lookahead is
identical to LALL(2) lookahead in this case), it appears that LALL'(2)
has at least one grammar that is not SLL(2).  Can you confirm for me
before I decide I'm totally nuts?! ;)  If that's SLL(2), then I'm at a
loss for the diff between LALL and SLL.  It'll be back to the parsing
theory books for 2 weeks of intense re-education.  yikes!

Happy holidays or upcoming happy new year or whatever to all...

Thanks,
Ter

>
>
>
>
>
>
>
> 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/
>
>
>
--
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!

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/

```