-------------------------------------------------------------------
解答
-------------------------------------------------------------------
言語処理工学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