苏小红，龚丹丹，王甜甜，马培军

(哈尔滨工业大学计算机科学与技术学院，150001哈尔滨)

程序切片技术是一种重要的程序分析和理解技术，广泛应用于程序调试、测试及软件维护中［1-2］.其原理和方法最早出现在文献［3］中，文献［3］根据数据流方程的迭代解对程序切片进行了定义，并提出了基于控制流图(control flow graph，CFG)的计算过程内程序切片的算法，但此方法所消耗的时间和空间均比较多，计算所得的程序切片准确性也不是很好.文献［4］引入了基于程序依赖图(program dependence graph，PDG)的图形可达性算法，用于计算过程内切片，但此算法只能计算一个过程内的切片问题，含有多个过程的程序切片计算问题并未得到解决.文献［5］通过把PDG扩展为系统依赖图(system dependence graph，SDG)，以计算过程间切片，根据系统依赖图，将函数间的切片问题转化为图的可达性问题［6］，从而解决了包含多个过程程序的切片计算问题.

目前，计算程序静态切片主要使用的方法是基于依赖图的遍历算法［7］.系统依赖图能够充分表示程序的数据依赖、控制依赖信息以及函数调用信息，但是SDG数据流分析的复杂度较高，而且生成系统依赖图的过程中，需要计算与切片无关的数据依赖，这些不必要的计算造成了时间和空间资源的浪费，并严重影响了切片计算的效率.类似地，传统的动态切片算法使用动态依赖图，复杂性也很高，针对该方法，文献［8］提出利用D/U表达式计算动态切片的方法，不需要使用动态依赖图，可以同时计算程序的……