Techniques for Context-Free Grammar Induction and Applications

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  author =       "Faizan Javed",
  title =        "Techniques for Context-Free Grammar Induction and
  school =       "Computer and Information Sciences, University of
  year =         "2007",
  address =      "Birmingham, Alabama, USA",
  month =        "5 " # dec,
  keywords =     "genetic algorithms, genetic programming, MARS,
  URL =          "",
  URL =          "",
  size =         "183 pages",
  abstract =     "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 research investigates the applicability of grammar
                 inference to software engineering and programming
                 language development challenge problems, where grammar
                 inference offers an innovative solution to the problem,
                 while remaining tractable and within the scope of that
                 problem. Specifically, the following challenges are
                 addressed in this research:

                 1. Recovery of a metamodel from instance models: Within
                 the area of domain-specific modelling (DSM), instance
                 models may evolve independently of the original
                 metamodel resulting in metamodel drift, an
                 inconsistency between the instance model and the
                 associated metamodel such that the instance model may
                 no longer be loaded into the modeling tool. Although
                 prior work has focused on the problem of schema
                 evolution, no previous work addresses the problem of
                 recovering a lost metamodel from instance models. A
                 contribution of this research is the MetAmodel Recovery
                 System (MARS) 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: An open
                 problem in DSL development is a need for reducing the
                 time needed to learn language development tools by
                 incorporating support for the description-by-example
                 (DBE) paradigm of language specifications like syntax.
                 This part of the dissertation focuses on recovering
                 specifications of imperative, explicitly
                 Turing-complete and context-free DSLs. A contribution
                 of this research is GenInc, an unsupervised incremental
                 CFG learning algorithm that allows further progress
                 towards inferring DSLs and finds a second application
                 in recovery of legacy DSLs.

                 The research described in this dissertation makes the
                 following contributions: i) A metamodel recovery tool
                 for DSM environments, ii) Easier development of DSLs
                 for domain experts, and iii) Advances in grammar
                 inference algorithms that may also have new
                 applications in other areas of computer sciences (e.g.,
  notes =        "
                 Advisor: Barrett Richard Bryant",

Genetic Programming entries for Faizan Javed