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

[Terence Parr]

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 
advantage in sequence information for lookahead, but LALL has the local 
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 
can differ only in the lookahead computation.  Ok, what about the 
following grammar, which I believe is LALL(2), but not SLL(2):

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

According to my prior understanding of SLL(2), the problem is that 
SLL(2) assumes lookahead of {ab,ac,ad} predicts production one of A 
even though lookahead ad is not possible; lookahead ad collides with 
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 
about it's membership.

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


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