4.2 信息流分析技术及部分求值技术介绍
信息流分析技术在程序优化,程序静态分析,程序测试等许多方面都有重要的应用.应用领域的不同,分析数据的属性也不同.我们的方法是通过对程序中变量值的获取与传播的分析,着重描述变量与表达式,表达式与变量,变量与变量之间的关系.
我们所研究的语言SOOL基本是从C++化简而来,这种面向对象式语言与函数式语言和逻辑式语言有很大的区别.其中,重要区别之一是:SOOL程序中变量的值是随着程序的执行而动态变化的.这使我们不能采用其它类语言的部分求值技术.
基于面向对象语言自身的特点,我们对面向对象语言求值,我们必须知道一个语句是否应被执行和一个表达式是否可计算.下面,我们给出部分求值技术的描述:
首先,我们引入状态STA和环境ENV: STA:V→{k,u} ENV:V→VAL
STA是变量到状态的映射,k表示变量已知,u表示变量值未知(初始状态所有变量为u);ENV是变量到其值的映射.
我们引入一个表达式求值函数:
M: EXP*STA*ENV→(EXP+VAL)*(k,u)
具体定义如下:
M(E,s,env)=(n,k) 若E=n,且n为常数或E=V,且s(v)=k, env(v)=n ;
(v,u) 若E=V,且s(v)=u;
M'(op,(x1,w1),(x2,w2)) 若E=E1 op E2,且M(Ei,s,env)=(xi,wi), i=1,2.
M'(op,(x1,w1),(x2,w2))= (n,k) 若w1=w2=k, 且x1 op x2=n;
(x1 op x2,u) 若w1=u或w2=u.
语句求值函数定义如下:
TRANS: Stm*STA*ENV→Stm*STA*ENV
在下面的语句求值函数中,(x/y)表示用x代替y 的值.语句求值函数具体定义如下:
(1)TRANS(skip,s,env) = (skip,s,env);
(2)TRANS(read(x1,x2,…,xn,y1,y2,…,ym),s,env)
= (read(y1,y2,…,ym),s(k/xi),env(val(xi)/xi))
其中xi为部分输入,val(xi)为xi的输入值.i=1,2,…,n;
(3)TRANS(v:=E,s,env)
= (v:=E',s[u/v],env) 若M(E,s,env)=(E',u)
= (skip,s[k/v],env[n/v]) 若M(E,s,env)=(n,k)
(4)TRANS(S1;S2,s,env)=(S1';S2'',s'',env'')
其中TRANS(S1,s,env)=(S1',s',env')
TRANS(S2,s',env')=(S2'',s'',env'');
(5)TRANS(IF E THEN S1 ELSE S2,s,env)
= TRANS(S1,s,env) 若M(E,s,env)=(true,k)
TRANS(S2,s,env) 若M(E,s,env)=(false,k)
(IF E' THEN S1';S1'' ELSE S2';S2'',s,env')
若M(E,s,env)=(E',u)
其中TRANS(S1,s,env)=(S1',s'',env'')
TRANS(S2,s,env)=(S2',s''',env''')
S1''=(v1:=n1;…;vm:=nm) (1≤i≤m)
若vi∈Ds1∧env''(vi)=ni∧((s''(vi)=k∧s'''(vi)=u)∨
(s''(vi)=s'''(vi)=k∧env''(vi)env'''(vi)))
S2''=(v1:=n1;…;vm:=nm) (1≤i≤m)
若vi∈Ds2∧env'''(vi)=ni∧((s'''(vi)=k∧s''(vi)=u)∨
(s''(vi)=s'''(vi)=k∧env''(vi)env'''(vi)))
其中Ds表示S定义的所有变量之集.
s'(v)= k 若 s''(v)=s'''(v)=k
u 若 s''(v)=u 或 s'''(v)=u
env'(v)= n 若 s'(v)=k∧n=env''(v)
若 s'(v)=u;
(6)循环语句的求值函数定义如下:
我们把循环语句视为:(WHILE E DO A,N)
其中,N=max(as(v)|v∈DA)+1,as(v)是变量v的稳定长度.
(a)若M(E,s,env)=(false,k) 则
TRANS((WHILE E DO A,N),s,env)=(skip,s,env)
(b)若M(E,s,env)=(true,k) 且n≥0,则
TRANS((WHILE E DO A,s,env)=
TRANS(A,(WHILE E DO A,N-1),s,env)
TRANS((WHILE E DO A,0),s,env)=
(WHILE E DO A,s,env)
(c)若M(E,s,env)=(E',u),则
TRANS((WHILE E DO A,N),s,env)=
TRANS'(IF E THEN (A;WHILE E DO A)
ELSE SKIP; ,s,env)
其中,函数TRANS'为一个新函数,它的定义与函数TRANS基本相同,其不同之处在于赋值语句与循环语句的处理.
TRANS'(V:=E,s,env)=(v:=E',s[u/v],env)
其中M(E,s,env)=(E',k/u)
TRANS'(WHILE E DO A,s,env)=(WHILE E DO A',s',env')
其中TRANS(A,s,env)=(A',s',env')
信息流分析技术通过对变量值的获取与传播的分析,分析输入变量和输出变量之间的关系,变量值的获取及变量值的传播.本文使用信息流分析技术和部分求值技术主要是用于寻找输入变量与判定表达式变量之间的关系以及程序中常量赋值的影响.
文章来源于领测软件测试网 https://www.ltesting.net/
