前回のあらすじ
LR parserの仕組みとInsert/Delete/ShiftによるError Recoveryについて、具体例を交えながら理解を深めました。 今回はいよいよError RecoveryをどうやってRubyに実装していくかを考えていきましょう。
実装方法を検討する
現状を確認する
はじめに現在のRubyのparserがどのように実装されているのか確認しましょう。 Rubyではlexerは手書き、parserの生成にはBisonを使っています1。
大雑把にいうとparse.yをBisonに渡してparse.cとparse.hを生成して、それらをコンパイルして使っています2。
parse.y -- bison --> parse.c & parse.h
つまりError Recoveryを実装するということは何かしらの方法でparse.c(とparse.h)にError Recoveryのコードを実装するということになります。
ちなみに https://www.ruby-lang.org/ で配布されているtarやzipにはparse.cもparse.hも生成済みのものが入っていますので、リリース済みのRubyをrbenvなどでインストールする場合には手元にBisonは必要ありません。Rubyをソースからビルドするときやtarやzipを作る際にはBisonを手元にインストールしておく必要があります3。
実装しないといけない機能
最低限のError Recoveryを実装するとして、parse.cに以下のような変更が必要になります。
1) Syntax Errorに遭遇したときの状態をもとにして、Error Recoveryに必要なInsert/Delete/Shiftの組み合わせを計算する関数を実装する
例えばyyrecover関数としてこの機能を実装します。
2) Error RecoveryでInsertするトークンを初期化する関数を実装する
yyrecover関数はtIDENTIFIERやkeyword_thenといったトークンの種類については決定してくれます。しかしそのトークンのsemantic valueについてはparser generatorを使う側の我々が決めないといけません。semantic valueというのはそのトークンの具体的な値のことで、例えばexitもputsも構文解析上はtIDENTIFIERというトークンになりますが、一方で構文解析より後の工程では再びexitやputsといった情報が必要になります。Error Recoveryは生成規則という文法上の情報をもとに行うので、トークンの種類を決定することはできますが、その具体的な値について決めることはしません。なのでparser generatorの利用者がトークン初期化用の処理を書けるようにして、それをparse.cに組み込む必要があります。
3) Bisonの生成するparserと1, 2で実装した関数を統合する
parserのerror時の挙動を変更してyyrecover関数を呼び出し、その結果に対して2の初期化関数を呼ぶ必要があります。yyrecoverを呼び出す前には今もっているトークンを一時的にどこかに退避する必要もあります。またyyrecoverは複数のトークンを返すことがあるので、それらのトークンをshift仕切るまではyyrecoverの戻り値を、shiftし終わったあとはyyrecoverを呼び出す前にもっていたトークンを復旧して使うという処理を追加します。
インプットif endをif true then endに修復するという前回の例をもとに具体的な解説をしましょう。
ifをshiftしてnext tokenがendになったときにerror状態になります。このときendはすでにlexerからparserに渡っているので、Error Recoveryをする前にendを退避しておきます。
syntax error, unexpected `end' (SyntaxError) if end ^~~
yyrecoverを呼び出した結果、無事にリカバリー用のトークンがみつかり、[true, then]というリカバリー用の2つのトークンが手に入りました。この2つのトークンをもとにshift/reduceをしていきます。
if true then
^~~ リカバリー用のトークンが見つかったときはここにいる
if true then
^~~ trueをshiftした
if true then
^~~ thenをshiftした
ここまでくると次にendがきても処理を進められるので、先ほど退避したendを復旧させます。
if true then end
^~~ endを復旧して処理を継続する
というわけで最低でも3つの追加・変更をparse.cに加える必要があります。
実装方法その1 (parse.cをさらに加工する)
一つ目の実装方法はsedや変換用のruby scpritを用意して、bisonコマンドが生成したparse.cをさらに加工する方法です。具体的にはこの前後に処理を追加します。
{$(srcdir)}.y.c:
$(ECHO) generating $@
$(Q)$(BASERUBY) $(tooldir)/id2token.rb $(SRC_FILE) > parse.tmp.y
$(Q)$(YACC) -d $(YFLAGS) -o y.tab.c parse.tmp.y
$(Q)$(RM) parse.tmp.y
$(Q)sed -f $(tooldir)/ytab.sed -e "/^#/s|parse\.tmp\.[iy]|$(SRC_FILE)|" -e "/^#/s!y\.tab\.c!$@!" y.tab.c > $@.new
# このあたりでさらにxx.rbを実行して $@.new に必要な関数を足したりする
$(Q)$(MV) $@.new $@
$(Q)sed -e "/^#line.*y\.tab\.h/d;/^#line.*parse.*\.y/d" y.tab.h > $(@:.c=.h)
$(Q)$(RM) y.tab.c y.tab.h
(1)のyyrecover関数はparse.cの関数定義と関数定義の間など、適切な場所を探して追加すればよさそうです。一方(3)の統合はyyparseという巨大な関数の中身を編集しないといけないので大変そうです。詳しくは後述しますが、複数のBisonのversionをサポートするという課題もあります。
実装方法その2 (テンプレートファイルを自分で管理する)
Bisonはparse.cを生成するのにm4で書かれたテンプレートファイルを使用します。Bisonではskeleton(s)と呼ばれておりdata/skeletons以下で管理されています。Rubyの場合はc-skel.m4とそこから呼ばれているyacc.cが関係します。
またbisonコマンドには-Sというオプションがあり、これを使うとテンプレートファイルを指定することができます。このときテンプレートファイルはBisonのディレクトリ以外のものを指定することができるので、Bisonからyacc.cをRubyのレポジトリにコピーしてきて管理をしていくという方法も考えられます。
とはいえこのテンプレートファイルはBisonの実装の詳細であり、Bisonのversionが変わればテンプレートファイルで利用可能なm4マクロの種類や名前が変わることもあり得ます。現在のRubyではBison 3.0以上を要求していますが、そうはいっても3.0から3.8までversionがあり、https://rubyci.org/を眺めていてもいろいろなversionのBisonが動いています。これら複数のversionを対象にメンテナンスをしていくのは簡単ではありません。同様の理由で一つ目の方法でも、たとえ同じparse.yを与えても使用するBisonのversionによって生成されるparse.cは変わります。結局方法1も方法2も異なるversionのBisonで動くようにするための労力を払っていく必要があります。ここでいう労力とは例えば複数versionで動作する1つのyacc.cを気をつけながら管理する、各versionごとにテンプレートファイルを用意してメンテナンスする、複数version用のCI環境を用意するなどといったことを指します。
| OS | Bison |
|---|---|
| Debian 10.13 | 3.3.2 |
| Ubuntu 18.04.6 | 3.0.4 |
| Ubuntu 20.04.4 | 3.5.1 |
| CentOS 7.9 | 3.0.4 |
| macOS Big Sur | 3.8.2 |
| SPARC Solaris 10 | 3.5.1 |
実装方法その3 (Bisonに機能を実装していく)
三つ目の方法はBison本体にError Recovery用のpatchを提供するという方法です。力強く説得力のある方法だと思います。とはいえこの方法もいくつか問題があります。
まずBisonがリッチなparser generatorであるという点です。BisonはC言語以外にC++/D/Javaのparserを生成することができます。またparserの種類も豊富で、LALR(1)以外にGLR, canonical LR, IELR(1)も生成可能です。詳しくは書きませんが他にもpush parserを作ることも可能です。日々Bisonのことを調べるたびにその偉大さに畏敬の念を覚えます。
RubyとしてはC実装のLALR(1)で通常のpull parserでError Recoveryができれば十分ですが、Bisonに実装をするとなると他のケースについても実装していく必要があるでしょう。
またもしBisonに実装されたとしても、各環境でほぼ最新のBisonをインストールしてもらう必要があります。可能であれば各環境でインストールされているBisonそのままでRubyがbuildできることが望ましいという要望があるので、最新のBisonを要求するというのは難しい意思決定になりそうです。
まとめ
いよいよError Recoveryを実装していくにあたって、Rubyのparserの実装およびBisonについて調べました。3つの実装方法について検討をしてきましたが、メンテナンスコストが高い(方法1 & 2)、実装コストが高い(方法3)、説得が難しい(方法3)といずれも簡単な方法ではありません。どうしたものでしょうか...
