17 Dec 1995 14:46:17 -0500

Related articles |
---|

How to convert Ambiguous G to UnAmbiguous? pschen@casd2.iie.ncku.edu.tw (1995-12-17) |

Re: How to convert Ambiguous G to UnAmbiguous? dw3u+@andrew.cmu.edu (Daniel C. Wang) (1995-12-17) |

From: | "Daniel C. Wang" <dw3u+@andrew.cmu.edu> |

Newsgroups: | comp.compilers |

Date: | 17 Dec 1995 14:46:17 -0500 |

Organization: | Senior, Math/Computer Science, Carnegie Mellon, Pittsburgh, PA |

References: | 95-12-092 |

Keywords: | parse, theory |

pschen@casd2.iie.ncku.edu.tw writes:

*> Is there a algorithm that convert a ambiguous grammar*

*> to an unambiguous grammar?*

For some CFG's there are no unambigous grammars.

*> Is there a method to detect a grammar is ambiguous or not?*

The above question is undecideable for general CFG's.

(i.e. as difficult as the halting problem)

*> have paper lists about this?*

Can't help much here but there are algorithims that can parse arbitary

CFG's in O(n^3) time, if you don't mind too much about performance. A

good introductory text on formal languages is probably a good place to

start, these questions are pretty old. Unfortunately, I don't have

exact refs handy, but the Dragon book and Hopcraft and Ullman's text

on formal languages are a must.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.