Re: Is a contextfree Grammar ambiguous ?

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

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