言語処理系論（萩谷） 2001.9.20

問題に誤りや不備を見つけた場合は，その旨を解答に書いておいて下さい．

1. 次の文法において，終端記号は id と ( と ) である．EとTは非終端記号
   である．開始記号はEである．

      E → id
      T → id
      E → (E)
      E → (T)E

(1) この文法がLALR(1)でないことを示せ．(10)

(2) C言語やJavaは，

      (型)式

   という形のキャスト演算子を含んでいる．上の文法のTを型，Eを式と考え
   ると，(1)の事実は，キャスト演算子があると文法がLALR(1)でなくなるこ
   とを意味している．キャスト演算子があったとしても文法がLALR(1)になる
   ような方策を考えよ．(10)

2. ブロック構造を実装する方法として，ディスプレイを用いる方法と，静的
   リンクを用いる方法がある．両方法について簡単に解説せよ．(15)

3. 次のように，コード生成のためのパターンとコストが与えられているとする．

           パターン             コスト

      (1)  (= (+ C R) R)          5
      (2)  (= R (* R))            6
      (3)  C                      1
      (4)  (* C)                  3
      (5)  (* (+ C R))            5
      (6)  (+ C R)                1
      (7)  (+ (* (+ C R)) R)      6
      (8)  (+ R R)                1
           ...                    ..

   ただし，Cは定数，Rはレジスタを表すとする．また，木構造は
   Lisp(Scheme)のリストで表現している．

   例えば，

      (= (+ a b) (* (+ c d)))

   という木構造は，

          (= (+ a R) R)               (1)
                  |  |
                  a  |                (3)
                     |
                     (* (+ c R)       (5)
                             |
                             d        (3)

   という四つのパターンによってタイリングすることができ，このコストは，
   5+1+5+1=12である．

   木構造が与えられたとき，ダイナミックプログラミングによって最小コス
   トのタイリングを求めるアルゴリズムを述べよ．Schemeのプログラムを書
   いてもよい．(15)

4. 以下は，条件の翻訳においてバックパッチを行う構文主導定義である．
   ただし，

      emit(... ...)は，... ...を中間コードの命令として出力する．
      nextquadは，中間コードの次の命令のアドレスを表す．
      makelist(q)は，qを唯一の要素とするリストを返す．
      backpatch(list,q)は，listに属するgoto文に行き先qを後埋めする．
      merge(list1,list2)は，二つのリストlist1とlist2をマージしたリストを返す．
      id.nameは，x，y，z，b などの変数の文字列を表す．
      relop.nameも，< や > などの演算子の文字列を表す．

   とする．

	Ｓ → id		{ emit(id.name);
				  Ｓ.nextlist := nil }

	Ｅ → id1 relop id2	{ Ｅ.truelist := makelist(nextquad);
				  Ｅ.falselist := makelist(nextquad+1);
				  emit('if'  id1.name  relop.name  id2.name
				       'goto_');
				  emit('goto_') }

	Ｓ → while Ｍ1 Ｅ do Ｍ2 Ｓ1
				{ backpatch(Ｓ1.nextlist, Ｍ1.quad);
				  backpatch(Ｅ.truelist, Ｍ2.quad);
				  Ｓ.nextlist := Ｅ.falselist;
				  emit('goto_' Ｍ1.quad) }

	Ｍ → ε		{ Ｍ.quad := nextquad }

	Ｓ → if Ｅ then Ｍ1 Ｓ1 Ｎ else Ｍ2 Ｓ2
				{ backpatch(Ｅ.truelist, Ｍ1.quad);
				  backpatch(Ｅ.falselist, Ｍ2.quad);
				  Ｓ.nextlist :=
				  merge(Ｓ1.nextlist,
					merge(Ｎ.nextlist, Ｓ2.nextlist)) }

	Ｎ → ε		{ Ｎ.nextlist := makelist(nextquad);
				  emit('goto_') }
	Ｓ → begin Ｌ end	{ Ｓ.nextlist := Ｌ.nextlist }

	Ｌ → Ｌ1; Ｍ Ｓ	{ ... }

	Ｌ → Ｓ		{ ... }

(1) ... の部分（二箇所）を補え．(10)

(2) 以下のプログラムを翻訳した結果を書け．(10)

      while x > y do begin
        while y < z do a;
        if u = v then b else c
      end

5. 流れグラフにおいて，基本ブロックBが基本ブロックB'を支配するとは，開
   始ブロックからB'に至る任意の経路上に必ずBが現れることを意味する．

(1) ループ不変式に関する最適化を行うために，流れグラフの中のループが持
    っているべき条件を，上の支配の概念を使って述べよ．(5)

(2) D(B)を，基本ブロックBを支配する基本ブロックの集合とする．D(B)を，B
    の先行ブロックPに対するD(P)を用いて表現せよ．(10)

(3) D(B)を求める反復アルゴリズムを定式化せよ．開始ブロックはB0とする．(15)

1.

      E' → E     $
      E → id     $
      T → id     $
      E → (E)    $
      E → (T)E   $

      E' → .E    $
      E → .id    $
      E → .(E)   $
      E → .(T)E  $

      E → (.E)   $
      E → (.T)E  $
      E → .id    )
      E → .(E)   )
      E → .(T)E  )
      T → .id    )

      E → id.    )
      T → id.    )

4.
      while x > y do begin
        while y < z do a;
        if u = v then b else c
      end


     L0
         if x > y goto L1
         goto L7
     L1
         if y < z goto L2
         goto L3
     L2
         a
         goto L1
     L3
         if u = v goto L4
         goto L5
     L4
         b
         goto L0
     L5
         c
     L6
         goto L0
     L7