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

mickunas@cs.uiuc.edu (Dennis Mickunas,297D,3336351,0000000)
23 Jan 1998 00:18:07 -0500

          From comp.compilers

Related articles
LL(2) always factorable to LL(1)? aduncan@cs.ucsb.edu (Andrew M. Duncan) (1998-01-17)
Re: LL(2) always factorable to LL(1)? clark@quarry.zk3.dec.com (Chris Clark USG) (1998-01-20)
Re: LL(2) always factorable to LL(1)? bill@amber.ssd.csd.harris.com (1998-01-21)
Re: LL(2) always factorable to LL(1)? mickunas@cs.uiuc.edu (1998-01-23)
Re: LL(2) always factorable to LL(1)? cfc@world.std.com (Chris F Clark) (1998-01-23)
Re: LL(2) always factorable to LL(1)? parrt@magelang.com (Terence Parr) (1998-01-23)
Re: LL(2) always factorable to LL(1)? thetick@magelang.com (Scott Stanchfield) (1998-01-24)
Re: LL(2) always factorable to LL(1)? parrt@magelang.com (Terence Parr) (1998-02-01)
| List of all articles for this month |

From: mickunas@cs.uiuc.edu (Dennis Mickunas,297D,3336351,0000000)
Newsgroups: comp.compilers
Date: 23 Jan 1998 00:18:07 -0500
Organization: University of Illinois at Urbana-Champaign
References: 98-01-071 98-01-080
Keywords: parse, 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
--


Post a followup to this message

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