言語処理工学A　期末テスト           2003年2月6日　井上克郎

ノート、教科書、持ち込み禁止  試験時間 

解答用紙の1ページ目(名前を書くところ）に1番の解答、2ページ目（1ページ
の裏）に２番、3ページめに3番、４ページ目に４番の解答を書くこと。
違う場所に書いたら半分に減点する。

（１） 以下の文章の空白に候補の中から適当な用語を埋めよ。

通常、手続き呼び出しが可能で、変数の［1]を持つ言語のプログラムをコンパ
イルすると、[2]と呼ばれるデータ構造をスタック上に作成するのが普通であ
る。一つの[2]は、一つの手続きや関数の[3]に対応しており、[4]な振舞が記
録される。

[2]の中には、[5],[6],局所変数、戻り値、戻り番地、退避情報、一時作業変数などが保存さ
れる。[5]を用いて手続き（関数）の本体の計算が進行する。また、[1]がネスト
する言語では、このほかに[7]が必要になる。

引数を番地渡しするばあいには、[5]として[8]が入る。また名前渡しの場合は、
引数計算をする[9]の[10]が入る。


［候補］

静的リンク、実行、スコープ、型定義、継承、宣言、動的、動的リンク、
エントリ、仮引数、サンク、駆動バッファ、リンクリスト、形式的、
ポインタ、ハッシュ、フレーム、配列、構造体、実引数、逆リンク、静的

[解答］
1 スコープ、2フレーム（または駆動バッファ）、
3実行、4動的、5実引数、6動的リンク、7静的リンク
8 ポインタ、9サンク、10ポインタ（またはエントリ）

（２）次の3番地コードプログラムを、

    １：基本ブロックに分割して上から順に番号を付け、フローグラフを書け

A:1-4, B:5-8, C:9-12, D:13, E:14-22, F:23-30

         A
	 ↓
     --→ B←-|
     |	 ↓---
     |	  C←-|
     |	 ↓---
     |	  D--------
     |	 ↓ 	 ↓
      ---E	 F

    ２：支配木(dominator tree)を作れ

       A
       |
       B
       |
       C
       |
       D
      |  |
     E    F

    ３：全てのback edgeを示し、Natural Loopを列挙せよ

    B-B または8-5 で  B
    C-C           で  C
    E-B           で  B,C,D,E

    ４：このプログラムはreducibleか否か、理由とともに答えよ

    reducible なぜなら全てのループはNatural Loop


     1	 i= m-1		16 t7=4*i
     2	 j= n		17 t8=4*j
     3	 t1=4*n		18 t9=a[t8]
     4	 v=a[t1]	19 a[t7]=t9
     5	 i=i+1		20 t10=4*j
     6	 t2=4*i		21 a[t10]=x
     7	 t3=a[t2]	22 goto 5
     8	 if tv goto 9 27 t14=a[t13]
     13	 if i>=j goto23 28 a[t12]=t14
     14	 t6=4*i		29 t15=4*n
     15	 x=a[t6]	30 a[t15]=x

（３）先ほどの3番地コードで最適化できる部分をできるだけ沢山列挙せよ。
また、それぞれその最適化の種類を書け。

略

（４）下記のプログラムに対して、

1 それぞれの行iのgen(i), kill(i)を示せ。（１行目のaの代入文はa1のよう
に示せ）
2 各in(i)とout(i)を用いてデータフロー方程式を立てよ。
3 in(1)={}としてデータフロー方程式を解いた結果の各out(i)を示せ。

1  a:=0 ;
2  if a<1 
3     then a:=a+1 ;
4  b:=3 ;

   gen	 	kill
1  1		3
2  -		-
3  3		1
4  4		-

Initilization

in(1)= -
in(2)= -
in(3)= -
in(4)= -

out(1)= 1
out(2)= -
out(3)= 3
out(4)= 4
---
Step1

in(1)= -
in(2)= 1
in(3)= -
in(4)= 3

out(1)= 1
out(2)= 1
out(3)= 3
out(4)= 3 4
----
Step2

in(1)= -
in(2)= 1
in(3)= 1
in(4)= 1 3

out(1)= 1
out(2)= 1
out(3)= 3
out(4)= 1 3 4
-----
Step3

in(1)= -
in(2)= 1
in(3)= 1
in(4)= 1 3

out(1)= 1
out(2)= 1
out(3)= 3
out(4)= 1 3 4  Same as Step 2 then termination
---------------