Grammar Inference Technology Applications in Software Engineering

University Of Alabama At Birmingham, Birmingham AL

Investigators

Abstract

There are many problems whose solutions take the form of patterns that may be expressed using grammars (e.g., speech recognition, text processing, genetic sequencing, programming language development, etc.). Construction of these grammars is usually carried out by computer scientists working with domain experts. Grammar inference (GI) is the process of learning a grammar from examples, either positive (i.e., the pattern should be recognized by the grammar) and/or negative (i.e., the pattern should not be recognized by the grammar). This research makes a fundamental contribution toward software engineering and grammar inference technology by: 1) advancing GI algorithms which may also have new applications in other areas of computer science (e.g., bioinformatics), 2) facilitating development of domain-specific languages (DSL's) for domain experts, thus increasing productivity and reliability, and 3) providing tools for recovering software model descriptions (metamodels) from models which have evolved independently of the metamodel. Memetic programming (MP) will be researched for recovering DSL's from example programs. MP extends genetic programming with local search and provides more effective solutions to many NP-hard problems. A local search technique based on incremental learning of context-free grammars (CFG's) will be developed along with memetic algorithms for CFG induction, in order to allow inference of DSL's. To perform metamodel inference, this research will: 1) improve abstraction hierarchy inference algorithms for metamodels, 2) recover the type information of metamodel entities, using program transformation, and 3) infer the modularization of large multi-tiered metamodels. These advancements are expected to allow inference of detailed, accurate and large scale metamodels.