Context-free grammars are widely used but still hindered by ambiguity. This stresses the need for detailed detection methods that point out the sources of ambiguity in a grammar. In this paper we show how the approximative Noncanonical Unambiguity Test by Schmitz can be extended to conservatively identify production rules that do not contribute to the ambiguity of a grammar. We prove the correctness of our approach and consider its practical applicability.

Additional Metadata
ACM Grammars and Other Rewriting Systems (acm F.4.2)
THEME Software (theme 1)
Publisher Springer
Editor A. Cavalcanti , D. Deharbe , M. Gaudel , J. Woodcock
Series Lecture Notes in Computer Science
Conference International Colloquium on Theoretical Aspects of Computing
Citation
Basten, H.J.S. (2010). Tracking Down the Origins of Ambiguity in Context-Free Grammars. In A Cavalcanti, D Deharbe, M Gaudel, & J Woodcock (Eds.), Proceedings of International Colloquium on Theoretical Aspects of Computing 2010 (7) (pp. 76–90). Springer.