LR法の構文解析の手順
参考
前提
こういう構文規則のparserで
code:構文規則
1. E := E + T
2. E := T
3. T := T * F
4. T := F
5. F := ( E )
6. F := id
a + b * c $という入力をparseする手順を示す
つまり[a,+,b,*,c,$]というToken列を入力に取る
準備するもの
table:構文解析表
ACTION GOTO
state id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
構文解析の手順
以下のような表を上から埋めていくとわかり易い
Reduceされたら出力ストリームに値が追加される
table:解析手順
状態 入力ストリーム 出力ストリーム スタック 表の見る箇所 次のアクション 説明用
0 a + b * c $ 0 0/id Shift 5 ①
5 + b * c $ 0 id 5 5/+ , 0/F Reduce 6 ②
3 + b * c $ 6 0 F 3 3/+, 0/T Reduce 4 ③
2 + b * c $ 6, 4 0 T 2 2/+, 0/E Reduce 2 ④
1 + b * c $ 6, 4, 2 0 E 1 1/+ Shift 6 ⑤
6 b * c $ 6, 4, 2 0 E 1 + 6 6/id Shift 5 ⑥
5 * c $ 6, 4, 2 0 E 1 + 6 id 5 5/*, 6/F Reduce 6 ⑦
3 * c $ 6, 4, 2, 6 0 E 1 + 6 F 3 3/*, 6/T Reduce 4 ⑧
9 * c $ 6, 4, 2, 6, 4 0 E 1 + 6 T 9 9/* Shift 7 ⑨
7 c $ 6, 4, 2, 6, 4 0 E 1 + 6 T 1 * 7 7/id Shift 5 ⑩
5 $ 6, 4, 2, 6, 4 0 E 1 + 6 T 1 * 7 id 5 5/$, 7/F Reduce 6 ⑪
10 $ 6, 4, 2, 6, 4, 6 0 E 1 + 6 T 1 * 7 F 10 10/$, 6/T Reduce 3 ⑫
9 $ 6, 4, 2, 6, 4, 6, 3 0 E 1 + 6 T 9 9/$, 0/E Reduce 1 ⑬
1 $ 6, 4, 2, 6, 4, 6, 3, 1 0 E 1 1/$ acc ⑭
①
初期状態
スタックが空の状態から始める
スタートはstateが0のところから表を見る
状態0であり、最初の入力ストリームの文字がaなので構文解析表の0/idを見る
これはs5なので、つまりShift 5を表す
これを「次のアクション」に書く
よって、次の行の「状態」は5になる
②
①によりs5が実行されるので
「状態」は5へ移動し
スタックには入力記号のidと状態5を積む
これはShiftが、「先頭の入力Tokenと状態をスタックにpushする」という命令のため。
構文解析表の5/+を見るとr6なのでReduceが起きる
スタックのトップの5と、次の入力にあたる+を見ている
Reduceは「スタックから記号 状態のペアを取り除き、構文規則に合致する」というものだった
6番目の構文規則F := idを適用してスタックのidをFに還元する
スタックからid 5を取り除くと、残るのは0なので、表の0/Fを見る
③
②でReduce 6が実行されたので出力ストリームに6を追加
④
③でReduce 4が実行されたので出力ストリームに4を追加
⑫
T := T * Fを適用するのでスタックから3ペアをpopする
つまりT,*,Fの3つ分をpop
0 E 1 + 6 T 1 * 7 F 10 → 0 E 1 + 6
その後、T 9をpush
T := T * Fの左辺のT
6/Tにあたる9
⑭
状態1で入力が$なので、1/$を見る
accなので成功して停止
この時点での出力ストリーム6, 4, 2, 6, 4, 6, 3, 1の規則をa + b * c $に適用すれば解析ができるということを表す