|[10 earlier articles]|
|Re: LR(n) parsers email@example.com (Thomas Schoebel) (1991-10-19)|
|Re: LR(n) parsers firstname.lastname@example.org (1991-10-22)|
|Re: LR(n) parsers email@example.com (Thomas Schoebel) (1991-10-24)|
|Re: LR(n) parsers sankar@Neon.Stanford.EDU (Sriram Sankar) (1991-10-24)|
|Re: LR(n) parsers firstname.lastname@example.org (1991-10-25)|
|Re: LR(n) parsers email@example.com (Thomas Schoebel) (1991-10-25)|
|Re: LR(n) parsers firstname.lastname@example.org (1991-11-06)|
|From:||email@example.com (Mark William Hopkins)|
|Organization:||Computing Services Division, University of Wisconsin - Milwaukee|
|Date:||Wed, 6 Nov 1991 19:29:45 GMT|
In article 91-10-088 firstname.lastname@example.org (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
Search the comp.compilers archives again.