前回のあらすじ
Ruby 3.3にむけてLALR parserを前提にError Recoveryを実装していくことになりました。
現在の進捗
- Corchuelo et al. のサブセットを実装した
- error recovery tokenのsemantic valueやlocationを設定できるようにした
"Repairing Syntax Errors in LR Parsers"
Don’t Panic! Better, Fewer, Syntax Errors for LR Parsers も参考にしている論文に Repairing Syntax Errors in LR Parsers があります。
この論文では
- insertions: 現在のlookahead tokenの前に1つtokenを追加する (追加したうえでそのtokenに基づいて状態を更新する)
- deletions: 現在のlookahead tokenを削除する
- shifts: N個のlookahead tokenをshiftする
という3つの操作を用いて、Syntax Errorからの復旧を試みます。
既存のShift rule (LR1)とReduce rule (LR2)に対して、Repair rule (LR3)を追加してSyntax Error時の処理を定義しています。LR3はさらに細かく
- Insertion rule (ER1)
- Deletion rule (ER2)
- Forward move rule (ER3)
の3つのruleからなります。それぞれ3つの操作と対応しています。
such that after applying it to an input string, parsing can either continue for at least N symbols or leads to an accepting configuration.
これら3つの操作をした結果、規定のN個のSymbolを処理できるような操作列が見つかれば、Error Recoveryする方法がみつかったということになります。
操作列を探す処理を制限する方法として、探索を幅優先で行うとともに
- Nt: これが何に関する上限かわかってないが、おそらくある状態に対して試すtoken数の上限?
- Ni: Insertionの上限数
- Nd: Deletionの上限数
と上限を設けることで最悪時の計算量を制限します。また論文では最終的に以下の数値にしたとあります。
we have found through experimentation that setting N = 3, Nt = 10, Ni = 4 and Nd = 3 produces good repairs.
変更点
Corchuelo et al. の方法を以下のようにさらに制限して実装をしました。
N = 1つまりerror発生時のlookahead tokenがshiftできる状態になったらError RecoveryしたことにするNd = 0つまりlookahead tokenの削除をしないNi = 5つまり最大5つまで任意のtokenをlookahead tokenの前に追加してよい
Rubyのlexerは状態に応じて同じ文字列でも異なるtokenを切り出す可能性があります。またparserのアクションはlexerの状態を変更することがあります。しかしparserのアクションはASTの状態を更新したりするため、Error Recoveryで操作列を探索するときはparserのアクションを実行しないようにしています。現時点ではlex stateとtokenとアクションの関係を完全には把握していないので、1番目の制限をいれることでError Recoveryにlexerを動作させないようにしています。
LSPを想定しているので、最後にユーザーが編集した箇所の付近でSyntax Errorが発生しやすいと思っています。一方で最終編集箇所の周辺こそ補完などを行ってほしいはずです。なので2つ目の制限でtokenの削除をしないようにしています。
3つ目の上限は適当に決めています。
メインの実装はこちら。yyrecoverで愚直にそれぞれのtokenを幅優先で試しています。
いくつかの例を試してみましょう。test.rbにコードを書いて./miniruby --dump=y ../../test.rbしています。
# 例1. 行末に改行を含まない obj.m(a # repair_terms found. id: 1, length: 1 # id: 1, repair_length: 1, repair_state: 105, prev_repair_id: 0 # ')'
obj.m(a)というようにリカバリーされています。よさそう。
# 例2. 行末に改行を含まない class # repair_terms found. id: 743, length: 2 # id: 743, repair_length: 2, repair_state: 90, prev_repair_id: 27 # "local variable or method" "`end'"
class a endというようにリカバリーされています。これは実際はactionの中でSyntax Errorが発生するのですが構文的には正しいので選ばれています。これはなにか対策をしないとだめそう。
# 例3. 行末に改行を含まない if 1 # repair_terms found. id: 9, length: 2 # id: 9, repair_length: 2, repair_state: 90, prev_repair_id: 1 # "`then'" "`end'"
if 1 then endというようにリカバリーされています。よさそう。
# 例4. 行末に改行を含まない def m obj. end # repair_terms found. id: 1, length: 1 # id: 1, repair_length: 1, repair_state: 90, prev_repair_id: 0 # "`end'"
def m obj. end end
つまりendメソッドの呼び出しにしたうえで、endを補ってdefを閉じています。
# 例5. 行末に改行を含まない def # repair_terms found. id: 1614, length: 3 # id: 1614, repair_length: 3, repair_state: 16, prev_repair_id: 91 # "`class'" '=' "`break'"
def class = breakというようにリカバリーされています。一行メソッド定義でfnameがreswordsのclass、arg == primary == breakですね。
error tokenのsemantic valueの話
この方法でError Recoveryに必要なtokenの種類(たとえばkeyword_classとか=とか)はわかりました。しかしtokenに必要な情報はそれだけではありません。semantic valueやlocationの情報も必要です。しかしこれらは本来yylex (CRubyの場合はparser_yylex)が決定しています。なのでなにか他の方法でerror recovery tokenのsemantic valueやlocationを設定できるようにする必要があります。
Bisonには%printerという機能があるのでこれを参考に%error-tokenという機能を実装してparse.y側で各tokenの種別に応じた初期化ができるようにしましょう。例としてkeyword_classのIDをclass_erに設定してみます。
# 例5. 行末に改行を含まない def $ ./miniruby --dump=y ../../test.rb # Next error recovery token is token "`class'" (0.0-0.0: class_er) # Next token is token "`class'" (0.0-0.0: class_er) # Shifting token "`class'" (0.0-0.0: class_er)
このようにちゃんとclass_erがsemantic valueに設定されていますね。
