Lrama へのコントリビューションを通して学ぶ Ruby のパーサジェネレータ事情

1. Lrama へのコントリビューションを通して学ぶ Ruby のパーサージェネレーター事情 株式会社永和システムマネジメント アジャイル事業部 小林 純一 (@junk0612) 大阪 Ruby 会議 03 ハートンホテル心斎橋別館 松風ホール 2023/09/09(Sat.)
2. 小林 純一 (@junk0612)
3. 自己紹介 • 小林純一 • X / GitHub: @junk0612 • 株式会社永和システムマネジメント アジャイル事業部 ◦ RubyxAgile グループ ◦ 構文解析器研究部員 • 音ゲーマー・ボードゲーマー
5. 本日のおしながき • パーサー周りの基礎知識 • Lrama にコントリビューションした話 • 実装を通して知った Lrama の内部構造 • 今後やってみたいこと
6. パーサー周りの基礎知識
7. パーサー周りの基礎知識 • 構文解析器の構成要素 ◦ レキサー ◦ パーサー ◦ パーサージェネレーター • 言語処理系の用語 ◦ 形式言語 ◦ 文脈自由言語 ◦ BNF
8. 構文解析器の構成要素 • レキサー ◦ テキストを読み込んで、トークンに分割するプログラム ◦ トークンに分割することをトークナイズという • パーサー ◦ トークン列を読み込んで、内部構造を取り出すプログラム ◦ コンパイラ系では「ソースコード → AST」 ▪ AST: Abstract Syntax Tree (抽象構文木) ◦ JSON や CSV のパーサーでは「テキスト → データ構造」 • パーサージェネレーター ◦ 文法ファイルを読み込んで、パーサーを生成するプログラム
9. CRuby 実行環境 .rb ファイル Ruby VM 構文解析器の構成要素
10. CRuby 実行環境 .rb ファイル Ruby VM レキサー トークン列 AST バイトコード パーサー 生成器 構文解析器の構成要素
11. CRuby 実行環境 .rb ファイル Ruby VM レキサー トークン列 AST バイトコード パーサー 生成器 パーサージェネレーター 文法ファイル パーサー 構文解析器の構成要素
12. CRuby 実行環境 .rb ファイル Ruby VM レキサー トークン列 AST バイトコード パーサー 生成器 パーサージェネレーター 文法ファイル レキサー トークン列 AST パーサー 生成器 パーサー 構文解析器の構成要素
13. 言語処理系の用語 • 形式言語 ◦ 「言語」を数学的・集合論的に取り扱う言語学の分野 ◦ 言語がどのようなテキストとして表されるかを考える ▪ 人間に意味のある言葉として認識されるかは気にしない ▪ 英語なら「アルファベットの羅列で、たまにスペースや 記号が入る」など ◦ 言語を構成する記号と、それらを結びつける文法からなる
14. 言語処理系の用語 • 文脈自由言語 (Context Free Grammar: CFG) ◦ 形式言語の1つで、以下の形式で表されるもの ▪ rule: A B C ... | D E F ... ▪ このような記法を BNF(Backus-Naur Form) という ◦ 世の中のほとんどのプログラミング言語が属する ◦ パーサージェネレーターの入力となる文法ファイルに使われる ◦ 他の文法によって展開できる記号を非終端記号という ◦ それ以上展開できない記号を終端記号という
15. 文脈自由言語と BNF number: digit digit digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
16. 文脈自由言語と BNF number: digit digit digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 00 ～ 99 の2桁の数字全体を表す言語
17. 文脈自由言語と BNF expression: digit '+' digit | digit '-' digit | digit '*' digit | digit '/' digit digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
18. 文脈自由言語と BNF expression: digit '+' digit | digit '-' digit | digit '*' digit | digit '/' digit digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 1桁の数の2項四則演算式を表す言語
19. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
20. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: expression
21. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: expression / digit
22. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( expression ) / digit
23. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( expression + digit ) / digit
24. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( digit + digit ) / digit
25. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( 2 + digit ) / digit
26. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( 2 + 7 ) / digit
27. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( 2 + 7 ) / 3
28. 文脈自由言語と BNF expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 1桁のかっこ付き四則演算式を表す言語
29. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( 2 + 7 ) / 3
30. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( digit + 7 ) / 3
31. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( digit + digit ) / 3
32. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( digit + digit ) / digit
33. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( expression + digit ) / digit
34. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: ( expression ) / digit
35. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: expression / digit
36. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 例: expression
37. 実際のパーサーの処理 expression: digit | expression '+' digit | expression '-' digit | expression '*' digit | expression '/' digit | '(' expression ')' digit: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' Accepted!
38. まとめ • ソースコードが実行・コンパイルされるとき、 レキサーとパーサーがプログラムを解析してデータ構造を作る • パーサーを文法ファイルから自動生成するプログラムを パーサージェネレーターという • パーサージェネレーターの入力に使われる文法ファイルは 文脈自由文法で書かれる • 文脈自由文法の記法として BNF がある
39. Lrama に コントリビューションした話
40. やったこと • Lrama に Named References を実装した
41. やったこと • Lrama に Named References を実装した 🤔
42. Lrama とは • Bison を代替するために作られた Ruby 製パーサージェネレーター • RubyKaigi 2023 で kaneko.y さんが発表した ◦ 詳しくは https://youtu.be/IhfDsLx784g?si=kO1q6mLpTa1bIRYL • CRuby 3.3 から導入される ◦ preview1 には入っているので、今この場でお試しいただけます ◦ ※ Ruby のふるまいは変わりません
43. Lrama を導入するメリット • Bison のバージョンに引きずられずに済む ◦ Bison はユーザーごとにバージョンが異なるので、古いものがインス トールされていることを想定しなければいけない ◦ 新しい機能が導入されても使えない • Ruby 独自の実装ができる ◦ LSP 向けに書きかけのコードをいい感じにパースする ◦ 複雑になっている文法のパースをうまくやる
44. Lrama が目指すところ • Usability • Maintainability • Universal Parser • 詳しくは RubyKaigi 2023 での kaneko.y さんの発表をどうぞ ◦ https://youtu.be/IhfDsLx784g?si=kO1q6mLpTa1bIRYL
45. Usability • Error-tolerant なパーサーがほしい ◦ 旧来のパーサーは、入力されたコードが文法的に正しいか どうかを判断すればよかった ◦ LSP が存在している現代においては、書きかけの半端なコード についてもなるべくパースしたいという要求がある ▪ Bison の panic モードでは文法エラーの場所を 読み飛ばしてしまうので困る
46. Maintainability • 歴史的経緯により、parse.y は非常に複雑になっている ◦ 特に、ここから生成される CRuby のパーサーとレキサーが 密結合しているのがメンテナンス性に悪影響を与えている • パーサーの力をうまく使ってやるともっとメンテナンス しやすくなるので、それを使うための機能を入れたい
47. Universal Parser • 世の中にはさまざまな Ruby 実装があり、 それぞれ独自のパーサーを利用している ◦ mruby や JRuby といった別実装 ◦ sorbet や typeprof のようなツール • 現在の CRuby のパーサーは CRuby 独自の機能に依存しており 移植が難しくなっている • 文法ファイルを整理することで、他実装にも利用できるパーサーを 作りたい
48. Lrama 周辺のパーサー事情 • YARP ◦ Bison が作ったパーサーを置き換えるべく作られている CRuby 向けの手書き (!) パーサー ◦ JRuby / TruffleRuby での実績もあるらしい • Bison ◦ GNU が開発した Yacc の後継のパーサージェネレーター ◦ CRuby においては、parse.y を読み込んで Ruby のパーサーを 出力するために使われていた • Racc ◦ 青木峰郎さんの開発したパーサージェネレーター ◦ parser gem (RuboCop の依存 gem) などで使われている
49. Q: Racc で Bison の置き換えってできないの？ 生成アルゴリズムは同じだが、下記の部分が異なっているために共通で利用 できる部分が少なく、イチから作ったほうが手間が少ない • 入力する文法ファイルそのものの文法 ◦ Bison は Yacc 由来、Racc は独自記法 • 出力するパーサーの言語 ◦ Bison は C、Racc は Ruby
50. Named References とは • Bison の機能の 1 つ • Action 内の References として非終端記号名を利用できる
51. Named References とは • Bison の機能の 1 つ • Action 内の References として非終端記号名を利用できる 🤔
52. %{ Prologue (約 1500 行) %} Bison declarations (約 200 行) %% Grammar rules (約 4500 行) %% Epilogue (約 8300 行) Bison 文法ファイルの構造 かっこ内は CRuby の parse.y における行数
53. %{ Prologue (約 1500 行) %} Bison declarations (約 200 行) %% Grammar rules (約 4500 行) ← 今回はここの話 %% Epilogue (約 8300 行) Bison 文法ファイルの構造
54. Grammar rules の構造 rule_name: rule rule .. rule { action } | rule rule .. rule { action } expression: NUMBER '+' expression { $$ = $1 + $3 } | NUMBER '-' expression { $$ = $1 - $3 } | '(' expression ')' { $$ = $2 }
55. Grammar rules の構造 rule_name: rule rule .. rule { action } | rule rule .. rule { action } expression: NUMBER '+' expression { $$ = $1 + $3 } ← | NUMBER '-' expression { $$ = $1 - $3 } ← 今回はここの話 | '(' expression ')' { $$ = $2 } ←
56. Action とは • Bison が生成するパーサーは、なにもしなければ 文法に則った入力になっているかどうかしか教えてくれない ◦ AST を作ったり、後の処理に必要な情報を保存したりはしない • 各文法の後ろに {} でくくってプログラムを書くことができる • $n や @n を使うと、文法中の記号の値を使って処理が行える ◦ この機能を (Numbered) References という
57. Action の具体例 expression: NUMBER '+' expression { $$ = $1 + $3 } この文法を受理したときの返り値は 1つ目の要素と3つ目の要素の足し算
58. Action の具体例 expression: NUMBER '+' expression { $$ = $1 + $3 } この文法を受理したときの返り値は 1つ目の要素と3つ目の要素の足し算
59. Action の具体例 expression: NUMBER '+' expression { $$ = $1 + $3 } この文法を受理したときの返り値は 1つ目の要素と3つ目の要素の足し算
60. Action の具体例 expression: NUMBER '+' expression { $$ = $1 + $3 } この文法を受理したときの返り値は 1つ目の要素と3つ目の要素の足し算
61. Named References とは • Numbered References の問題点 ◦ 記述的でなくわかりにくい ◦ 場所の番号で指定するため、 文法が変更になると書き直さなければならない • 上記の問題を解消するため、非終端記号名を参照して 値を使えるようにした機能が Named References
62. Named References とは expression: NUMBER '+' expression { $$ = $1 + $3 } | NUMBER '-' expression { $$ = $1 - $3 } | '(' expression ')' { $$ = $2 } expression[result]: NUMBER '+' expression[rest] { $result = $NUMBER + $rest } | NUMBER '-' expression[rest] { $result = $NUMBER - $rest } | '(' expression[inside-exp] ')' { $result = $[inside-exp] }
63. Named References とは expression: NUMBER '+' expression { $$ = $1 + $3 } | NUMBER '-' expression { $$ = $1 - $3 } | '(' expression ')' { $$ = $2 } expression[result]: NUMBER '+' expression[rest] { $result = $NUMBER + $rest } | NUMBER '-' expression[rest] { $result = $NUMBER - $rest } | '(' expression[inside-exp] ')' { $result = $[inside-exp] } 前に $ をつけてルール名で値を参照できる
64. Named References とは expression: NUMBER '+' expression { $$ = $1 + $3 } | NUMBER '-' expression { $$ = $1 - $3 } | '(' expression ')' { $$ = $2 } expression[result]: NUMBER '+' expression[rest] { $result = $NUMBER + $rest } | NUMBER '-' expression[rest] { $result = $NUMBER - $rest } | '(' expression[inside-exp] ')' { $result = $[inside-exp] } ルール記述側で [] でくくると別名をつけられる
65. Named References とは expression: NUMBER '+' expression { $$ = $1 + $3 } | NUMBER '-' expression { $$ = $1 - $3 } | '(' expression ')' { $$ = $2 } expression[result]: NUMBER '+' expression[rest] { $result = $NUMBER + $rest } | NUMBER '-' expression[rest] { $result = $NUMBER - $rest } | '(' expression[inside-exp] ')' { $result = $[inside-exp] } ルール名や別名に記号を含む場合は 呼び出し側も [] でくくれば OK
66. Named References とは expression: NUMBER '+' expression { $$ = $1 + $3 } | NUMBER '-' expression { $$ = $1 - $3 } | '(' expression ')' { $$ = $2 } expression[result]: NUMBER '+' expression[rest] { $result = $NUMBER + $rest } | NUMBER '-' expression[rest] { $result = $NUMBER - $rest } | '(' expression[inside-exp] ')' { $result = $[inside-exp] }
67. ここまでのまとめ • やったことの説明 ◦ Lrama に Named References を実装した ▪ Lrama は Bison を置き換えるために作られた パーサージェネレーター ▪ Named References は Bison が持つ機能で、Action 内の References として非終端記号名を利用できる
68. 実装を通して知った Lrama の内部構造
69. パーサージェネレーターの内部構造 パーサージェネレーター 文法ファイル レキサー トークン列 AST パーサー 生成器 パーサー
70. Lrama の内部構造 Lrama parse.y Lexer Token Grammar Parser Output パーサー
71. まずはテストを書く
72. どこに手を入れるか？ • Numbered References はすでに実装されている ◦ 非終端記号名と Action 内の呼び出しを関連づけられれば 関連からコードを生成する部分はすでにある ◦ Numbered References の実装を参考にして 非終端記号名と呼び出しを関連づけることにする
73. どこに手を入れるか？ Lrama parse.y Lexer Token Grammar Parser Output パーサー
74. どこに手を入れるか？ Lrama parse.y Lexer Token Grammar Parser Output パーサー
75. どこに手を入れるか？ Lrama parse.y Lexer Token Grammar Parser Output パーサー
76. どこに手を入れるか？ Lrama parse.y Lexer Token Grammar Parser Output パーサー
77. なぜレキサーに手を入れるのか • Lrama ではレキサーが文脈を持ってトークナイズしている ◦ 「いま何をパースしているか」という情報 • Action を読み込むとき、直前に読んだルールの場所を確認して 「どのルールを参照しているか」という関連づけまでやっている • これをまるごとパーサーに持っていくのは非常に大変だし、 もともとの設計にも合わない ◦ トークナイズ → パースというフェーズ分けをしたかった
78. 文脈をどこに持つか？ • レキサーは文脈を持っていないと適切なトークナイズができない ◦ コメントは読み飛ばす ◦ HereDoc の途中で改行が含まれてもパースエラーにしない ◦ etc. • これをパーサーに持つかレキサーに持つか
79. 文脈をどこに持つか？ • レキサーに持つと ◦ 入力から自身の状態を変えながら一気にトークナイズができ、 トークナイズ → パースというフェーズ分けができる • パーサーに持つと ◦ パーサーが状態を元に次のトークンをレキサーから受け取る ようになるので、レキサーはトークナイズに集中できる
80. https://github.com/ruby/lrama/pull/41 Pull Request
81. 今後やりたいこと • 内部パーサーの Racc による自動生成化 ◦ WIP の PR → https://github.com/ruby/lrama/pull/62 • Bison の機能の取り込み • kaneko.y さんによるやりたいことリスト → https://docs.google.com/document/d/1EAZzYMXBOdzK-6mMIj 2YNJxZZRVcpJxE7-4zXbHn8JA/edit?usp=sharing
82. 世はまさに 大パーサー時代 人々はパーサーの 海へと漕ぎ出す ――RubyKaigi 2023 LT kaneko.y