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

Constructing Dependence Graph for EFSM

作　　者：韩喆[1] 陈世鸿[1] 

机构地区：[1]武汉大学计算机学院,湖北武汉430074

出　　处：《小型微型计算机系统》2011年第4期577-583,共7页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术研究发展计划项目(2003AA00103)资助

摘　　要：将切片技术引入扩展有限状态机模型,可根据兴趣点约减状态及变迁数,对模型的分析与测试有重要意义.由于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.

关 键 词：程序切片 扩展有限状态机 依赖图 变迁 

分 类 号：TP182[自动化与计算机技术—控制理论与控制工程]