TY - JOUR
T1 - Analyzing Ambiguity of Context-Free Grammars
AU - Brabrand, Claus
AU - Giegerich, Robert
AU - Møller, Anders
PY - 2010
Y1 - 2010
N2 - It has been known since 1962 that the ambiguity problem for context-free grammarsis undecidable. Ambiguity in context-free grammars is a recurring problemin language design and parser generation, as well as in applications where grammarsare used as models of real-world physical structures.We observe that there is a simple linguistic characterization of the grammarambiguity problem, and we show how to exploit this by presenting an ambiguityanalysis framework based on conservative language approximations. As a concreteexample, we propose a technique based on local regular approximationsand grammar unfoldings. We evaluate the analysis using grammars that occurin RNA analysis in bioinformatics, and we demonstrate that it is sufficientlyprecise and efficient to be practically useful.
AB - It has been known since 1962 that the ambiguity problem for context-free grammarsis undecidable. Ambiguity in context-free grammars is a recurring problemin language design and parser generation, as well as in applications where grammarsare used as models of real-world physical structures.We observe that there is a simple linguistic characterization of the grammarambiguity problem, and we show how to exploit this by presenting an ambiguityanalysis framework based on conservative language approximations. As a concreteexample, we propose a technique based on local regular approximationsand grammar unfoldings. We evaluate the analysis using grammars that occurin RNA analysis in bioinformatics, and we demonstrate that it is sufficientlyprecise and efficient to be practically useful.
M3 - Journal article
SN - 0167-6423
VL - 75
SP - 176
EP - 191
JO - Science of Computer Programming
JF - Science of Computer Programming
IS - 3
ER -