资源描述：
《补充二 信息流分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、补充二数据流分析技术复习1、什么是元程序–程序的程序元程序的组成及元程序的作用。2、预处理:掌握三种中间表示3、掌握4种文法规则：结构规则；选择规则；表规则；词法规则。4、能用规则表示其程序源码。要点了解什么是数据流分析技术理解对数据流的十种定义找出下列程序的错误voidf1(int*p1,intp2,intp3){*p1=p3-p2;}main(){inta,x,y;printf("Typeinavaluefora");scanf("%d",&a);printf("");y=0;if(x!=0){f1(&y,a,x);}printf("Ais%d",a);}数据流分析技术数据流
2、分析技术是对源程序分析、获取程序中变量定值和传播的情况，帮助理解程序中的数据流动情况。数据流分析的用途编译优化、程序维护程序安全性的检查数据流分析所得结论同程序运行时的情况一致需要定义机器模型和操作语义，证明所得结论对操作语义可靠数据流分析收集的信息同基本块和控制流有关，通常和变量值无关数据流分析的最基本点：掌握赋值操作改变哪些变量的值。（1）如果没有引用变量，直接读取变量赋值（2）如果有引用变量，则很难静态分析什么变量被赋值。数据流方程定义定义一、基本块是一个顺序执行的命令序列。进入一个基本块，必须从第一条命令进入，退出基本块，必须由最后一条命令退出。特点：后续执行情况可判断。例1:x
3、=x+1;y=y+1;z=z+1;定义二、程序图是一个有向图，它的结点为基本块，有一个入口结点（无前驱结点）和一个出口结点（无后续结点）扩展：常用的程序图有三种表示（流程图N-S图PAD图）定义三、定值在基本块当中对变量x的赋值，若有d:x:=e(e代表一个表达式),则称有对x的定值，d:为x的定值点。(注：d:为程序中引入的标识，对程序无影响）定义四、注销若有对变量x的赋值x:=…,则程序注销了x的原定值。用kill[B]表示B中被注销的所有变量之集。定义五、向下暴露的定值设（Bi,di）为x的一个定值，若从di+1到Bi的出口再无对x的定值，则称x的di的定值为向下暴露的定值，并用d
4、ef[Bi]表示Bi中的所有向下暴露定值的变量之集。定义六、可能到达的定值说在（Bi,di）点x定值可能到达（Bj,dj）点，若从（Bi,di）存在一条路，且在该路上无x的定值。用符号in[Bi]和out[Bi]分别表示可能到达Bi块入口处和出口处的所有变量定值的集合可到达的定值数据流方程in[B*]={}，B*为入口块。；out[B]=def[B]∪(in(B)-kill(B))in[B]=∪(out[Bi])i=1,2,…n；Bi为B的前驱结点其中in[B]表示在B入口处有定值的变量之集out[B]表示定值可到达B出口处的变量定值之集实例：找出每个块中的可能到达的定值集合定义七、定义
5、性出现，使用性出现称第一次出现在赋值命令左部的变量出现（即x:=…第一次出现）为变量（x）的定义性出现，而称其他部位中的变量出现为其使用性出现定义八、向上暴露的使用在(Bi,di’)有x的使用性出现，若从Bi的入口到di’-1点无对x的赋值。则称x在(Bi,di’)点的出现为向上暴露的使用，用use_live[B]表示B中所有向上暴露的使用定义九、变量的活跃性说变量x在（Bi,di’）点活跃，若：1.存在一点（Bj,dj’）有x的使用性出现。且2.从（Bi,di’)到（Bj,dj’)存在一条通路，且在该路上无对x的定值。定义十、注销活跃性若在某一点（Bk,dk)有X:=E，则称注销X的活
6、跃性思考，如何求各个基本块入口处和出口处上活跃变量集？显然，在Bi块的入口处活跃的一定在前驱出口处活跃。（1）Bi块的局部向上暴露使用的变量（2）Bi块出口处活跃且不被Bi块所注销的变量活跃变量的数据流方程表示方法in_live[B]=use_live[B]∪(out_live[B]-kill_live[B])out_live[B]=∪in_live[Bi]Bi为B的后续out_live[B*]={}B*为出口块其中in_live[B]={在B入口处活跃的所有变量的集合}out_live[B]={在B出口处活跃的所有变量的集合}use_live[B]={Bi中所有局部向上暴露使用的变量集
7、合}kill_live[B]={x
8、B注销其活跃性的变量集合}。如果含有过程，该如何表达和分析数据流？定义十一、过程调用块把过程调用P(e1,…en)定义为一个独立的基本块，称为过程调用块。定义十二、过程的返回块调用块的接续为返回块（或return的后续块）难点：下标变量的分析别名问题数据流分析技术应用数据流分析的基础把各种数据流模式作为一个整体来抽象地研究，然后可以形式地回答数据流算法的下列几个基本问题：在什么情况下数据流分析中使
