コンパイラ構成論試験 1993.2.4 (萩谷)


1. 次のような文法を考える。Eが開始記号である。

	E → T
	E → E + T
	T → x
	T → x ( E )

(a) FOLLOW(E)とFOLLOW(T)を求めよ。$を忘れてはならない。(10点)

(b) I0を次のLR(0)項の集合(正準LR(0)集)とする。

	E'→ .E
	E → .T
	E → .E + T
	T → .x
	T → .x ( E )

次の遷移表が成り立つようにI1-I8を定めよ。(20点)

		I0	I1	I3	I4	I5	I7

	E	I1				I7
	T	I2			I6	I2
	x	I3			I3	I3
	+		I4				I4
	(			I5
	)						I8

(c) 上の文法がSLR(1)であることを説明せよ。(10点)


2. 次のような式を考える。

	(x1+x2)*(x3-(x4+x5))

(a) 上の式に対応するdagを書け。(10点)

(b) (a)で求めたdag上に必要なレジスタ数を見積もるラベルを付けよ。(10点)


3. 次の流れ方程式を解くアルゴリズムを簡単に述べよ。(20点)

	in[B] =  ∪               out[P]
	       PはBの先行ブロック

	out[B] = gen[B] ∪ (in[B] - kill[B])


4. 次の語句について簡単に説明せよ。(20点)

(a) ディスプレイ

(b) 後埋め法

(c) 強さの軽減

(d) induction variable(誘導変数)