Error Tolerant parserに関するアイデア
9月半ばに行われたRubyKaigi 2022以来、3ヶ月くらいError Tolerant parserについて調べたり考えたり実装をしたりしています。 途中でもいいからなにかにアウトプットしておくとよいというアドバイスをもらったので、今現在の状況や考えていることを書いておこうと思います。
Error Tolerant parserとは? どうしてそれが欲しいの?
通常parserはユーザーの入力を受け取り
- その入力がそのプログラミング言語にとって、validなものか否かをチェック
- validな場合、その後の工程にとって都合のいいデータ構造(例えばAST)に変換し、後工程に渡す
- invalidな場合、Syntax Errorをレポートする
といった処理を行います。
しかしIDEやLSP(Language Server Protocol)を前提にするとこの機能だけでは不十分になってきています。 補完を行うときなどには、まだ入力中のある種invalidな入力を受け取り、"なんかいい感じ"にパースしてその結果をもとに補完候補を提示したくなります。 たとえば以下の例では、3行目で引数の候補を提示してほしくなりますよね。
def m1 a = 1 obj.m2( # <= ここ end
このあたりの話は Ruby Committers vs the World by CRuby Committers - RubyKaigi Takeout 2021の11:50ごろからや、同Slides P.8あたりを参照してください。
Ruby 3.2ではどうなるの?
先日書いた通り試験的な機能をRuby 3.2には導入する予定です。 この機能におけるError Recoveryは大きく二つの要素からなっています。
1). error tokenを用いたRecovery
これはBisonが提供している機能で、生成規則にerrorを書くことで特定のケースでRecoveryを行います。もとからRubyでもerror tokenは利用していたのですが、今回Ruby 3.2ではその位置を少し調整しました。
2). 明らかな場合にendを補完する
入力を読み終えた時点で明らかにendを補う必要がある場合に、lexerがendを補うようになりました。
とはいえこれで十分かというとまだまだ改善の余地はたくさんある状態です。 例えば以下のようなコードに対しては現時点では全く情報が残りません。
node = RubyVM::AbstractSyntaxTree.parse(<<-END, error_tolerant: true) x = 1 if END pp node #=> (NIL@0:-1-0:-1)
Error Recoveryとは具体的になにをすることなのか
ざっくりというと入力されてきた文字列(token列)を編集して受理可能な状態にする作業といえます。 ここでいう編集とは以下の3つの操作の組み合わせになります。
- 必要だけど書かれていないtokenを補う(insertion)
- 書かれているtokenを捨てる(deletion)
- それらの組み合わせ(replace)
insertionの操作を行うかどうか、deletionの操作を行うかどうか、エラーに遭遇するまでの結果に対しても編集を行うかどうかなどいくつかの選択肢があり、それに応じて必要な時間やメモリサイズが変わってきます。
どんな選択肢があるの?
パーサ(ジェネレータ)の種類によってError Recoveryの実装方法、その得手不得手が異なってくるのでPEG、ANTLR、手書きパーサ、LALRについてみていきます。
PEG
PEGといえばPythonという偉大な先人がいるので調べてみると Guide to the Parser というドキュメントを発見しました。これによるとPEGにおいては確定的にここで失敗したという情報がないので詳しいエラー情報を出すためにひと工夫しているようです。invalid_ prefixなルールを入れておき、最初はこのルールを無視してパースを行い、もしエラーがあれば再度invalid_ prefixなルールを有効にしてパースを行い、そのinvalid_ prefixなルールの中でエラー処理を行うようです。コメントでも説明されています。
たとえばifをみてみると、if_stmt, elif_stmt, else_blockにそれぞれinvalidなケースをケアするルールが定義してあり
if_stmt[stmt_ty]:
| invalid_if_stmt
| 'if' a=named_expression ':' b=block c=elif_stmt {
_PyAST_If(a, b, CHECK(asdl_stmt_seq*, _PyPegen_singleton_seq(p, c)), EXTRA) }
| 'if' a=named_expression ':' b=block c=[else_block] { _PyAST_If(a, b, c, EXTRA) }
elif_stmt[stmt_ty]:
| invalid_elif_stmt
| 'elif' a=named_expression ':' b=block c=elif_stmt {
_PyAST_If(a, b, CHECK(asdl_stmt_seq*, _PyPegen_singleton_seq(p, c)), EXTRA) }
| 'elif' a=named_expression ':' b=block c=[else_block] { _PyAST_If(a, b, c, EXTRA) }
else_block[asdl_stmt_seq*]:
| invalid_else_stmt
| 'else' &&':' b=block { b }
invalidなケースのルールの中ではさらに細かくinvalidなパターンを列挙しています。invalid_if_stmtのひとつ目のルールはif condで:を書かずに改行してしまったケース。ふたつ目のルールはif cond:で改行したあとにINDENTがないケース、おそらくですが直前行のindentの深さをみてlexerでINDENTを切り出すか決めているのではないでしょうか。
invalid_if_stmt: | 'if' named_expression NEWLINE { RAISE_SYNTAX_ERROR("expected ':'") } | a='if' a=named_expression ':' NEWLINE !INDENT { RAISE_INDENTATION_ERROR("expected an indented block after 'if' statement on line %d", a->lineno) } invalid_elif_stmt: | 'elif' named_expression NEWLINE { RAISE_SYNTAX_ERROR("expected ':'") } | a='elif' named_expression ':' NEWLINE !INDENT { RAISE_INDENTATION_ERROR("expected an indented block after 'elif' statement on line %d", a->lineno) } invalid_else_stmt: | a='else' ':' NEWLINE !INDENT { RAISE_INDENTATION_ERROR("expected an indented block after 'else' statement on line %d", a->lineno) }
PEGにおいては選択(a / b)はaを試してみて成功しなかったらbを試すというものです。つまり全ての選択肢が失敗したケースがSyntaxErrorになります。なので"if condで:を書かずに改行"というように具体的なルールとしてエラーを記述しているようです。
ANTLR
ANTLRについてはちゃんと調べていないのですが、すくなくともANTLR4はC言語の構文解析器のコードを生成できないようです(サポートするパッチを書けばいいという話はありますが一旦割愛)。
手書きパーサ
手書きパーサにすれば実装する言語(CRubyの場合はC言語になると思う)で表現できるものは扱えるようになるので、だいたいなんでもできるようになるはずです。これは非常に魅力的な点です。 一方で表現力が高すぎるのではないかという不安ももっています。LRであれば受けられている恩恵、例えば
- 入力に対してO(n)で計算可能(もしくはどの程度計算に時間がかかるか事前に把握できる)
- shift/reduceもしくはreduce/reduce conflictを検知できる
- BNFなどの"DSL"により記述できる
といった利点を失うことになります。
- kinabaさんの http://www.kmonos.net/pub/Presen/HiC.pdf P.18 より
手書きの場合のRecoveryはdeletionを関数内部に書いていくというスタイルになると思います。golangおよびrust-analyzerの実装を少し見てみましょう。
まずはgolangの場合。たとえばoperandをパースしている箇所をみてみると、deletionを行っている様子がわかります。全体がtokenのtypeによるswitch文での分岐になっており、_Name, _Literalなどでない場合のdefaultの処理でエラー時の処理を行なっています。p.badExpr()でエラー時のNodeを作成します。また同時にadvanceを呼んで特定のtokenが出現するまでtokenを捨てます。
次にrust-analyzerの場合。fn(関数定義)をパースしている箇所をみてみると、deletionを行っている様子がわかります。fn foo() {}のfooをパースするときにname_rにITEM_RECOVERY_SETを渡して呼び出します。name_rは現在のtokenがIDENT(identifier)でない場合にerr_recoverを呼び出します。err_recoverは現在のtokenがrecoveryに含まれる時はerror messageを記録だけして処理を続けます。つまり1つtokenを削除しているといえます。
複数のtokenを削除するgolangと1つのtokenだけを削除するrust-analyzerという違いはありますが、どちらもエラー遭遇時点から先のtokenを削除のみを用いて復旧を図るというアプローチになっています。
このアプローチの場合、各関数においてどのトークンまでを捨てるかを考えてチューニングしていくことになると思うので、その作業に対してどのくらい指針となるものがあるかがポイントだと思います。
LALR
現在CRubyではGNU Bisonというパーサジェネレータを使ってLALRパーサを生成して使っています。
Bisonの標準的なError Recoveryの方法はpanic-modeと呼ばれたりします。この方法で難点と感じるのは
- 今までの計算結果を一部捨ててしまう(linkでいうと(2))
- その先のtokenも一部捨ててしまう(linkでいうと(4))
今ちょうど入力した文字(列)というのがSyntax Errorを引き起こしている可能性は高いので、そこを中心に入力tokenを破棄されてしまうのはあまり都合のよいものではありません。
では他にどのようなError Recoveryの方法が考案されているかというと
およびそこで参照されているものとして
のようにエラーに遭遇した場合にそれ以降の全てのtokenを対象にinsertion/deletionしてvalidなtoken列にするというアイデアがあります。
これまでのアプローチのなかでこれが一番広いアプローチだと思います。また文法定義を入力としてError Recoveryするコードを書けばよいという点も魅力です。手書きパーサのところで"各関数においてどのトークンまでを捨てるかを考えてチューニングしていくことになると思う"と書きましたが、入力となる文法規則がその指針となるというイメージです。
ではどうするか
私個人としては当面はLALR parserを前提にError Recoveryを実装できないか考えていくつもりです。
開発は今どんな感じなの?
とりあえず次の一歩として、生成規則をもとに各LR項について最短で右辺をつくれるtoken列を事前に計算し、エラーになったらそのtoken列を先頭から補完するという実装を試してみています。
def m1 a = 1 obj.m2( end
このような入力は以下のようなASTになります。あくまで入力をASTにすることが目的で、Recoveredは修復を行った結果をscriptとして表現した参考情報です。
========================= Input: def m1 a = 1 obj.m2( end => Recovered: def m1 a = 1 obj.m2( ) end AST: (SCOPE@1:0-4:3 tbl: [] args: nil body: (DEFN@1:0-4:3 mid: :m1 body: (SCOPE@1:0-4:3 tbl: [:a] args: (ARGS@1:6-1:6 pre_num: 0 pre_init: nil opt: nil first_post: nil post_num: 0 post_init: nil rest: nil kw: nil kwrest: nil block: nil) body: (BLOCK@2:2-4:3 (LASGN@2:2-2:7 :a (LIT@2:6-2:7 1)) (CALL@3:2-4:3 (VCALL@3:2-3:5 :obj) :m2 nil))))) =========================
