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. Furthermore we can identify tree patterns that will never occur in derivations of ambiguous strings. We prove the correctness of our approach and consider its practical applicability.
|THEME||Software (theme 1)|
|Series||Software Engineering [SEN]|
Basten, H.J.S. (2010). Tracking Down the Origins of Ambiguity in Context-Free Grammars. Software Engineering [SEN]. CWI.