27 Oct 1999 14:20:27 -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) |

[7 later articles] |

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.