前回のあらすじ
Error Recoveryについてまとめました。もう少し詳しくError Recoveryを説明したほうがいいと思ったので、今回は前回の内容を具体例を用いながら解説します。
最初にLR parserの仕組みについて説明し、その後Error Recoveryの仕組みについて説明します。
LR parserの仕組み
用語の解説
LR parserの仕組みの説明に入る前に、これから使う用語について簡単に説明します。
- 終端記号: Lexerが生み出す記号のことです。例えばRubyでは
keyword_class
("class"
)という記号はLexerが生み出します。トークンと呼ぶこともあります。 - 非終端記号: Lexerが生み出さない記号です。かわりに生成規則によって定義されます。例えば
primary
という非終端記号はprimary: k_class cpath superclass bodystmt k_end
というように定義されます。なおprimary
の定義はこれ一つだけではありません。一つの非終端記号が複数の定義をもつことがあります。 - 生成規則:
primary: k_class cpath superclass bodystmt k_end
のように記号(列)同士の関係を定義したものです。左辺が右辺を生成すると読むこともありますし、右辺が左辺へと還元されると読むこともあります。今回取り上げる例では常に左辺には非終端記号が1つだけ置かれています。
LR parserはプッシュダウン・オートマトン
プッシュダウン・オートマトン - Wikipedia の説明にあるようにプッシュダウン・オートマトン(Pushdown Automaton)とはスタックをもった有限オートマトンです。有限オートマトンとの違いとして
- "現在の状態"、"次の入力値"、"スタックのトップ"の3つの情報をもとに次の状態を決定することができます。有限オートマトンは"現在の状態"、"次の入力値"から次の状態を決定するので、そこに"スタックのトップ"が追加されています
- 次の状態に遷移するときスタックを操作することができます。スタックの操作なのでPushとPopの操作が可能です
LR parserをプッシュダウン・オートマトンとして実装したときの"状態"、"スタック"、"遷移"についてそれぞれ説明をします。
LR parserの状態
入力値はLexerの生成する(次の)トークンなのでいいとして、LR parserにおける状態とはなんなのでしょうか。それはLR項の集合です。LR項は生成規則と•
という記号から作られます。ざっくりというと•
はその位置にいるということを表しています。
たとえばRubyでif
式は以下のような生成規則で定義されています。
primary: k_if expr_value then compstmt if_tail k_end
ここから以下のようなLR項が作られます。同じ生成規則であっても、いる場所が違えば異なる状態になるというわけです1。
• k_if expr_value then compstmt if_tail k_end # ifの直前にいる k_if • expr_value then compstmt if_tail k_end # ifの直後にいる k_if expr_value • then compstmt if_tail k_end # thenの直前にいる k_if expr_value then • compstmt if_tail k_end # thenの直後にいる k_if expr_value then compstmt • if_tail k_end # 例えばelseの直前にいる k_if expr_value then compstmt if_tail • k_end # endの直前にいる k_if expr_value then compstmt if_tail k_end • # endの直後にいる
LR parserのスタック
LR parserのスタックにはLR parserの状態が積まれます2。
LR parserの遷移
LR parserの遷移は4種類に分類できます。
1) Shift
入力を一つ進め、新しい状態に遷移します。そして新しい状態をスタックにPushします。
2) Reduce
生成規則の右辺の数に応じてスタックを複数回Popします。Pop後のスタックのトップと生成規則の左辺の非終端記号に応じた状態に遷移し、新しい状態をスタックにPushします。
3) Accept
入力値がRubyの文法に従っていることがわかったので、処理を終わります。
4) Error
入力値がRubyの文法に従っていないことがわかったので、処理を終わります。Syntax Errorですね。
具体例
たとえば
if a == 1 then true else false end
という入力を解析するとします。これをトークンで表すと
keyword_if (if) tIDENTIFIER (a) tEQ (==) tINTEGER (1) keyword_then (then) keyword_true (true) keyword_else (else) keyword_false (false) keyword_end (end) END_OF_INPUT
となります。末尾にEND_OF_INPUT
という特殊なトークンを加えておきます。
1. 初期状態
まずスタックに0
という状態をPushし現在の状態を0
にします。その直後に2
という状態に遷移しますがこれはそういうものだと思ってください。
* 現在の状態: 0 * スタック: [0] * 入力値: [keyword_if, tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT] => * 現在の状態: 2 * スタック: [0, 2] * 入力値: [keyword_if, tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]
2. Shift keyword_if
次にkeyword_if
をShiftし、状態10
に遷移します。Shiftしたので入力値が一つ減ります。
* 現在の状態: 10 * スタック: [0, 2, 10] * 入力値: [tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT] # 状態 10 k_if: keyword_if •
状態10
というのはkeyword_if
まで読んだという状態です。
3. Reduce keyword_if
Rubyの文法にはk_if: keyword_if
、つまり非終端記号k_if
とは終端記号keyword_if
である、という生成規則があるのでこれを適用してReduceします。
生成規則の右辺に1つのシンボルがあるので、状態を1つPopし、現在の状態が2
になります。
* 現在の状態: 2 * スタック: [0, 2] * 入力値: [tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]
生成規則の左辺が非終端記号k_if
であり、現在のスタックのトップは状態2
なので状態93
に遷移します。よって今回のReduceでは最終的に以下のような状態になります。
* 現在の状態: 93 * スタック: [0, 2, 93] * 入力値: [tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT] # 状態 93 primary: k_if • expr_value then compstmt if_tail k_end
4. 条件部分の解析
ここからしばらく条件の部分(a == 1
)の処理が続きます。
tIDENTIFIER
をShiftして状態35
に遷移。その後var_ref: user_variable
, primary: var_ref
, arg: primary
と右辺が1つのReduceを繰り返し、状態88
になります。
* 現在の状態: 88 * スタック: [0, 2, 93, 88] * 入力値: [tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT] # 状態 88 expr: arg • "==" arg
tEQ
とtINTEGER
をShiftし、それぞれ状態347
と状態41
になります。
* 現在の状態: 41 * スタック: [0, 2, 93, 88, 347, 41] * 入力値: [keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT] # 状態 41 simple_numeric: tINTEGER •
その後はtINTEGER -> simple_numeric -> numeric -> literal -> primary -> arg
とReduceが続きます。間にarg: arg "==" arg
によるReduceを挟んでexpr_value
になります。
* 現在の状態: 586 * スタック: [0, 2, 93, 88, 347, 586] * 入力値: [keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT] # 状態 586 arg: arg "==" arg • => `arg: arg "==" arg`によるReduceで [88, 347, 586] をpopしたのちに88をpush * 現在の状態: 88 * スタック: [0, 2, 93, 88] * 入力値: [keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT] # 状態 88 expr: arg • => `expr: arg`そして`expr_value: expr` でReduceする * 現在の状態: 382 * スタック: [0, 2, 93, 382] * 入力値: [keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT] # 状態 382 primary: k_if expr_value • then compstmt if_tail k_end
無事k_if expr_value
まで解析が終わってthen
をShiftできるようになりました。条件部分を解析しているときのスタックの様子をみてみると[0, 2, 93]
の部分は常にスタックにつまれています。よってprimary: k_if • ...
まで解析が終わっている状態が維持され、それよりもスタックの上(図では右)で条件部分(expr_value
)の解析をしていることになります。
* スタック: [0, 2, 93] # 条件部分を解析する直前 * スタック: [0, 2, 93, 88] * スタック: [0, 2, 93, 88, 347, 41] * スタック: [0, 2, 93, 88, 347, 586] * スタック: [0, 2, 93, 88] * スタック: [0, 2, 93, 382]
5. Acceptsされるまで
その後もShiftとReduceを繰り返してkeyword_end
をShiftしてk_end: keyword_end
でReduceするところまできました。ここからはprimary -> ... -> program
とReduceを繰り返します。
* 現在の状態: 1091 * スタック: [0, 2, 93, 382, 628, 799, 972, 1091] * 入力値: [END_OF_INPUT] # 状態 1091 primary: k_if expr_value then compstmt if_tail k_end • => Reduceを繰り返す * 現在の状態: 1 * スタック: [0, 1] * 入力値: [END_OF_INPUT] # 状態 1 $accept: program • END_OF_INPUT
このprogramというのがRubyの文法の頂点に存在する非終端記号です。すべてのRuby scriptはprogram
といえます。状態1
かつEND_OF_INPUT
のときに状態3
に遷移します。状態3
にいけば以下のようにAcceptされます。
State 3 0 $accept: program "end-of-input" • $default accept
parser generatorの役割
BisonをはじめとしたLR parser generatorは文法定義をインプットとして、状態の計算や構文解析表(ある状態と入力に対してShift/Reduce/Accept/Errorのどれを行うかという対応表)を計算し、プッシュダウン・オートマトンのコードを生成してくれます。
構文解析表を読みやすい形にしたものの抜粋を載せておきます3。
State 93 344 | k_if • expr_value then compstmt if_tail k_end error shift, and go to state 380 "`class'" shift, and go to state 5 "`module'" shift, and go to state 6 ... expr go to state 381 defn_head go to state 218 ...
Error Recoveryの仕組み
プッシュダウン・オートマトンからみたError
LR parserをプッシュダウン・オートマトンとして実装したときに、Shift/Reduce/Accept/Errorの4種類の遷移があると書きました。Shift/Reduce/Acceptについては具体例を用いて説明しましたが、Errorについてはまだ説明いなかったので、Error Recoveryの仕組みに先立って説明します。
プッシュダウン・オートマトンからみたErrorというのはShift/Reduce/Acceptのいずれでもないケースです。ShiftをするかReduceをするかといった遷移は生成規則から決まるので、ある状態にいるときに来ても困るトークンが存在します。例えばif end
という入力を考えると
* 現在の状態: 93 * スタック: [0, 2, 93] * 入力値: [keyword_end, END_OF_INPUT] # 状態 93 primary: k_if • expr_value then compstmt if_tail k_end
と、keyword_if
をShiftしてk_if
にReduceするところまではいいのですが、この次にkeyword_end
がきてもShiftもReduceもできません。実際にRubyにこの入力を渡しても、end
は期待してないですと言われます。
syntax error, unexpected `end' (SyntaxError) if end ^~~
Error Recoveryの方法その1 (Insert)
復旧方法その1は都合の良いトークンを挿入する方法です。if end
の例であればif true then end
というようにtrue
とthen
の2つのトークンがあるものとして処理をすればAcceptされます。
* 現在の状態: 93 * スタック: [0, 2, 93] * 入力値: [keyword_end, END_OF_INPUT] # 状態 93 primary: k_if • expr_value then compstmt if_tail k_end => 入力値: [keyword_true, keyword_then, keyword_end, END_OF_INPUT] であるとして解析を進める * 現在の状態: 1091 * スタック: [0, 2, 93, 382, 628, 799, 972, 1091] * 入力値: [END_OF_INPUT] # 状態 1091 primary: k_if expr_value then compstmt if_tail k_end • => 最終的にAccept
もちろんtrue then
のかわりにa == 1 then
と4つのトークンを挿入してもAcceptされます。
Error Recoveryの方法その2 (Delete)
if a == 1 true else false end end
ではこのような場合はどうするのがいいでしょうか。class A\n
を追加してクラスの定義にしてしまうこともできます。
if a == 1 true else false end class A end
しかし最後のend
を削除してしまうほうが素直ではないでしょうか。
if a == 1 true else false end
というわけで2つ目の方法は入力トークンを削除するという方法です。
Error Recoveryの方法その3 (Shift)
ここまでは一箇所だけが壊れているケースをみてきましたが、3つ目のケースとして二箇所が壊れているケースを考えてみましょう。
if a == 1 end true else false # syntax error, unexpected `end', expecting `then' or ';' or '\n' (SyntaxError) if a == 1 end ^~~
一行目のend
が余分で、最後の行にend
が足りていません。
end
をDeleteするtrue
からfalse
まではインプットをそのまま使用する- 最後に
end
をInsertする
if a == 1 true else false end
という方法でこのインプットをリカバリーできます。このときの2番目の操作、つまり"インプットをそのまま使用する"というのがShiftという操作になります。Insertがインプットにないトークンを補うのに対して、Shiftはインプットに存在するトークンをShiftします。
Error Recoveryの処理というのは適切なInsert/Delete/Shiftの操作の組み合わせを見つける作業であると言えます。 ここで"適切な"というのがポイントで、次のような入力について考えてみましょう。
1 +
tINTEGER
(2
など)をInsertすることでリカバリーすることが可能です。しかし2 + 3
や2 + 3 + 4 + 5 ...
と複数のトークンをInsertすることでもリカバリーは可能です。というわけで複数のリカバリー方法があったときにどれが最も適切であるかというルールを決めておく必要があります。実際には操作の回数が少ないものほどよいというルールを用いて評価することが多いようです。10回Insertして10回Deleteするようなリカバリーよりも、1回Insertして1回Deleteするリカバリーの方が、もとの入力に近いのでよいということなのでしょう。
リカバリー方法を探すときにどのくらい時間がかかるかというのも大切なポイントです。ある状態にいるときに次に期待するトークンは複数あることが多いのでInsertの候補も複数あり得ます。インプットが残っている限りつねにDeleteを試すことが可能です。気をつけないと大量の候補を探索することになります。いつまでも候補を探し続けても困ってしまうので、例えばInsertは4回まで、Deleteは3回まで、Shiftは10回までといったように操作の回数に上限を設けることもあります。また3回連続でShiftできるようになったらリカバリーが成功したことにするなど、入力の最後まで行く前に打ち切ることもあります。探索するときのアルゴリズムも大切で、深さ優先な探索よりも幅優先な探索が好まれます。幅優先であれば操作回数の少ない候補を全部調べてから操作回数の1つ多い候補を調べるという順番になるからです。