LR(0)構文解析を行いながら、コンパイラの構文解析を学ぶ

以下、過去の自分向けのメモの移動。

コンパイラの主要な処理に構文解析がある。 今回は与えられたLR(0)文法規則に基づいて構文解析するオートマトンを作り、構文解析の手法について整理する。

問題

次の文法について、次の問を答えよ

S -> ( L ) 
S -> a
L -> L , S
L -> S

上から順にR1,R2,R3,R4と呼ぶ。

ただし、SとLは非終端記号、(と)と,とaは終端記号とする。

• LR(0)正準集合とオートマトンを求めよ
• 以下の文字列が示された文法から生成されるかどうか、また構文解析の結果を答えよ

LR(0)構文解析の方法

LR(k)構文解析とは

• 上向き構文解析(下向きは再帰的に行うが、バックトラックが発生するため大変)
• 左(Left)から読み、右端導出(Right most derivation)
• kとは、先読みできる記号の数

LR(0)構文解析の流れ

1. LR(0)正準集合とオートマトンをつくる
2. 構文解析表を作る
3. 構文解析表を元に解析する

方針: shiftまたはreduceを繰り返し、開始記号1つにまとまれば完了

• shift: 入力を1つ読み込むこと
• reduce: 文法規則を適用し、記号をまとめること

オートマトンの状態をスタックに積みながら、行う

shiftするときは、入力を読み込み、入力記号に従い有向辺を遷移する。遷移後の状態をスタックにpushする。

reduceするときは、適用する文法規則に則って、いままでの遷移を巻き戻し(スタックを記号数分popし)、適用後の記号の遷移を積み直す(pushする)。

オートマトンを表にまとめ、情報を更かして、shift、reduceの手順を示したのが構文解析表である。

LR(0)におけるオートマトンの作成

前提

LR(0)項とは ... (アイテム記法)

文法規則の右辺、各記号の前後1箇所に・(ドット)を加えたもの。例えばS -> ( ・L )といった表記

これは、ドットの前方は読み込み済みであること、ドットの後方は未読み込みであることを示す。

(読み込むとは、ドットを1つ右に移動させること(ドットが1つ右のLR(0)項を含む状態に遷移すること(後術)であって、ドットの次が何の値であるか確認することではない)。

LR(0)正準集合とは

LR(0)項の集合である。 オートマトンを作成する際に一緒に作成する。

LR(0)におけるオートマトンとは

LR(0)正準集合を状態、記号を1つもつ有向辺としたオートマトン。

LR(0)におけるオートマトンを作成する方法

1. 初期状態を定める

状態には開始記号が左辺で、ドットが最左なLR(0)項をすべて含む。 (※)を行う。

2. その他の状態を定める

既に存在する状態のドットが最右にないLR(0)項について、記号を一つ読み込んだ状態を新たにつくる。

遷移の有向辺には、読み込む記号をもたせる。 遷移後の状態は、記号を1つ読み込んだLR(0)項(ドットを1記号分右にずらしたLR(0)項)を含む。

さらに、遷移前の状態の他のLR(0)項について考える。 同じ記号を読み込める物があれば(遷移前のLR(0)項同士でドットの右隣の記号が一致すれば)、このLR(0)項についても、1記号読み込み後のLR(0)項を遷移後の状態に加える。

(※)を行う。

3. 繰り返す

行える限り 2. を行う。

(※)

ある状態について、この状態に含むLR(0)項を考える。

ドットの右隣に非終端記号のあるLR(0)項があるならば、その終端記号を左辺に持ちドットが最左であるLR(0)項をすべて同じ状態に加える。

作成したオートマトン

状態遷移表

digraph G {
  rankdir=LR;
  empty [label = "" shape = plaintext];
  node [shape = doublecircle];I2 I4;
  node [shape = circle];
  empty -> I0 [label = "start"];
  I0 -> I1 [label = "("];
  I0 -> I2 [label = "a"];
  I1 -> I2 [label = "a"];
  I1 -> I3 [label = "L"];
  I3 -> I4 [label = ")"];
  I3 -> I5 [label = ","];
  I5 -> I7 [label = "S"];
  I1 -> I1 [label = "("];
  I5 -> I1 [label = "("];
  I5 -> I2 [label = "a"];
  I1 -> I6 [label = "S"];
} 

状態I0

• S -> ・( L )
• S -> ・a

状態I1

• S -> ( ・L ) (・の右隣に非終端記号)
• L -> ・L , S
• L -> ・S (・の右隣に非終端記号)
• S -> ・( L )
• S -> ・a

状態I2

• S -> a ・

状態I3

• S -> ( L ・)
• L -> L ・, S

状態I4

• S -> ( L ) ・

状態I5

• L -> L , ・S (・の右隣に非終端記号)
• S -> ・( L )
• S -> ・a

状態I6

• L -> S ・

状態I7

• L -> L , S ・

構文解析表

現在の状態(スタックのトップ)の行、入力記号(読み込み前)の列のセルに、次の動作を書いた表。

次の動作とは、次のようなものである。

• shiftするかreduceするか
• shiftならどの状態に遷移するか
• reduceならどの文法規則を適用するか

構文解析表のつくりかた

1. 縦軸のラベル

縦軸にLR(0)正準集合を置く

2. 横軸のラベル

横軸に記号を置く。(このとき、終端記号と非終端記号は分ける、。終端記号に$(入力の終了を表す)を加える)

3. shift

遷移元の状態を行、遷移時の終端記号を列とするセルに、skと書き込む。(状態Ikに遷移する)

shift(入力を1つ読み込む)して、スタックにkを積む(状態Ikに遷移する)ことを表す。

4. reduce時のpushする(積み直す)状態

遷移元の状態を行、遷移時の非終端記号を列とするセルに、kと書き込む。(状態Ikに遷移する)

reduce時、還元後の状態(文法規則の左辺)をスタックに積み直す動作を表す。

5. reduce時の適用する文法規則

最右がドットであるLR(0)項を含む状態の行、終端記号の列にrkと書き込む。(文法規則Rkを適用する)

6. 完了状態

左辺が開始記号で右辺のドットが最右であるLR(0)項を含む状態の行 、$(入力終了)の列のセルに、accと書き込む。

accを参照したら構文が正しいことが示され、構文解析を終了する。

構文解析表の作成結果

今回の構文解析表は次の通り

I\記号	(	)	,	a	$	S	L
0	s1			s2
1	s1			s2		6	3
2	r2	r2	r2	r2	acc
3		s4	s5
4	r1	r1	r1	r1	acc
5	s1			s2		7
6	r4	r4	r4	r4
7	r3	r3	r3	r3

余談:構文解析表が表すもの

構文解析表の持つ情報は、次の3つに分けられる

1. オートマトンの状態遷移表

I\記号	(	)	,	a	S	L
0	1			2
1	1			2	6	3
2
3		4	5
4
5	1			2		7
6
7

2. reduce可能状態と適用する文法規則

I2のとき、文法規則R2を適用する。 I4のとき、文法規則R1を適用する。 I6のとき、文法規則R4を適用する。 I3のとき、文法規則R3を適用する。

3. 完了状態

I2,I4で全て読み込み済みのとき、構文解析が完了する。

構文解析

状態を記録するスタックを用意して、スタックトップと次の入力をもとに、動作を行う。

構文解析の方法

1. 初期状態Ikであるとき、kをスタックに積む

2. スタックtopの状態の行、次の入力記号の列のセルの指示に従う

sk

shiftする。

• 入力を読み取る。(次の動作のとき入力を次の終端記号にすすめる)
• スタックにkを積む

(オートマトンにおいて、入力の終端記号を辺とする状態遷移を行う)

rk

文法規則Rkに従ってreduceする。

• 文法Rkを適用することを記録する。
• 文法Rkの右辺の記号数分、スタックをpopする。(状態遷移を巻き戻す)
• 上行のpop後のスタックトップの状態を行、文法Rkの左側の記号を列とするセルの数字をスタックにpushする。(文法Rk左側の記号の状態遷移を積み直す)

acc

構文解析は成功。入力の分は、与えられた文法規則から生成される。 構文解析を終了する。

適用すべき文法規則とその順は、記録された文法規則Rkを順に読む。

空

構文解析は失敗。入力の文は、与えられた文法規則から生成されることはない。

構文解析の結果

次の文を構文解析する。

上から順に、解析の経過を記す。

((a,a),a)

入力	スタックtop	操作	スタック	読み取り済み	還元後	文法規則	補足
			0
(	0	s1	01	(	(
(	1	s1	011	((	((
a	1	s2	0112	((a	((a
,	2	r2	0116	((a	((S	2
,	6	r4	0113	((a	((L	24
,	3	s5	01135	((a,	((L,	24
a	5	s2	011352	((a,a	((L,a	24
)	2	r2	011357	((a,a	((L,S	242
)	7	r3	0113	((a,a	((L	2423
)	3	s4	01134	((a,a)	((L)	2423
,	4	r1	016	((a,a)	(S	24231
,	6	r4	013	((a,a)	(L	242314
,	3	s5	0135	((a,a),	(L,	242314
a	5	s2	01352	((a,a),a	(L,a	242314
)	2	r2	01357	((a,a),a	(L,S	2423142
)	7	r3	013	((a,a),a	(L	24231423
)	3	s4	0134	((a,a),a)	(L)	24231423
$	4	acc	0134	((a,a),a)$	S	242314231	accのときも文法規則r1は適用する。

以上より、与えられた文は、問題の文法規則から生成されることが示された。

((a,a),(a,a))

入力	スタックtop	操作	スタック	読み取り済み	還元後	文法規則	補足
			0
(	0	s1	01	(	(
(	1	s1	011	((	((
a	1	s2	0112	((a	((a
,	2	r2	0116	((a	((S	2
,	6	r4	0113	((a	((L	24
,	3	s5	01135	((a,	((L,	24
a	5	s2	011352	((a,a	((L,a	24
)	2	r2	011357	((a,a	((L,S	242
)	7	r3	0113	((a,a	((L	2423
)	3	s4	01134	((a,a)	((L)	2423
,	4	r1	016	((a,a)	(S	24231
,	6	r4	013	((a,a)	(L	242314
,	3	s5	0135	((a,a),	(L,	242314
(	5	s1	01351	((a,a),(	(L,(	242314
a	1	s2	013512	((a,a),(a	(L,(a	242314
,	2	r2	013516	((a,a),(a	(L,(S	2423142
,	6	r4	013513	((a,a),(a	(L,(L	24231424
,	3	s5	0135135	((a,a),(a,	(L,(L,	24231424
a	5	s2	01351352	((a,a),(a,a	(L,(L,a	24231424
)	2	r2	01351357	((a,a),(a,a	(L,(L,S	242314242
)	7	r3	013516	((a,a),(a,a	(L,(S	2423142423
)	6	r4	013513	((a,a),(a,a	(L,(L	24231424234
)	3	s4	0135134	((a,a),(a,a)	(L,(L)	24231424234
)	4	r1	01357	((a,a),(a,a)	(L,S	242314242341
)	7	r3	013	((a,a),(a,a)	(L	2423142423413
)	3	s4	0134	((a,a),(a,a))	(L)	2423142423413
$	4	acc	0	((a,a),(a,a))	S	24231424234131	accのときも文法規則r1は適用する。

以上より、与えられた文は、問題の文法規則から生成されることが示された。

(a,(a,a),a)

入力	スタックtop	操作	スタック	読み取り済み	還元後	文法規則	補足
			0
(	0	s1	01	(	(
a	1	s2	012	(a	(a
,	2	r2	016	(a	(S
,	6	r4	013	(a	(L	4
,	3	s5	0135	(a,	(L,	4
(	5	s1	01351	(a,(	(L,(	4
a	1	s2	013512	(a,(a	(L,(a	4
,	2	r2	013516	(a,(a	(L,(S	42
,	6	r4	013513	(a,(a	(L,(L	424
,	3	s5	0135135	(a,(a,	(L,(L,	424
a	5	s2	01351352	(a,(a,a	(L,(L,a	424
)	2	r2	01351357	(a,(a,a	(L,(L,S	4242
)	7	r3	013513	(a,(a,a	(L,(L	42423
)	3	s4	0135134	(a,(a,a)	(L,(L)	42423
,	4	r1	01357	(a,(a,a)	(L,S	424231
,	7	r3	013	(a,(a,a)	(L	4242313
,	3	s5	0135	(a,(a,a),	(L,	4242313
a	5	s2	01352	(a,(a,a),a	(L,a	4242313
)	2	r2	01357	(a,(a,a),a	(L,S	42423132
)	7	r3	013	(a,(a,a),a	(L	424231323
)	3	s4	0134	(a,(a,a),a)	(L)	424231323
$	4	acc	0	(a,(a,a),a)	S	4242313231

(((a,a),a),a)

入力	スタックtop	操作	スタック	読み取り済み	還元後	文法規則	補足
			0
(	0	s1	01	(	(
(	1	s1	011	((	((
(	1	s1	0111	(((	(((
a	1	s2	01112	(((a	(((a
,	2	r2	01116	(((a	(((S	2
,	6	r4	01113	(((a	(((L	24
,	3	s5	011135	(((a,	(((L,	24
a	5	s2	0111352	(((a,a	(((L,a	24
)	2	r2	0111357	(((a,a	(((L,S	242
)	7	r3	01113	(((a,a	(((L	2423
)	3	s4	011134	(((a,a)	(((L)	2423
,	4	r1	0116	(((a,a)	((S	24231
,	6	r4	0113	(((a,a)	((L	242314
,	3	s5	01135	(((a,a),	((L,	242314
a	5	s2	011352	(((a,a),a	((L,a	242314
)	2	r2	011357	(((a,a),a	((L,S	2423142
)	7	r3	0113	(((a,a),a	((L	24231423
)	3	s4	01134	(((a,a),a)	((L)	24231423
,	4	r1	013	(((a,a),a)	(L	242314231
,	3	s5	0135	(((a,a),a),	(L,	242314231
a	5	s2	01352	(((a,a),a),a	(L,a	242314231
)	2	r2	01357	(((a,a),a),a	(L,S	2423142312
)	7	r3	013	(((a,a),a),a	(L	24231423123
)	3	s4	0134	(((a,a),a),a)	(L)	24231423123
$	4	acc	0	(((a,a),a),a)	S	242314231231

以上より、与えられた文は、問題の文法規則から生成されることが示された。