程序分析技术第六讲一种信息流分析技术

程序分析技术,第六讲：一种信息流分析技术,一、处理的语言,S-skip|V:=e|Ifethenselses|Ifethens|s;s|Whileedos选择的原因：结果定理,e1,S1,S2,S3,S4,e2,二、基本方法,结构图,S3,S4,e1,S1,S2,e1,S1,基本定义定义：设S为一个语句，若在S中有V:=e,一则称S定义了v。用Ds表示S定义的所有变量之集。设S为一个语句，从G(S)入口到G(S)出口存在一条路，且在该路上无对变量x的赋值，则称S保护了x。用Ps表示S保护的所有变量之集。,定义：变量与表达式的关系若变量v在G(S)入口处值，直接或间接参与了表达式e的计算，则说v和e具有关系，记为vSe或者(v,e)S。定义：表达式与变量的关系若表达式e直接或间接参加变量v在G(S)出口处值的计算，则称e和v具有关系，记为eSv或者(e,v)S。,定义：变量与变量的关系S=SS(v,v)|vPS解释，v1Sv2，v在G(S)的入口值参与v2在G(S2)出口值的计算。v1Sv2，v1在G(S)的入口值可？G(S)的出口,3.计算方法空语句S：skip;Ds=,ps=Vs=,s=ps=(v,v)|vps赋值语句S：v:=e;DS=v,PS=V-vS=(v,e)|vV(e),S=(e,v)S=(v,v)|vuse(e)(v,v)|vPS,顺序语句S：A;BDS=DADB,PS=PAPBS=AAB,S=ABBS=AB条件语句S：ifethenAelseBDS=DADB,PS=PAPBS=(v,e)|vuse(e)ABS=AB(e,v)|v(DADB)S=AB(v,v)|vuse(e)，vDADB),简单条件语句s：ifethenAelse部分为skip可用上述规则计算。循环语句S：whileedoADS=DA,PS=VS=A*(v,e)|vuse(e)A)S=(e,v)|vDAA)A*S=公式计算,三、应用,1.看某一输入变量对那些输出变量有影响设vVi，v”Vo，若(v，v”)成立，则v对v”有影响。影响集（v，v”）v”Vo，(v，v”),2.看那些输入变量对某些输出变量的影响给定vv”，v|(v，v”)vv”被影响集对v”有影响,3.无用的输入变量若输入变量影响的输出变量集为空，则该输入变量对程序的运行结果无影响。4.无效语句v:=e，(e,v)|vVo=，则该语句可用skip替换或含有错误。,5.对循环语句的分析设有whileedoA，定义一个G(S),点集为DA，边集为A,定义：稳定变量在G(S),中，如果任一环路上的变量都没有列该变量的路，则称该变量是关于S稳定的例：whileedoX:=y+1;Y:=z+1;Z:=k+1;K:=m+1.,k,x,y,z,若循环体为x:=y+1;y:=z+1;z:=k+1;k:=m+1定义：稳定变量的稳定长度设v是关于S稳定的，终止于v的最长路径长度称为v的稳定长度，记为(v)。,x,y,z,k,例whileedox:=y+z;y:=z+1;z:=k+1;(x)=2定义：稳定表达式设e是循环语句s中的一个表达式，若use(e)中的变量都是稳定的，则称e是稳定的。,x,y,z,定义：稳定表达式e的稳定长度设e是关于s稳定的，其稳定长度用(e)表示。定义如下：(e)=max(v)|vuse(e)+1。,结论：任意一个稳定变量，当循环的次数到达一个定值（稳定长度+1）时，其值不会改变。任意一个稳定表达式，当循环的次数到达一个定值（稳定长度+1）时，