扩展有限状态机的依赖图构造及切片算法

Constructing Dependence Graph for EFSM

将切片技术引入扩展有限状态机模型,可根据兴趣点约减状态及变迁数,对模型的分析与测试有重要意义.由于EFSM模型基于变迁的依赖关系,传统的依赖图构造算法及基于标记已访问节点的切片算法并不适用.通过研究EFSM模型依赖关系的可传递性,提出EFSM模型的两级结构依赖图EPDG(EFSM Program Dependence G raph),使用变迁及其子节点分别表示控制依赖及数据依赖,将EFSM模型的切片转化为图形可达性问题,并给出EPDG的构造算法及切片算法,运用实例与已有成果做对比实验.

The slicing technology of Extended Finite State Machine model can reduce the number of states and transition. It is very important for analysis and test on EFSM model. The existent algorithm for constructing dependence graph or slicing can not be used in constructing dependence graph for EFSM model because of its special dependence relationship. In this paper, we do the research on the transmissibility of the special dependence relationship of the EFSM. Base on the research we propose the two-tier structure dependence graph called EPDG （ EFSM Program Dependence Graph ）. We use the child nodes of the transition to represent data dependence relationship and the transition nodes to represent control dependence relationship. Through it we turn the slicing on EFSM up to a graphic accessibility issues and we give the construction algorithm for EPDG, also the slicing algorithm. At last we use a example to do the compare experiment.