|LL(1) vs LL(k) email@example.com (1992-05-09)|
|Re: LL(1) vs LL(k) firstname.lastname@example.org (1992-05-09)|
|Re: LL(1) vs LL(k) email@example.com (1992-05-09)|
|Re: LL(1) vs LL(k) firstname.lastname@example.org (1992-05-13)|
|From:||email@example.com (Terence J Parr)|
|Keywords:||parse, LL(1), LR(1)|
|Date:||Sat, 9 May 1992 01:41:10 GMT|
> [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 firstname.lastname@example.org
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
Search the comp.compilers archives again.