29 Oct 1999 02:31:00 -0400

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) |

[4 later articles] |

From: | Xavier Nicollin <Xavier.Nicollin@imag.fr> |

Newsgroups: | comp.theory,comp.compilers |

Date: | 29 Oct 1999 02:31:00 -0400 |

Organization: | Institut IMAG, Grenoble (http://www.imag.fr) |

Distribution: | inet |

References: | 99-10-130 |

Keywords: | parse, LR(1) |

Linlist Leo wrote:

*>*

*> 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.*

It is incorrect: you cannot derive

iEtaeiEta

The rules for U should be:

U -> iEtS | iEtMeU

The grammar is then LR(1) (it is even SLR(1)).

*> 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.*

Sorry, no hint there. BTW, do there exist language inherently ambiguous?

--

| Xavier NICOLLIN (mailto:Xavier.Nicollin@imag.fr), INPG (ENSIMAG)

| VERIMAG - Centre Equation - 2, ave. de Vignate - 38610 Gieres - France

| Tel : (33 | 0) 476 63 48 46 -- Fax : (33 | 0) 476 63 48 50

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.