博士

ロボ子、今日はC言語用の軽量Yacc実装「miniyacc」について話すのじゃ。

ロボ子

Yaccですか。確かコンパイラを作る時に使うツールでしたよね。それが軽量版になったと。

博士

そうじゃ！このminiyaccは、たった一つのCファイルでできているのがすごいところじゃ。「学習用、別言語のYaccのブートストラップ、プログラムへの統合に利用可能」とあるぞ。

ロボ子

単一ファイルで実装されているのは、組み込み用途にも良さそうですね。入手方法はどうなっているんですか？

博士

ソースコードは[yacc.c](https://c9x.me/yacc/data/yacc.c)からダウンロードできるぞ。コンパイルは `cc yacc.c -o yacc` で簡単じゃ。

ロボ子

ライセンスはMIT/Xライセンスなんですね。これはかなり自由度が高いライセンスですね。

博士

その通り！特徴としては、「短く、C89で実装」「ほぼPOSIX準拠」などがあるぞ。昔ながらの環境でも動きそうじゃな。

ロボ子

C89準拠ですか。ずいぶんと古い規格ですね。でも、それだけ移植性が高いということですね。

博士

しかも、「生成されるテーブルはGNU Bisonと同程度に効率的」らしいぞ。高速な実装で「500以上の文法規則で1秒未満」とあるから、実用性も十分じゃな。

ロボ子

それはすごいですね！テーブル圧縮のアルゴリズムも工夫されているみたいですね。

博士

そうじゃ。「行変位テーブルを使用して、スパーステーブルを効率的に格納」しているらしい。Robert Tarjanの論文に記載されているアルゴリズムを使っているとのことじゃ。

ロボ子

へえ、そんな昔のアルゴリズムが今でも使われているんですね。基本に忠実な実装ということでしょうか。

博士

エラーリカバリとmid-actionルールは未サポートらしいが、「空の生成規則を持つ非終端記号を追加することでエミュレート可能」とのことじゃ。工夫次第でなんとかなりそうじゃな。

ロボ子

なるほど、ちょっとしたテクニックでカバーできるんですね。勉強になります。

博士

このminiyacc、小さいながらも、コンパイラの基礎を学ぶにはもってこいじゃな。ロボ子もこれでコンパイラを作ってみるのじゃ！

ロボ子

はい、博士！頑張ります！

博士

もしコンパイラが完成したら、ロボ子専用のプログラミング言語を作ってあげるのじゃ！

ロボ子

本当ですか！嬉しいです！どんな言語にしましょうか？

博士

うむ、それはもちろん、ロボ子が理解しやすいように、全部0と1だけで書ける言語じゃ！

ロボ子

…博士、それって、機械語そのものでは…？