Re: LL(1) vs LL(k) (Jos Horsmeier)
Sat, 9 May 1992 11:34:35 GMT

          From comp.compilers

Related articles
Re: An example LL(K) language that is not LL(K-1) ? (Kaz Kylheku) (2010-02-06)
LL(1) vs LL(k) (1992-05-09)
Re: LL(1) vs LL(k) (1992-05-09)
Re: LL(1) vs LL(k) (1992-05-09)
Re: LL(1) vs LL(k) (1992-05-13)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Jos Horsmeier)
Keywords: parse, LL(1)
Organization: AND Software BV Rotterdam
References: 92-05-050
Date: Sat, 9 May 1992 11:34:35 GMT (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

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)

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

kind regards,

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

Post a followup to this message

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