Re: LR(n) parsers

Sriram Sankar <sankar@Neon.Stanford.EDU>
Thu, 24 Oct 91 08:57:58 -0700

          From comp.compilers

Related articles
[7 earlier articles]
Re: LR(n) parsers (Nick Haines) (1991-10-16)
Re: LR(n) parsers mtxinu!angular! (1991-10-18)
Re: LR(n) parsers (Raul Deluth Miller-Rockwell) (1991-10-19)
Re: LR(n) parsers (Thomas Schoebel) (1991-10-19)
Re: LR(n) parsers (1991-10-22)
Re: LR(n) parsers (Thomas Schoebel) (1991-10-24)
Re: LR(n) parsers sankar@Neon.Stanford.EDU (Sriram Sankar) (1991-10-24)
Re: LR(n) parsers (1991-10-25)
Re: LR(n) parsers (Thomas Schoebel) (1991-10-25)
Re: LR(n) parsers (1991-11-06)
| List of all articles for this month |

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.


Post a followup to this message

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