こんにちはかねこです。私はCRuby(ruby/ruby)のコミッタをやっているのですが、最近はCRubyをメインのターゲットとしてLALR parser generator Lramaの開発をしています。 現役のLALR parser generator開発者として、日頃私以上にLR parserのことを考えている人はそうはいないでしょう。 この記事を読んでいる皆さんは構文解析、なかでも特にLR parserを理解するためにいろいろな教科書や記事を読んできたと思います。 一方でどんなに調べてもどこか腑に落ちない部分が残っているのではないでしょうか。 LR構文解析を勉強すると構文解析表に出会うとおもいます。 構文解析表を作る方法そのものは教科書に説明が載っており、その通りに手を動かせばこのような表を作ることはできるでしょう。 また出来上がった構文解析表をもとに実際に構文解析する手順も理解で

5/10から5/14の5日間、RubyKaigi 2023に参加するために松本市に行ってきました。前回参加したのがRubyKaigi 2019の福岡のときなので、じつに4年ぶりの参加でした。 今回はコミッター/登壇者/LTスピーカーとしての参加になりました。その結果、0日目のDevMeeting含めて3種類のスライドをつくり、3日目の"Ruby Committers and The World"含めて3回登壇するというイベント盛りだくさんなKaigiでした。 いやー、自分のRubyKaigi史上、最高のRubyKaigiでしたね。まさにParserKaigiだったのではないでしょうか。 いろいろ書きたいことはありますが、まずは時系列で振り返っていきましょう。 Day 0 (5/10) - DevMeeting DevMeetingに参加するためDay 0から松本へ向かいました。新宿から特急

前回のあらすじ Ruby Parser開発日誌 (7) - doについて考える - かねこにっき Rubyのdoのもつ複雑さを中心にMaintainabilityの改善方法について考えました。Practical LR Parser Generationで紹介されているNonterminal attributesというアプローチにprecedence(優先度)をさらに組み合わせることで、lexerの状態として管理しているものを構文に組み込むことに成功したのでした。 ところでRuby Committers vs The Worldの2022や2021をあらためてみると、おもに次の3つが解くべき問題だと言われています。 Usability (Error-tolerant parser) Maintainability Universal Parser 1と2についてはすでに分析と実装をしてきまし

前回のあらすじ Ruby Parser開発日誌 (4) - かねこにっき Error Recoveryに関する理解も深まり、Rubyのparserへ実装するために3つの実装方法を検討しましたが、どれもあまり簡単な方法ではありませんでした。この問題を解決するためにLALR parser generatorを実装したので今回はその紹介をしたいとおもいます。 Lrama LALR (1) parser generator github.com 前回検討したとおりBisonを使ってError RecoveryをRubyに実装していくのは困難を伴います。これを解決するために自前でparser generatorを実装し、generatorおよびtemplateの両方を自分で管理するという方法を思いついたので実装しました。 名前の由来 Lramaでリャマと読みます。LALR parser genera

今年の後半は久しぶりにRubyに機能を追加したりしており、Ruby 3.2に3つの機能(もしくは変更)をいれたので紹介したい。 Ruby 3.2リリースまであと一ヶ月くらいあるので、現時点でBugなどをみつけたら教えてほしい。 1. RubyVM::AbstractSyntaxTreeにkeep_tokensオプションを追加した 名前の通りtokenの情報を保持するようにし、あとでNodeからtokenを取得できるようにするためのオプション。 RubyVM::AbstractSyntaxTreeの.parse, .parse_file, .ofの3メソッドで使うことができる。 とりだすときはRubyVM::AbstractSyntaxTree::Nodeの#tokensもしくは#all_tokensでtokenを取得できる。 root = RubyVM::AbstractSyntaxTre