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

On 2010-02-01, Chariton Karamitas <chakaram@auth.gr> wrote:
> Hello,
>
> 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!


Note that the disjointness of the FIRST and FOLLOW sets criteria is
a marker of /strong/ LL(k) grammars, not LL(k) in general.


Jos Hormeier, in a May 9, 1992 posting to comp.compilers provides an example of
a strong LL(2) grammar that is not strong LL(1), taken from a textbook.


The thread is accessible through this URL:


http://compilers.iecc.com/comparch/article/92-05-052


Quote:


                An Introduction to Formal Language Theory
                Robert N. Moll, Michael A. Arbib, A.J. Kfoury
                Springer Verlag ISBN 0-387-96698-6


                page 129:


                <S> : a <B> <B> | b <C>
                <B> : <C> <B> | a <C>
                <C> : a b <S> | c


Cheers ...

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