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

SLK Mail <slkpg@cox.net>
Fri, 5 Feb 2010 15:47:23 -0500

          From comp.compilers

Related articles
An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-01-26)
Re: An example LL(K) language that is not LL(K-1) ? haberg_20080406@math.su.se (Hans Aberg) (2010-01-28)
An example LL(K) language that is not LL(K-1) ? chakaram@auth.gr (Chariton Karamitas) (2010-02-01)
Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-02)
Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-03)
Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-03)
Re: An example LL(K) language that is not LL(K-1) ? daniel.eliason@excite.com (fortunatus) (2010-02-04)
Re: An example LL(K) language that is not LL(K-1) ? slkpg@cox.net (SLK Mail) (2010-02-05)
Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-05)
Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-06)
Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-06)
Re: An example LL(K) language that is not LL(K-1) ? slkpg@cox.net (SLK Mail) (2010-02-06)
Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-10)
Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-10)
[2 later articles]
| List of all articles for this month |

From: SLK Mail <slkpg@cox.net>
Newsgroups: comp.compilers
Date: Fri, 5 Feb 2010 15:47:23 -0500
Organization: Compilers Central
Keywords: LL(1), bibliography
Posted-Date: 05 Feb 2010 17:33:07 EST

The following is the reference for the original paper on LL(k). It
should have a proof of the superset relationship of k to k-1 for the
LL languages.


Rosenkrantz, D.J. and R.E. Stearns (1970). "Properties of
Deterministic Top-Down Grammars," Inf. and Control, 17 (3), pp
226-256.


You may be thinking of the fact that LR(k) is reducible to LR(1). Not
so for LL because it cannot postpone parsing decisions, making it more
dependent on the lookahead than LR.


Example:


S -> a A a
S -> b A b a
A -> b
A ->


Can you convert this to LL(1)?


More info about LL(k) can be found in the FAQ and links on the


SLK Parser Generator site: http://members.cox.net/slkpg/



Post a followup to this message

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