はじめに
株式会社 Techouse でエンジニアをしております、kai と申します。 今回は RubyKaigi 2026 の一日目のセッションから、ydah さんの「Liberating Ruby's Parser from Lexer Hacks」について内容を紹介します。
セッションでは Ruby parser を長らく支えてきた lex_state が取り除かれるまでの経緯が語られました。ただし主題は lex_state を取り除いたこと自体ではなく、これまで一括りにされてきた Ruby 文法の曖昧性が 6 つの層に類型化され、そのほとんどが LR parser の枠組みのうちで解消可能であると解明されたことに置かれていました。
本記事は ydah さんのセッションを私なりに咀嚼したものです。前半では lex_state や LR parser、PSLR の前提を扱っています。後半では ydahさんが示された 6 層の分類に沿って、Ruby の曖昧性を辿ります。前半部が大分長くなってしまったので、セッション内容については「Layer 1-3」のセクションからお読みください。
Ruby の文法の難しさ
Ruby は他の言語と比較して文法が直感的で、自然言語のようにコードを書けるというのが魅力の1つだと考えています。
Ruby 公式ウェブサイト にも、以下のような記載があります。
Rubyはシンプルで直感的な文法を持っており、コードが自然な文章のように読めます。 複雑な記号や冗長な記述を排除し、書きたいことをそのまま表現できる設計思想が貫かれています。 無駄な記述が少なく、可読性が高いため、初心者にも優しく、経験豊富な開発者にとってもメンテナンスしやすい言語です。
また、別の箇所では次のように述べられています。
Rubyは表現力豊かな文法により、複雑なロジックも簡潔に記述できます。
「A Programmer's Best Friend」 というキャッチフレーズが示すように、人間が自然に扱いやすい文法を備えていることは、言語思想の根幹のひとつだと考えています。
一方で、こうした直感的な文法を実現するため、Ruby の parser 実装は複雑になっています。その複雑性の解消は近年の RubyKaigi における parser 関連セッションの主要テーマのひとつでした。複雑性の一因として本セッションで取り上げられたのが 曖昧性 です。
たとえば * という記号は、Ruby のソースコード中で文脈に応じて次の 3 種類の token として扱われます。
| 文脈 | 例 | token |
|---|---|---|
| 二項演算子 | a * b |
'*' |
| Splat | foo *args |
tSTAR |
| Rest Parameter | def f(*a) |
tSTAR |
どれも同じ * ですが、掛け算の演算子か、引数展開か、Rest Parameter かは前後の状況で決まります。教科書的な lexer は文脈に依存せず文字列を token に切ることができるとされています。一方 Ruby では parser の状況を lexer から覗かないと、どのように tokenize するか決められないのです。
このような曖昧性は Ruby 文法の複雑性を示す実例としてしばしば取り沙汰されてきました。ydah さんはセッション冒頭、これらの主張を引用された上で、次のように問題を再定義されました。
Ruby's grammar is ambiguous.
...well, that's not quite right.
Where is Ruby's grammar ambiguous — and why?
— slide 2, 3
「曖昧」として一緒くたにせず、どこが曖昧なのか、なぜ曖昧なのか を類型化することに取り組まれたのです。
lex_state の役割
類型化が求められた背景には、これまでの実装における曖昧性の扱いがあります。
Ruby は文法の曖昧さに対して lex_state という 13 bit の状態フラグで対処してきました。
/* parse.y */ enum lex_state_bits { EXPR_BEG_bit, /* ignore newline, +/- is a sign. */ EXPR_END_bit, /* newline significant, +/- is an operator. */ EXPR_ENDARG_bit, /* ditto, and unbound braces. */ EXPR_ENDFN_bit, /* ditto, and unbound braces. */ EXPR_ARG_bit, /* newline significant, +/- is an operator. */ EXPR_CMDARG_bit, /* newline significant, +/- is an operator. */ EXPR_MID_bit, /* newline significant, +/- is an operator. */ EXPR_FNAME_bit, /* ignore newline, no reserved words. */ EXPR_DOT_bit, /* right after `.', `&.' or `::', no reserved words. */ EXPR_CLASS_bit, /* immediate after `class', no here document. */ EXPR_LABEL_bit, /* flag bit, label is allowed. */ EXPR_LABELED_bit, /* flag bit, just after a label. */ EXPR_FITEM_bit, /* symbol literal as FNAME. */ EXPR_MAX_STATE };
ruby/ruby internal/ruby_parser.h#L60-L75
コメントにある通り、各ビットは tokenize の判断基準を lexer に提供します。
判断基準には、
- 改行を有意に扱う
+/-を符号扱いするか二項演算子扱いする- 予約語を予約語として扱う
などがあります。
parser はこれらのフラグを適宜更新し、lexer はその値を頼りに次の token を切り出します。
Ruby は教科書的な字句・構文解析を逸脱し、lex_state を通じて parser の状態を lexer に伝えることによって、柔軟な文法を実現してきました。これは Lexer Hack と呼ばれる workaround であり、Ruby parser はこの仕組みに長らく支えられてきました。
lex_state の問題
その一方で、lex_state は構造的な問題を抱えています。ydah さんはセッション中、その問題を次のように述べられました。
"We're in EXPR_BEG, so * is a splat." — OK.
But why is this EXPR_BEG?
Why is * a splat here and multiplication there?
lex_state gives the verdict but doesn't distinguish the cause.
— slide 17
lex_state は単なる parser と lexer の仲介役ですから、「今どのような状態にいるか」という情報のみを提供します。lexer はこれを見て tokenize の判断 (verdict) はできますが、なぜその状態にいるのかという原因 (cause) は理解できません。これは lex_state が単なる bit flag であることに由来します。lex_state を更新する処理は値だけを書き換え、「どの規則のもとで、どんな意図で parser の状態が変わったのか」を記録する機構を持ちません。状態遷移の仕様はコード上に明示されず、個々の代入による暗黙の仕様としてしか存在しなくなります。
この構造に起因する技術的問題を ydah さんは 3 つ挙げられました。
3 technical problem
01 Tight Coupling
The lexer depends on parser internals. Changes ripple unpredictably.
02 Poor Maintainability
One fix can break something else. Regression-prone.
03 Hidden Semantics
Language semantics are buried in lexer-state logic
— slide 18
実際に現行 master (5faeea8) の parse.y で SET_LEX_STATE の呼び出し箇所を数えてみると、のべ 105 箇所に達します。
$ grep -c SET_LEX_STATE parse.y 105
加えて、これらの書き換えは parser 側に閉じていません。SET_LEX_STATE は文法規則中のアクションだけでなく lexer 側からも呼ばれており、lexer 自身が自分の状態を書き換えています。parser → lexer の情報伝達という責務を超え、汎用の状態書き換え機構として拡張的に使われているのです。
結果として、parse.y を読み解くには文法規則だけでは足りません。各所に散らばる手書きの状態更新と、その各々が前提とする参照箇所まで追うことが求められます。文法定義と暗黙の state machine が密結合した事で、可読性が大きく損なわれています。
ydah さんはこれに加えて、次のような問いも投げかけられています。
Among the ambiguities lex_state resolves, aren't some of them not actually ambiguous in the grammar?
— slide 19
lex_state は parse.y においてどこからでも参照・更新が可能なため濫用され、文法上は本来曖昧でない場合にさえ利用されてしまっている、と問題提起をされています。
加えて、lex_state は以下の性質の異なる 3 種の問題を、区別せずに扱っているとも指摘されています。
Genuinely grammatical ambiguity
LALR compression artifacts
Semantic issues
lex_state doesn't distinguish between them. It treats all three the same way.
— slide 20
今回のセッションで、前述した本来は文法上曖昧でないものを 3 層、曖昧ではあるが性質の異なるものを 3 層、lex_state の担ってきた役割を計 6 層に分類されました。
| 層 | メカニズム | lex_state での扱い |
|---|---|---|
| 1 | 現在の state の action table を直接引く | EXPR_FNAME 等のフラグ参照 |
| 2 | 空文字規則の reduce 連鎖を辿る | default reduce の裏で曖昧化 |
| 3 | parser stack を pop した先を引く | reduce 後 state までは見えていない |
| 4 | pseudo-scanner で正規表現照合 | IS_LABEL_POSSIBLE 等の手書き分岐 |
| 5 | Lexer Context による state 分裂 | IS_BEG() / EXPR_BEG 等で判別 |
| 6 | local variable table の参照 | LAST_TOKEN_* (4 値) で残存 |
Lrama では PSLR を導入することでそれぞれに対し lex_state に依存しない別解を与え、lex_state の排除に成功しています。以降では各層の性質と lex_state での対応、PSLR による対応を見ていきます。
各層の解説の前に、まず PSLR の根幹となるアイデアを説明します。
PSLR とは
PSLR は Pseudo-Scannerless Minimal LR(1) の略称です。Lrama のメイン開発者 kaneko.y さんが 2023 年の parse.y ロードマップ で parse.y for Under graduate と称され、1 つのゴールに掲げられた目標です。
PSLR のアイデアについて、セッション中では以下のように述べられました。
The lexer can ask before returning a token: "If I return this token, will the parser accept it?"
— slide 24
If the parser's LALR state already knows which tokens could come next, there's no need for the lexer to maintain its own state.
— slide 26
従来の Ruby においては lex_state を介して parser の状態を lexer に伝える、という方式を採用しておりました。parser の状態に応じた振る舞いの変更は、lexer 側で各所に実装されていました。
しかし、本来 parser の状態はより多くの情報を持っています。それを利用すれば「現在の parser state で syntax error にならない token の集合」は導出可能です。PSLR では lexer が tokenize の前に毎度これを parser に問い合わせます。parser で受け入れ可能な token 集合の中から切り出す token を選択する、という挙動を実現します。
受け入れ可能な token の情報を parser から直接得られるため、lexer 側で parser の状態を確認して振る舞いを変える挙動自体が不要になります。lex_state もお役御免となり、随所に lex_state の更新と参照が記述された従来の parse.y を刷新し、可読性とメンテナビリティを向上させることが出来るのです。
LR parser の基本動作
ここからは PSLR の実装を理解するための前提知識を整理した上で、基礎的な実装を見ていきます。
※ 本レポートでは LR parser の基本用語の定義には踏み込みません。詳細は以下の資料をご参照ください。
lexer、parser の基本動作
Ruby の構文解析と字句解析は次のループで進みます。
- parser は次の token を lexer に要求する
- lexer は入力文字列から token を 1 つ切り出して返す
- parser は現在の state と token から、action table を引いて挙動を決定する
action table とは parser state × token の 2 次元表で、各セルに shift か reduce の action が記述されています。
| state/token | + |
* |
( |
tIDENT |
... |
|---|---|---|---|---|---|
| state 5 | shift 8 | error | shift 12 | error | ... |
| state 17 | error | shift 31 | error | error | ... |
| state 23 | reduce 4 | reduce 4 | reduce 4 | reduce 4 | ... |
| : |
action 以外には accept と error があり、accept は受理、error は構文エラーを表します。いずれもループの終了条件であり、accept または error に至るまで、上記 1-3 を繰り返します。
parser stack
LR parser は parser stack に state を積みながら入力を読み進めます。
shift は「token T を読み込み次の state に遷移する」action であり、parser stack に対し現在の state S の上に次 state S' を push します。
reduce は「規則 R の右辺長分の state を parser stack から pop し、GOTO 表で計算した次 state S' を push する」action です。下図は R: X → Y Z の場合で、Y と Z に対応する stack 上位 2 個の state を pop した後、GOTO 先の S' を push しています。
action table のセルに reduce R が入っていることは、その state では R の reduce 項目の lookahead 集合に対応 token が含まれることを表します。これは「R で reduce した後の処理を続ければ、最終的にその token を shift できる」ことを保証する記述です。
lexer から parser への問い合わせ
PSLR の lexer から parser への問い合わせには、先ほどの action table を利用します。
action table はこれまで、parser が token を受け取った後の action の選択のために利用されてきました。PSLR ではこれを lexer が token を切り出すタイミングで再利用し、parser が処理可能な token のみを切り出す動作を実現します。これにより lex_state を参照せずとも切り出すべき token を判断できるようになります。
ydah さんはこれを次のように整理されました。
The parser's action selection after receiving a token
— repurposed as a question before returning it. This is the core of PSLR.
— slide 30
例えば * を受け取ったとき、2 つの候補 token (* / tSTAR) について順に「もしこの token を返したら現在の parser は action を取れるか」を問い合わせます。ちょうど 1 つだけ action が定義されている候補を答えとして採用します。
Lrama では、この仕組みは yy_state_accepts_token という自動生成関数として実装されています。中身を読むために action table の圧縮構造について説明します。
action table の圧縮構造
action table は愚直に確保すると parser state 数 × token 数分のセルが必要になり、膨大なメモリ領域を必要とします。これを避けるため Bison や Lrama は yytable / yypact / yycheck / yydefact の 4 本の配列で action table を圧縮します。本節の整理は ruby/lrama の Compressed State Table ドキュメント に基づきます。
まず action table を1次元配列 yytable に並べます。各 state の行を順に連結し、yytable のセルには次の値を格納します。
- shift action: 遷移先 state id (正数)
- reduce action: 規則番号(shift の state id と衝突しないように負数で表現)
- syntax error:
YYTABLE_NINF
state ごとの開始位置は yypact[S] で保持します。これにより state S で token T を受けたときの action は yytable[yypact[S] + T] で取得できる形になります。
ただし、1次元化しただけでは必要とするセル数は変わりません。そこで yydefact で圧縮します。
各 state について「この state では多くの token に対してこう動く」というデフォルトの挙動をひとつだけ選び、それを yydefact[S] に格納します。デフォルトの挙動は次のいずれかから選ばれます。
- reduce: lookahead 集合が最も大きい reduce 規則 (= 最も多くの token を担当する規則) を選び、
yydefact[S]にその規則番号を入れる - error: 上記の reduce が選べない state では、
yydefact[S]に0を入れて syntax error 扱いとする
yytable 側からは、このデフォルトの挙動と一致するセルを省略します。これで sparse な行が圧縮されます。
ただし、この圧縮では問題が生じます。state S のデフォルト挙動に対応する token T' を受けて yytable[yypact[S] + T'] にアクセスする場面を考えます。T' に対する挙動は yydefact[S] に集約されて yytable 側では省略されており、その位置には他の state の entry が重なって入っている可能性があります。これでは state S の token T' 用 entry なのか、別 state が同じインデックスに置いた値なのかを区別できません。
![yycheck で `yycheck[i] ≠ T'` のとき異なる state の値とみなして token を判別する](https://res.cloudinary.com/dyjw65doo/image/upload/v1778420770/RubyKaigi-2026-ydah_-day1/yycheck.png)
この判別のために yycheck を利用します。yytable[i] が本来どの token 用の値かを yycheck[i] に記録しておきます。yycheck[yypact[S] + T'] == T' が成り立てば yytable の値を採用します。不一致なら state S の token T' は省略されたデフォルト挙動だったと判断して yydefact[S] にフォールバックします。
なお、デフォルト挙動以外を持たない state (全 token がデフォルト挙動を取る state) については、そもそも yytable 側に固有の entry がありません。この場合は yypact[S] に特別値 YYPACT_NINF を入れておき、yytable へのアクセスを省略して直接 yydefact[S] を引かせます。
また、default reduce による圧縮は parser の判定結果には影響しませんが、state machine としての動作に若干の差分が生じます。yydefact として reduce が選択された state S で、token T が syntax error になる場合の挙動を、圧縮前と後で比較します。
圧縮前は、state S で token T を受け取った時点で action table を参照し、即座に syntax error を返します。
圧縮後は、state S では syntax error を返さず default reduce を発火させます。ただし reduce → goto を経た先の state では、token T はその state の lookahead に含まれないので syntax error として判定されます。結果として不正な入力を誤って受理することはありません。
yy_state_accepts_token
これらを踏まえて関数本体を読みます。
int yy_state_accepts_token (int yystate, int yychar) { yysymbol_kind_t yytoken = YYTRANSLATE (yychar); int yyn = yypact[yystate]; if (yypact_value_is_default (yyn)) return 0; yyn += yytoken; if (yyn < 0 || YYLAST < yyn || yycheck[yyn] != yytoken) return 0; yyn = yytable[yyn]; if (yyn <= 0) return !yytable_value_is_error (yyn); return 1; }
ydah/lrama template/bison/yacc.c#L608-L625
この関数は parser の現在の state yystate のもとで、lexer が次に返そうとしている token yychar を parser が受理できるかを判定します。返り値は 1/0 でその token の受理可/否を表します。
まず yypact で state の base offset を取得します。token 番号を足してセル位置を計算し、範囲と yycheck をチェック、yytable から値を yyn に格納します。yyn が YYTABLE_NINF であれば 0 を、そうでなければ shift / reduce のいずれかに該当するため 1 を返します。
残るのは yypact_value_is_default(yyn) が真のとき、または yycheck[yyn] != yytoken のときです。いずれも yydefact にフォールバックするケースとなります。yydefact[S] が default reduce であり、かつ token T がその reduce 項目の lookahead に含まれていれば、parser は T を受理するべきです。一律で 0 を返す実装は一見不適当に見えます。
ここで yytable の reduce と default reduce の違いを整理します。前述の通り、あるセルに reduce R が入っていることと T が R の reduce 項目の lookahead に含まれることは等価でした。yytable に書かれた reduce は「lookahead に含まれる保証」とセットです。reduce 後の処理を続ければ最終的に shift されることが保証されているため、安全に 1 を返せます。一方 default reduce は yydefact 圧縮のトレードオフとして、lookahead の情報が欠落しており、yydefact[S] には規則だけが残っています。現在の state で T が lookahead に含まれるかは即座には判定できません。
yy_state_accepts_token は 現在の state で 受理可否を判定することを責務としているため、判断できないケースは accept しない側に倒し、保守的に 0 を返します。default reduce の goto 先まで辿って判定する拡張は、本関数をサブルーチンとして使う別関数で実装されており、Layer 2 以降で扱います。
この関数を通して、lexer は「現在の parser state でこの token を受理可能か」を問い合わせる能力を手に入れます。以降ではこの関数およびそのアイデアを拡張し、lex_state が対応してきた 6 層の曖昧性に対する PSLR による解法を示します。
Layer 1-3
Layer 1-3 はいずれも yy_state_accepts_token を核とした問い合わせの拡張であり、違いはその問い合わせを parser のどこまで覗くかという深さのみです。
Layer 1: 現在の state の action table を直接引く
代表例は def +(other) です。
def +(other) @value + other.value end
従来は def を読んだら lex_state の EXPR_FNAME bit を立て、そのフラグを参照して条件分岐し、+ を二項演算子ではなくメソッド名として解釈する処理をしていました。 (parse.y#L3530-L3534、parse.y#L10376-L10383)。
PSLR では yy_state_accepts_token を利用することで処理が不要になりました。def を shift した直後の state では、parser はメソッド名として許される終端記号のみを受理します。lexer は yy_state_accepts_token で二項演算子としての + が現在の parser state で受理されないことを確認し、メソッド名扱いと判断できます。
Traditionally:
SET_LEX_STATE(EXPR_FNAME)told the lexer "next is a method name."But the action table already knew.
— slide 33
ydah さんはこれを Layer 1 の整理として次のように述べられています。
These ambiguities were not ambiguous in the grammar at all.
lex_statewas unnecessarily mediating.— slide 34
この仕組みにより、(state, token) の組合せが yytable に明示的に entry を持つ場合は、その場で受理可能性を判定できます。
ただし、前述した通りこの方法は lookahead の情報が欠落している default reduce のケースでは通用しません。
yydefact にフォールバックする場合、reduce と goto による状態遷移を擬似的に追い、最終的に到達する state で token の受理可能性を確認します。これを担うのが Layer 2 / Layer 3 です。
Layer 2 では default reduce の規則が空文字規則(右辺長 0) の場合、Layer 3 はそうでない場合を扱います。
Layer 2: 空文字規則の reduce を辿った先を引く
Layer 2 は、空文字規則の reduce を辿った先の state で token の受理可能性を判定する仕組みです。
空文字規則とは右辺長 0 の規則で、reduce のときに pop が起きず、GOTO 先 state がそのまま push されます。stack 上の既存 state は取り除かれず、その上に新しい state が積まれていく挙動になります。Ruby のブロック引数 |x| は省略可能で、parse.y では opt_block_param_def という非終端記号がこの省略を空文字規則で吸収しています。
具体例として、Ruby の do の直後に * が来る場面を考えます。
[1, 2, 3].each do *a, b = [4, 5, 6] end
do を読み終えた直後、続く * を splat 演算子 tSTAR として扱いたい局面です。しかし、この時点で Layer 1 の yy_state_accepts_token(S0, tSTAR) を引くと 0 が返ります。
Layer 1 は現在の state の action table しか引きません。S0 で tSTAR を尋ねても、Sn まで辿った先で受理される可能性までは見通せず、結局「ここでは受理しない」と返してしまいます。
parse.y の該当箇所を確認します。
do_body : {
$$ = dyna_push(p);
CMDARG_PUSH(0);
}[dyna]<vars>
max_numparam numparam it_id allow_exits
opt_block_param_def[args] bodystmt
{ ... }
;
— ruby/ruby parse.y#L5283-L5302
do_body の右辺に並ぶ非終端記号はいずれも空文字規則を持っています。opt_block_param_def は先に挙げたブロック引数の有無を吸収する非終端記号です。
parser は do を読み終えてから * を shift できる地点に着くまでに、空文字規則を順に reduce して S0 → S1 → … → Sn と state を遷移します。tSTAR を実際に shift できるのは、すべての空文字 reduce を終えた Sn です。
このギャップを埋めるのが Layer 2 の yy_state_eventually_accepts_token です。空文字規則の reduce を仮想的に辿りつつ、各 state で Layer 1 を試して判定します。
int yy_state_eventually_accepts_token(int yystate, int yychar) { int visited[64] = {0}; for (;;) { if (visited[yystate]) return 0; // 循環検出 visited[yystate] = 1; if (yy_state_accepts_token(yystate, yychar)) return 1; // Layer 1 を試す int rule = yydefact[yystate]; if (rule == 0 || yyr2[rule] != 0) return 0; // 空文字規則でなければ諦める // 空文字規則の reduce 後の goto 先 state を計算 (yypgoto / yydefgoto を引く) // yystate = ...; } }
※ 上記は抜粋しやすいよう簡略化したコードになります。詳細は ydah/lrama template/bison/yacc.c#L636-L689 をご参照ください。
まず現在の state で Layer 1 を試します。受理できなければ yydefact で default reduce の規則を引きます。その右辺長 yyr2[rule] が 0 であれば空文字規則ですから、reduce 後の goto 先 state を計算して処理をループします。
Mid-rule actions and optional clauses create ε-chains.
Hidden by LALR's compression.
— slide 39
mid-rule action と optional 節が空文字規則の連鎖を作り出し、LALR の表圧縮はそれを隠蔽してしまいます。Layer 2 はこの隠れた連鎖を辿り直し、token の受理可能性を取り戻すための仕組みです。
Layer 3: parser stack を pop した先を引く
Layer 3 は、空文字規則ではない通常の default reduce を辿った先の state で token の受理可能性を判定する仕組みです。Layer 2 同様、圧縮により default reduce に関する lookahead の情報が欠落しているため、reduce を辿って先の state まで覗きに行きます。異なるのは reduce で 状態遷移が起こるため、state を辿るために parser stack を利用する必要がある点です。
例として yield *args を考えます。
def foo(*args) yield *args end
parse.y の文法規則のうち、yield に関係する箇所はこちらです。
command : ...
| k_yield command_args
| ...
;
k_yield : keyword_yield
{ ... }
;
— ruby/ruby parse.y#L3636-L3641 と parse.y#L4883-L4888
yield を shift した直後の state では * は受理されません。k_yield → keyword_yield の reduce を経て、command_args を読み始める state まで進んで初めて、 * を tSTAR として受理することが出来ます。k_yield → keyword_yield は空文字規則ではないため、Layer 2 の yy_state_eventually_accepts_token では辿ることができません。
空文字規則ではない通常の reduce では、前述の通り規則の右辺に対応する state を parser stack から pop します。先頭になった state から goto して新しい state に遷移します。Layer3 では通常の reduce で以前の state に戻る関係上、Layer2 と違って parser stack を覗き込む必要があります。
この処理は yy_state_deep_accepts_token という関数で実装されており、引数として parser stack の base/top ポインタを受け取ります。
int yy_state_deep_accepts_token(int yystate, int yychar, const short *stack_base, const short *stack_top) { // ... ループ内で: if (rhs_len > 0) { // 通常 reduce: stack を pop して下に隠れた state を露出 const short *target = stack_top - (stack_consumed + rhs_len); int uncovered_state = *target; // uncovered_state から goto して新 state へ // ... } // ... }
※ 上記は実装の流れを追えるよう一部を抜粋しています。詳細は ydah/lrama template/bison/yacc.c#L700-L788 をご参照ください。
stack_top から右辺長ぶん戻った位置の state を uncovered_state として取り出し、そこから goto して新しい state へ進みます。yield *args の例で言えば、現在 state は keyword_yield を shift した直後です。parser stack の一段下には shift する前の state が積まれています。Layer 3 はこの一段下の state を uncovered として取り出し、k_yield で goto して command_args を読む state まで進めます。その state で * が tSTAR として shift できるかを判定し、答えを lexer に返します。
Layer 1-3 のまとめ
ydah さんは Layer 1-3 をまとめて次のように述べられています。
The grammar itself isn't ambiguous.
Looking at the parser state correctly gives the answer.
— slide 42
三層はいずれも、parser の動作を何段実行した先の state を見るかの違いに過ぎません。文法自体は曖昧でなく、parser state の中に答えはずっとあった、と三層に共通して整理されています。
Layer 4
Layer 1-3 は同じ字句に対する複数の tokenize 候補のうちどれが適切かを、parser state を覗いて決める話でした。Layer 4 はそれとは異なる問いを扱います。文字列をどこで打ち切って tokenize するかという問題で、token 種別の選択ではなく token の境界自体が parser 文脈に依存する場合を相手にします。
name: の切り分け
f(name: 1) # name: は 1 token (tLABEL) f(name :foo) # name は tIDENTIFIER, :foo は tSYMBEG + tIDENTIFIER (3 token)
両者とも name の直後に : が現れますが、前者は name: の 5 文字を 1 つの tLABEL として切ります。後者は name を tIDENTIFIER として切り、:foo を tSYMBEG と tIDENTIFIER の 2 つに分けるので、合わせて 3 token になります。いずれも name までの入力列は同じですから、name を tIDENTIFIER と確定させる前に次の : を見て、どちらの切り方をするかを判断する必要があります。
lex_state による対応
従来の Ruby parser は、この境界決定を手書きの C コードで実装してきました。name を読み終えたあと、次の 2 つの macro を組み合わせて条件分岐します。
#define IS_LABEL_POSSIBLE() (\ (IS_lex_state(EXPR_LABEL|EXPR_ENDFN) && !cmd_state) || \ IS_ARG()) #define IS_LABEL_SUFFIX(n) (peek_n(p, ':',(n)) && !peek_n(p, ':', (n)+1))
— ruby/ruby parse.y#L8566-L8569
IS_LABEL_POSSIBLE() は lex_state を参照して label が許される位置かどうかを問い合わせます。IS_LABEL_SUFFIX(0) は次の文字が : であり、かつその次が : ではないことを peek で確認します。呼び出し側は tIDENTIFIER を確定する直前にこの 2 つを組み合わせ、両方が成立したときだけ : を 1 文字消費して tLABEL を返すという処理を書いていました。
if (IS_LABEL_POSSIBLE()) { if (IS_LABEL_SUFFIX(0)) { SET_LEX_STATE(EXPR_ARG|EXPR_LABELED); nextc(p); tokenize_ident(p); return tLABEL; } }
— ruby/ruby parse.y#L10336-L10343
このような処理は局所的には読みやすいのですが、同様の分岐が lexer の随所に埋め込まれているとなると、lexer 全体の挙動を把握するのは難しくなります。token の境界決定がどこでどう判断されているかは、実装を読まないと分かりません。lexer の仕様はコードの動作としてのみ暗黙に存在し、可読性とメンテナビリティの双方を損なってしまいます。
%token-pattern で token の正規表現を grammar に取り込む
Lrama はこれを解消するために %token-pattern という directive を導入しました。手書き実装の挙動に依存していた lexer の仕様を、正規表現による宣言的な記述に置き換えるアプローチです。
%token-pattern tIDENTIFIER /[a-z_][a-zA-Z0-9_]*/ %token-pattern tLABEL /[a-z_][a-zA-Z0-9_]*:/
詳細な仕様は ydah/lrama NEWS.md をご参照ください。
Lrama は build 時に %token-pattern の宣言を読み込み、それぞれを NFA に書き下します。その後得られた NFA を merge して単一の DFA を構築します1。この DFA は yy_scanner_transition[dfa_state][256] という 2 次元配列として C コードに展開されます。lexer 処理を手書きの条件分岐からこの配列を参照した走査に置き換えることで、token の境界決定を正規表現のマッチングに基づく単なる配列の lookup として単純化出来ます。得られた state machine を pseudo-scanner と呼びます。
これにより、メンテナーの基本的な関心はヒューリスティックな手書き実装から各 token の正規表現の設計に移ります。宣言的な token や文法のデザインとその処理機構が分離されることで、可読性とメンテナビリティを向上させることが出来ます。
parser 文脈で受理可能か確認する scanner_accepts table
pseudo-scanner は入力を 1 byte ずつ読み進め、受理状態に着くたび、ここまでの綴りがその token として受理可能だと教えてくれます。ただし、これだけでは parser 文脈に依存した切り分けはできません。
PSLR は、pseudo-scanner が受理状態へ到達するたび現在の parser state でその token を採用してよいかを確認する機構を与えます。これを実現するのが、parser state と pseudo-scanner 受理状態の組から、どの token を返すかを引ける 2 次元 table yy_scanner_accepts です。
yy_pseudo_scan で実行時に走査
scanner_accepts table を実行時に走査するのが yy_pseudo_scan 関数です。
int yy_pseudo_scan(int parser_state, const char *input, int *match_length) { int ss = 0; int ibest = 0, pbest = YY_PSLR_EMPTY_PATTERN; int i = 0; while (input[i] != '\0') { int next_ss = yy_scanner_transition[ss][(unsigned char)input[i]]; if (next_ss == YY_SCANNER_INVALID_STATE) break; ss = next_ss; i++; int sa = yy_state_to_accepting[ss]; if (sa != YY_ACCEPTING_NONE) { int pattern_index = yy_scanner_accepts[parser_state][sa]; if (pattern_index != YY_PSLR_EMPTY_PATTERN) { pbest = pattern_index; ibest = i; } } } *match_length = ibest; return yy_token_pattern_to_token_id[pbest]; }
※ 上記は抜粋しやすいよう簡略化したコードになります。詳細は ydah/lrama lib/lrama/output.rb#L678-L748 をご参照ください。
入力を 1 文字ずつ読み取り、yy_scanner_transition を現在の state ss と入力文字 input[i] で引いて次の state sa を得ます。sa が受理状態であれば yy_scanner_accepts[parser_state][sa] を引き、現在の parser state でその token を受理可能かを確認します。受理可能ならその token を pbest として記録します。この処理を繰り返し行うため、pbest にはそれまでに match した token のうち、parser state で受理可能なもののなかで最も長い match が記録されます。入力列を最後まで流し切るか、pseudo-scanner の遷移先がなくなったら走査を終え、pbest を token ID に変換して返します。
foo(name: "Ruby") を例に考えると、name まで読み終えた時点では pbest は tIDENTIFIER になっています。次の : を読むと tLABEL の受理状態に到達します。yy_scanner_accepts[parser_state][sa] でも tLABEL が許可されるため、pbest は tLABEL に更新されます。次の空白を読んだとき YY_SCANNER_INVALID_STATE で break し、tLABEL を返すことになります。
%token-pattern から自動生成された yy_scanner_transition と yy_scanner_accepts を組み合わせることで、parser 文脈に応じた token の境界決定を実現できます。
ydah さんはこれを Layer 4 について以下のように述べられています。
The boundary between lexing and parsing is blurred.
Grammatical decisions embedded inside token-level concerns.
— slide 49
token の切り分けを parser の状態に依存して行うことで、lexer と parser の境界が曖昧になっていることがわかります。手書き実装と比較すると、宣言的な正規表現と table lookup に置き換えたことで、lexer と parser の相互作用が宣言的に表現されるようになりました。
Layer 5
Layer 4 では、pseudo-scanner の受理状態と parser state の組に対して返すべき token が一意に定まる、という前提がありました。しかし、それは当たり前のことではありません。parser state の構築方法は一様でなく、アルゴリズム次第で同じ parser state に対して複数の token が受理されるケースが起こり得ます。
Bison がこれまで利用してきた LALR(1) はその 1 つです。LALR(1) parser state をそのまま使うと pseudo-scanner は実現できません。Lrama は state splitting で parser state を分割し、pseudo-scanner の正しい動作を担保しています2。
LALR(1) の state merging
LALR(1) は kernel が同じになる parser state を 1 つに merge することで、state 数を抑える設計です。
※ kernel の定義および LALR(1) の状態圧縮については本稿では説明を割愛します。詳細は junk0612 さんの From LALR to IELR: A Lrama's Next Step をご参照ください。
この state の merge は state ごとの文脈 (遷移列) を区別しないため、以下に例示するような問題が起こり得ます。
/ の tDIVIDE / tREGEXP_BEG
a / b # `/` は tDIVIDE (二項演算子) if /reg/ # `/` は tREGEXP_BEG (正規表現リテラルの開始)
以下の 2 つの parser state を考えます。
- State A は
argを読み終えた直後 (二項演算子待ち) で、次の/を tDIVIDE として tokenize したい状態である。 - State B は式の頭 (
ifの直後など) で、次の/を tREGEXP_BEG として tokenize したい状態である。
この 2 つの state が LALR の merge で state X に統合されたとします。PSLR では Layer 4 で見た scanner_accepts を build 時に構築します。merge された state X について scanner_accepts[X][fsa_state_for_/] を計算しようとすると、以下の状況になります。
- parser state X で受け入れ可能な token には
tDIVIDEとtREGEXP_BEGの両方が含まれる - pseudo-scanner の
/受理状態も両者を切り出す token の候補として扱う - セルには値を 1 つしか書けないので、正しい token を選べない
PSLR の状態分解
これは LALR(1) が文脈の異なる2つの状態を merge してしまっていることが原因です。Lrama は LALR の merge された state を 必要なところだけ再度分裂させ、それぞれに正しい scanner_accepts 行を持たせます。
これを実現するために %lexer-context という directive が導入されました。以下でその仕組みを述べます。
%lexer-context で symbol → context をマップ
Lrama は grammar ファイルに次のような宣言を書けるようにしました。
%lexer-context BEG keyword_if keyword_unless tLPAREN ... %lexer-context CMDARG tIDENTIFIER tFID tCONSTANT ... %lexer-context END tINTEGER tFLOAT keyword_end ')' ']' ...
これによりある token を読んだ後の文脈を、宣言的に管理できるようになります。
状態 X に入ってくる矢印を context でグループ化
%lexer-context を利用し状態を分割します。split_states_by_context の動きを順に追います。
X には少なくとも 1 つ、遷移元となる state Y が存在します。この Y → X の状態遷移を transition と呼びます。状態遷移は symbol の消費を伴うため、transition は (遷移元 state, 消費する symbol, 遷移先 state) の組で表現できます。
Lrama の実装には 2 種類の transition があります。Shift (terminal を消費) と Goto (reduce 直後に nonterminal を消費) で、いずれも次の構造を持ちます。
class Shift # Goto も同じ構造 attr_reader :from_state #: State # 遷移元 state attr_reader :next_sym #: Grammar::Symbol # 消費する symbol (terminal または nonterminal) attr_reader :to_items #: Array[Item] # 識別用の items サブセット attr_reader :to_state #: State # 遷移先 state ... end
参照: state/action/shift.rb、state/action/goto.rb
各 parser state X について以下を実行します。
- X に入ってくる transition をすべて見る。
- 各 transition の symbol を
%lexer-contextと照らし合わせ、どの context に属するかを判定する (infer_transition_context)。 - X への transition を context でグループ化する。
- 2 つ以上の context グループがある場合、最多の transition を持つグループを X に残す。それ以外のグループには新 state を作って transition を向け替える。
/ の例で言えば、X に入ってくる transition のうち arg 経由のものは END グループへ振り分けられます。keyword_if 経由のものは BEG グループへ振り分けられ、片方が元の X (END)、もう片方が新 state (BEG) として残ります。
これで LALR merge が scanner_accepts を壊す問題は解消されます。長年 lex_state が担っていた context の管理が、build 時の state 構造に焼き込まれます。
ydah さんはこれを Layer 5 の整理として次のように述べられています。
Ambiguity caused by LALR state merging
— an algorithmic side effect.
— slide 56
Layer 5 では、LALR(1) が副作用として作り出した曖昧性を扱いました。lex_state がこの副作用を条件分岐 として扱っていたために、これまで他の層との区別が曖昧になっていました。
Layer 6
Layer 1-5 はいずれも、parser・lexer・generator のいずれかで対応可能な話でした。Layer 6 はそれらの仕組みでは原理的に解けない領域です。インタプリタの実行時情報を参照しないと決められない曖昧性をここで扱います。
例: m << x と foo << x
m = 1 puts m <<0 # m << 0 (left shift) puts foo <<0 # foo(<<0) (heredoc argument)
m はローカル変数、 foo はメソッド呼び出しであることがわかります。lexer はこれに基づいて、<< を bit shift として解釈するか、heredoc の開始記号として解釈するか判断する必要があります。しかし、token としては m と foo のどちらも tIDENTIFIER として解釈されます。この扱いは、Ruby がローカル変数とメソッド呼び出しを構文解析・字句解析の段階で区別しないという設計に由来します。tIDENTIFIER を区別するには、インタプリタの local variable table を参照して、m がローカル変数であることを確認するほかありません。
last_token_type
このような曖昧性を扱うために、 last_token_type が導入されました。parser_state に 2 bit の値として追加され、「最後に見た token が何だったか」を以下の 4 値で表現します。
unsigned int last_token_type:2; #define LAST_TOKEN_OTHER 0 /* operator, keyword, delimiter */ #define LAST_TOKEN_LVAR 1 /* known local variable identifier */ #define LAST_TOKEN_VALUE 2 /* literal (integer, string end, symbol, etc.) */ #define LAST_TOKEN_METHOD 3 /* method/function name identifier */
lexer は token を返すたび local variable table を覗き、last token が LVAR / VALUE / METHOD / OTHER のどれに該当するかを判定し、last_token_type を更新します。lexer で last_token_type を参照して token を切り分ける処理は手書きの条件分岐として実装されます。
Layer 6 のまとめ
ydah さんはこれを Layer 6 の整理として次のように述べられています。
Semantic ambiguities invisible to the grammar.
Local vars and method calls looking identical
= Ruby's intentional design choice.
— slide 62
Ruby はローカル変数とメソッド呼び出しを構文的に区別しないことを意図的に選んだ言語です。両者を同じ記法で扱えることで、変数アクセスとメソッド呼び出しを意識せずに書ける簡潔さや、メソッド呼び出しを宣言として読める DSL との親和性が獲得されています。そのトレードオフとして字句解析の参照範囲が広範化し、 local variable table を参照して tokenize を行う手書き実装が必要になります。
ここまでの Layer の観察を通して、 lex_state のような手書き実装が必要だったのは Layer6 のような実行時の情報を取得する必要があるケースのみであることがわかりました。これにより 13 bit の lex_state を、2 bit (4 値) の last_token_type まで縮退させることが出来たのです。
まとめ
ydah さんは talk の終盤で、6 層を性質別に 3 つのカテゴリにまとめ直されています。
カテゴリ Layers 本質 Implementation Problems 1-3 Grammar isn't ambiguous Design Boundary / Algorithm 4-5 Lexing/parsing boundary; LALR side effects Language Design 6 Semantic ambiguity grammar cannot capture — slide 65
従来は全て lex_state によって混ぜこぜになって対応されていましたが、PSLR によってこれらを分離することが出来ました。
ydah さんはこれをセッションの最後に、次のように締めくくられています。
Deleting lex_state was the means
The real achievement: the structure of Ruby's grammatical ambiguity became visible.
— slide 68
lex_state の削除自体は手段にすぎず、本当の成果は Ruby の文法的曖昧性を分類し、その原因や対応を類型化できたことにあります。
6 つの分類による map は、今後 Ruby に新しい構文を提案するとき、それがどの層に属する曖昧性を生むかを検討するためのフレームワークとして機能します。
加えて、lex_state の別解が宣言的に与えられました (%token-pattern、%lexer-context)。parse.y からは手書き実装に依存する暗黙的な仕様が限りなく局所化され、読んで理解できる仕様書へと近づきました。魔境と呼ばれていた parse.y が構文解析の仕様を記述するドキュメントに近づきつつあります。Ruby の文法を学ぶ人・拡張する人にとっての入口が大きく開かれつつあることを、Rubyist として喜ばしく感じました。
Techouseでは、社会課題の解決に一緒に取り組むエンジニアを募集しております。 ご応募お待ちしております。
- 正規表現と有限オートマトンが等価であることは古典的な結果で、両者の変換手続きも確立されています。↩
-
Lrama の state の分裂には他にも、
scanner_acceptsが文脈によって異なるケースを扱う PSLR Signature splitting (実装はcompatible_split_state?を参照) と、mysterious conflict を解消する IELR splitting (実装はis_compatible?を参照) の 2 軸があります。詳細は junk0612 さんの From LALR to IELR: A Lrama's Next Step および Rage Against the annotate_predecessor をご参照ください。↩
