Analyzing Ambiguity of Context-Free Grammars

It has been known since 1962 that the ambiguity problem for context-free grammars
is undecidable. Ambiguity in context-free grammars is a recurring problem
in language design and parser generation, as well as in applications where grammars
are used as models of real-world physical structures.
We observe that there is a simple linguistic characterization of the grammar
ambiguity problem, and we show how to exploit this by presenting an ambiguity
analysis framework based on conservative language approximations. As a concrete
example, we propose a technique based on local regular approximations
and grammar unfoldings. We evaluate the analysis using grammars that occur
in RNA analysis in bioinformatics, and we demonstrate that it is sufficiently
precise and efficient to be practically useful.