Grammar Recovery from Parse Trees and Metrics-Guided Grammar Refactoring
N. Kraft, E. Duffy, and B. Malloy. IEEE Transactions on Software Engineering, 35 (6):
780-794(November 2009)
Abstract
Many software development tools that assist with tasks such as testing and maintenance are specific to a particular development language and require a parser for that language. Because a grammar is required to develop a parser, construction of these software development tools is dependent upon the availability of a grammar for the development language. However, a grammar is not always available for a language and, in these cases, acquiring a grammar is the most difficult, costly, and time-consuming phase of tool construction. In this paper, we describe a methodology for grammar recovery from a hard-coded parser. Our methodology is comprised of manual instrumentation of the parser, a technique for automatic grammar recovery from parse trees, and a semi-automatic metrics-guided approach to refactoring an iterative grammar to obtain a recursive grammar. We present the results of a case study in which we recover and refactor a grammar from version 4.0.0 of the GNU C++ parser and then refactor the recovered grammar using our metrics-guided approach. Additionally, we present an evaluation of the recovered and refactored grammar by comparing it to the ISO C++98 grammar.
%0 Journal Article
%1 Kraft2009
%A Kraft, Nicholas A.
%A Duffy, Edward B.
%A Malloy, Brian A.
%D 2009
%J IEEE Transactions on Software Engineering
%K grammar_induction grammar
%N 6
%P 780-794
%T Grammar Recovery from Parse Trees and Metrics-Guided Grammar Refactoring
%V 35
%X Many software development tools that assist with tasks such as testing and maintenance are specific to a particular development language and require a parser for that language. Because a grammar is required to develop a parser, construction of these software development tools is dependent upon the availability of a grammar for the development language. However, a grammar is not always available for a language and, in these cases, acquiring a grammar is the most difficult, costly, and time-consuming phase of tool construction. In this paper, we describe a methodology for grammar recovery from a hard-coded parser. Our methodology is comprised of manual instrumentation of the parser, a technique for automatic grammar recovery from parse trees, and a semi-automatic metrics-guided approach to refactoring an iterative grammar to obtain a recursive grammar. We present the results of a case study in which we recover and refactor a grammar from version 4.0.0 of the GNU C++ parser and then refactor the recovered grammar using our metrics-guided approach. Additionally, we present an evaluation of the recovered and refactored grammar by comparing it to the ISO C++98 grammar.
@article{Kraft2009,
abstract = {Many software development tools that assist with tasks such as testing and maintenance are specific to a particular development language and require a parser for that language. Because a grammar is required to develop a parser, construction of these software development tools is dependent upon the availability of a grammar for the development language. However, a grammar is not always available for a language and, in these cases, acquiring a grammar is the most difficult, costly, and time-consuming phase of tool construction. In this paper, we describe a methodology for grammar recovery from a hard-coded parser. Our methodology is comprised of manual instrumentation of the parser, a technique for automatic grammar recovery from parse trees, and a semi-automatic metrics-guided approach to refactoring an iterative grammar to obtain a recursive grammar. We present the results of a case study in which we recover and refactor a grammar from version 4.0.0 of the GNU C++ parser and then refactor the recovered grammar using our metrics-guided approach. Additionally, we present an evaluation of the recovered and refactored grammar by comparing it to the ISO C++98 grammar.},
added-at = {2010-01-01T12:40:22.000+0100},
author = {Kraft, Nicholas A. and Duffy, Edward B. and Malloy, Brian A.},
biburl = {https://www.bibsonomy.org/bibtex/2d7eb125dc615627c3a3f7bff525022a0/sjbutler},
interhash = {a41c593605e948faa723b3402fa92848},
intrahash = {d7eb125dc615627c3a3f7bff525022a0},
journal = {IEEE Transactions on Software Engineering},
keywords = {grammar_induction grammar},
month = {Nov.-Dec. },
number = 6,
pages = {780-794},
timestamp = {2010-01-01T12:40:22.000+0100},
title = {Grammar Recovery from Parse Trees and Metrics-Guided Grammar Refactoring},
volume = 35,
year = 2009
}