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

[Oliver Zeigermann]

Terence Parr wrote:

> 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 for sure no expert in anything, but I still think terms got 
confused, even though this is not your fault or Sarah's. Most books seem 
to use the definition for SLL given above and associate it with "strong 
LL" being the same. Now Grune/Jacobs have *a different* definition of 
"strong LL" and call it "strong-LL" which really is something else "all 
entries in the parse table have at most one element, i.e. it is 
deterministic". Using this definition strong-LL and LL are in the same 
class of grammars, i.e. every LL grammar is strong-LL and every 
strong-LL grammar is LL.

> 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).  

What is the definition of SLL you use, it seems to be neither of the 
ones given by Grune/Jacobs. Even if you are not confused, I am ;)

Oliver



 

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/