ambiguity of grammar and LR(k)

Linlist Leo <linlist@fudan.edu>
27 Oct 1999 14:20:27 -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)
[7 later articles]
| List of all articles for this month |

From: Linlist Leo <linlist@fudan.edu>
Newsgroups: comp.theory,comp.compilers
Date: 27 Oct 1999 14:20:27 -0400
Organization: Compilers Central
Distribution: inet
Keywords: parse, question, comment

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.


What I cannot figure out is whether there is any language that is not
inherently ambiguous but cannot be LR(k) for any k. I'd appreciate if
anyone can give me some hints.


thanks,


Linlist
--
-------------------------
Linlist Leo
linlist@fudan.edu
-------------------------
[Sure. Construct one along these lines:


S -> aX | bY
a -> A | aA;
b -> A | bA;


The idea is that you need to look past an arbitrarily large number of
A's which need to reduce to an arbitrarily large number of a's or b's
to find the disambiguating X or Y. -John]


Post a followup to this message

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