What is the trick of SLL(k) grammars subset LL(k) grammars for k>1

Oliver Zeigermann <oliver@zeigermann.de>
16 Jan 2004 22:58:10 -0500

          From comp.compilers

Related articles
What is the trick of SLL(k) grammars subset LL(k) grammars for k>1 oliver@zeigermann.de (Oliver Zeigermann) (2004-01-16)
| List of all articles for this month |

From: Oliver Zeigermann <oliver@zeigermann.de>
Newsgroups: comp.compilers
Date: 16 Jan 2004 22:58:10 -0500
Organization: T-Online
Keywords: parse, LL(1)
Posted-Date: 16 Jan 2004 22:58:10 EST

This is the sequel of me asking trivial questions and getting very
smart answers I do not understand which makes me yell at people ;)


Today's problem is how come every SLL(1) grammar is an LL(1) grammar
*and* the other way round, while this is not true for k>1. For k>1
SLL(k) grammars are a subset of LL(k). An example of an LL(2) grammar
which is not SLL(2) taken from Grune/Jacobs (this time lower case
letters are terminals):


S -> aAaa | bAba
A -> b | lambda


I have a problem with the proof given in Grune/Jacobs. I have no
objections and understand every step taken, but still have no
*intuition* why all this is true.


Thanks for any hints. Any - no - this is no homework, I am just an
all-purpose programmer who really is interested :)


Oliver


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.