C++でbison(パーサジェネレーター)を使う

コンパイラを作るにあたり構文解析(Parse)処理は要です。自分でゴリゴリと処理を書く方が最も柔軟ですが、それはそれでなかなか大変です。Palanでは、先人の知恵bisonを使って構文解析器を生成しています。

bisonとは

GNU版yaccです。C/C++/Javaの構文解析器を生成できます。入門としてはtoru0408さんの投稿が分かりやすいので分からない方はそちらをどうぞ。
→ 言語を作る！bisonとflexを使ってみた

C++で使いやすい構文解析器を生成する

bisonはC++をサポートしていますが、ネットではC言語での例がほとんどで、ググってもなかなかC++のよい例はあまり落ちてません。Palanではbisonを使ってC++コードの生成していますので、C++化のノウハウを紹介します。参考になるドキュメントは基本Bisonの正式マニュアルです。リアルなコードをみたい方はPalanのソースを覗いてください。

C++対応するには、まず定義ファイルを作ります。Cだと拡張子.yですが、C++の場合は.yyにします。拡張子によって生成ファイルの拡張子も変わりますが、気に入らなければコマンドライン-o オプションで出力ソースファイル名を指定できます(ヘッダ名は指定不可)。その中でbisonのスケルトンをC++用のスケルトンを指定します。任意のクラス名も指定できます。また、namespaceもデフォルトだとyyになってしまうので適切な名前を指定します。
※ namespaceを無名にしたかったのですができませんでした。

PlnParser.yy

%skeleton "lalr1.cc"
%require "3.0.4"
%defines
%define parser_class_name {PlnParser}
...
%define api.namespace {palan}

Cで書く場合は共用体でデータの受け渡しを行いますが、C++では宣言した型のインスタンスで受け渡しを行います。共用体も使えますが、C++のクラスを共用体で使うにはコンストラクタが使えないなど問題が多いです。型チェックもちゃんと働いて使いやすいので、共用体は使わないようにしましょう。下記のようにapi.value.typeにunionの代わりにvariantを指定して、tokenやtype毎に<>内に型を宣言すればよいです。

PlnParser.yy

%define api.value.type	variant

%token <int64_t>	INT	"integer"
%token <uint64_t>	UINT	"unsigned integer"
%token <string>	STR	"string"
...
%type <vector<PlnExpression*>>	arguments
%type <PlnExpression*>	argument

呼び出し方

bisonは字句を字句解析器(Lexer)から受け取る必要があります。受け取る関数についてはCと変わらずグローバル関数yylex()ですので、宣言が必要です。ここだけはC++っぽくないのですが、クラス化されたLexerを使用する仕組みは提供されています。その仕組みについてはまたの機会に。。

PlnParser.yy

%code
{
...
int yylex(palan::PlnParser::semantic_type* yylval);
}

yylex関数は戻り値としてtokenの種類と、tokenのインスタンスを返す必要があります。tokenの種類についてはbisonから出力されるPlnParserのヘッダに定義されています。インスタンスについては、引数に対してbuild<型名>()を使って値をセットできます。

lexer.cpp

#include "PlnParser.hpp"

int yylex(palan::PlnParser::semantic_type* yylval)
{
...
    // 整数の場合
    yylval->build<int64_t>() = std::stoll(yytext);
    return PlnParser::token::INT;
...
}

parse()メソッドでパース実行できます。

main.cpp

#include "PlnParser.hpp"

int main()
{
...
    PlnParser parser;
    int res = parser.parse();
...
}

vectorを使う際の注意

繰り返しの構文の部分ではSTLのvectorを使うことが多いと思いますが、アクションごとにインスタンスができるので、それごとに全コピーが発生するのは効率が良くありません。ここは、C++11のMoveセマンティクスを積極的に使いましょう!

PlnParser.yy

arguments: argument
    {
        $$.push_back($1);
    }
    | arguments ',' argument
    {
        $1.push_back($3);
        $$ = move($1);   // $$ = $1では全コピーが発生。
    }
    ;

つぶやき

C++のパーサーとしてはBoostのboost::spiritも検討しましたがコンパイルが遅すぎるのと、ミスった時のエラーメッセージがひどすぎて、本格的に使うのはやめた方がよさそうです。
bisonのノウハウまだちょっとあるけど、需要あるのだろうか。