Re: disambiguating transformations

Stephen J Bevan <bevan@computer-science.manchester.ac.uk>
Fri, 24 Sep 1993 08:34:38 GMT

          From comp.compilers
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)
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)
| List of all articles for this month |
Newsgroups: comp.compilers
From: Stephen J Bevan <bevan@computer-science.manchester.ac.uk>
Keywords: parse, theory
Organization: Compilers Central
References: 93-09-099
Date: Fri, 24 Sep 1993 08:34:38 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.


Whilst not directly answering the above, the following seems relevant :-


"It has been proven that the problem of deciding whether an arbitrary
context free grammar is ambiguous or not is undecidable. The next
question one might ask is whether there exists an unambiguous grammar for
an arbitrary context free language. The answer is no. There are
languages for which _no_ unambiguous grammar exists; this was first shown
by Parikh[61]".


Compiler Construction For Digital Computers - David Gries - Wiley 1971 - pp 47


[61] Parikh, R. J. On context free languages JACM 13:570-581 Oct 1966
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.