Sat, 9 May 1992 01:41:10 GMT

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

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.