LL(1) vs LL(k)

parrt@ecn.purdue.edu (Terence J Parr)
Sat, 9 May 1992 01:41:10 GMT

          From comp.compilers

Related articles
LL(1) vs LL(k) parrt@ecn.purdue.edu (1992-05-09)
Re: LL(1) vs LL(k) jos@and.nl (1992-05-09)
Re: LL(1) vs LL(k) j-grout@uiuc.edu (1992-05-09)
Re: LL(1) vs LL(k) mickunas@m.cs.uiuc.edu (1992-05-13)
| List of all articles for this month |

Newsgroups: comp.compilers
From: parrt@ecn.purdue.edu (Terence J Parr)
Keywords: parse, LL(1), LR(1)
Organization: Compilers Central
Date: Sat, 9 May 1992 01:41:10 GMT

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.

Post a followup to this message

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