I Would Prefer Not To.

He is (maybe) ydah.

Ruby構文解析器 開発日録#3 - RubyKaigi 2024に登壇してきました

私は2024年5月15日から17日まで、沖縄の那覇で開催されていたRubyKaigi 2024に参加し、登壇をしてきました。 RubyKaigiへの参加はRubyKaigi 2022からなので今年で3年目です。

もう2週間が経とうとしていますが、少しずつ気持ちを整理してようやく現実に戻ってきました。 この記事自体は帰りの飛行機の中で書き始めたのですが、つらつらと書いていると凄まじい長文となってしまいました。（6/2現在までずっと書いているとは思いもしませんでした。）

本文章内に、他の方の旧Twitterでのポストを引用していますが、もし問題がございましたらお手数ですがお知らせください。

これはゆいレールのはじまり

発表では、Lramaに新たな文法を拡張するというアプローチでparse.yのメンテナンス性を向上させるというお話をしました。

rubykaigi.org

言葉にするのは非常に難しいのですが、今年のRubyKaigiは"業を生きる"ための一歩を歩み始めたのだと感じています。 自分の内なる力に基づいて、突き動かされるという感覚になったのははじめてかもしれません。

未だ現実から戻れていない部分もありつつこの文章を書いているので、読みづらい部分もあるかと思いますがお付き合いいただけますと幸いです。

Lramaとの出会い

タコライス with 南の島感があるジュース

「どういう経緯でParserやLramaに興味を持ったのですか？」というご質問を会期中によくいただいたので、そこから順に書いていこうと思っています。 思い返せば私のRubyKaigi 2024はRubyKaigi 2023のDay1から始まっていたのだと思います。

その日は金子さんの「The future vision of Ruby Parser」の発表があった日でした。 私はRubyKaigi 2023は当日スタッフとして参加しており、私は大ホールの担当でした。大ホールへの誘導も終えてからだったので途中から聞いたことを覚えています。

その時の私はというとParserのことについては何も分からないという状態だったので、果たして理解できるだろうかと思い聞いていました。 しかし、金子さんの発表は「Parserがこういう問題を抱えている」から「このように解決して倒した」という構造になっていて、またそれぞれが短編集のように構成されていたので、途中から聞いた上に知識のない私だった訳ですが、分からないなりにも何だかワクワクしたことを覚えています。

そして、Lramaと関わることを決定的にしたのがDay4です。一日特に予定もなくゆっくり過ごしてから帰路につく予定だったので、松本ブルワリーに行きビールを楽しんでから帰阪しようかと考えていました。すると、たまたま松田さんが一人でビールを飲まれていた訳です。

私はRubyKaigi 2023では30分のトークもLTもプロポーザルを出していて、LTのみ採択されたという経緯もあって、それぞれのプロポーザルについてのフィードバックをもらいたいと思っていたので、尋ねてみたところ「OSSにパッチを送っているという点は良いですが、ydahさんはまだ誰でもやれることしかやっていないじゃないですか〜」というフィードバックをいただきました1。

また、「今回のセッションの中でydahさんと親和性がありそうなものでいうと、RuboCopにもよくパッチを送っているので、RuboCopでASTを扱っているんだからLramaとか見てみるといいんじゃないですか。Lramaはとても面白そうですよ。」という話をしていただきました。

そこで、私はDay1の金子さんのトークを聞いた時のワクワクを思い出して、「確かに楽しそうだなあ」と漠然と思いパッチを送り始めたというのが私がLramaに関わるきっかけでした。

RubyKaigi 2023 後から 2023年がおわるまで

Official Partyにて

そこからは定期的にLramaにパッチを送っていました。しかし、私は住んでいるのが大阪なこともあって中々その後すぐにオフラインのイベントでLramaの関係者と直接お会いしたことなかったように思います。

そして確かはじめて金子さんとお話ししたのは、大阪Ruby会議03でした。私はスタッフだったので、あまりゆっくりとお話しできなかったのですが、確か一部のセッションがすべて終わった後に「Lramaにパッチを送ってくれてますよね？今後もよろしくお願いします」と声をかけてもらったを覚えています。そして、前日に紹介したスタンドうみねこでの体験がよかったという話もしていましたね。

そこから、その後はKaigi on Rails 2023のDay1の2次会でこばじゅんさんとはじめてお話ししました。 大人数で向かったはずが、二人席で日本酒を飲みつつずっと話していたことを覚えています。日本酒が美味しすぎて飲み過ぎて話した内容は曖昧ですが、次はどこをやっていきます？という話をしていたので、我々はこの頃から実は変わらずparserの話を無限に生成していたのかもしれません。

そして、その後のKaigi on Rails 2023のオフィシャルパーティでお酒も飲まずにステージの辺りでparserの話をずっとしていたりしましたね。 これが #LR_parser_gangs の片鱗だったのかもしれないと思っています。金子さんからロードマップの話を聞いたりしつつ、当時はまだブログ記事になっていなかったLRパーサーを完全に理解した話を聞いていたのを覚えています。

yui-knk.hatenablog.com

yui-knk.hatenablog.com

そして、その後はRubyWorld Conference 2023でS.H.さんとも初めてお会いして、あの例のお店の前で金子さんから#12: Action is a local variableなどのRubyKaigi 2023のLTで時間が足りず話せなかったAdvanced Courseの話を聞いて笑っていたことを思い出します。

RubyWorldで言うと金子さんの思いを聞けたのもすごく良かったなと思っています。その話を聞いて、今後も私はLramaに関わっていくのだろうなと思ったことを覚えています。

そして、#LR_parser_gangsの正装こと大構文解析時代！ Parser age Tシャツのリリース。このTシャツは確か3色展開だったという記憶があるのですが、金子さん、こばじゅんさん、私と何も事前に示し合わせていないのにもかかわらず、全員が赤を選んでいたのですよね。#LR_parser_gangs は惹かれ合うという訳ですね（？）

なお、今回のトーク時の服装は事前の打ち合わせを行なっています。 　

そして、2023年最後のイベントがRuby 3.3 リリースパーティーです。確か一番前の方の席に座っていたことを覚えています。皆、#LR_parser_gangsの正装を着ていて凄く良かったですね。

ここで金子さんから「RubyKaigiのプロポーザルのレビューをしますよ」という話をいただいて、プロポーザルのレビューをしていただけることになりました。 この時期はgihyo.jp Ruby 3.3 特集の記事を書いている頃の時期だったと思うのですが、本当に丁寧にレビューをして下さってありがとうございました。

TitleやAbstractでRubyKaigiに参加している人に向けて、自分のトークに対して興味を持ってもらえるように考えるという観点は今後も大事にしたいと思っています。 また、想定読者層だけでなく、真の想定読者を具体的に決めるというのも今後のプロポーザルを書くにあたってやっていきたいと思います。

何度も書き直したものをレビューしていただいて無事にプロポーザルを書き切って提出しました。 そして、採択されたことを知った時は本当に嬉しかったです。

発表の話

Photo by @hsbt san

スライドはこちらです:

発表の内容としては、parse.yに生成規則のパラメーター化という概念を導入したという話をしました。 私たちがプログラミング言語を用いてプログラムを書くとき当たり前のように使える文法も誰かがそこに実装したからそこにあるわけです。

実はparse.yはかなりプリミティブな文法という厳しい制約の中で書くしかなかったということ、そしてLramaの誕生によってそこに新しく文法を拡張することで、parse.yのメンテナンス性が向上していくんだということ、そしてparse.yが悪魔城や、地獄や、魔境と呼ばれていた場所ではなくなっていくんだという、そんな未来の一片を感じていただけたのであれば幸いです。

私のトークは複数の異なる層の方に向けてそれぞれメッセージが伝わるように設計していました。 なので、ブログで様々な感想をいただいて非常に嬉しく思っています。Lramaやparse.yは本当に楽しいので、楽しそうだという印象を持ってもらえただけでも成功だと思っています。

また、私の発表の後にParameterizing Rulesのことや提案したことについて成瀬さん、akrさんのお話が聞けたのは非常に嬉しかったです。 いくつか方針も決まったのがあるので、やっていきます。

ブログ記事でのフィードバックでも頂いていたのですが、発表で扱ったParameterizing RulesやInliningについての記事についてはここにまとめていこうと思っています。 随時書いていくつもりですので少々お待ちください。

聞きにいけた発表について

Day0のなはーと近影

今回はDay2に登壇ということもあって、登壇まではソワソワしていたりスライドを直していたりで見たかったトークを観にいけなかったのが心残りでした..... 観たいトークがたくさんあるので、動画がアップロードされるのを楽しみにしています。

感想は書くと長くなり過ぎてしまって大変なことになるので、簡潔に書きたいと思いながら書いています。

Day1

Writing Weird Code

drive.google.com

本当に最高のKeynoteでした。WeirdなCodeの書き方を聞いていたら、突然Self TRICKが始まるの凄くよかったです。

こう、奥行きがあって様々な人が楽しめるトークで、例えば私が新卒の頃に戻って見たとしても楽しめますし、あと何十年先の私が見ても楽しめるのだろうなと思いました。

他の誰にもできない素晴らしいKeynoteでした。実際に会場で観ることができて本当に良かったです。

github.com

The grand strategy of Ruby Parser

speakerdeck.com

昨年は"私の"future visionだったのが、今年は"私たち"のgrand strategyという対比があるなと思っていました。 おそらくそれは去年から考えていたことで Ruby Parser開発日誌 (9) - RubyKaigi 2023で発表してきた ~ 世はまさに”大パーサー時代” ~ - かねこにっき で

"去年は一人でBisonを倒しました、今年はこれだけの仲間と一緒にこのボスを倒してきました"という話ができるといいな。

ということを書かれていて、本当にその通りになりましたね。 なぜLR Parserが良いのか、Lramaなのか、私"たち"はこの一年で何を成し遂げて私"たち"はどこに向かうのか、その大戦略を掲げた凄く良い発表でした。

また、これは昨年掲げたBisonを置き換えてparserをCRubyの内部からUniversal Parserとして独立させるということに対して、「金子さん以外の人にそれらのコードのメンテナンスをする人がいないのではないか？」という問いに対する強烈なアンサーだったのではと思っています。

1年前に何も分からなくて、ただワクワクするしかなかった私は金子さんの話の内容を理解出来ているんですよ。それもとても感慨深い発表でした。

Long journey of Ruby standard library

speakerdeck.com

default gemsをbundled gemsにしていく取り組みはとても尊いことで、更にとても大変そうに見えており...本当にありがとうございます。 ただ切り分ければいいだけでは勿論なくて、どのようにユーザーに伝えるかをケアするかを考えるのも大変そうだと思いながら聞いていました。 Rubyのバージョンを上げなくても問題を、問題を修正したバージョンのbundled gemsを利用することが出来るというのはとても良い世界だなと思いました。

Namespace, What and Why

speakerdeck.com

C++の文化圏に元々いたのでNamespaceの発表は非常に気になっていました。 Namespaceが入るとRubyが大きく変化するという機能なので、未来を感じて凄くワクワクしていました。 Ruby4.0の目玉機能になるかもしれないとのことで、非常に楽しみにしています。

Day2

Unlock The Universal Parsers: A New PicoRuby Compiler

slide.rabbit-shocker.org

parse.y is no longer a labyrinth!! まさか言及いただけると思っていなかったのでとても驚きました...! メモリ消費量が大きいVALUE/IMEMO/GCを着実に倒していき、凄まじい変化を定量的に見せるというのはやはり技術者としてカッコいい姿だと思っています。

Lrama-gen parserが真にUniversalなparserになっていくとともに、PicoRubyやmrubyのparserがCRubyと同じになっていくという未来って改めて凄いことだなと思いました。

RuboCop: LSP and Prism

speakerdeck.com

koicさんの362 日の Rubyist 活動が込められたトークでとてもよかったです! LSPの到来によってコミット前にRuboCopを実行することから解放されるのは本当に素晴らしい変更だと思っていて、大変お世話になっています。ありがとうございます。

一日目の金子さんの講演によって結末が変わって、追加のスライドを作ったと仰っていたスライドもとてもよかったです。 次の "362 日" には、どういう未来を信じてやっていけば良いかを改めてじっくりと考えるきっかけになりました。

Lightning Talks

Rearchitect Ripper

speakerdeck.com

Ripper has longstanding bugs like Bug #10436. The root cause of the bug is the limitation of Bison. However we can fix the issue now. Only on the Lrama.

このAbstructから良すぎるんだよな.....と思っていました。速度はPodcastを2倍速で聞いていた勢からだと聞き取れない早さではなかったです。 本当に楽しそうに話すんですよねと思いながら聞いていました。

Contributing to the Ruby Parser

speakerdeck.com

parse.yへのパッチを送るお話で、出来ることをやってみるという向き合い方に凄く共感していました。 最後、時間切れによって言葉としては聞けなかったのですがparse.y is Not Hell! We can hack parse.y!! ですね。

Drive Your Code: Building an RC Car by Writing Only Ruby

speakerdeck.com

Kyobashi.rbのPareja2ことhachiさん。Demoとてもよかったです。 電子工作がRubyで出来てラジコンがRubyで動くって凄く夢があっていいなと思いました。

こんな素敵なKyobashi.rbというコミュニティもあるので是非皆様のご参加をお待ちしています。

kyobashirb.connpass.com

Day3

From LALR to IELR: A Lrama's Next Step

speakerdeck.com

LR_parser_gang 締めくくりのトーク。完全に初見の気分で楽しむためにIELRの論文は読んでこなかった3のでとても新鮮で楽しく聴いていました。 論文から実装に落とし込む様というのは、やはりかっこいいなと思います。

トークを聞くまでは思っていたよりも小さい変更でIALRに対応できるの凄いなと驚いていたのですが、LALRで構文解析表を作った後に再計算すると知ってなるほど！と思いました。"Mysterious conflicts"になる実ケースが気になっています。どういうときに発生するのだろう...?

発表内で一緒に頑張っている仲間がいたから頑張ろうと思えたと仰ってましたが私も同じです。こばじゅんさんの存在があったから私も頑張れました。本当にありがとうございます。

Matz Keynote

Ruby4 へのバージョンアップがとうとう見えてきているのかという気持ちになりました。 Parserは今後どうなるのかというところですが、私は自分が信じているところでやっていくしかないのでやっていくぞというお気持ちです。

参加したイベント

これは唐突なやちむん通りのシーサー

以下のイベントに参加させていただきました。非常に楽しい時間をありがとうございました!

Day0

esminc.doorkeeper.jp

koicさんにRuboCop RSpecのv3.x系へのメジャーバージョンアップにあたって、色々と相談させていただきました。

また、この時にkoicさんの発表でも紹介されていたAutoCorrect: contextualのお話をお聞きしてRuboCop RSpecでも対応していきますという話をしていました。 ブログや大阪Ruby会議のあれそれで全然進められていないので、引き続きやっていきます。

koicさんと乾杯して、ゆっくりお話できたのは今回がはじめてで、この後の2次会でもDay1もDay3でもたくさん乾杯ができました。とても楽しかったです!

私のOSS活動しぐさはkoicさんとのRuboCopでのパッチ上でのやり取りで、その多くが形作られたものだと思っていて本当に感謝しています。ありがとうございます。

Day3にて直接話した記憶がありますが、私の初めてのOSSへパッチを送ったのはRuboCop Peroformanceへのパッチでした。

ドキドキしながらパッチを送ったのを今でも覚えています。そして、マージされた時の得も言われぬ高揚感も。 その時の体験が良すぎて、その体験がなければ今のようなOSSとの関わりはなかったのだと思います。

本当にありがとうございます。 そして、RuboCop RSpecはydahさんがいるから安心できると仰って貰えたのは非常に嬉しかったです。

またどこかでお会いした時は乾杯しましょう。（次は大阪ですかね。）

さて、話はNight Cruiseでの会話の話に戻り、ここからすでにずっとParserの話をしていました。

金子さん「型推論欲しい〜〜」、こばじゅんさんと僕「わかる〜〜」の図ですね。

パーサー三銃士を連れてきたよ！の例のコラが作成される時にはこの写真が使われるのでしょうね。

また、中田さんにもParameterizing Rulesの件でフィードバックいただいてありがとうございましたとご挨拶できてよかったです。 「過去10年で最高の parse.y」という言葉はここでParser gangsなテーブルでの話の中で聞いた記憶があるのですが、これを来年からも更新していかねばならないですねと思っていました。

Day1

ti.to

一回ホテルに荷物を置いていたらバスに乗り遅れてしまい、そのことに気づかずになはーと方面に向かっていたら合流したやんちゃさんとタクシーを探しながら会場に歩きつつ向かうというイベントから始まりました。お名前を聞きそびれてしまったのですが、途中で合流したお二人のRubyistの方と4人で無事タクシーに乗ることができて間に合ってよかったです。

そんなOfficial Partyでの一番の印象に残っているイベントはLramaのコミットビットをいただいたことですね。 これがRubyKaigiか.....と凄く感慨深い気持ちになりました。

そして、この後のn次会ではどんどん発表が迫ってきて精神的におかしくなっていて、おかしくなっていました.....。 この辺りから緊張により記憶が飛んでいるところもあってかなりおかしくなっていました..... 本当にご心配をおかけしました.....。

どうやって行ったか覚えていないステーキ

3時頃に寝たはずが翌日の午前5時に目が覚めてしまってそこから覚醒してしまって寝れなくて、スマホを眺めると上記の写真がカメラロールにあったのですが、本当にどうやって行ったか覚えていなくて限界状態だったんだなあと思いました。

身体も異常事態だったのか、ステーキの味が本当に感じられなくって焦っていたことは覚えています。また、酔いを覚まさないと.....!と思って深夜にライスを大盛りでおかわりして食べるという奇行に走っていたことも.....。そしてそのおかげで今胃が異常なまでにもたれていることも.....。

狂気の沙汰とはまさにこのことだなと思いました。

Day2

leanertechnologies.connpass.com

rubykaigikaraoke.doorkeeper.jp

様々な話をしていました。普段あまり話さないことについても話していましたね。 自分のトークも終わり解放感がありましたが、終わってしまったなあと喪失感もありました。

Day3

美味しいお肉をご馳走になったあと、シャークになりました。Follow The Sun, Catch The Sun.

connpass.com

After Partyでも様々な方とお話ができて本当によかったです。そして私の印象に残っていることは、jokerさんに感想を聞くことが出来たことです。つまり以下のjokerさんのブログの私の視点でのお話です。

joker1007.hatenablog.com

私のトークについて金子さんと戦略を立てていた時から、真の想定リスナーとしてjokerさんを想定して作成していました。 なぜかというと以下のjokerさんの記事にあるように、jokerさんはparser熱にあてられて自分でparserを実装してみるくらいには気持ちがある方だからです。

joker1007.hatenablog.com

そして、jokerさんを私も真の想定リスナーとしたいと思ったのは、実は私にとってjokerさんは私をRubyの世界に引き込んだRubyistなのです。 というのも、私は新卒で入社した会社では主に組み込み系や制御系のシステムを開発する仕事をしていて、業務で主に使用していたのはC言語やC++でした。

そして、新入社員だった頃の私がたまたま見つけて参加した、関西Ruby会議06そして、関西Ruby会議2017で登壇されていたのがjokerさんでした。

Rubyのことは「たのしいRuby」を読みつつざっと使い方を知っているぐらいだった当時の私には何も分からないという状態だったのですが、jokerさんの話はテックな話をjokerさん自身が誰よりも楽しそうに話しているのが凄く印象的で、「ここまで熱中して話せるRubyって楽しそうだなあ」「この人の話が分かるようになりたい」と思ったわけです。

特に関西Ruby会議2017ではgemの開発についてのお話で、自分が作ったライブラリを公開していろんな人に使ってもらえるのって凄く楽しそうでは...?というOSSの開発への興味もjokerさんのお話を聞いて感じたのでした。

その頃からかなり時間は経ってしまいましたが、現職への転職をきっかけにRubyを仕事として使うようになって、OSSの開発が趣味となり今に至るわけです4。そんな私にとっての憧れのRubyistでして、その人を想定聴衆としてトークを組み立てているというのは非常に感慨深いものがありました。

そして、ブログ記事で言及までしてもらった上に、Day2で特に印象に残ったと言ってもらえた訳です。この言葉をいただけたなら大成功だったなと思い、感無量でした。

さいごに

首里から街を眺めるシーサー

まだまだ話したいことはあるのですが、終わりが本当に見えなくなるので、この辺りで終わりにしようと思います。 本当に楽しすぎて、まだ終わらせたくない気持ちもありますが、そろそろ現実に戻っていく時間だなと思います。

#LR_parser_gangs の皆様へ、これからもよろしくお願いします。これからもやっていきましょう。 次の "362 日の Rubyist 活動" のテーマも決まったので私も後は進んでいくだけなのでやっていきます。

RubyKaigi中にお会いしたりお話しさせていただいた皆様、とても楽しい時間を過ごせました。本当にありがとうございました。 そして、今年のRubyKaigiも本当に最高でした。オーガナイザーの皆様、スタッフの皆様ありがとうございました。

それでは、次のパッチでお会いしましょう。Adiós!

  1. この話をするたびに、松田さんが「そんなひどいことをいう人がいるんですか〜？」と言うところまでがお決まりの流れになっています↩
  2. 文脈 https://en.wikipedia.org/wiki/Tetsuya_Naito↩
  3. そもそも読む時間が捻出できなかったとも言いますね.....はい.....↩
  4. Kaigi on Rails 2023のn次会のビアパブで突然jokerさんにこのような話を突然して、驚かせてしまったことを覚えています.....↩

Ruby構文解析器 開発日録#2

昨日に引き続き筆を執っています。今日はクリスマスイブですね。

さて、今回はANDPAD Advent Calendar 2023の24日目の記事として、今年Lramaの開発で手を動かしてきた内容の中で、これまで発表していないものを紹介します1。もうすぐ今年も終わりますので、いわゆる「今年の振り返り」となる内容です。

今年はどれくらい手を動かしたかというと大体140コミットほどでした。2 グラフを眺めているとKaigi on Rails 2023、RubyWorld Conference 2023辺りでKaigi Effectを受けていることが目に見えるので、とてもおもしろいですね。それでは、振り返りをしていきましょう。

#includeを明示しなくていいようにする

Bisonとの差分を解消した対応です。Bisonはヘッダーファイルを生成するオプションをつけると、#includeを明示しなくてもヘッダーファイルをインクルードしてくれます。 これをLramaでも同じ挙動にするために、-h、--header、-dオプションをつけた場合には、#includeを明示しなくてもヘッダーファイルをインクルードするようにしました。

たとえば、以下のコマンドを実行したとします。

lrama calc.y --header=calc.h -o calc.c

この場合、calc.yからcalc.cとcalc.hが生成されますが、calc.yにおいて以下のように#include "calc.h"を明示する必要がなくなりました。

#include <stdlib.h>
#include <ctype.h>

-#include "calc.h"

static int yylex(YYSTYPE *val, YYLTYPE *loc);
static int yyerror(YYLTYPE *loc, const char *str);

今までは#includeディレクティブにヘッダーファイルの名前を決め打ちで書く必要があったので、コマンドを以下のように変更するとたちまちコンパイルエラーになってしまっていました。3

lrama calc.y --header=other.h -o calc.c

Helpコマンドの改善

Lramaに文法ファイルを渡して色々と試していた時に、どんなオプションがあるのだろうと思っておもむろにlrama --helpを実行したところ、以下のような出力がされていました。

❯ lrama --help
Usage: lrama [options]
    -V, --version
    -S, --skeleton=FILE
    -t
    -h, --header=[FILE]
    -d
    -r, --report=THINGS
        --report-file=FILE
    -v
    -o, --output=FILE
        --trace=THINGS
    -e

Bisonのオプションと概ね同じ意味になっているとは思いましたが、--helpコマンドを実行した時に、どんなオプションがあるのかを一目でわかるようにするために、オプションを整理して表示するようにしました。

❯ lrama --help
Lrama is LALR (1) parser generator written by Ruby.

Usage: lrama [options] FILE

STDIN mode:
lrama [options] - FILE               read grammar from STDIN

Tuning the Parser:
    -S, --skeleton=FILE              specify the skeleton to use
    -t                               reserved, do nothing

Output:
    -h, --header=[FILE]              also produce a header file named FILE
    -d                               also produce a header file
    -r, --report=THINGS              also produce details on the automaton
        --report-file=FILE           also produce details on the automaton output to a file named FILE
    -o, --output=FILE                leave output to FILE
        --trace=THINGS               also output trace logs at runtime
    -v                               reserved, do nothing

Error Recovery:
    -e                               enable error recovery

Other options:
    -V, --version                    output version information and exit
        --help                       display this help and exit

そして、--helpコマンドを整理していて気づいたのですが、いくつかreservedになっているのみのオプションもあったので、整理しておいて良かったと感じました。 また、この副産物としてBisonとのオプションの差異に気づくこともできました。

具体的には生成するヘッダファイルを生成するのためのオプションは-Hなのですが、Lramaでは-hとなっていました。 これは段階的に、-Hオプションへと移行していて、v0.5.8以降のLramaではBisonとの差異は解消しています。

エラーメッセージの改善

Lramaはv0.5.7から、内部に持っている手書きパーサーが、Raccによる自動生成したものに置き換わりました4。つまり、parser.yという文法ファイルからparser.rbを生成するように変わりました。 それに伴い、内部パーサーで文法ファイルを解析する際に、もしパースエラーが発生した場合にはRaccが提供しているon_errorでerror_valueから情報がとれるのでエラーメッセージがリッチにできます。

なので、パースエラーが発生した場合に、以下のようにファイル名と位置情報とエラーが発生した周辺をエラーメッセージとして表示するようにしています。

❯ lrama -d test.y
parser.y:400:in `on_error': a.y:5:7: parse error on value #<struct Lrama::Lexer::Token::Ident s_value="invalid", alias_name=nil> (IDENTIFIER) (Racc::ParseError)
%expect invalid
        ^^^^^^^
        from racc/parser.rb:276:in `_racc_do_parse_c'
        from racc/parser.rb:276:in `do_parse'
        from parser.y:386:in `block in parse'
        from /ydah/lrama/lib/lrama/report/duration.rb:14:in `report_duration'
        from parser.y:381:in `parse'
        from /ydah/lrama/lib/lrama/command.rb:11:in `run'
        from lrama:6:in `<main>'

これによって、よりエラーとなった位置が分かりやすくなり、開発の体験を少しでもよくすることができたのではないかと思っています。 また、Lramaの内部でいくつか残っていたraiseだけしていた箇所も、それぞれ例外が発生した理由を追加しています。（すべて倒しきったはずです）

パフォーマンスの改善

Profileによるとlexerがそれなりに重かったです。 LexerではStringScannerを使って文法ファイルを読んでトークン列に分割していっているのですが、StringScanner#getchで一文字ずつ読んでいる箇所があり、ここがボトルネックになっているようでした。なので、StringScanner#scanで読めるところまで1回で読んでしまうように変更しました。

この変更によって、約30%ほど処理時間が改善しています。

Before

❯ lrama --trace=time -o parse.tmp.c --header=parse.tmp.h parse.tmp.y
parse    4.38929 s
compute_lr0_states    0.88006 s
compute_direct_read_sets    0.06813 s
compute_reads_relation    0.01174 s
compute_read_sets    0.04809 s
compute_includes_relation    0.72033 s
compute_lookback_relation    1.40715 s
compute_follow_sets    0.12471 s
compute_look_ahead_sets    1.00162 s
compute_conflicts    0.06503 s
compute_default_reduction    0.00617 s
compute_yydefact    0.08520 s
compute_yydefgoto    0.07973 s
sort_actions    0.00674 s
compute_packed_table    0.41180 s
render    0.09383 s

After

❯ lrama --trace=time -o parse.tmp.c --header=parse.tmp.h parse.tmp.y
parse    0.93149 s
compute_lr0_states    0.90139 s
compute_direct_read_sets    0.07115 s
compute_reads_relation    0.01218 s
compute_read_sets    0.04671 s
compute_includes_relation    0.69610 s
compute_lookback_relation    1.35323 s
compute_follow_sets    0.11844 s
compute_look_ahead_sets    1.01038 s
compute_conflicts    0.06607 s
compute_default_reduction    0.00666 s
compute_yydefact    0.08754 s
compute_yydefgoto    0.08042 s
sort_actions    0.00655 s
compute_packed_table    0.45709 s
render    0.08769 s

stackprofで見ても以下の通り、Lrama::Lexer#lex_c_codeという今回修正したメソッドの速度が改善した5ことが分かります。

Before

❯ bundle exec stackprof --limit 10 tmp/stackprof-cpu-myapp.dump
==================================
  Mode: cpu(1000)
  Samples: 6449 (3.30% miss rate)
  GC: 1784 (27.66%)
==================================
     TOTAL    (pct)     SAMPLES    (pct)     FRAME
      1858  (28.8%)        1858  (28.8%)     (sweeping)
      1305  (20.2%)        1216  (18.9%)     Lrama::Lexer#lex_c_code
       531   (8.2%)         371   (5.8%)     Struct#==
       785  (12.2%)         339   (5.3%)     Lrama::States#compute_look_ahead_sets
       294   (4.6%)         252   (3.9%)     Lrama::Context#compute_packed_table
       192   (3.0%)         192   (3.0%)     Integer#>>
       186   (2.9%)         186   (2.9%)     Integer#&
       188   (2.9%)         158   (2.4%)     Lrama::Lexer::Token#==
      3027  (46.9%)         147   (2.3%)     Array#each
       637   (9.9%)         138   (2.1%)     Lrama::States#compute_lookback_relation

After

❯ bundle exec stackprof --limit 10 tmp/stackprof-cpu-myapp.dump
==================================
  Mode: cpu(1000)
  Samples: 3711 (0.51% miss rate)
  GC: 186 (5.01%)
==================================
     TOTAL    (pct)     SAMPLES    (pct)     FRAME
       797  (21.5%)         338   (9.1%)     Lrama::States#compute_look_ahead_sets
       474  (12.8%)         307   (8.3%)     Struct#==
       329   (8.9%)         290   (7.8%)     Lrama::Context#compute_packed_table
       246   (6.6%)         240   (6.5%)     Lrama::Lexer#lex_c_code
       191   (5.1%)         191   (5.1%)     Integer#>>
       180   (4.9%)         180   (4.9%)     Integer#&
       187   (5.0%)         157   (4.2%)     Lrama::Lexer::Token#==
       592  (16.0%)         146   (3.9%)     Lrama::States#compute_lookback_relation
      3037  (81.8%)         138   (3.7%)     Array#each
       137   (3.7%)         137   (3.7%)     Lrama::States::Item#hash

さいごに

今回、紹介したものは細々とした対応が多かったかもしれないですが、少しずつでもLramaをより良くしていけたのではないかと思っています。 昨日の記事で紹介したParameterizing rulesの実装も着々と進んでいて、parse.yをより読みやすく理解しやすいものにしていくというゴールに向けて、着実に進んでいると感じています。来年も引き続きやっていきたいと思っているので、よろしくお願いします。

  1. 4日ほど前にまったく同じコンセプトの記事がありましたね。↩
  2. 実際に活発に開発をしだしたのは8月頃からなので、実質4か月ほどです。↩
  3. ruby/rubyにおいては対応前のLramaでもbuildに成功していたのでブロッカーにはなっていなかったですが、ヘッダーファイルの名前を決め打ちで書く必要がなくなるのは良いので、この対応を行いました。↩
  4. こばじゅんさん(@junk0612)の偉業です。この変更により文法の追加が非常にやりやすくなりました。↩
  5. 変更行はごく僅かですが結果としてあらわれると、とても気持ちいいですね。↩

Ruby構文解析器 開発日録#1

Ruby構文解析器 開発日録はこちらで書いていこうと思い立ち、すでに私のブログで書いていたものはここにも転記することにしました。 2024/05/25

以下から原文です。

最近はPure Ruby LALR parser generatorであるLramaにパッチを送っています。 気がつけば12月もあとわずかとなり、Ruby3.3.0のリリース日も近づいてきましたね。5月半ばに開催されたRubyKaigi 2023で金子さん(@spikeolaf)の「The future vision of Ruby Parser」を聞いてから、約半年が経ちました。あの時の自分はまさか半年後には自分がパーサージェネレーターの開発に関わっている人生を送っているとは思いもしなかったと思います。

今回のRuby3.3.0のリリースノートには、私が実装した機能が載っていてとても感慨深いです。

Use Lrama instead of Bison
...

  • Parameterizing Rules (?, *, +) are supported, it will be used in Ruby parse.y

継続して関わっていこうと思っているので、実装した機能や、学んだこと、今考えていることを記録として残していこうと思います。 今回は、Kyoto.rbやFukuoka.rbで発表した内容をまとめたものを書いていこうと思います。以下に発表資料を貼っておきます。

Lramaとは何なのか

Lramaとは何かを簡単に説明すると、Rubyで書かれたLALR (1)パーサージェネレーターです。パーサージェネレーターなのでパーサーそのものではなく、文法ファイルをインプットとしてパーサーを生成するためのツールです。 Ruby 3.2まではGNU Bisonという、パーサージェネレーターを使用していましたが、このBisonを置き換えるために金子さんによって作られました。

なお、LramaはRubyKaigi 2023の2日目にBisonからLramaへの移行は完了しています。

なぜ、BisonからLramaに置き換えたかったのか、その理由はいくつかあります。その内の1つは、Bisonのバージョンに引きづられずにすむという点です。 たとえばユーザー1ごとに使用しているBisonのバージョンは異なります。つまり、複数のバージョンを対象にメンテナンスをしなければなりませんでした。

要するに、異なるバージョンのBisonで動作するようにするための労力を払っていく必要があり、それをメンテナンスしていくのは簡単ではないです。 また、例え最新のバージョンのBisonで新しい機能が導入されたとしても、その新機能を使えないという制約がありました。 Lramaへと置き換えることで、これらの制約から解放されます。

つまり、Lramaへ置き換えることで、どうなるかというと以下の大きなメリットがあるということです。

  • 複数バージョンのBisonをサポートする必要がなくなる
  • 最新のBisonの機能を使えるようになる（実装すれば）
  • Bisonに縛られないので、もしBison以外のパーサージェネレーターの便利な機能も使えるようになる（実装すれば）

Lramaが目指すもの

Lramaが目指すものは、Bisonの機能をそのままRubyに移植することではありません。 詳しくは金子さんのRuby Parser Roadmapを参照していただければと思いますが、いくつかあるGoalのうちの1つに、parse.y for Under graduateというGoalがあります。 これは、parse.yををより読みやすく理解しやすいものにしていくというものです。歴史的な経緯によって、parse.yは複雑になってしまっているので、これを解消していくことが目標です。 具体的にいうと教科書などで構文解析について学習していれば、parse.yを読んで理解できる状態に持っていくことが目標です。

このゴールを達成するために、現在は前述の通りBisonに縛られることがなくなったので、パーサーを生成するための文法ファイルのBNF2の記法をよりリッチにしていくアプローチをとっています。 Bisonにはプリミティブな記法しか提供されていないので、他のパーサージェネレーターにはあるような便利な記法をLramaに実装していくことで、より読みやすく理解しやすい文法ファイルを作ることができるはずです。

我々はBisonからLramaに置き換えることで、どんなパーサージェネレーターの機能も実装すれば使えるようになったのです。 取り込むために文法を調整しながら実装していけばいいだけですし、実装すればするほど便利な文法が増えていくので、とても良いですね。

Menhirがやってきた

現在、LramaにMenhir3で提供されている記法を実装していっています。 MenhirはOCaml向けのLR(1)パーサージェネレーターです。OCamlにはocamlyaccというパーサージェネレーターがありますが、Menhirは互換性を保ちつつocamlyaccの機能を拡張したものです。 つまりはLramaと同じでより力を引き出したパーサージェネレーターを作るという目的を持って作られている訳ですね。

Menhirには便利な記法がいくつかありますが、その中の1つであるParameterizing rulesという記法を実装していっています。 Prameterizing rulesとは非終端記号の定義を、他の（終端または非終端）記号でパラメーター化できるというものです。つまり、文法ファイルにおける共通的なパターンのためのシンタックスシュガーを提供できる機能です。

ルールは基本的にはユーザーが定義するものです。要はマクロを定義しているようなものと考えてもらえれば良いと思います。 ただ、いくつかの汎用的なパターンについてはstandard libraryとして提供することを想定していて、これらはユーザーが定義する必要はありません。

言葉で説明してもよくわからないと思うので、実際にどのような記法なのかを見ていきましょう。 たとえば、以下のような文法ファイルがあったとします。

args    : arg
        | args ',' arg
        ;

これは、引数のリストを表現する文法です。4この文法をParameterizing rulesを使って書き換えると以下のようになります。

separated_list(',', arg)

こう見てみると、引数のリストを表現する文法ということがより明確になりますね。また、記述量も減っているので、より読みやすくなっています。 このルールについてはstandard library5として提供しているので、ユーザーはルールを定義する必要はありません。 Ruby 3.3では以下の表に示す、ルールをstandard libraryとして提供しています。

Name Recognizes Alias
option(X) є ｜ X X?
list(X) a possibly empty sequence of X’s X*
nonempty_list(X) a nonempty sequence of X’s X+
separated_list(sep, X) a possibly empty sequence of X’s separated with sep’s
separated_nonempty_list(sep, X) a nonempty sequence of X’s   separated with sep’s

また、Aliasに示すように正規表現でよく見るような6シンタックスシュガーも実装しています。

これらのstandard libraryはそれぞれのルールごとに展開する処理として実装していますが、最終的にはそれぞれのルールを定義した文法ファイルのみを提供するようにする必要があります。 Menhirでも同様に文法ファイルを提供して、ユーザーがパーサージェネレーターに渡す文法ファイルの前にloadすることで、standard libraryとして提供している7ので、Lramaでも同様に実装していく予定です。 このためには、ユーザー定義のルールのサポートを実装・改善していく必要があるので、これからの課題となります。

まとめ

Lramaとは何か、Lramaが目指すものは何か、BNFの記法の拡張のためにMenhirの機能を移植しているという内容を書いてきました。 Ruby Parser Roadmapを見た方はわかると思いますが、まだまだLramaが達成すべきGoalはたくさんあります。 パーサー/パーサジェネレーターの開発は難しいこともあるかもしれませんが、とても楽しいので是非興味がある方は参加してみてください。きっと楽しいと思います。

  1. ここでいうユーザーとは、Rubyを使用している人のことではなく、parse.yを触っているRuby開発者のことを指します↩
  2. Backus–Naur formのことを指します↩
  3. 余談ですが、Menhirはいわゆるモノリスやメガリスと呼ばれる石の記念物のことです。日本にもいくつか有名なMenhirがあるらしく、岐阜にはたくさんのMenhirがあるそうです。そうだ、岐阜に行こう。↩
  4. BNFは皆さん気がつくと読めるようになっているはずなのできっと説明は不要なはず。(BNFはBokutachi No Friendの略でもあります(?))↩
  5. 要は組み込みライブラリのようなものと考えてもらえれば良いと思います。↩
  6. https://docs.ruby-lang.org/ja/latest/doc/spec=2fregexp.html#quantifier↩
  7. https://gitlab.inria.fr/fpottier/menhir/-/blob/20230608/src/standard.mly?ref_type=tags↩