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')
信息流分析技術通過對變量值的獲取與傳播的分析,分析輸入變量和輸出變量之間的關系,變量值的獲取及變量值的傳播.本文使用信息流分析技術和部分求值技術主要是用于尋找輸入變量與判定表達式變量之間的關系以及程序中常量賦值的影響.
文章來源于領測軟件測試網 http://www.kjueaiud.com/
