Re: Is LL(k) LL(1) ?

William D Clinger <will@ccs.neu.edu>
29 Apr 1998 22:30:09 -0400

          From comp.compilers
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)
| List of all articles for this month |
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.