Ruby Parser開発日誌 (11) - RubyKaigi 2023 follow upで進捗について話してきた

8/19に開催されたRubyKaigi 2023 follow upで、Rubyのparserとparser generatorに関する進捗と今後の方針について話をしてきました。

rhc.connpass.com

当日の資料はこちらにアップロードしてあります。

speakerdeck.com

進捗とこれからの話

RubyKaigiでの発表を踏まえて3つの点についてRubyKaigiからの進捗とこれからの話をしました。

  • Error-tolerant
  • Universal Parser
  • Maintainability

Lramaとは

github.com

RubyでかかれたLALR parser generatorです。BNFをベースにしたDSL(parse.y)を受け取って、C言語実装のLALR parserを生成します。現在のCRubyはLramaが生成したparserを使用しています。

Error-tolerant

進捗は大きく2つあって、一つはRubyKaigiに向けて作りっぱなしになっていたerror_recovery branchをmergeしました。もう一つはError-tolerantの機能をcompile時ではなくruntimeで制御できるようにYYERROR_RECOVERY_ENABLEDやYYMAXREPAIRというinterfaceを追加しました。1つめのerror_recovery branchのmergeに関しては alitaso345 さんの尽力のおかげです。ありがとうございます。

次のステップとしてはError-tolerantの機能をRubyに繋ぎ込んでいきたいと思っています。現状繋ごうとすると、どこかメモリ周りのbugがあるようで参照先が途中で変わってしまってSEGVするので、どこかで集中してデバッグする必要がありそうです。

Universal Parser

進捗としてはRuby本体にUniversal Parser modeでbuildできる設定をいれたことです。[Feature #19719] Universal Parser by yui-knk · Pull Request #7927 · ruby/ruby · GitHub

S-H-GAMELINKS さんなどからPRもいただき、少しずつCRuby固有の関数への依存を減らしている状態です。

char関連の関数は移植できたので、そろそろAST NodeからRubyのobjectを消したり、unionで定義されているNodeをstructで定義するように書き換えていこうかなと思っています。

お手元でUniversal Parser modeでビルドしてみる方法について S.H. さんがブログにまとめてくださいました。

blog.agile.esm.co.jp

Maintainability

今回Maintainabilityについて話すうえであらためてparser generatorやLR parserの優れている点について考えてみました。いくつかあるのですが、まずはじめにBNFという広く使われているinterfaceで文法を記述できる点があげられます。つぎにparser generatorは人間が見落としがちな曖昧性(conflict)を自動で検出して報告してくれます。またある種のアルゴリズムでは具体的な文法によらずBNFをもとに自動的にError-tolerantなパーサーを生成することも可能です 1。

いいことばかりに見えるアプローチですが、LALR parser generatorについては一定のデメリットも指摘されています。

よくいわれるのがコンフリクトしたときに何が起きているのかよくわからない、またどのように解決したらいいのかわからないといったコンフリクトに関すること。どのように構文を拡張したらいいのかよくわからないといった拡張性に関すること。省略可能な構文や繰り返しの構文に関して一定のお作法があるなど文法ルールに関する書き味に関することなどです。

総じていえばプログラミング言語の文法を開発するときの体験が悪いということが問題だといえます。

コンフリクト解消の大変さ

コンフリクトに関してはLrama v0.5.4でCounterexamplesという機能を実装しました。ぶら下がり(dangling) elseというShift/Reduce コンフリクトの有名な例ですが、このようにコンフリクトがあるときに、それぞれ具体的な例を表示してくれる機能です。最適化の余地がまだ結構あるので速度については今後改善していきたいとおもっています。

shift/reduce conflict on token k_else:
    stmt: k_if expr k_then stmt • k_else stmt  (rule 1)
    stmt: k_if expr k_then stmt •  (rule 2)
  Shift derivation
    0:  stmt                                                                    "end of file"
        1: k_if expr k_then stmt                                    k_else stmt
                            1: k_if expr k_then stmt  • k_else stmt
  Reduce derivation
    0:  stmt                                                         "end of file"
        1: k_if expr k_then stmt                         k_else stmt
                            2: k_if expr k_then stmt  •

これでコンフリクトに関する難しさが全て解決したわけではありません。コンフリクトの例を理解して、ShiftするかReduceするかを決めたとします。そのときに文法ファイルをどのように書いたらいいか今のparser generatorはなにもアドバイスをくれません。実務的には %prec xxx と書くことで優先度を与えてShiftもしくはReduceのどちらに振舞うかを指示することが多いです。であればそれを最初から教えてくれてもいいのではないでしょうか。

shift/reduce conflict on token keyword_and:
    endless_arg: endless_arg • "`and'" endless_arg  (rule 267)
    endless_stmt: endless_arg •  (rule 263)

    If you want to shift "`and'", specify "endless_stmt : endless_arg %prec tLOWEST"
    If you want to reduce, specify "endless_stmt : endless_arg %prec keyword_not"

もう一つ改善点をいうと%prec xxx という表記はあまりわかりやすくありません。とくにあとからみたときに何をどう解決するために書かれたものかという情報があまりありません。ある地点において、あるtokenをshiftせよといったことがわかるような良い表記を思いつけばそれをサポートしたいとおもっています。

// 書き方の例
endless_arg     : ...
                | endless_arg keyword_and endless_arg %shift keyword_and
                | endless_arg keyword_or endless_arg  %shift(1)
                ;

文法ファイルをいじることの大変さ。または書き味がいまいちなこと

コンフリクト以外の点では2つのトピックをお話ししました。ひとつは今後の構文拡張について開発者にヒントをあたえられないかという話。もうひとつは文法定義にもう少しリッチな書き方を提供できないかという話です。

Rubyに新しい文法を追加するときに、既存の文法を壊さないように注意しながら文法を議論します。新しい書き方をしたときに今のRubyでSyntaxErrorになることを確認するというテクニックがよく使われます。ここから新しい文法を考えるときにヒントを得ることができるのではないかと考えています。具体的にはSyntaxErrorというのはある状態で次にくるべきtoken以外が来た場合に起きるので、文法のルールの書く部分で次に来てはいけないtokenを可視化することで新しい文法のヒントを提供できないかと考えています。

文法ファイルの書き味についても改善の余地があります。,区切りのarg_valueの連続(args)や省略可能な改行(opt_nl)といったルールの書き方は頻出で、書き方もテンプレート化しています。Menhirなどを参考にこれらテンプレート化した書き方向けにシンタックスシュガーを提供していきたいと思っています。

args        : arg_value
            | args ',' arg_value
            | ...
            ;

opt_terms   : /* none */
            | terms
            ;

opt_nl      : /* none */
            | '\n'
            ;

LexerとParserは分離可能なのか

Rubyのparserをいじっていると色々な情報をLexerからParserに移動したほうが見通しがよくなるのではないかと思うことがたまにあります。

例えばifという文字列に対応するtokenがRubyには2つあります(keyword_ifとmodifier_if)。Lexerはlex_stateで状態を管理しながら、このどちらを切り出すかを判断しています。いまはLexerとParserの両方がlex_stateを更新しています。しかし文法に関してはParserの方がより多くの情報をもっているので、%lexのような記法を用意してlex_stateを更新する箇所を全部Parser側に寄せてみてはどうかというアイデアがあります。

stmt | stmt modifier_if expr_value

=>

stmt | stmt %lex(EXPR_END) modifier_if expr_value

LRパーサーの機構はtokenによって遷移するオートマトンをstackで管理するというものです。一方でlex_stateもまたtokenによって遷移するオートマトンです。オートマトンとオートマトンを組み合わせたものもまたオートマトンなので、それをLRパーサーのstackで管理するというのは割と自然な発想ではないでしょうか。

他にもParser側の情報をうまく使えそうな例として、引数のないブロック呼び出しの例を紹介しました。

a do ||
end

Rubyには|と||(tOROP)という異なるtokenがあります。素朴にLexerを実装するときはより長いほうからマッチを確認します。しかし先ほどのブロック呼び出しの例では||ではなく|と|である必要があります 2。これを区別するためにもlex_stateが使われています。しかしdoのあとには||が来ないことは文法定義からわかりますし、いまdoの直後にいるかどうかはparserの状態からわかります。であればその情報をParserからLexerに伝えることでlex_stateを使わずとも適切なtokenを切り出すことができるのではないでしょうか。

最近このようなアプローチに関する論文があることをしったので、今回はあたらしくPSLR(1)という種類のparserを紹介しました 3。

最終的に目指すところ

Rubyの"parse.y"のなかでもLexerの部分はC言語で手書きされたロジックのかたまりです。ということは教科書などで構文解析を勉強したとしても、Lexerの部分はコードを読んで何が起きているか一から理解をしないといけません。これをPSLRなどの論理に沿った形で整理していくことで最終的には、教科書などで構文解析を勉強すればRubyのparserが理解できる状態にしていきたいと思っています。

懇親会で話したこと

懇親会で複数人とparserの話をする機会があったので、そのときに話したことを簡単にまとめておきます。

Error-tolerant parserのさらなる拡張の話

将来的にいくつかの機能拡張を考えています。

  • 今はtokenを補う(insertする)という操作だけなので入力ファイルのtokenを削除する操作も組み合わせてリカバリーを考えるようにする
  • その際にはinsertとdeleteのコストをそれぞれ設定できるようにしたい。というのもおそらく多くの場合において可能な限りもとの入力を残しておいた方がいいと想像されるので、insert 3回に対してdelete 1回が同じコストというような傾斜をかけたくなるはず
  • syntaxは通るがsemanticsが通らないかたちにリカバリーしてしまうことがあれば、生成規則にannotationをつけて特定のruleをリカバリー時に使わないようにするなどの工夫が必要になるかもしれない

LR parser 上から読むか横から読むか

makenowjust-labs.github.io

に関する話もしました(主にEarley法のほう)。私はLR parserを教科書通りに理解しているようで、以下のような状態をみると、defまで読んだ段階であってまだdef method ...の可能性もdef self.method ...の可能性もある1つの状態なんだと理解しています。一方これを2つのオートマトンを抱えている状態であって、以降の入力によってどちらのオートマトンが残るか(もしくはどっちも残らなくてエラーになるか)が決まるというふうに読むこともできます。ブログで紹介されている技法は後者の"2つのオートマトンを抱えている状態"に近しいと思ったのでした。

defn_head: • k_def def_name
defs_head: • k_def singleton dot_or_colon def_name

あとProcedural Automatonという単語をはじめて知りましたという話もした記憶があります。

いろいろあるLR parser、結局なにが違うのか

LR(0), LR(1), SLR(1), LALR(1), IELR(1)といろいろな種類があるが端的になにが違うのかという話になったので、それらはどのようなケースでReduceするかが異なりますね。という話をしました。どの種類であっても、ルールとdotの組み合わせ (k_if expr_value then compstmt if_tail • k_end など)から状態を構成しますし、各状態においてshiftをするかどうかについては変わりはありません。では何が違うかというと各状態でReduceするかどうかの判断が異なってきます。

例えば最も素朴なLR(0)ではルールの終わりにいるときは無条件でReduceをします。対してLR(1)などではルールの終わりにいてかつ次のtokenが一定の条件を満たす場合にのみReduceをします。条件というのは簡単にいえば、Reduceをしていったときに次のtokenが出現することがあるかというものです。LR(1)は一般に状態数が膨大になることがあるので、それらの状態をmergeしたものがSLR(1), LALR(1)です。状態をmergeした結果としてコンフリクトが新たに生じることがあるので、それらのうち状態を分割することで回避可能なものについて再度状態を分割するというのがIELR(1)のアプローチです。

まとめ

発表の準備はそれなりに大変でしたが、締め切りがあったおかげで実装も進みましたし、今後の展望についてもあらためて整理してお話しすることができました。

主催の笹田さん。会場提供 & 音響・配信 & DJ & 懇親会の運営などをしてくださったピクシブ株式会社様。スポンサーのみなさん。当日絡んでくださったみなさん。ありがとうございました。

  1. 例えばCPCT+ algorithm ([1804.07133] Don't Panic! Better, Fewer, Syntax Errors for LR Parsers)↩
  2. 過去にはtOROPのほうをつかって文法を定義していたので最終的には実装依存ですが、|と|のあいだに省略可能な引数があるというルールのほうがわかりやすいと思います↩
  3. 詳しくは PSLR(1): Pseudo-Scannerless Minimal LR(1) for the Deterministic Parsing of Composite Languages↩