Sat, 6 Feb 2010 01:03:08 +0000 (UTC)

From: | Kaz Kylheku <kkylheku@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sat, 6 Feb 2010 01:03:08 +0000 (UTC) |

Organization: | A noiseless patient Spider |

References: | 10-02-009 92-05-052 |

Keywords: | LL(1) |

Posted-Date: | 06 Feb 2010 09:57:58 EST |

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 ...

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.