1. 文脈自由文法の各非終端記号Aに対して，

                              ＊
    header(A) = { α | ∃w. S ⇒ αAw (最右導出) }

ここで，Sは開始，wは終端記号列，αは文形式(終端記号と非終端記号の混ざ
った記号列)を表す．

(a) A→βBγという形の生成規則によって，

                         ＊
        αAw ⇒ αβBγw ⇒ αβBvw

    という最右導出が存在するとき，文形式と非終端記号の対の間の関係 ==> 
    を

        (α,A) ==> (αβ,B)

    と定義する．次のことを示せ．
                                      *
        α ∈ header(A)  iff  (ε,S) ==> (α,A)

             *
    ただし，==> は ==> は反射推移閉包を表す．

(b) (a)を用いてheader(A)が正則言語であることを示せ．ただし，文脈自由文
    法の終端記号も非終端記号も，正則言語の終端記号とみなす．


2. 属性文法


	Ｄ → proc id;ＮＤ;Ｓ	{ t := top(tblptr);
				  addwidth(t, top(offset));
				  pop(tblptr); pop(offset);
				  enterproc(top(tblptr), id.name, t); }

    enterproc(t1,name,t)は、記号表t1にnameという名前の手続きを登録する。
    tは手続きの記号表。

	Ｎ → ε		{ t := mktable(top(tblptr));
				  push(t,tblptr); push(0,offset) }


* レコード型 (p.581, 図8.14)

	Ｔ → record Ｌ Ｄ end	{ Ｔ.type := record(top(tblptr));
				  Ｔ.width := top(offset);
				  pop(tblptr); pop(offset) }

	Ｌ → ε		{ t := mktable(nil);
				  push(t,tblptr); push(0,offset) }



3. コード生成

4. ポインタ変数への代入文は次のようなものに限る

	p = &a;
		aが配列の場合は p = &a+c; も許される。
	p = q+c;
	p = q-c;
	p = q;
	p = null;

IN(B) = { (p,a) | ブロックBの入口で
　　　　　　　　　　　ポインタ変数pが変数aを
　　　　　　　　　　　指す可能性がある }
OUT(B) = { (p,a) | ブロックBの出口で
　　　　　　　　　　　     ポインタ変数pが変数aを
　　　　　　　　　　　     指す可能性がある }




5. 以下の最適化の手法の中から二つ選び，それぞれ5行程度で説明せよ．

 共通部分式の削除
コンパイル時に実行してしまう。
定数の畳み込み
命令をより実行頻度の低いところに移す。
命令のループの外への移動
プログラムの形を変換する。
ループの変換
式の性質を利用して実行を省略する。
冗長な命令を取り除く。
無用命令の削除・複写の削除
特殊化する。
手続き呼出しの展開・判定の置換え