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

[Terence Parr]

On Tuesday, December 23, 2003, at 04:29 PM, Oliver Zeigermann wrote:
> Hmmm, the misunderstanding seems to be based on the difference between
> SLL (=simply LL) and strong-LL. As indicated by the reference Sarah
> already gave:
>
> http://www.cs.vu.nl/~dick/PTAPG.html
>
> p. 174, 8.2.3 claims every strong-LL(1) is LL(1) and the other way
> round, but not true for k > 1. This is what Sarah says. Now on p.167,
> 8.1 it says *simple LL(1)* also called *SLL(1)* is a subset of LL(1)
> which is obvious when we have a look at the informal definition: "all
> right-hand sides of a non-terminal start with a different terminal
> symbol". That's what Terence said. Both are more or less right then, 
> but
> were just using those confusing names differently.

Hi Oliver,

Interesting...never heard of "simple LL(k)".  I've only seen SLL(k) to 
mean Strong LL(k).  Anyway, I don't think we've been confusing that ;)

I am on vacation so I don't have my parsing theory books handy.  I'm 
going from memory, which we all know can be flawed. ;)  Particularly 
mine. (anybody seen my car keys? <snicker>).  My confusion arises from 
this grammar, which is clearly LALL(1) as ANTLR and PCCTS gulp it down. 
  [To ensure that rule t is called, I'll add it to the end of rule s for 
fun even though it is unnecessary.]

s : s2 B t ;

s2 : a | C ;

a : A | ;

t : a C ;

The Grune/Jacob book aside for the moment, I believe this grammar is 
not SLL(1).  Can anybody run this through an SLL(1) parser generator to 
simply check?  I remember SLL(k) computing the lookahead as simply 
FIRST(alpha FOLLOW(A)) for A->alpha without concern for any 
left-context (hence it's weakness compared to LALL and full LL).  Here, 
the lookahead for production

s2 : a

yields FIRST(a)==A union FOLLOW(a) which is {A,B,C}.  Since {C} also 
predicts

s2 : C

there is a conflict between the alternatives of rule s2 upon input C.  
Yet, ANTLR properly computes the "local" FOLLOW by taking advantage of 
some left-context--it knows that the rule t can never be called from s2 
and hence computing lookahead for the epsilon transfer of rule 'a' 
should not include C (from rule t).  When asked for full FOLLOW(a), 
ANTLR correctly gave me {B,C}, by the way.

As I've said before, you can transform this LALL(1)/LL(1) grammar to 
SLL(1) easily by duplicating rule 'a'.

I may be going crazy, but I think this is a simple proof by existence 
that there exists at least one grammar that is LALL(1), hence LL(1), 
that is not SLL(1).  One needs only to show that this grammar is also 
SLL(1) to shoot me down.  An easy kill. ;)

I think something is wrong with Grune/Jacob's book. ;)

Best regards,
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/