31 Oct 1999 01:25:45 -0400

Related articles |
---|

[5 earlier articles] |

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: | uranus!ikastan@uunet.uu.net (Ilias Kastanas) |

Newsgroups: | comp.theory,comp.compilers |

Date: | 31 Oct 1999 01:25:45 -0400 |

Organization: | CSUnet |

Distribution: | inet |

References: | 99-10-130 99-10-158 |

Keywords: | parse, LR(1) |

Xavier Nicollin <Xavier.Nicollin@imag.fr> wrote:

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

Yes, L = palindromes over {0,1}. The obvious grammar for L is

unambiguous; but L isn't LR(k) for any k, because L is not a deter-

ministic CFL.

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

{0^m 1^n 2^n} U {0^m 1^m 2^n}

Ilias

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.