言語処理工学 期末テスト 2005年 2月4日  井上克郎

教科書、ノート、その他持ち込み  なし！    

(1) 
program main(input,output);                                           
      i: integer;         
        
    procedure p(s);         
           j: integer;         
          
          function f(x);         
             k: integer;         
             begin         
               k:= x * i;         
             return(k)         
           end;         
        
       begin { of p }                   
       j:=f(s) ;                        
       if j > 5 then return;            
       else begin                       
          s:=s*3 ;                    
          p(s);                       
          end                 
       end; { of p}             
                                  
    begin{ of main}            
    i:= 2;                     
    p(i)                       
    end.                      

このプログラムの実行時、最もスタックが長くなる時の、スタックの中の各
呼出のフレーム（駆動レコード）の概略を次の要領で書け。

各フレームの持ち主の手続き／関数の名前
  およびフレーム内の
１ 実引数（［変数名：値］ の組で書く）
２ 動的リンク（ポインタの指すところを有向辺で書け）
３ 静的リンク（ポインタの指すところを有向辺で書け）
４ ローカル変数（［変数名：値］ の組で書く）

他の情報は不要。


(2) 次の3番地コードについて答よ。


1    a=1
2 LT:b=a+1
3    if a> b goto LY
4 LX:b=b+2
5    if a==b goto LX
6 LY:if a<>c goto LZ
7    a=b*2
8    goto LT
9 LZ:c=a+b


(2-1) このコード列を基本ブロックに分け（各ブロックに前からb1, b2,
... と順に番号を付けよ）、フローグラフを書け（各ブロック番号を頂点とし、
その間の辺をひく）。

(2-2) 得られたフローグラフに基づいて、支配木(dominator tree)を書け。

(2-3) 後退辺（バックエッジ）を全てあげ、それぞれに付属するループをブロッ
ク番号で示せ。

(2-4) 各ブロックのgen, kill集合を求め、IN、OUTのデータフロー方程式を立
てて、それを解け。解く過程のステップを明示せよ。


	gen	kill
b1	1	7
b2	2	4
b3	4	2
b4	-	-
b5	7	1
b6	9	-



	step1	step2	step3	step4	step5
	12479	12479	12479	12479	12479

in1	00000	00000	00000	00000	00000
out1	10000	10000	10000	10000	10000

in2	00000	10010	10010	11110	11110
out2	01000	11010	11010	11010	11010

in3	00000	01100	11110	11110	11110
out3	00100	00100	10110	10110	10110

in4	00000	01100	11110	11110	11110
out4	00000	01100	11110	11110	11110

in5	00000	00000	01100	11110	11110
out5	00010	00010	01110	01110	01110

in6	00000	00000	01100	11110	11110
out6	00001	00001	01101	11111	11111