29 Oct 1999 02:32:16 -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) |

[3 later articles] |

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

Newsgroups: | comp.theory,comp.compilers |

Date: | 29 Oct 1999 02:32:16 -0400 |

Organization: | UNI-C |

Distribution: | inet |

References: | 99-10-130 |

Keywords: | parse, LR(1) |

Linlist Leo <linlist@fudan.edu> writes:

*> But it can be written in an umambiguous way. I devised the following*

*> grammar(maybe incorrect).*

*> S -> M | U*

*> M -> iEtMeM | a*

*> U -> iEtS*

The standard solution from the Dragon Book is identical to yours,

except it also contains the production

U -> iEtMeU

which allows strings such as

if E then if E then a else a else if E then a

to be parsed.

*> What I cannot figure out is whether there is any language that is not*

*> inherently ambiguous but cannot be LR(k) for any k.*

*> [Sure. Construct one along these lines:*

*> S -> aX | bY*

*> a -> A | aA;*

*> b -> A | bA;*

The problem here is the particular grammar you give- not the language

itself. The language described by your grammar does have a LR(0)

grammar:

S -> TX | TY

T -> A | TA

(which is not surprising as the original grammar is left regular hence

the language it defines is regular).

--

Henning Makholm

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.