Grammar Inference Technology Applications in Software Engineering

语法推理技术在软件工程中的应用

• 批准号: 0811630
• 负责人: Barrett Bryant
• 金额: $ 45万
• 依托单位: University of Alabama at Birmingham
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0811630&HistoricalAwards=false
• 关键词: Grammar; Inference; Technology; Applications; Software

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.

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