Faster ambiguity detection by grammar filtering
Presented at the Workshop on Language Descriptions, Tools and Applications, Paphos, Cyprus
Real programming languages are often defined using ambiguous context-free grammars. Some ambiguity is intentional while other ambiguity is accidental. A good grammar development environment should therefore contain a static ambiguity checker to help the grammar engineer. Ambiguity of context-free grammars is an undecidable property. Nevertheless, various imperfect ambiguity checkers exist. Exhaustive methods are accurate, but suffer from non-termination. Termination is guaranteed by approximative methods, at the expense of accuracy. In this paper we combine an approximative method with an exhaustive method. We present an extension to the Noncanonical Unambiguity Test that identifies production rules that do not contribute to the ambiguity of a grammar and show how this information can be used to significantly reduce the search space of exhaustive methods. Our experimental evaluation on a number of real world grammars shows orders of magnitude gains in efficiency in some cases and negligible losses of efficiency in others.
|Software/Program Verification (acm D.2.4), Grammars and Other Rewriting Systems (acm F.4.2)|
|Software (theme 1)|
|C. Brabrand (Claus) , P.-E. Moreau|
|Workshop on Language Descriptions, Tools and Applications|
|Organisation||Software Analysis and Transformation|
Basten, H.J.S, & Vinju, J.J. (2010). Faster ambiguity detection by grammar filtering. In C Brabrand & P.-E Moreau (Eds.), Proceedings of the Tenth Workshop on Language Descriptions, Tools and Applications. ACM.