31 Oct 1999 01:24:29 -0400

Related articles |
---|

[4 earlier articles] |

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

Re: ambiguity of grammar and LR(k) sol!ikastan@agate-ether.berkeley.edu (1999-11-02) |

From: | Henning Makholm <henning@makholm.net> |

Newsgroups: | comp.theory,comp.compilers |

Date: | 31 Oct 1999 01:24:29 -0400 |

Organization: | UNI-C |

Distribution: | inet |

References: | 99-10-130 99-10-167 |

Keywords: | parse, theory |

"Matt Timmermans" <mtimmerm@microstar.nospam-remove.com> writes:

*> Linlist Leo wrote in message 99-10-130...*

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

*> Lots of them. Here's an easy one:*

Like the earlier example we've seen, this is example of a *grammar*

that is unambigous yet not LR(k) for any k.

However, note that Linlist asks for *languages*, not *grammars*.

The language described by your grammar certainly *can* be LR(k)

simply by describing it with another grammar than the one you give.

Indeed the language in question:

{ xc^nb | n > 0 } U { xc^na | n > 0 }

is regular, so it trivially has a LR(0) grammar.

--

Henning Makholm

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.