Beyond traditional program slicing

ABSTRACT

Traditional program slices are based on variables and statements. Slices consist of statements that potentially affect (or are affected by) the value of a particular variable at a given statement. Two assumptions are implicit in this definition: 1) that variables and statements are concepts of the programming language in which the program is written, and 2) that slices consist solely of statements.Generalised slicing is an extension of traditional slicing where variables are replaced by arbitrary named program entities and statements by arbitrary program constructs. A model of generalised slicing is presented that allows the essence of any slicing tool to be reduced to a node marking process operating on a program syntax tree. Slicing tools can thus be implemented in a straight-forward way using tree-based techniques such as attribute grammars.A variety of useful program decompositions are shown to be instances of generalised slicing including: call graph generation, interface extraction, slicing of object-oriented inheritance hierarchies and slices based on type dependences. Examples are also given of how slicing can enhance understanding of formal compiler specifications and aid the creation of subset language specifications.

REFERENCES

• 1: Hiralal Agrawal , Richard A. Demillo , Eugene H. Spafford, Debugging with dynamic slicing and backtracking, Software—Practice & Experience, v.23 n.6, p.589-616, June 1993 [doi>10.1002/spe.4380230603]
• 2: Hiralal Agrawal, On slicing programs with jump statements, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.302-312, June 20-24, 1994, Orlando, Florida, United States
• 3: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, ACM SIGPLAN Notices, v.25 n.6, p.246-256, Jun. 1990
• 4: Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers. Addison-Wesley, 1986.
• 5: L. Badger and M. Weiser. Minimizing communication for synchronizing parallel datafiow programs. In Proc. of the 1988 International Conference on Parallel Processing, University Park, PA, August 1988. Pennsylvania State University Press.
• 6: Thomas Ball , Susan Horwitz, Slicing Programs with Arbitrary Control-flow, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.206-222, May 03-05, 1993
• 7: . Binkley. Using semantic differencing to reduce the cost of regression testing. In Proc. IEEE Conference on Software Maintenance, pages 41-50, Washington, D.C., November 1992. IEEE Computer Society.
• 8: David Binkley, Precise executable interprocedural slices, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.31-45, March–Dec. 1993 [doi>10.1145/176454.176473]
• 9: Jong-Deok Choi , Jeanne Ferrante, Static slicing in the presence of goto statements, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1097-1113, July 1994 [doi>10.1145/183432.183438]
• 10: Pierre Deransart , Martin Jourdan , Bernard Lorho, Attribute grammars: definitions, systems and bibliography, Springer-Verlag New York, Inc., New York, NY, 1988
• 11: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 12: Keith Brian Gallagher , James R. Lyle, Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering, v.17 n.8, p.751-761, August 1991 [doi>10.1109/32.83912]
• 13: Robert W. Gray , Steven P. Levi , Vincent P. Heuring , Anthony M. Sloane , William M. Waite, Eli: a complete, flexible compiler construction system, Communications of the ACM, v.35 n.2, p.121-130, Feb. 1992 [doi>10.1145/129630.129637]
• 14: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 15: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 16: Daniel Jackson , Eugene J. Rollins, A new model of program dependences for reverse engineering, ACM SIGSOFT Software Engineering Notes, v.19 n.5, p.2-10, Dec. 1994
• 17: S. C. Johnson. YACC - Yet another compiler-compiler. Computer Science Tech. Rep. 32, Bell Telephone Laboratories, Murray Hill, N.J., 1975.
• 18: U. Kastens , W. M. Waite, Modularity and reusability in attribute grammars, Acta Informatica, v.31 n.7, p.601-627, Oct. 1994 [doi>10.1007/BF01177548]
• 19: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3]
• 20: Hareton K. N. Leung , Hassan K. Reghbati, Comments on program slicing, IEEE Transactions on Software Engineering, v.13 n.12, p.1370-1371, December 1, 1987 [doi>10.1109/TSE.1987.233147]
• 21: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 22: Linda M. Ott , Jeffrey J. Thuss, The relationship between slices and module cohesion, Proceedings of the 11th international conference on Software engineering, p.198-204, May 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74587.74614]
• 23: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• 24: Frank Tip, A Survey of Program Slicing Techniques., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994
• 25: William M. Waite , Lief H. Carter , Lynn R. Carter, An Introduction to Compiler Construction, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 26: Mark Weiser, Programmers use slices when debugging, Communications of the ACM, v.25 n.7, p.446-452, July 1982 [doi>10.1145/358557.358577]
• 27: Mark Weiser. Reconstructing sequential behavior from parallel behavior projections. Information Processing Letters, 17:129-135, October 1983.
• 28: Mark Weiser. Program slicing. IEEE Trans. on Software Engineering, SE- 10(4):352-357, July 1984.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

General Terms:
Algorithms, Design, Languages