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) |
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)?
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.