Re: LL(2) always factorable to LL(1)?

Chris Clark USG <clark@quarry.zk3.dec.com> writes:


>> I'm TA-ing a compilers course, and am looking for some good examples
>> of (for example) languages that are intrinsically LL(0,1,2) and same
>> for LR. It's clear that some languages can be expressed in an LL(2)
>> grammar, but the grammar can be further factored. For example:
>>
>> S -> id "=" Expr | id "(" Params ")"
>>
>> is LL(2) but can be factored to
>>
>> S -> id rest
>> rest -> "=" E | "(" Params ")"
>>
>>Is this always possible?


>The theoretical answer is yes. Any LR(k) language is also an LL(1)
>language. Of course, we may not have the LL(1) grammar for that
>language.


As for intrinsically LR(k), all deterministic CFLs are intrinsically
LR(1); all prefix-free deterministic CFLs (also categorized as the
"strict-deterministic context free languages) are intrinsically LR(0).
Moreover, you can mechanically convert any LR(k) grammar to LR(1), or,
if the language is prefix-free, to LR(0).


As for the part about LL(k) vs LL(k-1) and LR vs LL, I'm afraid that
the theoretical answer (despite what LL enthusiasts like to believe)
is "the LL languages form a strict heirarchy, and the LL languages are
properly included in the LR languages." Let me quote a couple of
exercises from from Aho & Ullman's "The Theory of Parsing,
Translation, and Compiling, Volume 1: Parsing":


**5.1.22. Show that for all k>=0, there exist languages which are
LL(k+1) but not LL(k).


*5.2.28. Show that there exist languages which are LR but not LL.


Of course, the *practical* answer is that the theory doesn't mean much.
In practice, all translator-writing systems, whether top-down or
bottom-up, are capable of finessing all practical programming constructs.


If you don't want to think about the exercises too much, answers follow....


SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER
SPOILER


5.1.22 Given a fixed integer k, the following language is LL(k+1),
but not LL(k):


a^n (b | c | c^k d)^n for n>0




5.2.28 The following language is LR(0), but not LL(k) for any k:


a^n b^n | a^n c^n for n>0




--
M. Dennis Mickunas
Department of Computer Science 1304 W. Springfield Ave.
University of Illinois Urbana, Illinois 61801
mickunas@cs.uiuc.edu (217) 333-6351
--

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