Techniques for Context-Free Grammar Induction and Applications

Grammar Inference is the process of learning a
grammar from examples, either positive (i.e., the
grammar generates the string) and/or negative (i.e.,
the grammar does not generate the string). Although
grammar inference has been successfully applied to
many diverse domains such as speech recognition and
robotics, its application to software engineering
has been limited. This book provides an overview of
the area and discusses the following applications of
grammar inference: 1) Recovery of a metamodel from
instance models: the MetAmodel Recovery System
(MARS), a system that uses grammar inference in
concert with a host of complementary technologies
and tools to address the metamodel drift problem. 2)
Recovery of domain-specific language (DSL)
specifications from example DSL programs: GenInc, an
unsupervised incremental CFG learning algorithm that
allows further progress towards inferring DSLs and
finds a second application in recovery of legacy
DSLs. This book is directed at researchers and
software developers interested in learning about the
exciting field of grammar inference and its
applications to software maintenance issues.