Grammar Inference Technology Applications in Software Engineering

有许多问题的解决方案采取可以使用语法(例如，语音识别、文本处理、基因测序、编程语言开发等)来表达的模式的形式。这些语法的构建通常是由计算机科学家与领域专家合作完成的。语法推理(GI)是从例子中学习语法的过程，无论是积极的(即模式应该被语法识别的)还是否定的(即模式不应该被语法识别的)。该研究对软件工程和语法推理技术做出了根本性的贡献：1)改进了GI算法，这些算法也可能在计算机科学的其他领域(例如，生物信息学)中有新的应用；2)促进了领域专家的领域特定语言(DSL)的开发，从而提高了生产率和可靠性；3)提供了从独立于元模型演化的模型中恢复软件模型描述(元模型)的工具。为了从示例程序中恢复DSL，将研究模因编程(MP)。该算法扩展了遗传规划的局部搜索功能，为许多NP-Hard问题提供了更有效的解决方案。提出了一种基于上下文无关文法增量学习的局部搜索技术(CFG‘s)和上下文无关文法归纳的Memtic算法，以实现对DSL的推理.为了进行元模型推理，本研究将：1)改进元模型的抽象层次推理算法；2)通过程序变换恢复元模型实体的类型信息；3)推断大型多层元模型的模块化.预计这些进展将允许对详细、准确和大规模的元模型进行推断。

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.