前回のあらすじ
Error Recoveryに関する理解も深まり、Rubyのparserへ実装するために3つの実装方法を検討しましたが、どれもあまり簡単な方法ではありませんでした。この問題を解決するためにLALR parser generatorを実装したので今回はその紹介をしたいとおもいます。
Lrama LALR (1) parser generator
前回検討したとおりBisonを使ってError RecoveryをRubyに実装していくのは困難を伴います。これを解決するために自前でparser generatorを実装し、generatorおよびtemplateの両方を自分で管理するという方法を思いついたので実装しました。
名前の由来
Lramaでリャマと読みます。LALR parser generatorのYaccやBisonの流れをくむものとして、リャマという名前にしました。LR parser generatorなのでLlama (LL)ではなくLrama (LR)と綴ります。
parser generatorの概要
主な特徴は以下の通りです
- Rubyによる実装
- Bisonの入力ファイルと同じ形式のファイルを入力とし、C実装のparserを生成する
- 生成可能なparserはLALR(1) parser
- Rubyの
toolディレクトリにインストールして使う想定 - いつでもBisonをLramaに置き換えることが可能なレベルには実装が終わっている
Rubyによる実装
レポジトリをみてわかるようにRubyで実装されています。RubyをソースコードからbuildするときにはBASERUBYという形でRubyが要求されています。LramaはBASERUBYで実行されることを想定しています。
入力と出力
現在のBison用のファイル、つまりparse.yを入力にとります。出力はC実装のparser、つまりparse.cです。
ruby/rubyとの関係
gemとしても配布していますが、ruby/rubyに関していえばtoolディレクトリにインストールして使う想定です。インストールというのは定期的にLramaのソースコードをruby/rubyのtoolディレクトリにコピーしてコミットするという運用を考えています。
RubyのMakefileはYACC変数でbisonコマンドを差し替えることができるので、toolディレクトリにインストールする以外の作業なしで切り替えが可能です。具体的にはLramaのCIでRubyをbuildしているこの行をみてください。
完成度
現在のRubyのparser generatorとして必要な機能は全部実装してあります。
Ruby 3.0.5, 3.1.0, 3.2.0でBison 3.8.2と同等のCコードを出力することを確認しています。
またintegration testとして、Rubyのmaster branchでLramaを使ってRubyをbuildしmake test-allがパスすることを確認しています。
問題は解決したのか
前回明らかになった問題は大きく2つに分けられます。どちらもLramaを実装したことで解消しました。
1. Bisonのテンプレートファイルという実装の詳細に依存すると大変
今後必要な機能はLramaに実装し、LramaとRubyはparse.yで常にやり取りするようになります。なのでRuby側でparse.cをさらに編集したり、テンプレートファイルを持ったりする必要はありません。
2. Bisonのversionをコントロールするのが大変
常にtool以下にインストールされた実装にのみ依存するようになるので、ruby/rubyのコミットが決まればparser generatorの実装が一意に決まるようになります。
副次的な効果として、"(手元のBisonのversionが変わったせいで)なにもしないのに壊れた"が発生しなくなります 1。
次回予告
拡張可能なparser generatorの実装が手に入ったので、これを利用してRubyのparse.yのMaintainabilityを改善できないか検討・実装を進めています。次回はMaintainabilityに関するお話をしたいと思います。
