Techouse Developers Blog

テックハウス開発者ブログ｜マルチプロダクト型スタートアップ｜エンジニアによる技術情報を発信｜SaaS、求人プラットフォーム、DX推進

RubyKaigi 2024 - From LALR to IELR: A Lrama's Next Step (Day3)

Ruby RubyKaigi2024 カンファレンス

ogp

こんにちは、2024年にTechouseに新卒入社したakiと申します。
本記事では、Rubykaigi 2024 3日目のJunichi Kobayashi(@junk0612) さんによるセッション、「From LALR to IELR: A Lrama's Next Step」について紹介させていただきます。

CRuby/Lramaと現状の問題点

junk0612さんは永和システムマネジメントのRailsエンジニアの方で、Lramaのコントリビュータ、コミッターとしても活躍されています。セッションでは、これまでのLramaとその問題点、解決のための道筋についてお話しいただきました。

Lramaとは？

これを読んでいるみなさんはご存知のことかと思いますが、Lramaとは、RubyのLALRパーサジェネレータです。RubyKaigi 2023にて、Yuichiro Kaneko(@spikeolaf)さんによって発表されました。

CRubyの問題点

Lramaはparse.yにある文法を解釈してparserを生成しているわけですが、そのparse.yにはある問題点があります。それは、Lexerの状態管理が複雑であることです。
例えば、以下のようなコマンドを実行します。

$ ruby -e 'p 1.. || 2'

実行結果はどのようになるでしょうか？個人的には、以下のような出力を期待しました。

$ ruby -e 'p 1.. || 2'
=> 1..

しかし実際には、以下のようにエラーが出力されます。

-e:1: syntax error, unexpected '|'
p 1.. || 2
-e: compile error (SyntaxError)

エラーとなっている箇所は二本目の|であり、パーサが||を or として認識できていないことがわかります。
では、parse.y側では、この規則はどのように表現されているのでしょうか？ parse.yには以下のように記述されており、

case '|':
  if((c = next(p)) == '|') {
    ...
    if(IS_lex_state_for(last_state, EXPR_BEG)) {
      c = '|';
      pushback(p, '|');
      return c;
    }
    return tOROP;
  }

github.com

if(IS_lex_state_for(last_state, EXPR_BEG))の条件式から、EXPR_BEGの値によって、|として解釈されるか、||として解釈されるかが決まっていることがわかります。上記のようなLexerの状態によって解析の結果が決定されるケースは、この例の他にもたくさんあるそうです。

これを修正することはparse.yに手を入れることで可能です。しかし、parse.yは既に複雑かつ大規模なコードになっており、局所的な修正の影響範囲を見積もることも容易ではありません。

このような問題は、根本的にはLexerとParserの密結合な実装が起因しています。理論的には、字句解析を行うLexerと、構文解析を行うParserは疎結合にできるとされています。しかし実際には、tokenizeしたい内容が、これまでコードを読んできた内容、つまりLexerの状態によって変わってしまう場合が数多くあります。この理論と実態の乖離により、「Lexerの複雑な状態管理」という問題が生じてしまっているようです。

では、どのようにLexerの状態管理の問題を解決すべきなのでしょうか？

ScannerlessParser

セッションでは、上記の問題を解決するために、ScannerlessParserをLramaに導入することが試みられている、と述べられていました。
ScannerlessParserは、今までのLexerによる字句解析とParserによる構文解析を（出来るだけ）分離していた手法とは異なり、両者を単一のステップで実行する、というアプローチになります。ScannerlessParserの内部では、LexerとParserは互いに状態を監視しながら、お互いの処理を行います。
この実装方針は「ソースコードを読んでいる最中に、Parserは、次にどのようなトークンが来るのか文法規則から推測可能である」という考え方から考案されています。これにより、Lexerの状態管理を開発者側でなく、コンピュータ側に任せることができるという点で利点があります。

Ruby Parser Roadmapでは、ScannerlessParserへの道筋として、IELRの実装が挙げられています。今回のセッションのメインは、このIELRの説明およびその実装についてでした。

docs.google.com

IELR

IELRを理解するためには、その前提となるCanonicalLR、LALRを理解する必要があります。
さらにその前談となるLR構文解析については、Kanekoさんの以下のブログが世界一わかりやすいので、参照するようにセッション中にも言及されていました。

yui-knk.hatenablog.com

CanonicalLR

CanonicalLRは、BNFに従って状態遷移を行うLRとは異なり、還元によって得られるトークンがLookahead setに含まれる場合のみ、状態遷移を行うような構文解析器になります。
言語としての表現力が高い事が特徴ですが、LR法と比較して、オートマトンの状態数が大きくなるため、メモリ消費量が大きく、結果的にパフォーマンスが悪いというポイントもあります。

LALR

CanonicalLRに対し、オートマトンの状態のうち、同じ「核」を持つものをマージすることで、状態数の削減を実現したものがLALRです。
一方で、CanonicalLRよりも表現可能な言語が乏しいというトレードオフがあります。また、状態のマージがConflictを起こすことも問題となっています。GNUBisonではこれを「Mysterious Conflict」と表現しています。

IELR

IELRは、LALRとCanonicalLRの表現力の差を埋めつつ、LALRの状態数の少なさを得た、いいこと取りの構文解析器です。

そのような便利な構文解析器を、どのように実現しているのでしょうか？セッションでは、その手順についての解説がありました。大まかには、はじめにLALRの状態のマージ結果を得て、その後にMysterious Conflictが起きている状態を検知し、状態のマージを再分解する、といった流れです。

  1. はじめに、LALRパーサの構文解析表を作成する。
  2. 次に、CanonicalLRパーサのオートマトンの各状態のlookahead setを初期状態から再計算していく。
  3. 互いのlookahead setから、Mysterious Conflictが起こるかどうかを判定する。
  4. 判定結果によって、マージされた状態を再分解する。

IELRの実装

IELRの実装は以下のPRから確認できます。

github.com

セッションでは、コードの概略についても解説がありました。

def split_states
  ...
  @states.each do |state|
    state.transitions.each do |shift, next_state|
      compute_state(state, shift, next_state)
    end
  end
end

github.com

@statesはLALRの状態集合であり、各状態に対して、BFSでcompute_stateメソッドを実行しているようです。

compute_stateの実装は以下のようになっています。

def compute_state(state, shift, next_state)
  k = propagate_lookaheads(state, next_state)
  s = @ielr_isocores[next_state].find {|st| is_compatible(st, k) }

  if s.nil?
    ...
    @lookaheads_recomputed[new_state] = true
    @item_lookahead_set[new_state] = k
    state.update_transition(shift, new_state)
  elsif(!@lookaheads_recomputed[s])
    @item_lookahead_set[s] = k
    @lookaheads_recomputed[s] = true
  else
    merge_lookaheads(s, k)
  end
end

github.com

詳しい処理については追えていないのですが、propagate_lookaheadsメソッドは、CanonicalLRによるlookahead setの再計算を行なっているそうです。二行目の@ielr_isocores[next_state].find {|st| is_compatible(st, k) }によって、再計算したlookahead setとLALRのlookahead setに互換性があるかどうかを検証しています。互換性がない場合には、if s.nil?の条件分岐に入り、状態の再分解が行われているようです。

今後の展望

セッションの最後には、今後の展望として以下の項目が挙げられていました。

  • IELRのPRのマージ
  • PSLRパーサの生成の実現
  • parse.yのリファクタリングと、lex_stateからの解放

感想

パーサの実装については難しい印象があったのですが、junk0612さんのセッションでは大まかな内容がわかりやすく解説されており、初学者の自分でも楽しく拝聴することができました！個人的には、大学時代に学んだオートマトンや自由文脈文法の話が実装され、今自分が書いているRubyの上で動いている、ということに非常に感動しました。これを機に、自分も構文解析の世界に足を踏み入れてみたいと感じました。

終わりに

Techouseでは、社会課題の解決に一緒に取り組むエンジニアを募集しております。 ご応募お待ちしております。 jp.techouse.com