Re: Is a contextfree Grammar ambiguous ?

aycock@csc.uvic.ca (John Aycock)
7 Nov 1998 01:26:53 -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: aycock@csc.uvic.ca (John Aycock)
Newsgroups: comp.compilers,comp.theory
Date: 7 Nov 1998 01:26:53 -0500
Organization: University of Victoria
Distribution: inet
References: 98-11-037
Keywords: parse, theory

Martin asked:
> Does an algorithm to decide whether a context free grammar is
> ambiguous exist ?


Chris Clark USG (clark@quarry.zk3.dec.com) wrote:
: 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.


The definition of a context-free grammar is independent of any notion
of ambiguity. For example, the grammar


E -> E + E
E -> n


is ambiguous since there are two distinct leftmost derivations for the
sentence "n + n + n", and it is most certainly a context-free grammar;
each left-hand side consists of a single nonterminal symbol.


There are also a number of algorithms known for parsing ambiguous
context-free grammars, such as Earley's and Tomita's algorithm.


As for the original question, it's undecidable if an arbitrary
context-free grammar is ambiguous. Any good theory text should have
the proof -- I found it in Hopcroft & Ullman's _Introduction to
Automata Theory, Languages, and Computation_. As Chris stated,
though, if you can construct a LL/LR parser for a grammar (without
conflicts), then it is unambiguous, but if you *can't* construct one,
then that tells you nothing about the grammar's ambiguity.


John


Post a followup to this message

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