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

> 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

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