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

"Scott Stanchfield" <thetick@magelang.com>
24 Jan 1998 12:18:47 -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: "Scott Stanchfield" <thetick@magelang.com>
Newsgroups: comp.compilers
Date: 24 Jan 1998 12:18:47 -0500
Organization: MageLang Institute - http://www.MageLang.com
References: 98-01-071 98-01-080 98-01-086
Keywords: parse, LL(1)

Bill Leonard wrote in message 98-01-086...
>It is true that any LR(k) language is also an LR(1) language, but that
>doesn't mean much in relation to LL(k) languages.


Theory aside for a moment...


Has anyone actually seen an LALR(k) grammar _for_a_useful_language_
that cannot be represented in predicated LL(k)? (Or even in LL(1) if
you left factor like crazy).


Back to theory:


Has anyone proven that the set of languages that can be represented by
a predicated LL(k) grammar is a proper subset of those that can be
represented in LR(k)?


I know (in my gut ;) that it would be at least a much bigger subset, but has
any real thought gone into it?


--
-- Scott


Scott Stanchfield, Santa Cruz, CA
        http://www.scruz.net/~thetick








--


Post a followup to this message

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