7 Nov 1998 01:26:53 -0500

Related articles |
---|

Is a contextfree Grammar ambiguous ? mmeyer@rhso.de (Martin Meyer) (1998-10-30) |

Re: Is a contextfree Grammar ambiguous ? clark@quarry.zk3.dec.com (Chris Clark USG) (1998-11-06) |

Re: Is a contextfree Grammar ambiguous ? mickunas@cs.uiuc.edu (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? mickunas@cs.uiuc.edu (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? aycock@csc.uvic.ca (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? dmr@plan9.bell-labs.com (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? cfc@world.std.com (Chris F Clark) (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? cfc@world.std.com (Chris F Clark) (1998-11-12) |

Re: Is a contextfree Grammar ambiguous ? jmlake@unity.ncsu.edu (1998-11-15) |

From: | aycock@csc.uvic.ca (John Aycock) |

Newsgroups: | comp.compilers,comp.theory |

Date: | 7 Nov 1998 01:26:53 -0500 |

Organization: | University of Victoria |

Distribution: | inet |

References: | 98-11-037 |

Keywords: | parse, theory |

Martin asked:

*> Does an algorithm to decide whether a context free grammar is*

*> ambiguous exist ?*

Chris Clark USG (clark@quarry.zk3.dec.com) wrote:

*: The semantic nit is that by definition a context free grammar is*

*: unambiguous. That is, if your grammar is ambiguous it is not a*

*: context free grammar.*

The definition of a context-free grammar is independent of any notion

of ambiguity. For example, the grammar

E -> E + E

E -> n

is ambiguous since there are two distinct leftmost derivations for the

sentence "n + n + n", and it is most certainly a context-free grammar;

each left-hand side consists of a single nonterminal symbol.

There are also a number of algorithms known for parsing ambiguous

context-free grammars, such as Earley's and Tomita's algorithm.

As for the original question, it's undecidable if an arbitrary

context-free grammar is ambiguous. Any good theory text should have

the proof -- I found it in Hopcroft & Ullman's _Introduction to

Automata Theory, Languages, and Computation_. As Chris stated,

though, if you can construct a LL/LR parser for a grammar (without

conflicts), then it is unambiguous, but if you *can't* construct one,

then that tells you nothing about the grammar's ambiguity.

John

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.