Techouse Developers Blog

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

RubyKaigi 2025 - The Implementations of Advanced LR Parser Algorithm (Day2)

RubyKaigi2025

ogp

はじめに

ジョブハウスでエンジニアをしております、新卒 2 年目の aki と申します。 今回は RubyKaigi 2025 の二日目のセッション、junk0612 さんの「The Implementations of Advanced LR Parser Algorithm」について内容を紹介させていただきたいと思います。

序章

junk0612 さんは Ruby で実装された parser generator である Lrama のコミッターであり、主に parser を生成するアルゴリズムを実装されている方であると認識しております。
昨年も RubyKaigi 2024 にて「From LALR to IELR: A Lrama's Next Step」というタイトルでお話をされていました。昨年の発表の内容は、parser の生成アルゴリズムを LALR から IELR への移行することを主題とし、IELR のコンセプトや実装の概要についてお話されていました。当時はその PullRequest は Draft の状態でしたが、一年の間にその PR がマージされ、IELR アルゴリズムを利用して parser を生成できるようになりました。
以下のように lr.type オプションを ielr に指定することで、LALR ではなく IELR を利用して parser を生成することができます。

$ lrama -D lr.type=ielr grammar.y

parser アルゴリズムの概要

セッションでは、IELR アルゴリズムの概要と実装にあたってのポイントについてお話しされていました。

始めに {0, 1} のアルファベットと掛け算、足し算のみを扱う数式を例として文法規則の説明をされておりました。

exp: exp + num
   | exp * num
   | num
num: 0
   | 1

例えば 1 + 0 * 1 という文字列に対して、トークンを一つずつ読み込んでいきます。このトークンを一つ読み込む動作を Shift と呼びます。
Shift を続けると、トークン列に文法規則を適用できるタイミングが来ます。たとえば 1 を読み込んだ後には、num: 1 という文法規則を適用し、1 を num に置き換えることができます。この動作を Reduce と呼びます。
ある文字列に対して文法規則に従い Shift/Reduce を繰り返した操作列は、木構造で表現することができます。1 + 0 * 1 の場合は以下のように表現できます。

parse_tree

(算術演算子を利用していますが、初等算数の一般的な演算子の優先順位に従っていないのがちょっとした面白ポイントです)

上記の例では Reduce が可能な任意のタイミングで Reduce しました。処理中のどのタイミングで Reduce を行うかは重要な問題で、任意の可能なタイミングで Reduce を行おうとすると問題が生じる場合があります。

method_call: method_name
           | method _name '(' args ')'

例えばこのような文法規則に対し、

save! (name: 'Junichi')

上記のような文字列が与えられたとします。(save! はメソッド名として tokenize されることを前提としています)
この時、トークンを読み込んで逐次的に Reduce を行うアルゴリズムですと、save! を読み込んだ時点で method_name -> method_call の Reduce が起こってしまいます。実際は引数付きのメソッド呼び出しとしてパースする必要があるわけですから、逐次的な Reduce が最適なアルゴリズムではないことがわかります。

これに対するアプローチとして、「次のトークンを先読みして Shift/Reduce を決定する」という方法があります。先ほどの例であれば Reduce する前に ( を先読みすることで、 method_call: method _name '(' args ')' という文法規則によって Reduce される可能性がある、ということが分かります。parser はこれに従い ( を Shift することで、正しく Reduce を行うことができます。
では、先読みの結果を利用してどのようにアクションの選択すればよいのでしょうか？例えば以下のような文法を例に考えてみます。

statement: method_call 'if' exp
         | method_call 'unless' exp
method_call: method_name
           | method _name '(' args ')'

メソッド呼び出しに後置 if と unless を強制する不思議な文法です。これに対し、

save! (name: 'Junichi')

という文字列が与えられたとします。この場合は先ほど同様、先読みした ( に対して Shift を選択することで正しくパースができます。

save! if valid?

こちらの場合はどうでしょうか？先読みして if を読み込んだ場合、save! を method_name -> method_call として Reduce することで正しくパースができます。

save! end valid?

また上記の場合、end を先読みしたとき、このようなトークンが現れることは文法規則から推測されないのでエラーを返します。

つまり、先読みした結果を基に Shift/Reduce/エラー の3つの動作のうちどれを行うか決定する必要があるのですね。(エラーだけ毛色は違いますが)基本的に、以下のような原則でこの選択を行うと良いようです。

  1. 先読みしたトークンを含む文法が現在のトークン列をそのまま含むものである場合、Shift を行う。
  2. 先読みしたトークンを含む文法が現在のトークン列を還元した結果遷移する状態である場合、Reduce を行う。
  3. 先読みしたトークンがどの文法にも含まれないものである場合、例外を投げる。

先読みによってより適切に Reduce のタイミングを選択出来ることが分かりました。
しかし、愚直に行うと一個先のトークンを先読みする度に文法規則を確認して、対応する文法規則を探して、、、という処理を行う必要があります。これは効率的とは言えませんし、そもそも、 「それぞれ状態でどのトークンが来る可能性があるか」というのは、文法規則から予測ができるはず です。そこで、LR parser は「Look-ahead Set」として状態毎に次に来ることが予測されるトークンの集合を予め計算します。

この Look-ahead Set の計算方法は LALR と IELR で異なります。
LALR（Look-Ahead LR）の場合は言語の文法規則全体を元に、各状態に対して次に来る可能性のあるトークンの集合を計算します。
一方で IELR（Inadequacy Elimination LR）の場合は、それまで読んできたトークン列も加味し、次に来る可能性のあるトークンの集合を計算します。
IELR は文脈を加味して次に来る可能性のあるトークンを制限するため、LALR と比較して Look-ahead Set が過分に大きくなる事を避けられるわけですね。
実際に以下で例を見てみましょう。

cond_stmt: 'if' method_call 'then' body 'end'
         | 'while' method_call 'do' body 'end'
method_call: method_name
           | method _name '(' args ')'

メソッド呼び出しに加えて if と while の2つの条件文が追加された文です。この文法に対して、以下のような文字列が与えられたとします。

if valid? do save! end

この時、 valid? まで読み込んだ状態を考えてみましょう。この後に do が来ないということは我々人間は容易に予測できます。過去に if を読み込んでいるので、while から始まる RHS にしか含まれない do が来ることはあり得ないわけですね。
よってこの時点で例外を投げることが理想的なのですが、LALR の Look-ahead Set は文法全体を元に計算されています。したがって、 単純に「method_call の後ろに do が来ることはあり得るよね」と解釈します。後は先程の原則に従い、Reduce を選択してしまいます。
この例の場合、上記の Reduce を行ったとしても最終的にはエラーを返すので、パースできないという結果は変わらないのですが、LALR の先読みの問題が分かる良い例になっているかと思います。

上記の例は parser の外部から見た挙動には影響しないものでしたが、中には parser の実行結果に直接影響を与えるような問題もあります。例えば以下のような文法規則があったとします。

S: 'a' A 'a'
 |'b' A 'b'
A: 'a'
 |'a' 'a'

この文法に対して以下のような文字列が与えられたとします。

baab

この時、最初の ba までを読み込んだ状態を考えてみましょう。parser は次のトークンである a を Shift することもできますし、a を Reduce して非終端記号 A を得ることもできます。 のときに Shift を行わないとパースできなくなってしまうため、この Conflict（競合）がパース結果に影響を与えることになります。

状態と Mysterious Conflict

このような Conflict のうち、LALR のアルゴリズムが起因して発生する Conflict として Mysterious Conflict というものがあります。IELR ではこの Mysterious Conflict を解消する事ができます。 ここでは Mysterious Conflict を理解するために必要な parser における状態の扱いと、 Mysterious Conflict の種類について見ていきましょう。

parser の同値性や挙動を分析するためにオートマトンを考えることがあります。LR parser では、ある入力系列に対して「どの文法規則のどこまでを読み込んでいる可能性があるか」を 状態 として表現します。ここではこの状態の扱いにのみ着目して、parser 生成のアルゴリズムを見ていきます。(厳密な定義は避け、アイデアベースで紹介を行いますのでご了承ください)

Canonical LR と LALR の違い

Canonical LR

Canonical LR オートマトンは素朴に状態を扱います。状態を区別する要素として：

  1. 文法規則のどこまで読み込んでいるか
  2. Look-ahead Set

の両方を考慮します。これにより精密な状態遷移が可能になりますが、当然状態数は膨大になります。

LALR

LALR では、状態数削減のために：

  1. 同じコア（文法規則のどこまで読み込んでいるか）を持つ状態をマージ
  2. Look-ahead Set は和集合にする

という方法を取ります。これにより状態数は大幅に削減されますが、新たな問題として「Mysterious Conflict」が発生する可能性があります。

以下に簡単な例を示します：

S: a A a
 | b A b
A: a
 | a a

この文法上で適当な文字列の先頭から a を読み込んだとき、それぞれのアルゴリズムで対応する可能性のある状態を見てみましょう。

Canonical LR では、以下のような状態が考えられます：

※ 図中の • は現在の読み込み位置を示します。
また、{...} で囲まれたアルファベットの集合は Look-ahead Set を示します。

状態1:
  A: a • , {a}
  A: a • a, {a}
状態2:
  A: a • , {b}
  A: a • a, {b}

Look-ahead Set を考慮した状態の切り分けがされている事がわかります。

一方、LALR ではコアが同じ状態をマージするので、次のようになります：

状態3（状態1、2 マージ後）:
  A: a • , {a, b}
  A: a • a, {a, b}

このようにして状態数を削減することができます。

一方で、この操作が文法規則と Look-ahead Set の対応関係を曖昧にしてしまうことがあります。 これにより、Mysterious Conflict という問題が発生する場合があります。

例えば上述の例ですと、状態2は Conflict を持っていませんが、状態1は a に対する Shift/Reduce Conflict を持っています。この2つの状態がマージされることで、状態3は a に対する Conflict を持つようになってしまいます。これが典型的な「Mysterious Invasive Conflict」の例です。元々 Conflict していなかった状態が、他の Conflict を持つ状態とマージされたことで、Conflict に「侵入」されてしまったのです。

他にも以下のような Mysterious Conflict の例があります。

Mysterious New Conflict

Conflict を持たない2つの状態がマージされることで、新たに Conflict が発生することがあります。状態のマージによってどの Look-ahead Set の要素がどの文法規則に対応するかが不明瞭になってしまうことによる Reduce-Reduce Conflict が発生するようなケースです。例えば以下のような文法規則があったとします。

S : a C d
  | b C e
C : c
D : c

この文法において、文字列 c を読み込んだ状態を考えてみましょう。
Canonical LR では：

状態1:
  C : c • , {d}

状態2:
  C : c • , {e}

状態3:
  D : c • , {d}

各状態で個別に見ると、 Conflict は発生しません。
しかし LALR においては：

状態1（状態1、2、3 マージ後）:
  C : c • , {d, e}
  D : c • , {d}

ここで、次のトークンが d の場合、C に還元すべきか D に還元すべきかが不明瞭になり、Reduce-Reduce Conflict が発生します。これが「Mysterious New Conflict」です。

Mysterious Mutated Conflict

他にも、Conflict を持つ状態同士がマージされる事象も発生します。最初から Conflict しているなら分解してもマージしても一緒なのでは？と思われるかもしれません。問題点としては、Conflict の原因が曖昧になってしまうことが挙げられます。Mysterious New Conflict と同様文法規則と Look-ahead Set の対応関係が失われてしまうため、何が起因して Conflict が発生しているのかがわからなくなってしまいます。これが「Mysterious Mutated Conflict」です。

IELR のアイデア

IELRは、LALR が抱える Mysterious Conflict の問題を解決するためのアルゴリズムです。
方針は実直なものであり、LALRの手法で状態のマージを行った後に、Mysterious Conflictを検出し、可能であればその状態を分割し直す、というものです。これを実装するための基本的なアイデアとして以下のような処理が説明されておりました。

  1. Conflict が発生している状態を検出し、その情報を annotation として前状態に伝搬する。
  2. 初期状態から Look-ahead Set の再計算を行い、反対方向に伝搬する。
  3. 伝搬された Look-ahead Set が基の Look-ahead Set と 互換性 を持たない場合、状態の分割を行う。

実装のイメージはスライドの図の可読性が高いのでそちらを参照していただければと思います。

speakerdeck.com

ここで言う互換性とは、「Look-ahead Set による Conflict が遷移前も同様に発生しているのかどうか」という概念であるようです。例えば先ほどの Mysterious Invasive Conflict の例で考えてみると、LALRのマージされた状態に遷移してくる前の状態として、以下のような2つの状態が考えられます。

1つ目は一文字目に a を読み込んだ状態、

S: 'a' • A 'a', {'#'}
A: • 'a', {'a'}
A: • 'a' 'a', {'a'}

2つ目は一文字目に b を読み込んだ状態です。

S:'b' • A 'b', {'#'}
A: • 'a', {'b'}
A: • 'a' 'a', {'b'}

ここで、マージされた状態で発生している a が Look-ahead Set の要素であることによる Shift/Reduce Conflict は、同様に1つ目の状態でも発生していることが分かります。この時、「2つの状態の Look-ahead Set には互換性がある」とします。
反対に2つ目の状態については a が入力として与えられても Shift を行うだけですから、次状態との Look-ahead Set の互換性はないとされます。完全に状態のマージに巻き込まれただけというわけです。よって状態の分割を行い、Mysterious Invasive Conflict が解消される、というわけですね。

実装面の問題

アルゴリズムの全体像は述べた通りですが、実装面では実行時間に課題がありました。始めは parser 生成がそもそも終了しなかったようです。

1. annotation のループ

オートマトン上で閉路があると、annotation の伝搬が無限ループに陥ってしまいます。これは annotation のフラグを用意することで解決されたようです。これにより parser 生成が終了するようにはなりましたが、実行に 1−2 時間を要しており、さらなる高速化を行ったとのことでした。

2. 高速化

Look-ahead Set の計算時間は大きいようで、いくつかのキャッシュとなる変数の導入やし、LALR のアルゴリズムでも利用されている SCC (強連結成分分解) を利用することで高速化が実現されたようです。

3. 不要なアノテーションの削除

先ほどの紹介では annotation の付与は Conflict が発生した状態の前状態を辿って伝搬されていく形でした。しかし、実際には Conflict の原因となっている状態にのみ annotation を付与していけば十分であることが分かります。実装中では Conflict の原因となるアクションに関係があるかどうかを検証した上で annotation を付与するようにしたようです。(ここについても前述のスライドがビジュアライズされていてわかりやすかったです)

展望

1. 速度改善

上述の高速化を伴いプログラムの実行時間は 1 分程に短縮することができました。今後はこれをさらに高速化することが一つの目標として挙げられていました。

2. do の識別

また、「こんなことができるのではないか？」というアイデアとして、do キーワードの識別が挙げられていました。Ruby における do という文字列は予約語でありますが、対応するトークンは4つ存在します。(条件文の do、ブロック文の do、ラムダ式の do、、、といった具合でコンテキストを lex_state によって識別し、異なるトークンとして切り出しているようです)これは文脈によってある程度予測可能なものであると推測されており、IELRの strict な Look-ahead Set の計算を利用することで、lex_state を利用しない do の識別が可能になるのではないか？というアイデアが語られていました。

感想

昨年の発表と合わせて非常に面白かったと感じました。昨年の発表で理解できていなかった Mysterious Conflict の話が大まかに理解できたので嬉しい気持ちになりました。 また昨年コードベースで紹介された IELR の実装がアイデアベースで紹介され、素人の私でもわかった気になれる内容で楽しかったです。do キーワードに関する展望に関しても、 parser のこれまでの lex_state の問題と地続きな内容が語られており、今後が非常に楽しみです！ロードマップに記載のある Scannerless parser、ひいては parse.y Under graduate までの道のりについても一層楽しみになりました！

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

jp.techouse.com