|How to convert Ambiguous G to UnAmbiguous? email@example.com (1995-12-17)|
|Re: How to convert Ambiguous G to UnAmbiguous? firstname.lastname@example.org (Daniel C. Wang) (1995-12-17)|
|From:||"Daniel C. Wang" <email@example.com>|
|Date:||17 Dec 1995 14:46:17 -0500|
|Organization:||Senior, Math/Computer Science, Carnegie Mellon, Pittsburgh, PA|
> 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.
Return to the
Search the comp.compilers archives again.