PURe

Program Understanding and Re-engineering: Calculi and Applications

Navigation

Related

News

Sep 18 Paper Towards a Coordination Model for Interactive Systems by MarcoAntonioBarbosa, JoseCampos and LuisSoaresBarbosa has been accepted for FMIS'06 (Macau).

July 3 Paper Configurations of Web Services by MarcoAntonioBarbosa and LuisSoaresBarbosa has been accepted for FOCLASA'06 (Bonn, Germany).

July 3 Paper Strong Types for Relational Databases by Alexandra Silva and JoostVisser has been accepted for the Haskell Workshop 2006 (Portland, USA).

June 16 Paper Strongly Typed Rewriting For Coupled Software Transformation (by AlcinoCunha and JoostVisser) accepted by RULE 2006 (Seattle, USA).

May, 26 Paper Transposing Partial Coalgebras (by LuisSoaresBarbosa and JoseNunoOliveira) accepted for publication in TCS, Elsevier.

May, 11 Papers Type-safe two-level data transformation (by AlcinoCunha, JoseNunoOliveira and JoostVisser) and Pointfree factorization of operation refinement (by JoseNunoOliveira and Cesar Rodrigues) have been accepted by FM'06 (Canada).

May, 8 A paper entitled An Orchestrator for Dynamic Interconnection of Software Components, by MarcoAntonioBarbosa and LuisSoaresBarbosa, accepted at MTCoord'06 (Bologna).

More...

SdfMetz: metrication of SDF grammars

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

Scatter plot VAR against N
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.

Background

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:

  • SDF page at program-transformation.org.

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

Immediate successor graph
Fig 2: Immediate successor graph of a fragment of the VDM-SL grammar.


Transitive successor graph
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:

Furthermore, five DMS grammars for ECMAScript, PHP, Java, Verilog, and C++ were sampled:

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

Evolution of grammar metrics
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

Credits

The main developers of the SdfMetz tool are:

We thank Dr. Tobias Kuipers from the Software Improvement Group and Dr. Ira Baxter from Semantic Designs Inc. for allowing us to perform measurements on grammars of their respective companies.


blog stats

r15 - 04 Nov 2007 - 19:18:26 - JoseBacelarAlmeida
This site is powered by the TWiki collaboration platform Copyright © by the contributing authors. Ideas, requests, problems? Send feedback.
Syndicate this site RSSATOM