Re: How to convert Ambiguous G to UnAmbiguous?

"Daniel C. Wang" <dw3u+@andrew.cmu.edu>
17 Dec 1995 14:46:17 -0500

          From comp.compilers
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)
| List of all articles for this month |
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.