Re: How to convert Ambiguous G to UnAmbiguous?

"Daniel C. Wang" <>
17 Dec 1995 14:46:17 -0500

          From comp.compilers

Related articles
How to convert Ambiguous G to UnAmbiguous? (1995-12-17)
Re: How to convert Ambiguous G to UnAmbiguous? (Daniel C. Wang) (1995-12-17)
| List of all articles for this month |

From: "Daniel C. Wang" <>
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 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.