Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| [7 earlier articles] |
| Re: LR(n) parsers nickh@harlqn.co.uk (Nick Haines) (1991-10-16) |
| Re: LR(n) parsers mtxinu!angular!jas@uunet.uu.net (1991-10-18) |
| Re: LR(n) parsers rockwell@socrates.umd.edu (Raul Deluth Miller-Rockwell) (1991-10-19) |
| 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: | Sriram Sankar <sankar@Neon.Stanford.EDU> |
| Keywords: | parse, grammar, LR(1) |
| Organization: | Compilers Central |
| References: | 91-10-076 91-10-088 |
| Date: | Thu, 24 Oct 91 08:57:58 -0700 |
Dale Worley asks:
> When was this proven? 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) languages are a strict subset of LR(n) languages for any n > 0.
Also for n,m > 0, language(LR(n)) = language(LR(m)).
Having said this much, let me also note that all the parsing algorithms
I have seen (e.g., in the dragon books) make the following transformation
to the grammar:
If S is the original start symbol of the grammar, then create a new
non-terminal S1, and a new terminal $, and add the production:
S1 -> S$
The language that results from this transformed grammar (i.e., all strings
in this language end with $, and have no other $ in them) is LR(0).
There is a proof in Hopcroft&Ullman for this.
Sriram.
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.