はじめに
こんにちは、株式会社 Techouse でエンジニアをしている @miyatis です。
先日開催された RubyKaigi 2026 で、@yui_knk さんがセッションを発表されました。 本記事では「Kingdom of the Machine: The Tale of Operators and Commands」というその内容について紹介します。
本セッションは、Ruby のパーサにまつわる議論に踏み込んだ内容です。 Ruby は長らくパーサジェネレータを使っていましたが、近年 Prism という手書きパーサが登場し、Ruby 3.4 以降のデフォルトになっています。 本セッションでは手書きパーサが内包する複雑性を一貫して主張しています。 本ブログではその前提知識となるパーサや文法理論について説明した後、手書きパーサの複雑性について解説します。
1. パーサとは
そもそもパーサとは何でしょうか。 まず以下のような Ruby スクリプトがあるとします。
puts 1 + 2
これは機械からするとただの文字列でしかないので、まずはトークン列に分解します。
[on_ident] [on_int] [on_op] [on_int] "puts" "1" "+" "2"
その後、このトークン列が文法として正しいかを判定します。 パーサはこの判定を担います。 では、この判定はどのように行っているのでしょうか。 それを知るためには、まず文法とは何かを説明します。
文法とは
文法を簡単に説明すると、言語を生成する規則のことです。 この規則を文法規則と呼びます。 文法規則を記述する代表的な記法として BNF（バッカス・ナウア記法） があり、本記事でも以降この記法を用います。 例えば、四則演算の文法を BNF で書くと、以下のようになります。
S ::= E
E ::= E + E
| E - E
| E * E
| E / E
| number
ここで S は開始記号と呼ばれ、文法規則を適用していくときの出発点になります。
S ::= E は「S は E に展開される」という規則で、これを起点に E の規則を繰り返し適用していくことで、具体的な式が生成されます。
E の規則は、「式とは『式 + 式』『式 - 式』『式 * 式』『式 / 式』のいずれか、あるいは数値である」という定義です。
ここで使われている記号は、大きく 2 つに分類できます。
- 終端記号 (terminal symbol) — それ以上展開できない記号。BNF の例で言えば
+ - * /やnumberといったトークン。 - 非終端記号 (nonterminal symbol) — 文法規則によって他の記号列に展開される記号。上の例で言えば
SやEといった記号。
では実際に、開始記号 S から出発して 1 + 2 を生成してみましょう。
1 + 2 の場合
開始記号 S から文法規則を順に適用していきます。
S → E （規則 S ::= E を適用） → E + E （規則 E ::= E + E を適用） → number + E （左の E に規則 E ::= number を適用） → 1 + E （number を 1 に） → 1 + number （右の E に規則 E ::= number を適用） → 1 + 2 （number を 2 に）
四則演算の文法とは、こうして生成できる式すべての集合を定めているわけです。
では逆に、与えられたトークン列がこの文法に含まれるか（＝文法的に正しいか）はどう判定するのでしょうか。
2. LR パーサとは
パーサには様々な種類がありますが、代表的なものは LR パーサ（Left-to-right, Rightmost derivation） です。 LR パーサは左から右へとトークンを読んでいって、文法規則を逆方向に適用していきます。 この操作を繰り返して、最終的に開始記号が得られたら文法的に正しいと言うことができます。
また、LR パーサはスタックを使って動作し、以下の 2 つの操作によって解析を進めます。
- shift — 次のトークンを読み進め、スタックに積む操作。
- reduce — スタックの先頭が文法規則にマッチしたら、まとめて置き換える操作。
例えば、1 + 2 の場合は以下のように進みます。
スタック 残りトークン 操作 [] [1, +, 2] （初期状態） [1] [+, 2] shift [E] [+, 2] reduce（1 → E） [E, +] [2] shift [E, +, 2] [] shift [E, +, E] [] reduce（2 → E） [E] [] reduce（E + E → E） [S] [] reduce（E → S）
このようにして、スタックに対して shift/reduce を繰り返すことで、開始記号 S が得られたため、1 + 2 は文法的に正しいと言えます。
1 + 2 * 3 の問題：shift/reduce コンフリクト
次に 1 + 2 * 3 の場合を考えてみましょう。
しかし、この場合は単純にはいきません。
以下のように処理が進みます。
スタック 残りトークン 操作 [] [1, +, 2, *, 3] （初期状態） [1] [+, 2, *, 3] shift [E] [+, 2, *, 3] reduce（1 → E） [E, +] [2, *, 3] shift [E, +, 2] [*, 3] shift [E, +, E] [*, 3] reduce（2 → E）
次の操作として、2 つの選択肢が発生します。
- reduce —
E + Eを今すぐEに reduce する。 - shift —
*を shift して、スタックに積む。
1 の場合は、1 + 2 の reduce が先に行われるため、(1 + 2) * 3 として解釈されます。
対して、2 の場合は 2 * 3 の reduce が先に行われるため、1 + (2 * 3) として解釈されます。
どちらにすべきでしょうか。これを shift/reduce コンフリクトと言います。 LR パーサはこのコンフリクトをどう解決するかを、あらかじめ決めておきます。 具体的にどうやって対応しているかはパーサごとに異なるため、以降では具体的にパーサジェネレータや手書きパーサの動作について確認していきましょう。
3. パーサジェネレータ
パーサジェネレータは、第 1 章で紹介した BNF で記述した文法規則を入力として受け取り、LR パーサを自動生成するツールです。
shift/reduce コンフリクトの解決
先ほどのコンフリクトをどのように解決しているのでしょうか。 パーサジェネレータでは、優先順位指定を追加することで解決できます。
%left '+' %left '*'
後に書いた演算子ほど優先順位が高くなるため、* は + より強くなります。
これにより、パーサは + と * を比較して、より強い * を shift し、expr + expr の reduce を後回しにします。
そして重要なのは、コンフリクトが発生したことをパーサジェネレータが検出して報告してくれる点です。 文法に曖昧さがあれば、パーサ生成時に気づけます。
4. 手書きパーサの登場
パーサジェネレータは強力ですが、実は Ruby 3.4 以降ではデフォルトのパーサは Prism という手書きパーサです。 Prism の README では、次のように説明されています。
Prism is a portable, error tolerant, and maintainable recursive descent parser for the Ruby programming language.
つまり「移植性が高く、エラー許容性があり、保守性が高い」再帰下降パーサです。 Prism は以下のように、再帰下降で構文解析します。
1 + 2 + 3 を解析する場合、次のような再帰的なコードで表現できます。
def parse_expression left = parse_number # まず数値を読む if next_token == '+' read('+') # + を読む right = parse_expression # 再帰的に右辺を読む return Add(left, right) end return left end
binding power による優先順位の表現
では先ほどの 1 + 2 * 3 のような演算子の優先順位はどう扱うのでしょうか。Prism は Pratt parsing という手法を使用しています。
Pratt parsing の核となる概念として、binding power というものがあり、これによって演算子の優先順位を決定しています。
各演算子に「左結合力」と「右結合力」を設定します。
| 演算子 | 左結合力 | 右結合力 |
|---|---|---|
| + | 10 | 11 |
| * | 20 | 21 |
右辺を読み続けるかどうかを、次の演算子の左結合力と現在の右結合力を比較して決めます。
1 + 2 * 3 をパースする場合を考えます。
1 + 2 まで読んだ時点で、次に現れる * の扱いを判断します。
ここで、2 のトークンの右側の演算子（*）の左結合力と、左側の演算子（+）の右結合力を比較します。
* の左結合力（20）が + の右結合力（11）より大きいので、* 側に読み進めると判断します。
結果として 1 + (2 * 3) と正しく解釈されます。
5. 手書きパーサは本当に良いのか
Pratt parsing は、演算子の優先順位を簡潔に表現できるのが強みです。 また、BNF 記法のような文法理論を知る必要もなく、一見扱いやすく見えます。 しかし実態としては、文法と内部実装が混ざることで複雑性が発生し、保守性が低下しているのではないかという疑いがあります。 実際の例を見ていきましょう。
問題 1：文法理論の再発明（FIRST 集合）
Ruby には、文脈によって解釈の変わる曖昧なトークン列があります。
例えば 1... という構文は、後続トークン次第で 2 つの解釈ができます。
Prism では 1... の後のトークンが式の先頭になり得るのであれば、1... を Range と判断します。
なり得なければ、1... を Endless Range と判断します。
この判定を担っているのが、token_begins_expression_p という関数です（src/prism.c）。
static PRISM_INLINE bool token_begins_expression_p(pm_token_type_t type) { switch (type) { case PM_TOKEN_EQUAL_TILDE: // ... 多数のトークンタイプを列挙 return false; default: return true; } }
実は文法理論には、この関数に対応する概念があります。FIRST 集合です。スライドでは次のように定義されています。
The FIRST set of a nonterminal or production is the set of terminal symbols that may appear at the beginning of a string derived from it.
日本語に訳すと、次のような内容です。
ある非終端記号や生成規則 (production) から導出される文字列について、その先頭に現れうる終端記号の集合。
ここで関係するのは「式」という非終端記号の FIRST 集合です。これに属するトークン（終端記号）こそ、token_begins_expression_p で true を返すべきトークンです。
パーサジェネレータではこれが BNF から自動的に計算されます。開発者が書く必要はありません。
しかし手書きパーサでは、token_begins_expression_p として手動で実装しています。
手書きパーサは、文法理論を避けているようで、実装内部では既存の文法理論を再発明してしまっているのです。
加えて、Ruby に新しい式を追加するたびにこの関数を更新する必要があります。 更新を忘れれば、サイレントなバグになります。
パーサジェネレータでは、FIRST 集合は BNF から自動的に計算されます。 開発者は文法規則を書くだけでよく、新しい式の種類を追加しても FIRST 集合の更新を意識する必要はありません。
問題 2：binding power の限界
binding power はシンプルで強力な仕組みです。しかし文脈によって優先順位が変わる場合には対応できません。
Ruby には実際にそういうケースがあります。
例えば、rescue は以下の 2 つの文脈において、優先順位が変わります。
通常時であれば、優先順位は rescue < and であるため、and が先に結合します。
f(1, 2) rescue a and b #=> f(1, 2) rescue (a and b)
ですが、Endless Method（def m = ... の形式の定義）の中では、この優先順位が逆転し、rescue > and になります。
def m = f(1, 2) rescue a and b #=> (def m = f(1, 2) rescue a) and b
単純な binding power の比較では、こうした文脈依存の優先順位を表現できません。
結果として、実装者は binding power の外側に追加のロジックを書かざるを得ず、コードは複雑になります。
パーサジェネレータでは、BNF で文脈ごとに別の文法ルールを定義することで、こうした優先順位の切り替えを表現できます。
問題 3：文法の曖昧さを検証できない
セッションのスライドには「Grammar is a living thing（文法は生き物）」と題したページがあり、次のように述べられています。
There are always some people who want to add new grammar. One of the points that comes up in such discussions is whether adding that grammar is syntactically sound. In other words, whether it introduces ambiguity.
日本語に訳すと、次のような内容です。
新しい文法を追加したい人は常に存在します。そうした議論において焦点となるのは、追加する文法が構文的に健全であること、すなわち新たな曖昧さを生まないかという点です。
Ruby の文法は今後も変わり続けます。 新しい文法を追加するたびに、その曖昧さの検証が必要となります。
パーサジェネレータなら、BNF を変更するたびに shift/reduce コンフリクトとして曖昧さが自動的に検出されます。
手書きパーサにはこの仕組みがありません。文法の変更が曖昧さを生んでいても、テストで踏むまで気づけません。
パーサジェネレータと Pratt parser の比較
ここまでの議論を整理すると、両者の違いは以下のようにまとめられます。
| 観点 | パーサジェネレータ | Pratt parser（手書きパーサ） |
|---|---|---|
| 文法の記述 | BNF で宣言的に記述 | 再帰下降のコードで手続き的に記述 |
| 優先順位の表現 | %left / %right ディレクティブ |
binding power |
| 文脈依存の優先順位 | 文脈ごとに別の文法ルールを定義可能 | binding power の外側に追加ロジックが必要 |
| FIRST 集合 | BNF から自動計算 | 手動実装（更新漏れがサイレントなバグになる） |
| 文法の曖昧さ検出 | shift/reduce コンフリクトとして生成時に検出 | 検出機構なし（テストで踏むまで気づけない） |
| 学習コスト | BNF と LR 解析の理論を要する | 一見低いが、複雑なケースでは文法理論の概念を結局再発明する |
総じて、Pratt parsing で形式化されている理論は binding power による優先順位の扱いまでです。 FIRST 集合や曖昧さ検出、文脈依存の優先順位といった問題は、実装側で個別に対応することになります。
Ruby は文法が複雑です。そのため、文法理論の概念を実装内部で再発明する場面が出てきます。
まとめ
今回のセッションを通じて、手書きパーサとパーサジェネレータの違いを理解できました。
また、アフターパーティーで発表者の金子さんとお会いしたり、セッションに関する質問をさせていただいたりするなど、非常にありがたい体験になりました。 RubyKaigi に参加するのは 2 回目ですが、Ruby コミッターの方とのコミュニケーションを通じて、前回よりも Ruby コミュニティを実感できました。
Techouseでは、社会課題の解決に一緒に取り組むエンジニアを募集しております。 ご応募お待ちしております。
