！！！！解答！！！！

			言語処理工学Ａ 中間テスト
						       １１／２５／９９

教科書、ノートほか持ち込み可

（１）Javaプログラムは、通常Javacと呼ばれるコンパイラで、バイトコード
BCと呼ばれる中間言語に変換された後、JavaVM (Java Virtual Machine)と呼
ぶインタプリタで解釈実行される。Javac自身はBCで書かれている。

いま、あるJavaで書かれた目的プログラムPが、ある計算機X上でコンパイルさ
れて実行されるまでの様子をＴ図形で書け。ただし、Xで稼働するJavaVMは、
「Xの機械語XMで記述された、BCを入力として、Xの機械語XMを出力とするコン
パイラ」として表すこと。

      P				  P			P
      |				  |			|
    Java : Java   ---  BC   :	  BC  :	  BC  ---   XM: XM
		   |			       |
		   BC :	BC  --- XM	       XM
                             |
			    XM


（２）文法G4(p.69)を、図4.10(p.75)の順位表を利用して、(n+i)*n を構文解
析する過程を図4.8で示すような表であらわせ（右文形式、非終端記号を除い
た記号列、ハンドルの組を各還元ごとに書くこと）


$(n+i)*n$	$<<(<>+<>)>>*<>$	n
$(E+i)*n$	$<<(<<+<>)>>*<>$		i
$(E+E)*n$	$<<(<<+>)>>*<>$		E＋E
$(E)*n$		$<<(==)>>*<>$		(E)
$E*n$		$<<*<>$			n
$E*E$		$<<*>>$				E*E
$E$		$$				受理


（３）次の文法Gにたいして、Follow集合、正準LR(0)集成、LR(0)オートマト
ン、構文解析表を求めよ。

文法G
	(0) E'-> E
	(1) E -> E + T
	(2) E -> T
	(3) T -> i

また、i+i の構文解析の過程を図4.12(P.79)のように示せ。

Follow(E') ={$}
Follow(E) = {$,+}
Follow(T) = {$,+}

I0	E' -> .E
	E  -> .E + T
	E  -> .T
	T  -> .i

I1	E'  -> E.
	E   -> E. + T

I2	E  -> T.

I3	T  -> i.

I4	E  -> E + .T
	T  -> .i

I5	E  -> E + T.


st	E	T	i	+	
0	1	2	3	
1				4
2
3
4		5	3
5	


         action			  goto
st	i	+	$	E	T	
0	s3			1	2
1		s4	受理
2		r2	r2
3		r3	r3
4	s3				5	
5		r1	r1


stack		input		action
				initialize
0		i+i$
				shift3
0i3		 +i$
				reduce3,2 
0T2		 +i$
				reduce2,1
0E1		 +i$
				shift4
OE1+4		  i$
				shift3	
0E1+4i3		   $
				reduce3,5
0E1+4T5		   $
				reduce1,1
0E1		   $
				accepted