文法規則を考えるときと、解析過程を考えるときにごっちゃになるやつ
文法規則を考えるとき
こういう入力を受理する規則を考えたい
( i1 + i2 ) * i3
最終目標は以下の規則を作成すること
code:bnf
E -> E + E
E -> E * E
E -> (E)
E -> i
最終目標の規則を全く知らない状態でどうやって考えていくか
入力から理想のASTは容易に想像できるので、いったんそれを作ってから考える #?? 解析過程を考えるとき
こういう規則があるとする
code:bnf
E -> E + E ①
E -> E * E ②
E -> (E) ③
E -> i ④
そしてこういう入力があるとする
( i1 + i2 ) * i3
この入力を、規則に基づいて解析することを考える
①の左辺のEであることを仮定して解析を始め、
それぞれの非終端記号に対応する関数を呼び出し、最終的に必要な終端記号になっているかを認識する 入力文字列の頭から一文字ずつ読んでいけばいい
最終的に①のEになっているかを認識する
これをやるためには入力記号列が全てわかっている状態から始める必要がある
なのであまり現実的なものではない
つまり④→①の順に見ていくってことかmrsekut.icon
このとき、以下のような手順に考える
解析するときは一文字ずつ読み込んでいく
規則は矢印の反対方向に見ていくことになる
受理するかどうかの判定？
ASTの作成？
実際の動作
table:動作
スタック 残り入力 動作
1 $ (i1+i2)*i3$ シフト
2 $( i1+i2)*i3$ シフト
3 $(i1 +i2)*i3$ E->i
4 $(E +i2)*i3$ シフト
5 $(E+ i2)*i3$ シフト
6 $(E+i2 )*i3$ E->i
7 $(E+E )*i3$ E->E+E
8 $(E )*i3$ シフト
9 $(E) *i3$ E->(E)
10 $E *i3$ シフト
11 $E* i3$ シフト
12 $E*i3 $ E->i
13 $E*E $ E->E*E
14 $E $ 受理
この表の作り方は解析に使う構文解析器の種類によって異なる
参考
後で見つけたがコレも同じだな
詳しい
このノートで知りたいことがだいたい書いてあった