Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| disambiguating transformations MATT@waikato.ac.nz (Matt Melchert) (1993-09-22) |
| Re: disambiguating transformations bevan@computer-science.manchester.ac.uk (Stephen J Bevan) (1993-09-24) |
| Re: disambiguating transformations rad@cs.ucsb.edu (1993-09-25) |
| Disambiguating an arbitrary CFL (was: disambiguating transformations) markh@csd4.csd.uwm.edu (1993-09-25) |
| Re: disambiguating transformations bart@skinner.cs.uoregon.edu (Bart Massey) (1993-09-26) |
| Re: disambiguating transformations thinx!jos@relay.nluug.nl (Jos Horsmeier) (1993-09-27) |
| Newsgroups: | comp.compilers |
| From: | Jos Horsmeier <thinx!jos@relay.nluug.nl> |
| Keywords: | parse, theory |
| Organization: | Compilers Central |
| References: | 93-09-099 93-09-120 |
| Date: | Mon, 27 Sep 1993 08:23:28 GMT |
Matt Melchert <MATT@waikato.ac.nz> writes:
|I am looking for an algorithm which will take a (possibly) ambiguous context-
|free grammar and perform transformations on it to yield an equivalent
|non-ambiguous context-free grammar. Does such a thing exist? If not, do we
|know why not? Any ideas or references would be appreciated.
Our moderator adds the following question:
|[Is this even decidable? -John]
No, it is not. The question whether or not a context free grammar is
ambiguous is an undecidable question. The proof is quite simple:
Given a Post Correspondence problem P = { v_1, ... v_n, w_1, ... w_n }
construct the following production rules for the grammar G:
S -> T | U
T -> v_i T i | v_i i
U -> w_i U i | w_i i
for i in [1 ... n]
Now, in order to decide whether or not this grammar is ambiguous, one
has to solve the embedded Post Correspondence problem P.
Does anybody mind if I say `Q.E.D.' now? ;-)
kind regards,
Jos aka jos@and.nl aka thinx!jos@convex.com
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.