LR法の構文解析表
ACTION表とGOTO表から構成される
以下の2つより構成される
ACTION表
各マスには構文解析動作関数が書かれているのでそれを実行する
構文解析動作関数
(記号, state) -> Actionの定義
空白のところへ遷移したら何かが間違っている
Actionは以下よりなる
$ s_i
Shiftして状態$ iをスタックにpush
$ r_j
番号$ jの生成規則でReduceする
acc: 受理
終了記号$をShiftする動作
構文解析を成功の状態で終了する
空白は誤り
空白にたどり着いた場合はエラーになる
GOTO表
その非終端記号を解釈し終えたときに次に遷移すべき状態を示す
これらはなに？項目？動作？
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
構文解析表の作成手順
例として以下の規則からなる文法の構文解析表を作ることを考える
code:bnf
L -> A ∨ L | A
A -> N ∧ A | N
N -> ¬N | (L) | p
code:bnf
L' -> L
L -> A ∨ L | A
A -> N ∧ A | N
N -> ¬N | (L) | p
分解する
code:bnf
0: L' -> L
1: L -> A ∨ L
2: L -> A
3: A -> N ∧ A
4: A -> N
5: N -> ¬N
6: N -> (L)
7: N -> p
Reduce時に使うので各規則に番号を振っている
各文法の規則すべてに対する閉包関数closureを作成する