程序合成是指根据给定问题的具体描述由计算机自动生成满足要求的程序。这是一种用底层编程语言自动合成程序的任务,其目标是通过具体的算法策略找到符合用户意图的程序。用户意图使用各种形式表示,包括逻辑规范、示例、自然语言、部分程序甚至相关程序。语法引导的程序合成问题使用逻辑规范来表达用户对于期望程序的要求。最新的研究证明,使用语法模板来补充逻辑规范对于求解程序合成问题有潜在益处,即由逻辑规范和语法规范组成了语法引导的程序合成问题的约束。目前针对程序合成问题的求解技术还有许多不足之处。例如通过示例编程的方法限制用户必须提供一定数量的输入输出示例对,自动演绎合成是非常有效的方法,但只适用于特殊的语法或应用程序,枚举搜索方法是在中小型基准测试中表现良好,能生成简洁的表达式,并能够从输入输出示例中进行概括。然而,它的性能会随着最小的正确结果的规模变大而急剧下降,在采用分而治之与枚举搜索结合的求解策略中,没有有效处理反例样本增量式生成的问题。因此本文提出一种应对语法引导程序合成问题的反例样本不断生成问题的增量式学习方法,以提高程序合成的效率。本文利用增量决策树算法,来实现对于语法引导程序合成问题的程序表达式合成。首先通过分而治之的枚举搜索方法从给定的语法空间中生成表达,然后利用决策树学习算法将枚举得到的各表达式组件组合成为待验证的程序。对于经验证后新增的反例样本,本文在已生成决策树的基础上,通过保存在各树节点上的信息进行找出最优的测试属性实现对决策树的更新转换。随后的更新演变成为一种在线学习过程,即根据程序验证器不断反馈的样本,对决策树模型进行调整,以实现对符合约束要求的程序的生成。该算法可以实现在求解过程中保存已学到的知识,并且在已有知识上进行更正和更新,减少了对反例进行重复学习造成的开销,提高对问题的求解效率。此外,本文还将传统的C4.5决策树学习算法和CART决策树学习算法应用到语法引导的程序合成问题求解中。通过对比实验比较了不同的条件表达式选择策略对合成效率的影响,并且将实现本文算法的INCsolver与当前最先进的两个合成求解器对比。结果显示,INCsolver能够解决实验测试数据集60%以上的问题,并且在其中的30个问题上求解速度最优。