The Program Slicing Technology Based On A Small Object-Oriented Language

Program slicing is an important technique to analyze and understand programs. A program slice S is composed of a set of statements in program P which can influence the value of a variable v at a special program point n , at which, (n, v) is named as slicing criterion. Computing a slice sets can get a set of program statements that directly or indirectly contributed to the value of the variable v in the slicing criterion (or the ones influenced by the variable v).Program slicing works in many fields such as program analysing , understanding and software engineering project. Programing slicing has drew people's attention widely since it was introduced in 1979. This technology has been already very mature at present. Especially there are many mature algorithms for static slicing and dynamic slicing now, These algorithms mainly include dataflow algorithm that Mark Weiser puts forward, picture reachability algorithm based on system dependence graph proposed by K.J.Ottendtein, L.M. Ottendtein and Horwitz's, and information flow algorithm that Bergeretti puts forward, etc... Along with static slicing becoming mature, people begin to develop new fields of the program slicing. First, introduce some slicing algorithms for different languages, such as the picture reachability algorithm for the C ++ language from Larsen and Harrold, then which are developed for the special mechanism of JAVA language by Kovacs et al and Zhao. Second, extend the concepts of slicing, which bings program slicing technology to the more large filed.With the wide application of object oriented language, people begin to study the program slicing for O.O. language, but there are some special mechanisms such as inherit, polymorphism, dynamic binding in O.O. language, which traditional methods can't resolve. Then people have proposed some new methods to solve these problems. According to the present research station, the program slicing methods for the O.O language have been formed primarily.These methods add some information or modify the construction of the formal graph to realize the mechinisms in O.O language. Although the algorithms for these methods have been formed in basic,t relative tools are still very few. Moreover,the slicing technique of the O.O language is still the primary stage.Based on such a situation, we decide to develop a slicing system for O.O language, which can deal with various kinds of special mechanisms with high efficiency.This paper mainly discusses the design and implementation of a Program Slicing system based on Model Object-Oriented Language (Later referred as MOOL): a small O.O language defined by myself, and describes the design and implementation of a complete static program slicing system.The following works have been done: (1) Define MOOL language and complete the lexical analysis and syntactical analysis; (2) Obtain the Class-level dependence graph from the code information tree of the source program,then input Class-level slicing criterion and obtain the Class-level slice of the source program. (3) Obtain the Method-level dependence graph from the Class-level slice,then input Method-level slicing criterion and obtain the Method-level slice of the source program. (4) Obtain the Statement-level dependence graph from the Method-level slice,then input Statement-level slicing criterion and obtain the Statement -level slice of the source program(Program slice).The first part: : according to the slicing technique of the text treatment in the paper, apply compiling technique to define the grammar of MOOL language, then add proper semantic actions to its grammar, finally use the syntactical analysis module of the Perl language"Parse::RecDescent"to implement its lexical analysis and syntactical analysis automatically and obtain the code information tree of the source program of MOOL.Context-free grammar is adopted to define the grammar of the MOOL language, and express it according the rules of the"Parse::RecDescent"module. Limited automation technique is adopted to do lexical analysis, while recursive descent parse technique is adopted to do syntactical analysis.The second part: This paper adopts the separate layer slicing algorithm instead of the traditional method which extends the system dependence graph of the Object-Oriented language to compute the slice of the source program and improves the slice step by step.First, scan the code information tree of the source program by the scan algorithm ,analyze the Inherited dependence relation among the class to obtain the Class layer dependence graph, then analyze the dependence relation among the objects , such as creation , converging ,communication and instantition between the class and the object to obtain the Object-level dependence graph of the source program.Second, add all kinds of dependence of the Object-level dependence graph into the class layer dependence graph to obtain the Class-level dependence graph. Finally, input a Class-level slicing criterion and obtain the Classt -level slice of the source program through the Graph-reachable algorithm.The Class-level slicing criterion is the mapping of the slicing criterion on class.Third, on the basis of the Classt -level slice,analyze the MSV dependence and the MUIV dependence among the member variables andthe member methods to obtain the Method-level dependence graph, then input Method-level slicing criterion, adopt Graph-reachable algorithm, obtain the Method-level slice of the source program. The Method-level slicing criterion is the mapping of the slicing criterion on method.Fourth, on the basis of the Method slice, analyze the control dependence,the data dependence and ordinary dependence among the statements to obtain the Statement-level dependence graph, then input Statement-level slicing criterion, and adopt graph reach algorithm to obtain the Statement-level slice of the source program. This Statement-level slice is the progam slice which we compute at last. The Statement-level slicing criterion is the slicing criterion that is user-idefined.In the last three stage, we use graph reach module in graph module of Perl to decide whether it is reachable between any two nodes in all the dependence graphs, which has improved work efficiency greatly.This paper has defined the program slicing in MOOL and has given the solution for the transformation from the results of MOOL program slice to actual program.Based on the compiling technology, graph theory and program slicing theory, this paper has discussed the strategies for the implementation of static program slicing technique, has presented us a whole implementation plan and has developed the slicing tool-MST, which can compute the program slicing of the MOOL language by using Perl. This implementation plan is a good try for the implementation of static program slicing system for Object-oriented language.