Re: ambiguity of grammar and LR(k)

Nathan Hartzell <nhartzell@macalester.edu>
29 Oct 1999 02:35:13 -0400

          From comp.compilers
Related articles
ambiguity of grammar and LR(k) linlist@fudan.edu (Linlist Leo) (1999-10-27)
Re: ambiguity of grammar and LR(k) hanskamp@introweb.nl (Hans Kamp) (1999-10-28)
Re: ambiguity of grammar and LR(k) hanskamp@introweb.nl (Hans Kamp) (1999-10-29)
Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-29)
Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-29)
Re: ambiguity of grammar and LR(k) mtimmerm@microstar.nospam-remove.com (Matt Timmermans) (1999-10-29)
Re: ambiguity of grammar and LR(k) nhartzell@macalester.edu (Nathan Hartzell) (1999-10-29)
Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-31)
Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-31)
Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-31)
Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-31)
Re: ambiguity of grammar and LR(k) uranus!ikastan@uunet.uu.net (1999-10-31)
Re: ambiguity of grammar and LR(k) linlist@fudan.edu (Linlist Leo) (1999-10-31)
[1 later articles]
| List of all articles for this month |
From: Nathan Hartzell <nhartzell@macalester.edu>
Newsgroups: comp.theory,comp.compilers
Date: 29 Oct 1999 02:35:13 -0400
Organization: Macalester College
Distribution: inet
References: 99-10-130 99-10-137
Keywords: parse, LR(1)

The grammar


> > S -> M | U
> > M -> iEtMeM | a
> > U -> iEtS
is really close to the unambiguous grammar. The only place you went wrong
is that the M rule is off just a bit. It should be
M -> iEtMeU
Since a one-armed if can be hung off the Else clause of a two-armed If with
no ambiguity.


> Linlist Leo <linlist@fudan.edu> schreef
> > It is well-known the following grammar is ambiguous so that it is
> > not LR(k) for any k.
> > S -> iEtSeS | iEtS | a
> > ('a' is not important, maybe just some assigning statement)
> >
> > But it can be written in an umambiguous way. I devised the following
> > grammar(maybe incorrect).
> > S -> M | U
> > M -> iEtMeM | a
> > U -> iEtS
> >
> > I guess it LR(1). Any correction will be welcomed.

Post a followup to this message

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