23 Jan 1998 00:18:07 -0500

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

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.