Sat, 9 May 1992 11:34:35 GMT

Related articles |
---|

Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-06) |

LL(1) vs LL(k) parrt@ecn.purdue.edu (1992-05-09) |

Re: LL(1) vs LL(k) jos@and.nl (1992-05-09) |

Re: LL(1) vs LL(k) j-grout@uiuc.edu (1992-05-09) |

Re: LL(1) vs LL(k) mickunas@m.cs.uiuc.edu (1992-05-13) |

Newsgroups: | comp.compilers |

From: | jos@and.nl (Jos Horsmeier) |

Keywords: | parse, LL(1) |

Organization: | AND Software BV Rotterdam |

References: | 92-05-050 |

Date: | Sat, 9 May 1992 11:34:35 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.