Program slicing
From Wikipedia, the free encyclopedia
In computer programming, program slicing is the computation of a program slice. The program slice consists of the parts of a program that may affect the values computed at some point of interest, referred as a slicing criterion. Program slicing can be used in debugging to locate more easily source of errors. Other applications of slicing include software maintenance, optimization, and program analysis.
Slicing techniques has been knowing a rapid development since the original definition of Mark Weiser. At first, the slicing was only static, i.e. applied on the source code with no other information than the source code. Bogdan Korel and Janusz Laski introduced dynamic slicing which works on a specific execution of the program (for a given execution trace). Other forms of slicing exist, for instance path slicing.
Contents |
[edit] Static slicing
Based on the original definition of Weiser, informally, a static program slice S consists of all statements in program P that may affect the value of variable v at some point p. The slice is defined for a slicing criterion C=(x,V), where x is a statement in program P and V is a subset of variables in P. A static slicing includes all the statements that affect variable v for a set of all possible inputs at the point of interest. Static slices are computed by finding consecutive sets of indirectly relevant statements, according to data and control dependencies.
[edit] Example
int i; int sum = 0; int product = 1; for(i = 0; i < N; ++i) { sum = sum + i; product = product *i; } write(sum); write(product);
This new program is a valid slicing of the above program with respect to the criterion (write(sum),{sum}):
int i; int sum = 0; for(i = 0; i < N; ++i) { sum = sum + i; } write(sum);
In fact, most static slicing techniques, including Weiser's own technique, will also remove the write(sum) statement. Indeed, at the statement write(sum), the value of sum is not dependent of the statement itself.
[edit] See also
[edit] References
- Mark Weiser. "Program slicing". Proceedings of the 5th International Conference on Software Engineering, pages 439–449, IEEE Computer Society Press, March 1981.
