Re: LL(1) vs LL(k)

parrt@ecn.purdue.edu (Terence J Parr) writes:
|[ LL(k-1) < LL(k), but no examples handy ]


Ok, here's one ... I've bluntly stolen this one from:


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


The language generated by this grammar is strong LL(2) but not strong
LL(1). The <B> productions can not be distinguished with just one symbol
look-ahead.


BTW all LL(1) languages are strong LL(1) by definition.


|Given any deterministic language L, L$ (L appended with EOF) can always
|be described with an LR(0) grammar [Knuth65].


|which is a really nifty bit-o-trivia regarding LR. Too bad the same is not
|true for LL; unless, of course, you assume the input is finite--then you
|could just delineate all possible input sequences and you'd have a simple
|(but huge) regular grammar.


Yes, but I consider that as `cheating' ;-) Here's a nice non-LL(k)
language:


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


kind regards,


Jos aka jos@and.nl
AND Software bv, Westersingel 108, NL-3015 LD Rotterdam
Phone: +31 (10) 436 7100 Fax: +31 (10) 436 7110
--

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