5
$\begingroup$

A grammar is ambiguous if at least one of the words in the language it defines can be parsed in more than one way. A simple example of an ambiguous grammar $$ E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ 1 \ |\ ... $$ because the string 1+2*3 can be parsed as (1+2)*3 and 1+(2*3). For context free grammars (CFGs) ambiguity is not decidable [1, 2]. This implies that non-ambiguity is also not decidable. Moreover, at least one of ambiguity and non-ambiguity cannot even be recursively enumerable, for otherwise ambiguity of a given CFG $G$ could be decided by running the enumeration of ambiguity and non-ambiguity together and seeing which one contains $G$ (and one of them must).

So which problem is harder in this sense? Ambiguity or non-ambiguity?

  1. D. G. Cantor, On The Ambiguity Problem of Backus Systems.

  2. R. W. Floyd, On ambiguity in phrase structure languages.

$\endgroup$
9
$\begingroup$

Ambiguous grammars can be enumerated, since each ambiguous grammar has a proof of ambiguity, namely a word with two different parses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.