Kinx 実現技術 - Yacc/Bison

コンパイラ・コンパイラの話

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。作ったものの紹介だけではなく実現のために使った技術を紹介していくのも誰の役に立つかもしれないしね。その道の人には当たり前でも、そうでない人にも興味をもって貰えるかもしれないので。ソースを具体的にさらすのは（アドホックにやってる部分もあるので）多少恥ずかしいが、どうせ OSS にしてるし、まぁいいか。

最初のテーマは構文解析。なお、以下のような感じで記事をプランしてみる。

• コンパイル時編
  • 構文解析 ... Bison を使っている。kmyacc に変えるかもしれない。（本記事）
  • Switch-Case ... 色々条件を判断。結構複雑。
• 実行時編
  • VM（Virtual Machine） ... gcc ではダイレクト・スレッディング。
  • Garbage Collection ... ザ・マーク・アンド・スイープ。静的スコープの扱い。
  • JIT ... ネイティブの機械語コードにコンパイルするために採用した方法。
  • Fiber ... 思い付きで実装したら割と動いたのでその方法。

Kinx での構文解析

Yacc/Bison とは

Kinx での構文解析は今現在 GNU Bison を使っている。いわゆる LALR(1) の Yacc 系統のパーサ・ジェネレータ。コンパイラを作る時のジェネレータであるため、俗に コンパイラ・コンパイラ と呼ばれている。GNU Bison 自体は GPLv2 だが、その出力（パーサ自体）は例外条項によって自分でライセンスを付けることができる。

元々コンパイラを書く場合、手書きの再帰下降構文解析で実装するのが好きだったのだが、あとから文法を理解しやすい、変えやすいという点で Yacc にしよう、と思ったので使った。最初は miniyacc という簡易 Yacc を使っていたのだが、エラーリカバリ処理がない という致命的な弱点のため現在は GNU Bison を使うように修正。ただ、Windows で Bison を使うのは面倒なのでここだけ Linux で修正する、という作業が非常に面倒くさいことになっている。それもあって、kmyacc に乗り換えようかなー、というのが現時点のステータス。

ちなみに、再帰下降構文解析（再帰下降パーサ）とは、BNF で書いた時の構文ルールを関数呼び出しの形で表したもの。結構書いてて面白い。例えば、expr → ... → factor という流れで、factor には '(' expr ')' が定義されているとき、factor 関数の中で '(' を認識したら再帰的に expr 関数を呼ぶことで構文解析していく。トップダウン的に下方向に向かって解析し、途中再帰的に上に戻ってくるので再帰下降と呼ばれている。詳しくは Wikipedia も参照してみるといいかも。

構文解析・字句解析

構文定義ファイルは src/kinx.y にあり、構文自体は BNF という記法で書く。尚、Yacc(Bison) の動きに関しては、Rubyソースコード完全解説 にある 第9章 速習yacc がわかりやすくて良いと思ったので紹介しておきます。

今回作ったパーサに関して、特徴的なところをピックアップしてみよう。

字句解析部分

コンパイラを作る場合、実は構文解析の前に 字句解析 というフェーズが入る。だいたい以下のような流れで進む。

字句解析
   ↓
構文解析
   ↓
意味解析

字句解析は yacc と対になって lex というツール（Bison の場合 flex）を使うのも標準的なのだが、私は lex は使わない。字句解析は手書きしている。src/lexer.c がソース。いろいろなステータスを細かく制御するのに都合がいいし、手書きでもそれほど面倒な処理ではないので、今回も手書きした。このほうが都合が良いのは、例えば、using のような構文は、字句解析レベルで実施しており、入力ソースを動的に入れ替えるようになっている。

一般的に構文解析では、主に 見た目 だけ扱う。見た目さえ正しければよい。内容が妥当かどうかは次の意味解析のフェーズで行う。

正規表現リテラル

あと、Factor のところに正規表現リテラルが来るのだが、字句解析レベルで /= を DIVEQ と認識してしまっているので、DIVEQ が来た時に /= で始まった正規表現リテラルと判断するようにしている。状態遷移的に DIVEQ として扱われる場所と異なるのでこれはコンフリクトしない。正規表現の最初の文字が = であることをきちんと認識すればよいという感じで扱った。

kmyacc について

kmyacc は森公一郎氏（故人）が作った素晴らしいパーサ・ジェネレータ。非常に昔からお世話になっているツールの一つ。Yacc を使おうというときはたいがいこれを使っていた。なぜ今回使っていなかったのか、それはビルド環境に yacc 含めたかったのでライセンスの緩い miniyacc にしたから（MIT License）。現時点では Bison に変えてしまったので kmyacc で全然かまわない。正直、森氏は後世に名を遺すべき人であって、kmyacc も遺しておくべき作品だと思う。彼が亡くなったとき（2015年）は、それはもう日本のプログラミング業界でひと騒動あったのも記憶に新しい。

森氏は LSI-C の作者でもあり、試食版というフリーの LSI-C にも（かなり）昔お世話になった。出力アセンブラが美しいことで有名だ。実際、当時は C では遅いのでサブルーチンはアセンブラで書く ということをやっており、これは今でいう Java は遅いのでライブラリは JNI で書く と同じことだと思えばよい。時代が変わってもやってることは変わんないな。扱うレイヤが変わっただけだ。

その時、当時使っていた Turbo C のアセンブラ出力と LSI-C のアセンブラ出力を見比べて 確かになんて美しいんだ、と感動した記憶もある。どう違うかというと、LSI-C は極限までレジスタを割り当てるので、ほとんどスタックを汚さない。Turbo C は関数呼び出しの引数は基本スタック渡しで汚いなー、と。アセンブラでサブルーチンを作る際に LSI-C の出力コードは大いに参考になった。

話は尽きないので、昔話はここでおしまいにしよう。

つまりは、森氏の名前と kmyacc という作品を後世に遺すべく、今後 Bison から kmyacc に鞍替えする計画を立てるかもしれない、ということだ。

おわりに

あまり構文解析処理自体には触れていないが、ソースコードを見てみると何となく理解できるかもしれない。もちろん、バグがあれば教えて下さい。お願いします。

最後はいつもの以下の定型フォーマットで締め括り。

• 最初の動機は スクリプト言語 KINX（ご紹介） を参照してください（もし宜しければ「いいね LGTM」ボタンをポチっと）。
• リポジトリは ここ（https://github.com/Kray-G/kinx） です。こちらももし宜しければ★をポチっと。