Metric-Based Analysis of Context-Free Grammars

James F. Power	Brian A. Malloy1
Department of Computer Science	Department of Computer Science
National University of Ireland, Maynooth	Clemson University
Kildare, Ireland	Clemson, SC 29634
James.Power@may.ie	malloy@cs.clemson.edu

Abstract:

Recent advances in software engineering have produced a variety of well established approaches, formalisms and techniques to facilitate the construction of large-scale applications. Developers interested in the construction of robust, extensible software that is easy to maintain should expect to deploy a range of these techniques, as appropriate to the task. In this paper, we provide a foundation for the application of established software metrics to the measurement of context-free grammars. The usual application of software metrics is to program code; we provide a mapping that allows these metrics to be applied to grammars. This allows us to interpret six software engineering metrics in a grammatical context, including McCabe's complexity metric and Fenton's impurity metric. We have designed and implemented a tool to automatically compute the six metrics; as a case study, we use these six metrics to measure some of the properties of grammars for the Oberon, ISO C, ISO C++ and Java programming languages. We believe that the techniques that we have developed can be applied to estimating the difficulty of designing, implementing, testing and maintaining parsers for large grammars.