Research On Methods Of Software Semantic Analysis Based On Abstract Syntax Tree

With the development of computer science and technology,new tasks and challenges appear in the field of software quality,semantic analysis of software,which is an important method of improving software quality, has been widespread concerned in society. However,there are some shortcomings in the primary software semantic analysis, such as high complexity and low rate of accuracy and so on. Firstly, a new algorithm that reconstructing syntax tree is proposed in this paper,and the number of nodes of the abstract syntax tree is reduced largely by it; Secondly, an optimization algorithm which is related to the system dependence graph is proposed based on the abstract syntax tree, and the scale of the system dependence graph is reduced effectively; Finally, based on the reachability algorithm of the simplified system dependence graph,the entire semantic analysis of software is completed by computing the program's dynamic slices in this paper. It is that the semantic method of software, mentioned in this paper, has an important significance in improving the rate and accuracy of semantic analysis of software.Firstly, the structure of abstract semantic nodes and the meaning of each part which are generated by GCC(GNU Compiler Collection) are introduced in this paper. According to the problems that the abstract syntax tree, generated by GCC, has a chaotic structure and redundant nodes, an reconstruction algorithm of abstract syntax tree is proposed based on the standardized file of GCC, and the standardized file of GCC which contains useful nodes is generated by making the abstract syntax tree nodes generated by GCC standardization and deleting the redundant nodes, and the scale of nodes of the abstract syntax tree is reduced effectively by rebuilding the abstract syntax tree of program which is based on the file.Secondly, an algorithm to build the control flow graph based on program's control dependence graph is proposed, it breaks the conventional process that building control dependence graph is prior to building control flow graph in the traditional system dependence graph. The subsequent parts of the operation can be omitted if users just need to control the dependence, therefore, it brings more flexibility for the software semantic analysis. Thirdly,on the basis of the abstract syntax tree, a SSDG(simplified system dependence graph)algorithm based on equivalent substitution of dependency graph is proposed in this paper.According to the thought of equivalence substitution of dependency graph, it can reduce the flexibility of building system dependence graph effectively by using the program dependence graph to replace the system dependence graph. Finally, computing the dynamic slices of program based on the reachability algorithm of SSDG can avoids the defect that the cyclic edge cannot be marked correctly in reachability algorithm of graph by decomposing the process of program's execution into two cases: cyclic and non-cyclic, furthermore, the reachability algorithm of graph can avoid the defects of high time complexity effectively that caused by repeated iteration in the data flow equation algorithm.The development tool,vs2010, a simulation platform,is used to simulate the algorithm mentioned in this paper, and the result of simulation shows that the software semantic analysis algorithm can compute the program's slices more efficiently and accurately comparing with traditional algorithm.