sonota486

2023-01-22に更新

『RubyでつくるRuby』のMinRubyのパーサを書いた（手書きの再帰下降パーサ）

Ruby MinRuby parser

読了目安：15分

これは Ruby Advent Calendar 2022 の25日目の記事です。

書籍 『RubyでつくるRuby ゼロから学びなおすプログラミング言語入門』（以下、 『RubyでつくるRuby』 ）で扱われているミニ言語 MinRuby のパーサを書いてみました。

『RubyでつくるRuby』は、Ruby を使った基本的なプログラミングの入門から始まり、後半ではミニ言語 MinRuby（Ruby のサブセット）のインタプリタを作って最終的に MinRuby言語で MinRuby インタプリタを書くところまでやってしまう、という内容の入門書です。

……と自分なりに内容紹介してみましたが、以下もあわせて参考にしていただければと思います。

書籍『Ruby でつくる Ruby』が発売されます - まめめも
- 著者の遠藤さん
『RubyでつくるRuby』の読み方（私論） - golden-luckyの日記
- ラムダノートの鹿野さん

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門 – 技術書出版と販売のラムダノート

プログラミングを始めるなら、プログラミング言語を自分でつくってみるのがいちばん！最低限の機能なら、こんなに簡単にインタプリタを作れます。よくわからなかったプログラミングも、裏側の仕組みから分かってしまえば怖くない！　

2016年9月から2017年1月にかけてアスキーjpの「プログラミング＋」コーナーで連載された大好評のWebコンテンツ『Rubyで学ぶRuby』を、さらにわかりやすく紙版の書籍として編纂しなおして発売するものです。豊富なイラストもカラーで完全採録。

プログラミング初心者を想定して丁寧に解説してある
分量が多すぎず（144ページ）読み通しやすい
評価器にフォーカスしており、パーサはスコープ外
- パースは minruby gem にまかせる

たしか発売された頃に読んで「せっかくだからパーサも自作したい」と思った記憶があります。当時はパーサの作り方についての知識が足りずどうすればよいか分からなかったのですが、その後あれこれあって簡単なものなら作れるようになりました。

できたもの

https://github.com/sonota88/cookpad-hackarade-minruby/tree/recursive-descent-parser

  $ wc -l rcl_*.rb my_minruby_parser.rb 
   33 rcl_common.rb
   65 rcl_lexer.rb
  496 rcl_parser.rb
   17 my_minruby_parser.rb
  611 合計

一応動いてはいます。advent calendar には間に合った……リファクタリングなどは冬休み以降の宿題にします。

（2023-01-22 追記） interp.rb がパースできるようになりました。

動作例

  $ cat test3-4.rb
n = 1
while n < 100
  if n % 3 == 0
    if n % 5 == 0
      p("FizzBuzz")
    else
      p("Fizz")
    end
  else
    if n % 5 == 0
      p("Buzz")
    else
      p(n)
    end
  end
  n = n + 1
end

  $ ruby my_minruby_parser.rb test3-4.rb
[:stmts, [:var_assign, "n", [:lit, 1]],
 [:while,
  [:<, [:var_ref, "n"], [:lit, 100]],
  [:stmts,
   [:if,
    [:==, [:%, [:var_ref, "n"], [:lit, 3]], [:lit, 0]],
    [:if,
     [:==, [:%, [:var_ref, "n"], [:lit, 5]], [:lit, 0]],
     [:func_call, "p", [:lit, "FizzBuzz"]],
     [:func_call, "p", [:lit, "Fizz"]]],
    [:if,
     [:==, [:%, [:var_ref, "n"], [:lit, 5]], [:lit, 0]],
     [:func_call, "p", [:lit, "Buzz"]],
     [:func_call, "p", [:var_ref, "n"]]]],
   [:var_assign, "n", [:+, [:var_ref, "n"], [:lit, 1]]]]]]

cookpad-hackarade-minruby

まずは先行事例を軽く調べました。

Hackarade #04: Create Your Own Interpreter - クックパッド開発者ブログ

完全セルフホスト：MinRubyでパーサを書き、minruby gemに依存せずにinterp.rb単体でセルフホストするようにした

さすがのクックパッドさん。今回私はここまではやっていません。パーサを MinRuby で書くのもおもしろそう……。

同記事により、 mame/cookpad-hackarade-minruby というリポジトリでテストケースが用意されていることを知りました。ありがたく有効活用させていただきましょう。

mame/cookpad-hackarade-minruby: material for Cookpad's Hackarade #4

今回はこのテストケースを使い、自作パーサと minruby gem に同じ入力を与えて同じ結果になればヨシ！ということにしました。

方針

パーサ入門でよくある再帰下降パーサにしました。

専用のパーサライブラリを使うのに比べるとデメリットもあり本格的な言語実装ではあまり採用されない手法だと思いますが、入門者目線だと「全部自分で書いたぞ感」「全部把握できてる感覚」が得られるという、とても良い良さがあります。

（ちなみに、Rust製 Ruby 実装 ruruby のパーサは手書きだそうです。すごい……。）

ここで選択肢が2つあり、

(1) 何もないところから全部書く
(2) Ruccola のパーサを改造する

ちょっとだけ (1) を試した後、時間（というか計画性）がないこともあって (2) に切り替えました。
さて、Ruccola というのがスッと出てきましたね。これはなんでしょうか。

Ruccola とは

Ruccola は私が自分の勉強のために作っている素朴な自作プログラミング言語です。

https://github.com/sonota88/ruccola

最新の知見を盛り込んだキラリと光る言語……とかでは全然なく、現代の水準からするとかなり原始的なものです。自分の勉強用・入門用なので素朴でよいと割り切っています。

2021年にセルフホストできた（詳しくは↓の記事を参照）後も趣味の盆栽プログラミング的にちびちびと機能追加やリファクタリングを続けています。

素朴な自作言語Ruccolaのコンパイラをセルフホストした - Qiita

コンパイラを Ruby で書いている
Ruccola言語のコードの見た目は Ruby っぽい
なんとなくC言語っぽいものをイメージして作ったが、現時点では型がない（整数しかない）ので B言語や BCPL の方が近いのかも（詳しくないのでボンヤリした書き方）

ざっくり書くとこんな感じです。このうち「見た目は Ruby っぽい」というのがポイントで、Ruccola のパーサ（ 202-12-25 時点のソース）にいくつか手を加えれば MinRuby のパーサとして使えそうでした。

コード例です。以下は Ruccola言語で書いた cat コマンド。

def main()
  var EOF = -1;
  var c;

  while (true)
    c = getchar();
    if (c == EOF)
      break;
    end

    write(c, 1);
  end
end

だいたい Ruby ですね。中身は原始的なのに見た目は Ruby 風なので、書いているとちょっと不思議な気分になります。

作者の目にはだいたい Ruby と同じに見えますが、Ruby に慣れている方には次のような点が目に付くのではないでしょうか。

文末の ; （必須）
while の条件式を囲む ( ) （必須）
変数宣言の var（必須）

他にも関数呼び出しの ( )、関数定義の仮引数を囲む ( )、エントリポイントとなる main 関数も必須です。

自分が言語実装ビギナーなので、難しいことをしなくていいように Ruby の文法にいろいろ制限を加えてこうなっています。Ruby と完全にコンパチではありませんが、構文ハイライトやエディタのインデント支援は Ruby 向けのものがだいたいそのまま使えています。

ちなみに、Ruccola よりももっとコンパクトな mini-ruccola（元は vm2gol-v2 という名前だった）もあります。VM〜コンパイラを割と素朴に書いて1500行以下というもの。自分が欲しい（難しすぎず、簡単すぎず、読み書きに慣れている言語向けの）教材が見つけられず、じゃあ自分で作ってしまえとなって作ったもの。

https://github.com/sonota88/vm2gol-v2

以前週刊Railsウォッチで紹介していただきました。

週刊Railsウォッチ（20210209後編）Rubyでミニ言語処理系を作る、Kernel#getsの意外な機能、CSSのcontent-visibilityほか｜TechRacho by BPS株式会社

作った順番としては mini-ruccola の方が先で、最初にこっちで簡単なコンパイラ実装になんとか入門し、その後セルフホストに必要な機能を追加していく形で Ruccola を作っていきました。

主な変更点

演算子の優先順位

Ruccola では自分でも手に負えるようにいろいろと単純化しています。演算子の優先順位もそのひとつで、たとえば 1 + 2 * 3 という式は (1 + 2) * 3 として扱われます（単純に左結合とする）。

えっそれでいいの？と思いましたか？思いますよね。

言語処理系の解説を見ると必ずといっていいほど演算子の優先順位の話題が出てきて、自作言語を作るには避けて通れないトピックであるかのように思われます。私もある時までそう思い込んでいたのですが、実はそんなことはありません……と思うんですよね（微妙な自信のなさ）。

Ruccola では 1 + (2 * 3) と解釈させたい場合は明示的に括弧で優先順位を指定して 1 + (2 * 3) と書けばよい、ということにしています。たまに自分でも忘れていて素でびっくりします。まあ自分の勉強用の言語だからいいんですよこれで。最初から実装しなくてもよいので後回しにしています。Ruccola言語の記述力がまだ低いため、今入れてもコード量が膨れるデメリット（セルフホストしているのでばかにならず、下手に機能追加すると自分が困る）の方が大きそうで嫌かなという考えもあり。

ちなみに、似たような方針を採っている言語として VTL (Very Tiny Language) という言語があると後から知りました。仲間がいた……。

VTLでは，演算子の間に優先順位は存在せず，左から順番に演算が行われます．演算の順序を変えたい場合は括弧"()"をつけます．例えば，"2+3*4"の結果は"20"となり，"2+(3*4)"の結果は"14"となります．

あ、ていうか優先順位を明示する言語といえば Lisp があるじゃないか、とこの記事を書いていて今思い至りました。Lisp、心強いですね。

さて、Ruccola ではそれでいいとして、演算子の優先順位に対応しないと cookpad-hackarade-minruby のテストが通りません。なんとかしなければ。

これについては自分にとって今回初めてという訳ではなく、以前単体で履修していたのでした。

四則演算と剰余のみのexprコマンドをRubyで作ってみた

これを組み込めばいけるはず。

test1-4.rb と test1-5.rb の間の飛躍が大きかったので小さなテストを追加しながら進めました。

まずは一番優先順位の低い 1 == 2 から
二番目に優先順位の低い < を右側に加えた 1 == 2 < 3
...
1 == 2 < 3 + 4 * 5 が (1 == (2 < (3 + (4 * 5)))) と解釈できればOK
ここまでできたら test1-5.rb が通る

という流れで進めることで意外とすんなり書き換え完了しました。

参考: 演算子式 (Ruby 3.1 リファレンスマニュアル)

優先順位まわりについては書籍『Rubyで作る奇妙なプログラミング言語』もおすすめです。私はこの本の写経で入門しました。

if と case

Ruccola では if 文は case 文のシンタックスシュガーという扱いになっています。「case文が動けば if文はそのサブセット扱いにできるよね」という、大は小を兼ねる的な素朴な発想によるものです。あと Ruccola の前身の mini-ruccola は最初はパーサがなくて構文木を手書きするところからスタートしたため、その都合もあります。

MinRuby では逆になっていて、 case 式は内部的に入れ子の if 式としてパースされます（『RubyでつくるRuby』 p85）。ここは今回『RubyでつくるRuby』を読み返してなるほどと思ったところでした。

改行の扱い

Ruccola では現時点では if文の条件式全体を囲む括弧は省略不可です（case文、while文も同様）。また、代入や関数呼び出しなどの文の末尾にはセミコロンが必須です。改行はスペースと同じように字句解析の段階で捨てています。

if (i == 10)
  p(1);
end

一方 MinRuby では条件式を囲む括弧や関数呼び出しなどの末尾のセミコロンは省略可能です。改行の考慮が必要そう。

if i == 10
  p(1)
end

改行を考慮したパースはこれまで経験がなく不確実な部分でしたが、結論からいえば特別な対応は不要で、適当に改行を読み飛ばすだけで cookpad-hackarade-minruby のテストは通りました（というか試しにやってみたら字句解析の段階で全部捨てても大丈夫だった）。

今の実装では、式とみなせるまとまりの次に二項演算子が来たら「まだ式の続きがあるな」と判断し、そうでなければ「いったんそこで式が終わっているな」と判断する、という動作になっています。
たとえば上のコード例だと i == 10 の次に p というトークンが来ています。これは二項演算子ではありませんから、ここで式の区切りと判断され、i == 10 と p 以降は別のまとまりだということになります。

i == 10 + ...
        ^ 二項演算子なのでまだ式が続いていると判断

i == 10 p ...
        ^ 二項演算子ではないので p からは別のまとまり

あくまで cookpad-hackarade-minruby のテストのカバー範囲と今回作ったパーサの実装の組み合わせでは問題なかったというだけで、Ruby に近づけていこうとするとどこかでちゃんとした対応が必要になってくるでしょうね。

配列・ハッシュ

Ruccola では配列リテラルや配列の要素にアクセスするための専用の構文は（まだ）ありません。ハッシュはサポート予定なし。

なので配列・ハッシュまわりは新たに書きました。ここはすんなり書けてしまって特に書くことがありません。

TODO

if, case まわりがいいかげんなのでもうちょいちゃんとやる
interp.rb をパースできるようにする（ここまではやりたい）

（2023-01-22 追記）上記2つ完了しました。「これで完璧！」というものではありませんが、とりあえず interp.rb はパースできています。

おわりに

以上のように自作言語 Ruccola のパーサにいくつかの変更を加えることで MinRuby のパーサを作ることができました（ただし cookpad-hackarade-minruby のテストを通すところまで）。

以前から MinRuby のパーサ作れないかなーとボンヤリ考えていたのでこの機会に実現できてよかったです。

以下、おまけ的な雑多な話題・メモなどです。

おまけ

再帰下降パーサについて

再帰下降パーサについては書籍やウェブに解説がたくさんありますので「再帰下降パーサ」「再帰下降構文解析」などで調べてください。英語だと recursive descent parser です。

今回作ったものはパーサだけで 500行くらいありますし、再帰下降パーサの一番最初の入門用としてはちょっと大きいかもしれません。そういう場合は分解してちょっとずつ手を付けるのがおすすめです。

くりかえしの構造
- 関数定義の仮引数、関数呼び出し時の引数、演算子を含む式、配列リテラル、ハッシュリテラルなど、いろんなところで登場する
- 数 のあとに , 数 をくりかえし
- 例: 1, 2, 3
- 数 のあとに 演算子数 のくりかえし
- 例: 1 + 2 + 3
[[]], [[[]]] のような入れ子の構造
演算子の優先順位

上の方でも書いたように、演算子の優先順位は後回しにできますから、先にそれ以外の部分を作ってから後付けで追加するのもよいと思います。

「MinRuby のパーサを書いてみたいけどいきなり全部書くのは無理そう……また今度にしよう」と思った方は、まず次のような簡単なものから手を付けてみるのはどうでしょう。どちらも50行くらいです。

入れ子の配列だけをパースできるパーサを作る（手書きの再帰下降パーサ）
- ((), (())) のような入れ子の括弧だけをパースできるパーサ。コード例があった方がよさそうと思って簡単なものを昨日急いで書きました。
- n年前の自分に「これで入門しろ」「最初はこれでいいと思うよ」といって送りつけるとしたらこれ
正規表現エンジン（ロブ・パイクのバックトラック実装）をRubyで写経した
- バックトラック方式の正規表現エンジンもおすすめです。こっちも手軽。手軽だけどおもしろい。再帰下降パーサに考え方が似ています。

MinRuby 関連

今回調べていて見つけたもの。

https://speakerdeck.com/m_seki/extend-your-own-programming-language-rubykaigi-2018

MinRuby に末尾呼び出し最適化を実装する話や Rinda + MinRuby の話。

https://matsubara0507.github.io/posts/2019-05-16-minruby-with-patternmatch.html

パーサは「木を組み立てる」処理がメインなのでパターンマッチの出番はそんなにありませんが、評価器は「木を使う」処理がメインなのでパターンマッチを使うといい感じに書けますね。

mal (Make a Lisp)

https://github.com/kanaka/mal

Lisp に興味のある方には mal（Make a Lisp）もおすすめです。ちょうど『RubyでつくるRuby』の Lisp 版といった感じで、簡単な Lisp インタプリタを作ってセルフホストするまでが11ステップに分かれており、テストを通しながら作っていきます。入門者向けのシンプルな実装ですが、マクロや例外機構、末尾呼び出しの最適化まで含まれています。すでに Ruby 版の実装（主な部分は500行程度）もリポジトリに含まれていますから、そのまま写経してもいいですし、自力で書いて詰まったときに参考にすることもできます。

ちなみに私は一度 Ruby で写経した後 LibreOffice Basic で書くということをやりました。

LibreOffice BasicでLispインタプリタ（mal）を書いた - Qiita