Re: An example LL(K) language that is not LL(K-1) ?

klyjikoo <klyjikoo@gmail.com>
Tue, 2 Feb 2010 15:27:14 +0330

          From comp.compilers

Related articles
An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-01-26)
Re: An example LL(K) language that is not LL(K-1) ? haberg_20080406@math.su.se (Hans Aberg) (2010-01-28)
An example LL(K) language that is not LL(K-1) ? chakaram@auth.gr (Chariton Karamitas) (2010-02-01)
Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-02)
Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-03)
Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-03)
Re: An example LL(K) language that is not LL(K-1) ? daniel.eliason@excite.com (fortunatus) (2010-02-04)
Re: An example LL(K) language that is not LL(K-1) ? slkpg@cox.net (SLK Mail) (2010-02-05)
Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-05)
Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-06)
[6 later articles]
| List of all articles for this month |

From: klyjikoo <klyjikoo@gmail.com>
Newsgroups: comp.compilers
Date: Tue, 2 Feb 2010 15:27:14 +0330
Organization: Compilers Central
References: 10-02-009
Keywords: LL(1)
Posted-Date: 02 Feb 2010 23:09:32 EST



> I don't think your assumption that any LL(k) can be transformed into
> an LL(k-1) is correct. The 'k' in LL(k) is assumed to be the supremum
> of lookahead symbols that you need in order to parse your input. So,
> suppose you have an LL(2) grammar, then you cannot convert it to an
> LL(1) since the LL(1) equivalent won't have disjoint FIRST/FOLLOW sets!


> I am not yet very experienced when it comes to compilers, so, if my
> answer is wrong correct me please! :-)n


Thanks to Hans, Consider this example :


  1) Z := X
  2) X := Y
  3) X := bYa
  4) Y := c
  5) Y := ca


> The book by Waite and Goos, "Compiler Construction", sec 5.3, p. 124,
> gives an example of an LL(3) grammar that isn't LL(2)


After substitution of production 4 and 5 in production 2 and 3 ...the
following grammar can obtained:


          Z := X
          X := c
          X := c a
          X := b c a
          X := b c a a


Now after left factoring....the following grammar can obtained...that
is an LL(1) grammar:


        Z := X
        X := c A
        A := eps
        A := a
        X := b c a B
        B := eps
        B := a



Post a followup to this message

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