Re: LR(n) parsers

markh@csd4.csd.uwm.edu (Mark William Hopkins)
Wed, 6 Nov 1991 19:29:45 GMT

          From comp.compilers

Related articles
[10 earlier articles]
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-19)
Re: LR(n) parsers drw@riesz.mit.edu (1991-10-22)
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-24)
Re: LR(n) parsers sankar@Neon.Stanford.EDU (Sriram Sankar) (1991-10-24)
Re: LR(n) parsers ge@sci.kun.nl (1991-10-25)
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-25)
Re: LR(n) parsers markh@csd4.csd.uwm.edu (1991-11-06)
| List of all articles for this month |
Newsgroups: comp.compilers
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Keywords: parse, LR(1)
Organization: Computing Services Division, University of Wisconsin - Milwaukee
References: 91-10-036 91-10-088
Date: Wed, 6 Nov 1991 19:29:45 GMT

In article 91-10-088 drw@riesz.mit.edu (Dale R. Worley) writes:
>Last I heard was that it wasn't known of LR(k) was larger than LR(0).
>Also, is it known yet if there are unambiguous CF languages that aren't LR?


LR(0) < LR(1), and LR(1) = LR(k) for all k > 1. In fact, LR(1) =
deterministic-CFL languages < unambiguous CFL-languages.


This is last I heard. :)


There's a procedure to transform LR(k) grammars to LR(1) grammars, but you
may not like the results, so usually it's more prudent to do the
transformation the *other* way (LR(1) -> LR(k)), and in fact, is often
more prudent to represent such a language even by an ambiguous grammar
(like the C statement grammar).


The governing rule is not parseability, but simplicity. Who cares if it's
LR(1) parseable if the equivalent ambiguous grammar turns out to be 5
times smaller (as is the case for C) and that much easier to write a
parser for (by hand even)?
--


Post a followup to this message

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