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

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/

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