Tracking Down the Origins of Ambiguity in Context-Free Grammars
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.
|ACM||Grammars and Other Rewriting Systems (acm F.4.2)|
|THEME||Software (theme 1)|
|Editor||A. Cavalcanti , D. Deharbe , M. Gaudel , J. Woodcock|
|Series||Lecture Notes in Computer Science|
|Conference||International Colloquium on Theoretical Aspects of Computing|
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.