Mon, 1 Aug 1994 04:18:32 GMT

Related articles |
---|

Unambiguity proofs for CFG's matt@waikato.ac.nz (1994-07-29) |

Re: Unambiguity proofs for CFG's bromage@mundil.cs.mu.OZ.AU (1994-08-01) |

Newsgroups: | comp.compilers |

From: | bromage@mundil.cs.mu.OZ.AU (Andrew Bromage) |

Keywords: | theory, parse |

Organization: | Compilers Central |

References: | 94-07-087 |

Date: | Mon, 1 Aug 1994 04:18:32 GMT |

Status: | RO |

matt@waikato.ac.nz (Matt Melchert) writes:

*>Last year I posted a query as to whether it was possible to determine if a*

*>grammar is unambiguous. The answer is that it is not, the proof being the*

*>Post Correspondence Problem. But further reflection has yielded the*

*>intuition that if "ambiguity" is equivalent to "can produce more than one*

*>parse tree for some input", then wouldn't it be enough to show that for a*

*>given grammar any input could still only produce one parse tree?*

Yes, it would be enough to do that. It might even work for some grammars.

The problem would still remain undecidable.

The proof that I've seen (see, for example, Theorem 11.8.3 from Sudkamp's

excellent introductory text, "Languages and Machines") relies on the

definition that a grammar is ambiguous if it contains a string that can be

generated by two distinct leftmost derivations (which, as I understand it,

is the usual definition). This definition is equivalent to your definition

(there being two distinct parse trees), because any given parse tree has one

unique left derivation and that any left derivation has one unique parse

tree. (Exercise: prove this --- it's not hard)

Cheers,

Andrew Bromage

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.