-------------------------------------------------------------------
解答
-------------------------------------------------------------------

   言語処理工学A 中間テスト           2002年12月12日 井上克郎

ノート、教科書、持ち込み禁止  試験時間 10:30-11:40

解答用紙の1ページ目(名前を書くところ)に1番の解答、2ページ目(1ページ
の裏)から3ページめにに2番の解答を書くこと。
違う場所に書いたら半分に減点する。


(1) 今、演習で作成しようとしているパスカルサブセットのコンパイラの作成、
実行過程をT図式で書くことにする。以下のような名前を使う。
	パスカルサブセット		PAS
	Scanner				PAS --> TOK
					    X86
	Scannerが出力するトークン列	TOK
	コンパイラの出力CASL		CAS
	C言語				C
	X86機械語			X86

	GCC Cコンパイラ			C --> X86
					  X86

        CASLコンパイラ(実際は		  CAS --> X86
	インタプリタだが簡単のため             X86
	コンパイルして実行するとする)

1. 課題で作るX86上で動く目的のコンパイラ(実行形式)をT図式で表せ。

	TOK  -->  CASL
	     X86

2. 実際には、上記の目的のコンパイラは、C言語で開発し、X86上でコンパイルして
    1. を得ている。このコンパイルの様子をT図式で表せ。

       TOK  -->  CASL    TOK --> CASL
	    C     C  --> X86 X86
                     X86
3. あるPASで書かれたプログラムPがX86のプログラムにX86上で変換される過
    程をT図式で書け。

       P               P               P               P
      PAS PAS --> TOK TOK TOK --> CAS CAL CAS --> X86 X86
              X86             X86             X86

(2)次の拡張文法GのLR構文解析表を求めよ(途中のfollow集合、正準LR(0)集
成、LR(0)オートマトンをそれぞれ書くこと。)
また、 ( i ) の構文解析の過程を示せ。

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


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

正準LR(0)集成

S0
	E'-> .E
	E -> .E + T
        E -> .T
        T -> .( E )
	T -> .i

S1 = S0/E
	E'-> E.
	E -> E. + T

S2=S0/T
        E -> T.

S3 = S0/( = S3/( = S5/C
	E -> (.E )	
	E -> .E + T
        E -> .T
        T -> .( E )
	T -> .i

S4 = S0/i
	T -> i.

S5 = S1/+ = S6/+
 	E -> E +.T
        T -> .( E )
	T -> .i

S6 = S3/E
        E -> ( E.)
	E -> E.+ T

S7 = S5/T
	E  -> E + T.

S8 = S6/)
	T  -> ( E ).

LR(0)オートマトン

State	E	T	+	(	)	i	$
0       1       2               3               4           
1                       5                                         
2                                                                 
3       6       2               3               4                    
4                                                                 
5               7               3               4                    
6                       5              8                            
7                                                                 
8                                                                 
                                                                 

LR(0)構文解析表

State	E	T	+	(	)	i	$
0       1       2               S3             S4           
1                       S5                             Accept     
2                       R2             R2              R2        
3       6       2               S3             S4                    
4                       R4             R4              R4         
5               7               S3             S4                    
6                       S5             S8                           
7                       R1             R1              R1         
8                       R3             R3              R3         

構文解析過程

0	(i)$		S3
0(3	 i)$		S4
0(3i4	  )$		R4
0(3T2	  )$		R2
0(3E6	  )$		S8
0(3E6)8	   $		R3
0T2	   $		R2
0E1	   $		Accept