29 Apr 1998 22:30:09 -0400

Related articles |
---|

Is LL(k) LL(1) ? feedME!minotoko@uunet.uu.net (1998-04-15) |

Re: Is LL(k) LL(1) ? will@ccs.neu.edu (William D Clinger) (1998-04-29) |

Re: Is LL(k) LL(1) ? corbett@lupa.Eng.Sun.COM (1998-05-04) |

Re: Is LL(k) LL(1) ? torbenm@diku.dk (Torben Mogensen) (1998-05-07) |

Re: Is LL(k) LL(1) ? jhf@lanl.gov (Joseph H. Fasel) (1998-05-12) |

From: | William D Clinger <will@ccs.neu.edu> |

Newsgroups: | comp.compilers |

Date: | 29 Apr 1998 22:30:09 -0400 |

Organization: | Northeastern University |

References: | 98-04-065 |

Keywords: | LL(1), theory |

*> Can any LL(k) grammar be transformed into an LL(1) one ?*

No:

It has been shown that the classes of LL(k) languages are distinct

for every k, and properly contained in the deterministic languages.

Thus there are some languages with SLR(1) (or even LR(0)) grammars

that do not have LL(k) grammars at all! This is sometimes thought

to prove the superiority of the LR approach, but, in practice,

programming languages do not actually seem to fall in the gap

between LL(1) languages and deterministic languages....

-- J J Horning, "LR Grammars and Analyzers", in Bauer and Eickel

[editors], Compiler Construction: an Advanced Course, second

edition, Springer-Verlag, 1976.

Will

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.