Research On Theory And Application Of Program Slicing

In the1970s,with the exponential growth of softwares’ scale, understanding andmaintaining programs became more and more difficult. Some researchers found that inthe large-scale program debugging: when a large software system was divided intoseveral smaller programs in accordance with some rules, it was easy to understand andmaintain these smaller programs. This was the prelude of people studying programdecomposition technology. After many years’ development, there were a lot of fruitfulresults in the theory and application of program decomposition technique. Informationhiding, HIPO (Hierarchy Plus Input/Processing/Output), program slicing technologyare typical program decomposition techniques. Program slicing technology was themost important program decomposition technique,its emergence and developmentcaused an epochal change in the program decomposition field.Program slicing technology decomposed a program in accordance with somecertain rule for achieving the purpose of reducing the program’s codes. Its conceptraised for the first time in Mark.W’s doctoral thesis in1979, Mark.W is a well-knownsoftware engineering expert. By analyzing the data in a mainstream program,Mark.Westablished a control flow graph which was used to describe the dependencies betweenprogram statements, and proposed a program slicing algorithm which was based ondata flow equations. With the emergence of procedural languages, the researchersfound that using the algorithm of Mark.W to calculate the slice of a program includingmultiple processes was very difficult, because it was very complex and difficult toestablish a data flow equation for every process. Karl.J.O et al analyzed thedependencies between statements in a program, proposed the concept of the programdependence graph as an abstract representation of the source code. Jeanne.F et alproposed the graph reachability algorithm based on the program dependence graph and solved the problem of calculating a single process’s slice.Based on the research ofJeanne.F et al, Susan.H et al proposed the concept of a system dependence graph andthe two-pass graph reachability algorithm which was based on the system dependencegraph, Solved the problem of calculating slices of the program which containsmultiple processes. With the continuous development of computer science, some newlanguages, such as object-oriented language, specification language, aspect-orientedlanguage, ontology language, hardware description languages have appeared, scholarsall over the world applied the basic ideas of the program slicing to these languages,proposed the definitions of the slices of the above languages and methods ofcalculating these slices. These methods are based on data flow equations and graphreachable algorithm, and improve or extend the two methods. After nearly30years ofdevelopment, the program slicing technology has made great achievements in boththeory and application, has been widely used in software debugging, softwaremaintenance, software testing, software metrics, software reuse, program verificationand other fields.Although main methods of calculating program slices are improving or extendinggraph reachable algorithm now,but creating graphical representation for each statementof the ultra-large-scale program will consume huge storage space. Therefore it isnecessary to discover new slicing methods to compensate for this deficiency. JinlongFei first applied the idea of program slicing to the ontology, established theconcept of the ontology dependency graph, proposed the method of calculating theslices of the ontology based on the ontology dependence graph.Jin Longfei onlyproposed the outlook of applying the ontology slices to ontology evolution, ontologymerging, ontology mapping and other fields of the ontology, so it is necessary tofurther discuss the algorithm of calculating ontology slices and its application in thefield of ontology. There have been many methods for calculating slices ofobject-oriented programming languages, many foreign research institutions havedeveloped some program slicing tools based on object-oriented languages, but theimplementations of the slicing tools are still rare in the country, it is necessary to implement an automatic slicing tool of an object-oriented programming language.Based on the above problems, we have done some researches on the theory andapplications of program slicing in this paper.First, we refered to the mechanisms of Java and C++, regarded JAVA as theprototype,by removing the JAVA programming language complex concepts andsyntax, such as interfaces, multiple inheritance, polymorphism, obtained a subset ofthe Java language MOOL (Model Object-Oriented Language). This paper gave therecursive descent grammar of MOOL and a MOOL example program, based on thehierarchical slicing model which was proposed by Li Bixin to calculate the slices ofJAVA programs, hierarchically created the class layer dependency graph、the methodlayer dependency graph and the statement layer dependency graph of the exampleprogram, and used Perl language to implement MST (MOOL Slicing Tool)which canautomatically slice a MOOL program.Secondly, based on the analysis of program slicing methods proposed bypredecessors, we defined a flexible slicing criteria about procedure-oriented programs,gave a new slicing method which was based on the criteria.The method according tothe control dependencies and data dependencies between the statements of a program,divided the program into a block structure, the slices was decomposed into blockinside slices and block outside slices.we used block inside slicing algorithm and blockinside iteration slicing algorithm to calculate the block inside slices and block outsideslices.Using block structure to represent the program made the slicing method moresimple and efficient; the diversity slicing criteria made it possible to calculate the slicesof any variable of the specified statement, and enhanced the versatility of the slicingmethod.Finally, based on the ontology slicing method of Jin Longfei,we proposed anontology slicing method based on hierarchical ontology dependency graph. Themethod improved the construction process of the dependency graph in the classicslicing method, flexibly controlled the hierarchy of the dependency graph, it canreduce the complexity of the dependency graph in accord with the requirements, thereby solved the problem of high complexity of the classic method.This paperprovides a feasible solution of the application of the ontology slicing method.Thesolution is a useful attempt.At the end of the paper we discussed the finished work and the future work.Thestatic slicing tool implemented in the paper can calculate static slices of the MOOLprogram in accordance two slicing criteria which was defined by us, further work is toimprove the existing slice tool to enable them to calculate the dynamic slices and theconditional slices of MOOL programs, further to develope the slicing tools of C++and JAVA. In the paper, block-based slicing method was proposed to calculate theslices of the process-oriented language, improving existing methods so that we can useit to calculate the slices of the object-oriented language is the future work. Thehierarchical ontology slicing method proposed in the paper is an attempt of applyingprogram slicing to the ontology, the future work is applying the program slicingtechnology to analyzing ripple effect of Ontology Evolution and developing automatedontology slicing tools.