プログラムの依存関係解析に基づく
デバッグ支援システムの試作
佐藤 慎一 y

小林 孝則 y飯田 元 z

井上 克郎 y

鳥居 宏次 zy大阪大学 基礎工学部 情報工学科
奈良先端科学技術大学院大学 情報科学研究科〒５６０ 大阪府豊中市待兼山町 1-3
大阪大学 基礎工学部 情報工学科 知能情報処理学講座
Tel:06-850-6571(内線 6571)
z

E-mail:s-sato@ics.es.osaka-u.ac.jp

ソフトウェアが大規模化，複雑化するにつれ，プログラム中のバグ位置を特定するのが容易ではなくなっている．本研究では，プログラムの依存関係解析に基づいて，スライス抽出や部分解釈を行ない , プログラム全体からバグに関係のある部分のみを抽出し，それを対象にデバッグを行なえるようなシステムの試作を行なった．本シス
テムは，もとのプログラムからスライスを抽出したり，部分解釈に基づいたプログラムの簡単化を行なう. また，得られた部分プログラムを実行させたり，特定の変数に直接影響を及ぼす文や変数を参照したりしながらデバッグを行なうことができる. 本システムを用いれば，バグ位置の特定を比較的効率良く行なうことができるため，結果としてソフトウェアの開発効率が上がると考えられる．
依存関係解析, プログラム依存グラフ, スライス, 部分解釈, デバッグ

1

Debug support system based on program
dependence analysis
Shinichi SatoyyTakanori Kobayashiyz

Ha jimu Iida

Katsuro Inouey

Ko ji Toriiz

Department of Information and Computer Sciences,
Faculty of Engineering Science,Osaka UniversityzNara Institute of Science and Technology

1-3 Machikaneyama, Toyonaka, Osaka 560, Japan
Tel:06-850-6571(6571)
E-mail:s-sato@ics.es.osaka-u.ac.jp
Debugging large and complex software is not easy task since localizing and identi ng faults are very di cult. We
have depeloped a debug system which extracts program slices and partially evaluates program texts based on program
dependence analysis. Using this system, we can extract parts of the program which would relates to bugs, and also
we can execute and trace the extracted parts. Therefore we consider e orts of debugging would be reduced, and itseÆciency will be improved.
program dependence analysis, program dependence graph(PDG), program slice, partial interpretation, debugging

1

1

まえがき
通常プログラムをデバッグする際には，対象となるプログラム全体を扱う．従って，プログラム

本稿では，これ以降，2 章でプログラムの依存
関係解析の概要を，3 章で作成したシステムの概要を, 4 章でシステムの実行例を, 5 章で考察を述べる．

が大きくなるとデバッグ時にはエラーの原因の特定だけで時間がかかってしまい，このことがプロ
グラム開発の効率を悪化させている．
このような場合に，エラーに関係があると思われる部分だけをプログラムから抽出するような機能があれば，開発者はプログラムの一部分だけに注目してエラーの位置の特定ができ, 開発効率の向上が期待される．
本研究では，スライスや部分解釈を用いて，プ
ログラム全体から注目する文や変数に関係のある部分だけを抽出し，その部分のみに対して処理を行なうようなデバッグ支援システムの試作を行なった．スライスとは，プログラム中のある文 s でのある変数の値に影響を与える文の集合，もしくはs での変数の定義が影響を与える文の集合である．
スライスを用いることにより，ある出力変数に関係のある文のみをプログラムから抽出することができる. また，部分解釈では，プログラムに対する入力変数の値をある値に固定することにより, プ
ログラムサイズの縮小を目的として, プログラムの変換を行なう.
これまで，いくつかのスライスを利用したデバッ
グ支援ツールが発表されている [2, 5]. しかし，これらはいずれもプログラムの実行系列を解析して2プログラムの依存関係解析
本論文で述べるデバッグ支援システムは，プログラムの依存関係解析の結果得られるプログラム
依存グラフ (Program Dependence Graph, 略してPDG) から, スライシングや部分解釈を行なうこと
によってプログラムの参照範囲を縮小することによりデバッグの支援を行なう．
2.1

プログラム依存グラフ（PDG）

PDG はプログラム内の文の依存関係を表すグラフである．PDG の節点はプログラム中の各文及びif 文や while 文の条件判定部分を表し，辺は変数の影響を伝えるデータ依存 (Data Dependence, 略して DD) 関係及び条件文や繰り返し文の制御の影響を伝える制御依存 (Control Dependence，略してCD) 関係を表す．
DD は，各頂点の到達定義集合 (Reaching De nitions, 略して RD) を求めることによって得られる．PDG 上でのある頂点 t の RD とは，変数 v と頂点 s との組 hv; si の集合である．これは，得られるスライス (動的スライス) に基づくもので，

 プログラム中の文 s で変数 v を定義している．

実行させるたびにスライスを計算しなければなら プログラム中の二つの文 s と t の間に v を必ず定義するような文がない．

ない上，実行系列を保存しておく必要があるために解析結果が膨大な量になる．
本研究では，動的スライスではなく，プログラことを示している．t の RD に hv; si が含まれ，かムの依存関係を解析し，それに基づいて求められ

つ t が v を参照する時，s から t への DD 関係があるスライス (静的スライス) を利用することにより，るという．

抽出したスライスを一つのプログラムとして扱っ

また，ある条件判定部分 s の結果により文 t の実てデバッグを行なうことができる. また，静的ス

行の有無が決定される時，s と t との間に CD が存

ライスを利用することにより, デバッグだけでな在するものとする．すなわち CD は if 文や while 文

くソフトウェアの部品化や保守などにも役立つとの条件判定部分からそれらの内部ブロックに属す考えられる．

る文への影響であり，これはプログラムを解析す

さらに，部分解釈を用いることにより，スライれば容易に求められる．

スを求めにくいようなプログラムに対しても対象

一般にプログラムには複数の手続きが定義されプログラムのサイズを縮小し，デバッグや保守をている．各手続き間には引数や大域変数を通じて効率良く行なえるようになる．

DD 関係が生じる. これらの DD 関係を表すため

に，PDG にプログラム中の文とは直接対応しない
節点 (中継節点と呼ぶ) を用意する．

nm-para-in

n-para-inm

PDG の作成は，プログラムを解析し，プログラ
ムの各文を PDG の節点に切りわけ，プログラム
中の各文における RD を求め，それをもとにしてPDG の各辺を生成することによって行なわれる．
詳細は，[7, 8] を参照されたい．

nb-para-in

if m<n thenma-para-in

n

n
m

a

temp:=abswap(m,n)nwhile n<>0 do
m

y

n
a:=b

x

temp

w:=m mod nnma例として 図 1 のプログラムに対応する PDG を

nm:=nb:=temp

w

b

n

n

図 2 に示す．図の PDG の中で角の丸い四角がプ

n:=wb-para-outma-para-out

ログラム中の各文に対応する節点で，楕円が中継m

gcd:=mgcd

m節点である．また，有向辺のうち，実線で名前がついているものが DD 関係の辺で，破線のものがCD 関係の辺である．実線についている名前は，その DD 関係の辺が影響を伝える変数の名前である．
また，破線で囲まれている部分はプログラム上の

gcd-exit
writeln(’Input x and y’)
a-para-in

gcd

b-para-in

readln(x,y)
x
b

a

gcd

b

c:=gcd(a,b)

一つの手続きを表す．

writeln(’x=’,x,’ y=’,y)

x

y

a

y

y

x

g:=gcd(x,y)

cxylcm:=(a div c)*(b div c)*cg

l:=lcm(x,y)
lcm

lcm

1

program euclid(input,output);2

var x,y,g,l:integer;3function gcd(m,n:integer):integer;forward;

4

procedure swap(var a,b:integer);

5

var

6

begin

7

temp:=a;
a:=b;

9

11

function lcm(a,b:integer):integer;var

13

c:integer;

begin

14

c:=gcd(a,b);

15

lcm:=(a div c)*(b div c)*c

17

end;
function gcd;

18

var

19

begin

20

w:integer;

if m ＜ n then begin

21

swap(m,n);

22

end;

23

while n ＜＞ 0 do begin24

w:=m mod n;

25

m:=n;

26

n:=w;

27
28

end;
gcd:=m;

29

end;

30

begin

31

writeln('Input x and y');32

readln(x,y);33

writeln('x=',x,' y=',y);34

g:=gcd(x,y);35

l:=lcm(x,y);36

writeln('gcd=',g);37

writeln('lcm=',l);38

writeln(’gcd=’,g)

図 2: PDG の例

b:=temp;
end;

12

16

writeln(’lcm=’,l)temp:integer;

8

10

l
lcm-exit

end.

2.2

スライス

スライスは，前節で述べた PDG を探索することにより得られる．PDG を与えられた頂点から辺の順方向に探索していくものを forward slice と呼び，逆方向に探索していくものを backward sliceを呼ぶ．
スライスの例として， 図 1 のプログラムのうち，36 行目の変数 g に関する backward slice が 図 1 の下線部分である．g に影響を及ぼさない部分 , すな
わち関数 lcm に関する部分はスライスに含まれて
いない.
2.3

部分解釈

本稿で述べる部分解釈とは，プログラムに対す
る入力変数の取る値を固定したときにプログラム
中の一部の文で参照される式や変数の値を静的に

図 1: PDG の元のプログラム決定できるときには, その値をそれらに代入し，その結果不要な文や手続きが現れた場合にはそれらを削除することである．

(

入力変数の固定によるプログラム P の部分解釈

3

vx
i

の手順を次に示す．

1. P の大域変数の中から固定の対象とする入力
変数 x (複数個でも良い) を選ぶ.
2. 目的とする機能を選び出すのに応じて x の値
(特定の固定値 a) を定め, 変数とその値の組
hx; ai を作る．その他の大域変数と局所変数
y については不定値 ? との組 hy; ?i を作る．
（これらの組の集合をプログラム状態と呼ぶ.）

3. 主プログラムの本体（複合文）M および 2．

= vxi のとき
vx 6= vx のとき
i
i
1

vx

?;

1

2

i

2

この定義の意味は変数 xi が両方のプログラム状
態 State1 と State2 で同じ値を持つならば新しいプ
ログラム状態 State3 においてその値が保存され, そうでなければその値は ? となるということである．
上記の手順でプログラムが部分解釈されると, 元のプログラムにあった手続きの呼び出しや, 変数の定義, 参照がなくなることが起こり得る．その結果, それらの手続きや変数自体が不要となり，さらに文が削除できる場合がある．
手続きが不要となる場合は，その手続きが一度(M; M State) を呼び, その返り値を出力する.

も呼び出されない場合である．そのような場合に4. 呼び出しが削除されなかった各手続きについて, その手続きが呼び出された時のプログラム
状態を集めたプログラム状態集合 FiAllState
中のすべてのプログラム状態を演算 Æ を使って併合して, その手続きの初期プログラム状
態 FiState を作成する.

は, その手続き自体を削除できる.
次に, 変数が不要となるのは次の 2 つの場合である．

 参照する文がない.
 自分自身の再定義にしか参照されない.
したがって, この場合は以下のような手順で不5. 呼び出しが削除されなかった各手続きについて, 手続きの本体（複合文）Fi およびその手続きの初期プログラム状態 Fi State を引数として関数手続き simple (Fi ; Fi State) を呼び,その返り値を出力する.
ここで，simple (S; State) は与えられたプログ
ラム状態 State を利用して文 S を部分解釈した文
0

1

vx ;
i

のプログラム状態 M State を引数として関数
simpleS=を返す．simple は関数 exec とともに定義され要な代入文と入力文を削除することができる.

1. 前述の簡素化結果のプログラムを PDG に変換する.
2. その PDG の頂点のうち代入文もしくは, 入力
文の頂点を調べてそこから到達できる頂点が存在しない場合, その代入文もしくは, 入力文は削除する.

る．exec (S; State) は与えられたプログラム状態

このような手続きおよび変数が不要となる場合

で文 S を部分計算した結果の新しいプログに不要な手続き宣言と不要な文の削除を行なった

ラム状態を表す．simple; exec の詳細は本稿の最結果, 新たに手続きの呼び出し，変数の定義や参後に添付した付録で述べる．

照がなくなることが起こる場合があるので, そのState

また, プログラム状態の併合を行なう演算 Æ は,

場合はその結果のプログラムに対して, 上に述べ以下のように定義される．いま，2 つのプログラム

たような文の削除ができないか確認する必要があ

状態 State1 と State2 が与えられており，る. よって, 上に述べたような文の削除は新たに削State1= fhx ; vx1 i; . . . ; hxn; vxn ig

State2= fhx ; vx1 i; . . . ; hxn; vxn ig

1

1

1

1

2

2

であるとする．これらに演算 Æ を適用した時の結果は次のようになる．
State1

除する文がなくなるまで繰り返しておこなう.
部分解釈の例として， 図 3 のプログラムの入力
変数のうち，変数 b を'n' に，変数 c を'y' に固定して部分解釈を行なった結果のプログラムを 図 4に示す．
入力変数 b を'n' に固定した結果，入力文が削除

Æ State2 = fhx1 ; vx1 i; . . . ; hxn; vxn ig
33

され，また，その値が'y' のときに実行されるはずであった 27 行目から 38 行目の部分が削除されている．また，入力変数 c を'y' に固定した結果，program wordcount(in,out);
var a,b,c:char;in:array[0..1000] of char;

24 行目の if 節が削除されている．

i:integer;
letter,word,line:integer;
isinword:boolean;1
2

program wordcount(in,out);

begin

var a,b,c:char;writeln('Count the letter?(y/n)');3

in:array[0..1000] of char;

4

i:integer;5

letter,word,line:integer;

6

isinword:boolean;

readln(a);writeln('Count the word?(y/n)');writeln('Count the line?(y/n)');
i:=0;

7

letter:=0;89line:=0;
begin

while in[i]10writeln('Count the letter?(y/n)');11

readln(a);12writeln('Count the word?(y/n)');13

readln(b);14writeln('Count the line?(y/n)');15

readln(c);16i := 0;17

letter := 0;18word := 0;19line := 0;20

isinword := false;21

while in[i]2224line:=line+1;
i:=i+1end;
if a='y' thenend.

if in[i] = EOL thenif (in[i] ＜ ＞' ')and(in[i] ＜ ＞ EOL) then

28

begin

30

if isinword = false then

31

begin

32

isinword := true;

33

word := word +1

34

end

35

end

36

else

37

isinword := false;
i := i +1

39

end;

40

if a = 'y' then42

writeln('letter =',letter);
if b = 'y' then43

writeln('word44

if c = 'y' then45
46

writeln('line=',word);=',line)end.

図 3: 部分解釈前のプログラム3

図 4: 部分解釈後のプログラム

line := line + 1;
if b = 'y' then29

41

writeln('line =',line)

if c = 'y' then26

38

writeln('letter =',letter);＜＞ EOF do beginletter := letter + 1;

25
27

letter:=letter+1;
if in[i]=EOLN thenif a = 'y' then23＜＞ EOF do begin

if a='y' then

システムの概要
本章では，本研究で試作したデバッグ支援シス

テムの概要について述べる．

扱う．

 手続きは再帰呼び出しも扱う．ただし，部分
解釈ではこれは扱えない．また，手続きの引数の渡し方については，値渡しと変数渡しの二種類を許す．
 変数のデータ型はスカラー型のみでポインタ型は扱わない．具体的には整数型，文字型，論理型およびそれらを要素に持つ配列型とした．
このように，簡単化されてはいるものの, プログ
ラミング言語の基本的な文の構造はすべて含んでいるので，拡張は容易に行なうことができる．
3.2

システム構成本システムの構成図を 図 5 に示す．本システム
は，おおまかには，ソースコードの構文解析を行
ないつつプログラム中の各文を PDG の各節点と対応づけるパーザ部，その結果に基づいて PDG を作

3.1

言語仕様

本システムが対象とする言語は，以下のような仕様を持つ Pascal のサブセットである．

 文として, 代入文，条件文, 繰り返し文，手続き呼出文, begin{end で囲まれる複合文を成するアナライザ部，PDG を探索してスライスを得るスライサ部，PDG を利用してプログラムの部
分解釈を行なう部分解釈部，プログラムの実行を行なうインタープリタ部に分けられる．
ユーザがコード化が終了したプログラムを入力
すると，システムは, アナライザ部でそれを解析

また，部分解釈部やスライサ部から出力された
簡素化プログラムをインタープリタ部で実行する

アナライザ部

プログラム

ことができる．この場合にも上述のようなデバッ
PDG

グ作業を行なうことができる．このようにして，デ構文木、変数情報

バッグの対象を限定することにより，効率良くデバッグ作業を進めることができる．
部分解釈部

スライサ部

インタープリタ部

スライス起点情報

入力制限情報4

実行例
本システムの実行例として， 図 6 に示される

スライス結果部分解釈結果

実行結果

バグを含むプログラムをデバッグする例を考える．
このプログラムは，入力された５つの数字の合計，

図 5: システムの構成図
する．解析が終了すると，PDG および実行に必要な構文木や変数の情報などが生成される．
ユーザはこの段階でシステムにどの動作をさせるかを指定する．ユーザがプログラムを実行させた場合には，システムは, インタープリタ部にアナライザ部が生成した構文木や変数の情報などを渡して，プログラムを実行させる．その際，通常

最大，最小, 平均を計算し，出力するプログラム
である.

1. プログラムを解析し，インタープリタ部で実行させる．この実行結果が 図 7 である．これを見ると，明らかに, 最大値を示す MAX の値が誤っている．

2. この値を出力した変数 ( 図 6 における 32 行目の変数 Max) に関する backward slice を抽出する．このとき， 図 8 のようなウィンドウが現の実行だけでなく，ステップ実行やブレークポイ

れる．この画面で，スライスを抽出したい変ントの設定，変数値の参照などのデバッグに必要

数名や CD および DD のどちらの依存関係にな作業も行なうことができる．

ついて PDG を探索するか，PDG をどのレベ

また，実行させた結果誤った出力が得られた場

ルまで探索するかなどの情報を入力する. こ合，ユーザはプログラム全体を対象とするのでは

こでは，変数名 Max とし, CD，DD の両方のなく，その出力に関係のある部分のみをプログラ

依存関係について PDG をできる限り探索すムから抽出し，その抽出部分をデバッグの対象とることにする．こうして得られるスライス結することができる．

果は 図 9 中の網掛け部分として参照される．

部分解釈で入力変数を固定する場合には，シス
テムは, PDG および構文木などの情報を部分解釈部に渡す．また，ユーザはどの入力変数をどの値に固定するのかといった情報を入力する．それらをもとにして部分解釈部で部分解釈が行なわれ，その結果, プログラムの一部の機能のみを実現するプログラムが生成される．
スライスを抽出する場合には，スライサ部に，PDG やどの変数に関するスライスを抽出するのかといったユーザからの入力が渡され，スライスが3. 32 行目の Max に直接定義を行なっている文は，
14 行目の文である．これはスライスを計算する際に, レベルの設定を 1 などの適当な値に設定することにより得られる．

4. この文にブレークポイントを設定し，スライ
ス部分のみを実行させる．すると，この文自体は何度も実行されているにも関わらず，Maxの値が変化していないことがわかる．これは，この文で参照される変数が A[1] となっている

計算される．そのスライス結果は，元のプログラ

ためで，それを A[i] に修正することにより正ムの部分プログラムとして，スライサ部から出力しい結果が得られる．

される．

1
2

program coverage(input,output);varSum, Max, Min, Mean: integer;3

A: array[1..5] of integer;4n: integer;

5
6

procedure calc(var sum, max, min, mean: integer);

7

var

8

begin

i: integer;

図 8: スライス選択画面

9i := 1 + 1;

10

while i ＜= n do

11

begin

12

sum := sum + A[i];13

if A[i] ＞ max then14max := A[1]else if A[i] ＜ min then15
16

min := A[i];17i := i + 1

18

end;

19

mean := sum div n;

20

end;

21
22

begin

23

n := 5;24

writeln('Please Input ',n,' values');25

readln(A[1],A[2],A[3],A[4],A[5]);26

Sum := A[1];27

Max := A[1];28

Min := A[1];29

Mean := A[1];30calc(Sum, Max, Min, Mean);31

writeln('SUM

32writeln('MAX: ', Max);33

writeln('MIN: ', Min);34
35

writeln('MEAN: ', Sum);: ', Mean)end.

図 6: バグを含んだプログラム

図 9: スライス結果際に使用されている手続き型言語 (C,Pascal など)にも適用させること, また，このような対話的な
図 7: 実行結果

5

プログラムの依存関係解析システムに適した, イ
ンクリメンタルに解析を行なえるような解析アル
ゴリズムの適用などが挙げられる．

まとめ
プログラムから依存関係にもとづいてバグに関係のある部分のみを抽出するデバッグ支援システ
ムを作成した．本システムを用いることにより，プ
ログラム全体を対象としていた従来のデバッガを用いるよりも効率の良いデバッグを行なえることが期待される．また，プログラムの一部の機能を実現する部分のみを抽出できることから，ソフト
ウェアの部品化などの保守作業にも役立つと考えられる．
今後の課題としては，実際にシステムを使用してその評価を行うことや，対象言語を拡張し，実

参考文献[1] Aho, A.V., Sethi,
S. and Ullman,
J.D.:\Compilers : Principles, Techniques, andTools", Addison-Weseley, 1986.
[2] Agrawal, H., Demillo, R.A. and Spa ord,
E.H.:\Debugging with Dynamic Slicing and
Backtracking", Software{Practice and Experience, Vol.23(6), pp. 589{616(1993).
[3] Horwitz, S. and Reps, T.:\The Use of Program Dependence Graphs in Software Engineering", Proceedings of the 14th International
Conference on Software Engineering, pp. 392{
411(1992).

[4] 小林 孝則:\入出力変数の制限情報を利用したプロ
グラム簡素化ツールの試作" , 大阪大学基礎工学部
情報工学科特別研究報告 (1995{03).
[5] Shimomura, T.:\Bug Localization Based on
Error{Cause{Chasing Methods", Transactionsof information Processing Society of Japan, Vol.
34, No. 3, pp. 489{500(1993).
[6] 高谷 暢之:\入出力の制限情報を利用したプログラ
ム簡素化手法の提案", 大阪大学大学院基礎工学研
究科修士学位論文 (1994{02).
[7] 植田 良一，練 林，井上 克郎，鳥居 宏次:\再帰を含むプログラムの依存関係解析とそれに基づくプ
ログラムスライシング"，信学技報，SS93{24, pp.

33{40(1993{09).
[8] 植田 良一:\再帰を含むプログラムのスライスを求めるアルゴリズムの提案", 大阪大学大学院基礎工学研究科修士学位論文 (1994{02).
[9] Weiser, M.: \Program Slicing", Proceedings ofthe Fifth International Conference on Software
Engineering, pp. 439{449(1981).

付録：simple および exec 関数(1) 空文: exec(; State) = State
simple(; State) = 

ただし,State =

x ; vx1 i; . . . ; hxn ; vxn ig   eval (expr (x1 ; . . . ; xn ); State) が定数値 n を返すとき

( n1
fh

vxi =
0

?



それ以外のときここで関数 eval (expr; State) は与えられたプログ
ラム状態 State で与えられた式 expr を評価した式を示す．結果は State で値が決まる変数をすべてその値で置き換えた式である．また，置き換えによって式が計算できるようになった場合はその値を返す．

(5) 分岐文: if expr then S1 else S2

exec (if expr then S1 else S2 ; State)
8 exec (S ; State)1>>   eval (expr; State) = true のとき>< exec (S2 ; State)=   eval (expr; State) = false

のとき
>
>
exec
(
S
exec
(
S
1 ; State)
2 ; State)>:
それ以外のときÆ

simple (if expr then S1 else S2 ; State)
8 simple (S1 ; State)>>   eval (expr; State) = true のとき>>
simple(S2 ; State)><   eval (expr; State) = false のとき=
if eval (expr; State) then>> simple (S1 ; State)

>
else
>
>
(S2 ; State): simpleそれ以外のとき(2) 複合文: (S1 ; S2 ;    ; Sn )exec((S1 ; S2 ;    ; Sn ); State)= exec((S2;    ; Sn ); exec(S1 ; State))
simple((S1 ; S2 ;    ; Sn ); State)= simple (S1 ; State) ;simple ((S2 ;    ; Sn ); exec (S1 ; State))

exec(input(xi ); State)= fhx1 ; vx1 i; . . . ; hxi ; vxi i; . . . ; hxn ; vxn ig
0exec(output(xi ); State) = State
simple(input(xi ); State) = input(xi )simple(output(xi ); State) = output(xi )vxn ig; vxi は0

exec(xi := expr(x1 ; . . . ; xn ); State)= fhx1 ; vx1 i; . . . ; hxi ; vxi i; . . . ; hxn ; vxn ig
simple(xi := expr(x1 ; . . . ; xn ); State)= xi := eval(expr(x1 ; . . . ; xn ); State)0

exec (while expr do S end; State)
8 exec (while expr do S end; exec (S; State))><   eval (expr; State) = true のとき=Stateeval (expr; State) = false のとき>: State    それ以外のとき
0(3) 入出力文: input(xi), output(xi)ただし，State = fhx1 ; vx1 i; . . . ; hxn ;Input{Var 中の xi の値である.
(4) 代入文: xi := expr (x1 ; . . . ; xn )(6) 繰り返し文: while expr do S end

simple (while expr do S end; State)8   eval (expr; State) = false のとき
>
>
while
eval
State) do>< simple ((expr;
S;
State
)
=
end
0

>
>
>
:



それ以外のとき

ただし，State = fhx1 ; vx1 i; . . . ; hxn ; vxn ig とすると，State = fhx1 ; vx1 i; . . . ; hxn ; vxn ig
0

(
vxi =

?

0

vxi

0

0

xi が S 中で定義される可能性があるときそれ以外のとき