SdfMetz computes metrics for SDF grammars. Among the supported metrics are counters of terminals, non-terminals, productions, and disambiguation constructs, McCabe's cyclometric complexity, and structure metrics such as tree impurity and normalized count of grammar levels.
The metrics implemented by SdfMetz are explained and illustrated in:
Tiago Alves and Joost Visser, Metrication of SDF Grammars. Technical Report, DI-Research.PURe-05.05.01, Departamento de Informática, Universidade do Minho, May 2005. pdf
Fig 1: Scatterplot of non-terminal count versus Halstead size metrics.
This technical report also shows metric values for 27 non-trivial grammars, and some discussion of the interpretation of this data. Some exerpts from the report are included below. A companion tool SdfCoverage, for measuring grammar coverage is also mentioned in the report.
SdfMetz is intended to be an instrument for Grammar Engineering. An overview of research into grammar engineering can be found in:
P. Klint and R. Lämmel and C. Verhoef, Towards an engineering discipline for grammarware, link.
In particular, SdfMetz is inspired by
James F. Power and Brian A. Malloy, A metrics suite for grammar-based software, link.
We have adapted their suite of metrics to the SDF grammar notation, and extened it with a few SDF-specific metrics. Also, the SdfMetz tool supports generation of immediate and transitive successor graphs from SDF grammars. For details, see the technical report Metrication of SDF grammars.
SDF stands for Syntax Definition Formalism. It is a purely declarative (no semantic actions) and modular grammar notations which is supported by Generalized LR Parsing. For information and resources regarding SDF, see:
The initial motivation for the development of the SdfMetz tool came from a grammar development project where an SDF grammar for the VDM-SL language was recovered from an ISO reference manual. A description of the use of SdfMetz for monitoring that grammar development process can be found in:
Tiago Alves and Joost Visser, Grammar-centered Development of VDM Support. In proceedings of the Overture Workshop, colocated with Formal Methods 2005. Technical Report of the University of Newcastle, to appear, 2005. pdf
Tiago Alves and Joost Visser, Development of an Industrial Strength Grammar for VDM. Technical Report, DI-Research.PURe-05.04.29, Departamento de Informática, Universidade do Minho, April 2005. pdf
The deliverable of that project, a VDM-SL front-end, can be found on the VooDooMFront web page.
Features
Fig 2: Immediate successor graph of a fragment of the VDM-SL grammar.
Fig 3: Transitive successor graph of the same fragment of the VDM-SL grammar.
SdfMetz is a command line tool. For details about its usage, type SdfMetz -h at the command line prompt.
Input
SdfMetz accepts one of more SDF grammar files as input.
Alternatively, SdfMetz accepts grammars in Semantic Designs' DMS grammar notation.
Output
The metric values computed by SdfMetz can be exported as a nicely formatted textual report, or as comma-separated-value files, for easy import into e.g. Excel or SPSS.
SdfMetz calculates immediate and transitive successor graphs to compute structure metrics. These graphs can also be exported, in the dot format of AT&T's GraphViz'.
In addition, SdfMetz can export the non-singleton levels of the input grammars. These are groups of non-terminals that are mutually reachable from each other in the grammar's successor graph.
Computed metrics
The suite of metrics computed by SdfMetz is defined and explained in the technical report Metrication of SDF grammars. They include counters for non-terminals, terminals, productions, and disambiguations constructs, McCabe's cyclometeric complexity, and structure metrics such as tree impurity and normalized count of levels.
A grammar comparison experiment
As an initial experimant in grammar metrication, we have applied SdfMetz to collect metrics data for a range of grammars from various origins. Full details about this experiment can be found in the Section Data Collection in:
Tiago Alves and Joost Visser, Metrication of SDF Grammars. Technical Report, DI-Research.PURe-05.05.01, Departamento de Informática, Universidade do Minho, May 2005. pdf
Sampled grammars
The sampled grammars include 18 SDF grammars for languages such as Yacc, BibTex, Fortran, Toolbus, Stratego, SDF itself, Java, SDL, C, Cobol, DB2, PL/SQL, VDM-SL, and VB.Net. These grammars were obtained from the following sources:
sfi - Grammars freely available in the Strafunski bundle
In the report, metrics calculated by us are presented side by side with those of four BNF grammars from the paper A metrics suite for grammar-based software of Power and Malloy.
Raw data
The technical report presents the collected metrics data in a series of tables, one for each category of metrics. The raw data of the experiment is available upon request in a single comma-separated-value file.
A grammar monitoring experiment
Fig 4: Plot of three grammar metrics for 48 subsequent development versions.
The initial motivation for the development of the SdfMetz tool came from a grammar development project where an SDF grammar for the VDM-SL language was recovered from an ISO reference manual. A description of the use of SdfMetz for monitoring that grammar development process can be found in:
Tiago Alves and Joost Visser, Grammar-centered Development of VDM Support. In proceedings of the Overture Workshop, colocated with Formal Methods 2005. Technical Report of the University of Newcastle, to appear, 2005. pdf
Tiago Alves and Joost Visser, Development of an Industrial Strength Grammar for VDM. Technical Report, DI-Research.PURe-05.04.29, Departamento de Informática, Universidade do Minho, April 2005. pdf
The deliverable of that project, a VDM-SL front-end, can be found on the VooDooMFront web page.
Implementation
The SdfMetz tool was implemented in the functional programming language Haskell using the Strafunski bundle for generic traversal support.
The tool was developed using a grammar-centered approach, where various kinds of functionality were automatically generated from a concrete syntax definition of the SDF language (the SDF language specified in SDF). The parser was automatically generated with sdf2table, from the SDF bundle. The Haskell support for representing, and pretty-printing abstract syntax trees (ASTs) was automatically generated with Sdf2Haskell, from the Strafunski bundle. AST traversal and marshalling support was generated with the Strafunski-aware DrIFT tool.
The reusable functionality of SdfMetz has been organized as modules of the UMinho Haskell Libraries. The structure metrics and underlying graph algorithms have been implemented on a generic graph representation, available from these same libraries.
Download
The SdfMetz tool (version 1.1) is available for download in a self-contained distribution. (download)
As alternative, it can also be obtained as part of the UMinho Haskell Libraries & Tools.
Future work
Apart from adding more metrics to the repertoire of SdfMetz, we intend to do the following:
Add front-ends for Yacc and ANTLR grammars
Collect more grammars for experimentation
Perform more comprehensive statistical analysis on the collected data