LR法の構文解析の手順
参考
前提
こういう構文規則のparserで
構文規則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列を入力に取る
準備するもの
構文解析表 | 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されたら出力ストリームに値が追加される
解析手順| 状態 | 入力ストリーム | 出力ストリーム | スタック | 表の見る箇所 | 次のアクション | 説明用 |
| 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 $ に適用すれば解析ができるということを表す