LL(1) vs LL(k)

John writes:


> [On that third bullet, I thought anything that was LL(k) was also LL(1),
> albeit perhaps requiring ugly rewrites of the grammar. -John]


Actually, theory says that LL(k-1) grammars describe a strictly smaller
class of languages than LL(k) although I can't find an example I'm convinced
can't be rewritten as LL(1). Maybe someone can respond with a language.
On the other hand, LR(k) is reducable to LR(1). In fact, I think that if you
guarantee an EOF symbol you can even show it can be LR(0) as well:


Given any deterministic language L, L$ (L appended with EOF) can always
be described with an LR(0) grammar [Knuth65].


which is a really nifty bit-o-trivia regarding LR. Too bad the same is not
true for LL; unless, of course, you assume the input is finite--then you
could just delineate all possible input sequences and you'd have a simple
(but huge) regular grammar.


Terence Parr parrt@ecn.purdue.edu
Purdue University Electrical Engineering


[Knuth65] Donald E. Knuth, "On the Translation of Languages from Left
                    to Right," Information and Control 8, 1965, pp 607-639.
--

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