Ruby Parser開発日誌 (3)

前回のあらすじ

Ruby Parser開発日誌 (2) - かねこにっき

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項は生成規則とという記号から作られます。ざっくりというとはその位置にいるということを表しています。

たとえばRubyif式は以下のような生成規則で定義されています。

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

tEQtINTEGERを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というようにtruethenの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が足りていません。

  1. endをDeleteする
  2. trueからfalseまではインプットをそのまま使用する
  3. 最後にendをInsertする
if a == 1
  true
else
  false
end

という方法でこのインプットをリカバリーできます。このときの2番目の操作、つまり"インプットをそのまま使用する"というのがShiftという操作になります。Insertがインプットにないトークンを補うのに対して、Shiftはインプットに存在するトークンをShiftします。

Error Recoveryの処理というのは適切なInsert/Delete/Shiftの操作の組み合わせを見つける作業であると言えます。 ここで"適切な"というのがポイントで、次のような入力について考えてみましょう。

1 +

tINTEGER (2など)をInsertすることでリカバリーすることが可能です。しかし2 + 32 + 3 + 4 + 5 ...と複数のトークンをInsertすることでもリカバリーは可能です。というわけで複数のリカバリー方法があったときにどれが最も適切であるかというルールを決めておく必要があります。実際には操作の回数が少ないものほどよいというルールを用いて評価することが多いようです。10回Insertして10回Deleteするようなリカバリーよりも、1回Insertして1回Deleteするリカバリーの方が、もとの入力に近いのでよいということなのでしょう。

リカバリー方法を探すときにどのくらい時間がかかるかというのも大切なポイントです。ある状態にいるときに次に期待するトークンは複数あることが多いのでInsertの候補も複数あり得ます。インプットが残っている限りつねにDeleteを試すことが可能です。気をつけないと大量の候補を探索することになります。いつまでも候補を探し続けても困ってしまうので、例えばInsertは4回まで、Deleteは3回まで、Shiftは10回までといったように操作の回数に上限を設けることもあります。また3回連続でShiftできるようになったらリカバリーが成功したことにするなど、入力の最後まで行く前に打ち切ることもあります。探索するときのアルゴリズムも大切で、深さ優先な探索よりも幅優先な探索が好まれます。幅優先であれば操作回数の少ない候補を全部調べてから操作回数の1つ多い候補を調べるという順番になるからです。

まとめ

  • プッシュダウン・オートマトンを利用してLR parserを実装します。
  • 正しくないインプットを与えるとプッシュダウン・オートマトンがどこかで停止してしまいます。その状態がError状態です。
  • Error状態になったときにInsert/Delete/Shiftという3種類の操作をおこなってインプットを修正することで、プッシュダウン・オートマトンが再び処理をすすめられるようにします。これがError Recoveryです。
  • Insert/Delete/Shift操作の組み合わせを探すときは、計算量が大きくならないようにいろいろな工夫をする必要があります。

  1. LR項はカーネル項(Coreとも)と非カーネル項に分類でき、正確にはカーネル項とその閉包を使って状態を定義します。
  2. なぜスタックにも状態を積むのかという点については LR構文解析の原理 がおすすめです。
  3. --report=states,itemsets,lookaheads,solvedといったオプションをbisonコマンドに渡すことで生成できます。