Research On The Method Of Program Synthesis Guided By Algorithm Knowledge

Program synthesis(Program Automatic Generation)is an important research direc-tion in the field of software engineering,which aims at software development activities that automatically generate corresponding program codes according to user intentions.How to effectively limit the program search space has always been one of the core issues in the field of program synthesis.Many studies have reduced the search space of programs by designing domain-specific languages(DSL),but the synthesized DSL programs are barely readable and require domain-related knowledge.Due to the large program space of general programming languages,it is difficult to synthesize large-scale complex pro-grams with control structures(such as Java).Aiming at the limitations of current general-purpose programming language synthe-sis technology,this paper proposes an algorithm knowledge guided program synthesis method,which aims to use the program information contained in the algorithm pseu-docode to promote synthesis.The main contributions and innovations of this thesis are as follows:(1)A program synthesis method guided by algorithm knowledge is proposed.Aim-ing at the standard algorithm pseudocode,a parsing algorithm is proposed to parse the pseudocode text into the structure information of the target program and the related in-formation of local variables to guide the process of synthesis.Based on the algorithm knowledge obtained from the analysis,a corresponding heuristic generation strategy is developed for the synthesizer to improve the synthesis efficiency.We have conducted experiments to verify this method on 18 complex tasks,and successfully solved 13 of them,showing that the method can effectively utilize algorithmic knowledge and make it possible to synthesize complex programs with control structures.(2)A program synthesis framework combining algorithm recommendation and al-gorithm guidance is proposed.This framework focuses on the code in synthetic program-ming competition problems.Firstly,an algorithm recommendation method based on a text classification model is proposed.The text classification model is trained and tested on the data set of the problem and the algorithm class name,and finally a more accurate algorithm recommendation is realized.We conducted an overall experimental evaluation on the collected programming competition topics,and finally successfully synthesized 3typical algorithm programs,indicating that the framework can initially solve some pro-gramming competition problems.