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

程序分析技术第六讲：一种信息流分析技术一、处理的语言S-skip|V:=e|Ifethenselses|Ifethens|s;s|Whileedos选择的原因：结果定理e1S1S2S3S4e2二、基本方法1.结构图S3S4e1S1S2e1S12.基本定义定义：设S为一个语句，若在S中有V:=e,一则称S定义了v。用Ds表示S定义的所有变量之集。设S为一个语句，从G(S)入口到G(S)出口存在一条路，且在该路上无对变量x的赋值，则称S保护了x。用Ps表示S保护的所有变量之集。定义：变量与表达式的关系若变量v在G(S)入口处值，直接或间接参与了表达式e的计算，则说v和e具有关系，记为vSe或者(v,e)S。定义：表达式与变量的关系若表达式e直接或间接参加变量v在G(S)出口处值的计算，则称e和v具有关系，记为eSv或者(e,v)S。定义：变量与变量的关系S=SS{(v,v)|vPS}解释，v1Sv2，v在G(S)的入口值参与v2在G(S2)出口值的计算。v1Sv2，v1在G(S)的入口值可？G(S)的出口3.计算方法空语句S：skip;Ds=,ps=Vs=,s=ps={(v,v)|vps}赋值语句S：v:=e;DS={v},PS=V-{v}S={(v,e)|vV(e)},S={(e,v)}S={(v,v)|vuse(e)}{(v,v)|vPS}顺序语句S：A;BDS=DADB,PS=PAPBS=AAB,S=ABBS=AB条件语句S：ifethenAelseBDS=DADB,PS=PAPBS={(v,e)|vuse(e)}ABS=AB{(e,v)|v(DADB)}S=AB{(v’,v)|vuse(e)，vDADB)}简单条件语句s：ifethenAelse部分为skip可用上述规则计算。循环语句S：whileedoADS=DA,PS=VS=A*({(v,e)|vuse(e)}A)S=({(e,v)|vDA}A)A*S=公式计算三、应用1.看某一输入变量对那些输出变量有影响设v’Vi，v”Vo，若(v’，v”)成立，则v’对v”有影响。影响集{（v’，v”）v”Vo，(v’，v”)}2.看那些输入变量对某些输出变量的影响给定v’v”，{v’|(v’，v”)v’v”}被影响集对v”有影响3.无用的输入变量若输入变量影响的输出变量集为空，则该输入变量对程序的运行结果无影响。4.无效语句v:=e，{(e,v)|vVo}=，则该语句可用skip替换或含有错误。5.对循环语句的分析设有whileedoA，定义一个G’(S),点集为DA，边集为A定义：稳定变量在G’(S),中，如果任一环路上的变量都没有列该变量的路，则称该变量是关于S稳定的例：whileedoX:=y+1;Y:=z+1;Z:=k+1;K:=m+1.kxyz若循环体为x:=y+1;y:=z+1;z:=k+1;k:=m+1定义：稳定变量的稳定长度设v是关于S稳定的，终止于v的最长路径长度称为v的稳定长度，记为(v)。xyzk例whileedox:=y+z;y:=z+1;z:=k+1;(x)=2定义：稳定表达式设e是循环语句s中的一个表达式，若use(e)中的变量都是稳定的，则称e是稳定的。xyz定义：稳定表达式e的稳定长度设e是关于s稳定的，其稳定长度用(e)表示。定义如下：(e)=max(｛(v)|v∊use(e)｝)+1。结论：任意一个稳定变量，当循环的次数到达一个定值（稳定长度+1）时，其值不会改变。任意一个稳定表达式，当循环的次数到达一个定值（稳定长度+1）时，其值不会改变。若whileedoA中的e是稳定的，很有可能出错（陷入死循环）。应用：可根据上述分析结果，进行应用。例如：部分求值的程序例化（循环展开）