29 Oct 1999 02:35:13 -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) |

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

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.