使用自然语言进行程序合成( 三 ) 引用DesaiA,GulwaniS,HingoraniV,etal

（1）领域特定语言：一个领域特定语言 L = (G, TC)由一组上下文无关文法 G（其中 G\T 表示终结符集、GR 表示产生式规则集）和一个可以检查给定程序类型正确性的类型/语义检查器 TC 构成；
（2）训练数据：训练数据由一组形如(S, P)的对组成，其中：S 是一个英语句子， P 是用领域特定语言 L 写成的预期程序。一个英语句子 S 可以简单表示为一个单词序列[w1, w2, … , wn]；
（3）NL-to-\DSL\的功能目标\：生成的 NL-to-DSL 生成器应该能够将一个英语句子翻译成一个由排序后程序组成集合[P\1, P2, …, P\k] 。其中所有的程序都由 L 编写。
4 语言转换算法本文提出的合成算法（算法 1）从用户处获取自然语言命令作为输入，并创建候选 DSL 排名列表作为输出。算法的第一步（第 2 行的循环）是利用定义了 NL 到终结符映射的字典结构 NLDict 将用户输入中的而每个单词转换为一个或多个终结符。该循环遍历输入语句的每个字符。针对每一个索引，算法将利用 NLDict 挑选出相关单词，并查找 DSL 中与这些单词相关终结符集。从本质上来说， NLDict 为每个终结符进行了编码，并根据输入的英语单词决定在最终生成的预期程序中选用哪些终结符。
字典 NLDict 会分别将每个自然语言单词与一组终结符关联起来。终结符可能是常量值，也有可能是参数空缺的的函数（留白参数用“□”表示）。因此，当在算法 1 的第三行上应用 NLDict 时，生成程序中某些函数的参数可能会发生缺失，进而输出不完整的程序。以语句“Print all lines that do not contain 834（打印除 834 以外的所有行）”为例：由于语法中包含产生式规则 PrintCmd := Print(SelectStr ， IterScope) ，且字典将单词“print”与函数 Print 关联在了一起，那么这样就会生成不完整的程序 Print(□, □) 。这些空缺将在后续被一些能够匹配参数 SelectStr 和 IterScope 的程序所替换。
文章插图
算法 1 NL-to-DSL 合成算法
在完成了基本终结符集合的构建之后，算法 1 将采用 Bag 算法（算法 2）来生成一个包含所有候选程序的集合 ResT ，对应算法 1 的第 5 行。算法 1 的最后一步是结合得分和权重，对集合中所有的候选程序进行排序，对应算法 1 第 8 行。
文章插图
算法 2 Bag 子合成算法
5 训练阶段本节主要介绍分类器、权重和单词到终结符映射的学习过程。训练阶段的关键在于 ① 确定使用哪种机器学习算法；② 利用 DSL 设计者提供的高阶训练数据生成为机器悬系算法服务的低阶训练数据。
5.1 映射得分分类器（Cmap）Cmap 的功能是利用单词 w 的 POS 标签预测 w 映射到某个终结符 t ∈ G\T 的可能性。本文使用了一种朴素贝叶斯分类器的现有实现来训练分类器 Cmap ，用于训练 C\map 的算法如算法 3 所示。
文章插图
算法 3 训练映射得分分类器 Cmap
文章插图
相似性元组主要为两个目标服务：第一，通过 UsedWords ，引导系统侧重那些“使用了输入语句中所有部分”的映射；第二，通过 D\isjointness ，引导系统侧重那些惩罚了“使用输入语句中单个部分来构建多个不同子程序”的映射。
5.2 结构得分分类器（Cstr）本部分将介绍为结构得分服务的分类器 Cstr 的训练过程。对于每一个连接 Conn ，都有一个分类器 C\str [Conn]与之对应。分类器 Cstr [Conn]的主要功能是预测一个组合 c 是连接 Conn 的一个实例的概率。本文使用了朴素贝叶斯分类器的现有实现来生成训练数据，训练过程如算法 4 所示。
文章插图
算法 4 训练结构得分分类器 Cstr
算法 4 的关键思路是在不记录单个步骤得分的情况下（SynthNoScore）运行合成算法，目的是利用一个英语句子 S 构造包含所有可能程序结果的集合 A\llOpts 。 P’是 AllOpts 中的一个程序。任何出现在 P\’但没有出现在 P 中的组合都将被用作负样例（Negative Example）；相反的，如果该组合同时出现在 P’和 P 中，那么它将被用作正样例（Positive Example）。
5.3 字典构建利用 DSL 中终结符的名字（表示函数和参数），本文提出的方法将通过一种半自动化的方式构建字典 NLDict 。对于名字恰好对应英文单词（例如 Insert）的操作，作者直接利用 WordNet 同义词列表来收集所有和该操作（插入操作）相关的所有常用同义词；对于终结符的名字不是一个英文单词、而是采用某种命名方式产生的单词的链接（例如 StartsWith）的操作，作者首先利用命名规则分解操作名称，紧接着再解析出每个子名称对应的同义词。