とにかくparserとparser generatorをやっている一年でした。世はまさに"大パーサー時代"！！！
Ruby3.3 リリースが目前に迫りました！
— OSS-Vision Official (@OssVision) December 14, 2023
リリースに向けまつもとさんから
「大構文解析時代！ Parser age」
のキーワードを頂きTシャツにアレンジしました。
多くの皆さんで Ruby3.3 リリースを祝し、関係各位に感謝しましょう。
当コレクションも、収益の一部を… pic.twitter.com/uTv3kxJ0Hz
その中でもとくに自分にとって大きな変化だったのは以下の出来事でした。
- Lrama LALR (1) parser generatorを実装して、Rubyに取り込んだ。これによってRubyからGNU Bisonへの依存が消えた。
- 最初は一人で始めたRubyのpaserの刷新大事業だったが、各方面に仲間ができてチームで開発ができるようになった。
- RubyKaigi 2023をはじめ登壇の多い年になった。海外のカンファレンスにも初めて参加した。
Lramaの進捗
Ruby Parser Roadmap - Google スライド
ロードマップを作った当初はこれを全部やるのか... という気持ちになったりしていましたが、Lramaの開発でもparse.yの開発でも多くの人が協力してくれており、確実に進捗しています。
Replace hand written parser with Racc
Lramaのparserを手書きparserからRaccによる自動生成のparserへと置き換えるという目標です。 これは@junk0612さんが実装してくれました。 これによりParameterizing rulesをはじめとした新機能導入の際の文法変更が容易になったり、Lramaのエラーメッセージを改善することができたりとLramaの開発全体が恩恵を受けています。
個人的には新しい文法をLramaに入れる時に、既存の文法を壊していないかを機械的に判断できるようになったのが大きいです。 その結果、曖昧な文法を避けるためにLramaではTagによる型の指定を後置修飾にするという判断をしています。
Option, List (syntax sugar)
@ydah_さんがParameterizing rulesの実装を着々と進めてくださっております。
現在のLramaでは?や+といった短縮記法を使えますし、%ruleを用いて独自のParameterizing rulesを定義することもできます。
Lramaの今後の機能拡張としてはMenhirがサポートしている%inlineのサポートがあります。通常のParameterizing rulesは新しくruleを定義するものですが、%inlineの場合はその場にruleを展開します。実装難易度が高いですが、conflictする可能性が減る便利機能なので実装したいです。
Remove Object from Node
Node構造体からRuby Objectへの依存を消すという目標です。 Ruby 3.3でNode構造体のリファクタリングをしたので、新しいNodeを定義するのも簡単になり、作業を始められるようになりました。
早速Ruby 3.4にむけて改善を入れました。__LINE__に対応するNodeを新しく追加し、Integerへの依存を1つ減らしています。
github.com
@S.H.さんが他のNODE_LIT(数値などのリテラル用のNode)の変更に取り組んでいて、現在はNumeric関連のNodeを実装しNODE_LITからRubyのObjectへの依存を消しているところです。
RubyのObjectへの依存を消していくためにはArrayやStringやEncodingのサブセットを独自に実装していく必要があります。ファーストステップとしてNodeからの依存を消すのがよいので、NODE_LITやNODE_STRから順次取り組んでいきます。
Union to Struct (Node) & Optimize Node memory management
RubyのNode構造体のリファクタリングは無事に完了し、各Nodeが必要十分なメモリを使うように最適化しました。 詳しくはこちらのRuby Parser開発日誌 (15) - Ruby の NODE を Union から卒業させた - かねこにっき記事で書いています。
Delete parser level optimization
parserレベルで最適化をした結果、構文木の一部が消えてしまうことがあります。
Ruby 3.3では以下のような冗長な入力であっても、1に該当するNodeが残るようにしました。
なおcompile.cのレベルでは最適化されるので、生成されるISeqは変わりません。
ruby --dump=p -e "1; 2;" ########################################################### ## Do NOT use this node dump for any purpose other than ## ## debug and research. Compatibility is not guaranteed. ## ########################################################### # @ NODE_SCOPE (id: 4, line: 1, location: (1,0)-(1,5)) # +- nd_tbl: (empty) # +- nd_args: # | (null node) # +- nd_body: # @ NODE_BLOCK (id: 2, line: 1, location: (1,0)-(1,4)) # +- nd_head (1): # | @ NODE_LIT (id: 0, line: 1, location: (1,0)-(1,1))* # | +- nd_lit: 1 # +- nd_head (2): # @ NODE_LIT (id: 1, line: 1, location: (1,3)-(1,4))* # +- nd_lit: 2
まだ残っている最適化として、以下のようなコードでNODE_RETURNが消されてしまうというのがあります。
この辺も来年は変えていきたいです。
def m return 1 end
Scanner state update syntax
Rubyのparse.yが複雑な理由のひとつはsemantic analysisに必要な情報などを構文解析のstackで管理しているからだという分析をしました。 その分析に基づいて専用のstackを自動で作成する構文を導入する予定です。 このあたりの背景について詳しくはDeclarative parse.yのスライドで説明しています。
パッチはあるので整理してmergeしていきたいです。
RBS
Lramaではrbsファイルを適宜書くようにし、CIでsteep checkを実行しています。
@Little_RubyistさんがCIの整備などをしてくれて、rbsを導入してくれました。
久しぶりに触るファイルでメソッドの引数がなんだったか調べるときなどに便利ですね。
ある変数がnilになるかどうか手軽にわかるのもレビューをしているときに役立っています。
いまはSteepfileのconfigure_code_diagnosticsがデフォルトのままなのですが、いくつか設定を変えた方がいいかもなと思っています。
確認したところ現時点でlib以下のファイルが71に対して、sig以下のファイルが38でした。
登壇とカンファレンス
5月 RubyKaigi 2023
松本で開催されたRubyKaigi 2023に現地参加し登壇しました。福岡で開催したRubyKaigi 2019以来となる、4年ぶりのRubyKaigiへの参加でした。
RubyKaigiではレギュラーセッションでの登壇、LTでの登壇、Ruby Committers and The Worldでの登壇と3回ほど壇上に上がりました。
"世はまさに大パーサー時代"の由来となったLTはこちらから。
また会期中のRuby 3.3.0-preview1 リリースにあわせてLramaをRubyに取り込み、Bisonへの依存を消しました。
5月 手を動かして振り返る RubyKaigi 2023
手を動かして振り返る RubyKaigi 2023 - connpass
ゲストセッションに登壇しました。 LTが3つあったのですが、そのうち2つがLramaに関するものでした。とてもうれしいですね。
6月 深掘りRubyKaigi 2023
STORESさんの企画「深掘りRubyKaigi 2023」にmakenowjustさんと一緒に登壇しました。 当日の様子は文字起こしレポートとしてSTORESさんのブログにまとまっています。 密度の濃い話ができてとても楽しかったです。
8月 RubyKaigi 2023 follow up
RubyKaigi後の進捗発表をしてきました。
RubyKaigiから3ヶ月がたち、LR parserの利点やLR parserのあるべき姿についてより理解が深まったタイミングでした。 プログラミング言語の文法をデザインする際にLR parserがいかにそれをサポートできるかといった話や、parserとlexerの状態共有を統合的に設計しなおすことが大事という話をしました。
9月 大阪Ruby会議03
@junk0612さんがLramaについて話をするということで、大阪にいってきました。 プログラミング言語のパースという一部分を担うparser generatorの内部構造もまた、言語処理系と似た構造になるという話が興味深いですね。
11月 Fukuoka.rb #333 Ninja Talk 大会
Fukuoka.rb 333回記念ということで、parse.yの将来について話をしました。6人中4人がparserもしくはparser generatorの話をしていました。
私はparse.yをもっとDeclarative(宣言的)にしようという話をしました。 オートマトンおよびそれを応用したLR parserは良い構造をしています。 それをさらに発展させることでよりDeclarative(宣言的)なparser実装になるはずです。 論理に則ったDeclarativeなparserにすることで、教科書などで得られる知識とparse.yの実装の乖離をなくしていくことができ、それが"parse.y for Under graduate"というロードマップ上のひとつのゴールだという話です。
LR parser界の巨人であるMenhirとLramaが対比されている『Menhir is here!』も感慨深い発表でした。
11月 RubyWorld Conference 2023
Ruby Prize 2023 最終ノミネート者になったので、松江で開催されたRubyWorld Conference 2023に行ってきました。 Ruby Prize 最終ノミネートは2018年に続き2回目です。
結局毎晩parserの話をしていたような気がします。
12月 RubyConf Taiwan 2023
@junk0612さんが今度は台湾でLramaの話をするというので台湾にいってきました。 CFGやBNFの話からはじまりLR構文解析器の挙動、Lramaへのcontributionの話へとポイントを丁寧に押さえた発表でした。 @junk0612さんはRacc化とNamed Referencesという大きめの2つのテーマを今年実装してくださいました。次はIELRに取り組むとのことで楽しみにしています。
初めての海外カンファレンス、初めての台湾でしたがとても楽しめました。 台湾でも毎晩parserの話をしていたような気がします。
Ruby Parser開発日誌 (ブログ)
実装や設計、関連する研究の紹介など、Rubyのparser(parse.y)とparser generator(lrama)に関することを主に書いている当ブログですが、今年は15本の記事を書きました。 その時々で取り組んでいることや考えていることを書いており、どの記事も思い出深いのですが、大舞台だったRubyKaigiについて書いたRuby Parser開発日誌 (9) - RubyKaigi 2023で発表してきた ~ 世はまさに”大パーサー時代” ~ - かねこにっきと、LR構文解析表と文法定義の関係を簡潔に説明したRuby Parser開発日誌 (14) - LR parser完全に理解した - かねこにっきがとくに印象に残った記事です。特後者はいままで教科書などで説明できていなかった内容だと思うので、人類の構文解析に関する知識の発展に貢献できたのではないかと考えいます。
現在進行形で開発しているプロジェクトにおける様々な設計方針や判断の背景が読める機会はあまりないと思うので、来年も引き続きRuby Parser開発日誌を書き、LR parserおよびparser generatorの面白さをお伝えできたらと思います。
それではみなさん、良いお年を！！！
