- author = "Faizan Javed",
- title = "Techniques for Context-Free Grammar Induction and Applications",
- school = "Computer and Information Sciences, University of Alabama-Birmingham",
- year = "2007",
- address = "Birmingham, Alabama, USA",
- month = "5 " # dec,
- keywords = "genetic algorithms, genetic programming, MARS, GenParse",
-
URL = "
http://www.cis.uab.edu/softcom/dissertations/JavedFaizan.pdf",
- broken = "https://www.cis.uab.edu/softcom/dissertations.php",
- 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., bioinformatics).",
-
notes = "See also
\cite{Javed:book}
https://www.sigsoft.org/dissertations.html
http://www.cis.uab.edu/node/1971 http://genealogy.math.ndsu.nodak.edu/id.php?id=123516 Advisor: Barrett Richard Bryant",
