Grammar Inference Technology Applications in Software Engineering

有许多问题的解决方案采用可以用语法表示的模式形式（例如，语音识别、文本处理、基因排序、编程语言开发等）。这些语法的构建通常由计算机科学家与领域专家合作完成。语法推理（GI）是从例子中学习语法的过程，可以是积极的（即模式应该被语法识别）和/或消极的（即模式不应该被语法识别）。本研究对软件工程和语法推理技术做出了根本性的贡献：1)推进GI算法，这可能在计算机科学的其他领域（例如，生物信息学）也有新的应用；2)促进领域专家的领域特定语言（DSL）的发展，从而提高生产力和可靠性；3)提供工具，用于从独立于元模型发展的模型中恢复软件模型描述（元模型）。本文将研究模因编程（Memetic programming， MP）从实例程序中恢复DSL。MP将遗传规划扩展到局部搜索，为许多np困难问题提供了更有效的解决方案。本文将开发一种基于上下文无关语法增量学习的局部搜索技术，并结合模因算法对上下文无关语法进行归纳，从而实现对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.