Re: Is a contextfree Grammar ambiguous ?

dmr@plan9.bell-labs.com
7 Nov 1998 01:27:56 -0500

          From comp.compilers

Related articles
Is a contextfree Grammar ambiguous ? mmeyer@rhso.de (Martin Meyer) (1998-10-30)
Re: Is a contextfree Grammar ambiguous ? clark@quarry.zk3.dec.com (Chris Clark USG) (1998-11-06)
Re: Is a contextfree Grammar ambiguous ? mickunas@cs.uiuc.edu (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? mickunas@cs.uiuc.edu (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? aycock@csc.uvic.ca (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? dmr@plan9.bell-labs.com (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? cfc@world.std.com (Chris F Clark) (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? cfc@world.std.com (Chris F Clark) (1998-11-12)
Re: Is a contextfree Grammar ambiguous ? jmlake@unity.ncsu.edu (1998-11-15)
| List of all articles for this month |

From: dmr@plan9.bell-labs.com
Newsgroups: comp.compilers
Date: 7 Nov 1998 01:27:56 -0500
Organization: Compilers Central
References: 98-10-172 98-11-037
Keywords: parse, theory

Chris Clark wrote (quoting)--
  >> Does an algorithm to decide whether a context free grammar is
  >> ambiguous exist ? If yes, can it state which productions lead the
  >> grammar to be ambiguous ?


  > There is a little semantic nit with this question, but for the
  > question you are trying to ask is probably yes.


  > The semantic nit is that by definition a context free grammar is
  > unambiguous. That is, if your grammar is ambiguous it is not a
  > context free grammar.


I'm only an old country lawyer, but I kinda thought that context-free
grammars were defined by simple syntactic characterization of
production systems, and, for example, that with terminals a, b,
nonterminals S, A, B, the grammar


S -> A | B
A -> a
B -> a


was a context-free grammar. It is not hard to see that the language
is indeed regular, not just CF, but this grammar is ambiguous as hell.


And, by golly, I kinda thought that it was undecidable whether a
particular CFG defines an inherently ambiguous CFL.


Dennis


Post a followup to this message

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