援用

Desai A, Gulwani S, Hingorani V, et al. 程序合成利用自然语言[C]//第 38 届国际软件工程大会论文集。2016: 345-356.

摘要

随着计算机逐渐普及，人机交互变得越来越普遍。许多重复性或专业任务通常需要编写小型的、一次性程序。然而，为了编写这些一次性程序，用户可能需要投入大量时间和精力去学习特定领域的语言（DSL），这为用户带来不便。

本文介绍了一个通用框架，可以构建一种利用自然语言（NL）合成特定领域语言（DSL）的程序合成器。该框架以DSL定义和训练数据（NL/DSL对）为输入，通过训练并使用基于关键词编程翻译的分类器，结合最优权重和自然语言处理（NLP）特性，实现了目标程序合成器的构建。该框架适用于文本编辑、智能教学系统和航班信息查询等领域。本文提供了三个针对不同领域的程序合成器，分别基于1200多个英语描述。预期程序在合成程序列表中排在Top-1和Top-3的概率分别为80%和90%。

关键词

自然语言；特定领域语言；程序合成

1 引言

程序合成是一种根据给定的规格（Specification），使用特定领域语言（DSL）自动生成程序的过程。传统的程序合成依赖完全规格。由于编写完全规格困难且验证结果也相当复杂，导致传统程序合成并未广泛应用。

近年来，研究者尝试在程序合成过程中使用样例（Examples）作为指导。样例规格比完全规格更容易获得，因此更加实用。例如，实例编程（PBE）系统。然而，当样例数量过多时，构建规格变得困难。相比之下，自然语言描述在某些领域，如航班信息查询系统（ATIS），可能更适合用于指导程序合成。

本文解决了利用自然语言（NL）合成特定领域语言（DSL）程序的问题。为了保证程序的准确性，作者将程序合成器的输入定义为一组排序后的程序，而非单一程序，并允许用户通过查看源代码和程序输入来选择程序。本文提出的合成算法在基准测试上表现稳定：80%的情况下，预期程序排在Top-1；90%的情况下，预期程序排在前三。此外，为了帮助用户选择程序，作者还提供了无歧义的英语描述。

2 研究动机

本文探讨了三种应用场景，分别是：文本编辑操作（2.1节）、智能教学系统中的自动构造问题（2.2节）和航班信息查询系统（2.3节）。

2.1 文本编辑

在阅读Office程序（如Microsoft Excel和Word）的论坛时，作者发现许多关于如何进行复杂文本编辑操作的问题。这些操作比简单的文本搜索或字符串替换更为复杂，需要用户掌握正则表达式、条件语句和循环语句等高级技术，这对大多数用户来说难度较大。

表1展示了文本编辑领域相关的语法和基准样本。作者设计了一种DSL，用于描述这些复杂的文本编辑任务，通过将复杂任务分解为简单任务，使得用户能够更轻松地完成这些任务。

2.2 自动机理论（智能教学）

形式化方法在智能教学系统中的应用已经取得显著成效，包括问题生成、解答生成和反馈生成等多个领域。例如，在自动机理论中，作者设计了一种DSL，用于帮助学生构造自动机。这种DSL不仅可用于生成正确答案，还可以生成反馈和问题变体。

表2展示了自动机领域的基准样本。通过使用DSL，系统能够生成正确答案并提供有效的反馈。

2.3 航班信息查询系统（ATIS）

ATIS是一个用于查询航班信息的标准基准，包括英语查询和包含航班信息的数据库。作者设计了一种基于SQL操作的DSL，用于描述航班查询任务。

表3展示了ATIS领域的基准样本。通过使用DSL，系统能够将自然语言查询转化为SQL查询。

3 问题定义

本文主要研究如何使用给定的DSL定义和训练数据合成目标NL-to-DSL合成器。具体定义如下：

1. 特定领域语言（DSL）：DSL由上下文无关文法G和类型/语义检查器TC构成。
2. 训练数据：训练数据由形如(S, P)的对组成，其中S是一个英语句子，P是用DSL编写的预期程序。
3. NL-to-DSL的目标：生成的NL-to-DSL生成器应能将一个英语句子翻译成一个由排序后的程序组成的集合[P1, P2, …, Pk]。

4 转换算法

本文提出的合成算法（算法1）从用户输入的自然语言命令开始，生成候选DSL排名列表。算法的第一步是将用户输入中的每个单词转换为一个或多个DSL终结符。这一过程通过字典结构NLDict实现，根据输入的英语单词决定最终生成的预期程序中选用哪些终结符。

在生成基本终结符集合后，算法采用Bag算法生成所有候选程序的集合。最后，结合得分和权重对候选程序进行排序。

5 训练阶段

本文介绍了分类器、权重和单词到终结符映射的学习过程。训练阶段的关键在于确定使用哪种机器学习算法，以及如何将高阶训练数据转换为适合机器学习算法的低阶训练数据。

5.1 映射得分分类器（Cmap）

Cmap用于预测一个单词映射到某个DSL终结符的可能性。本文使用朴素贝叶斯分类器来训练Cmap分类器。

5.2 结构得分分类器（Cstr）

Cstr用于预测一个组合是否是某个连接的一种实例。本文使用朴素贝叶斯分类器生成训练数据。

5.3 字典构建

通过半自动化的方式构建字典NLDict。对于名字恰好对应英文单词的操作，直接使用WordNet收集相关同义词；对于名字不是英文单词的操作，则先分解操作名称，再解析每个子名称的同义词。

致谢

本文由南京软件学院2020级硕士钱瑞祥翻译转述。