FlexとBisonで実用的なパーサーを作る
パーサージェネレーターと言えば Flex と Bison が有名です。しかし Flex と (特に)Bison のドキュメントは長くて複雑なため、ちょっと複雑なことをすると急に難易度が上がります。この記事ではこれらのツールを使って実用的なパーサーを作る手順を紹介します。基礎はあまり説明しないので、ドキュメントの最初あたりは読んでおくと良いです。
ドキュメント自体も少し探しにくいので以下にリンクを載せておきます。
インストールには色々な方法があるのですが、私は Nix でインストールしました。Nix は全てのパッケージマネージャの上位互換なので(?)おすすめです。一度触ってみてください。
この記事で実装するパーサーは以下の機能を持ちます。
- reentrant
- トークンの位置の認識
- 構文木の構築
エラー回復は実装していません。やる気があったらやります。。。
私は以前 Haskell で node-semver のパーサーを作ったことがあるので今回もこのパーサーを作りますが、詳細な node-semver の文法の解説はしません。^1.2.3
とか、~2.3
とか>=1.2.3-alpha.1+x86
とかの文字列をパースできたら成功と思ってもらってよいです。
node-semver を Flex と Bison で実装したリポジトリはこちらです。
レキサー の実装
Flex のオプション
まずは レキサー を作っていきます。Flex の文法定義ファイルには.l
の拡張子をつけることが一般的です。モダンなmake
では.l
を認識してよしなにやってくれるらしいです。
いきなりですが Flex の option では以下を指定します。
%option reentrant header-file="lex.yy.h" noyywrap
%option bison-bridge bison-locations
-
reentrant
: レキサー をスレッドセーフにする。これがないとグローバル変数を多用して治安が悪くなる。 -
header-file="lex.yy.h"
: ヘッダファイルを生成する。 -
noyywrap
: 入力が EOF になったときに復帰処理をしない。(単純化のため) -
bison-bridge
,bison-locations
: bison と連携できる レキサー を生成する。
このオプションを指定すると Flex は以下のシグネチャを持つ レキサー を生成します。
int yylex ( YYSTYPE * lvalp, YYLTYPE * llocp, yyscan_t scanner );
yylex は呼び出されるとトークンを 1 つ認識するまで読み進め、トークンの種類を表すint
を返します。数字や識別子などの意味値を持つトークンは、引数のYYSTYPE * lvalp
を yylex の中で書き換えることで意味を記録します。YYLTYPE * llocp
はトークンの位置情報を受け渡します。yyscan_t scanner
は レキサー と パーサー の状態を保存しておく変数で、reentrant
オプションによって生成されます。これらの引数をつかって Flex と Bison で情報をやり取りします。
また、%option header-file="lex.yy.h"
を指定するとヘッダファイルも生成してくれるため、他のプログラムから Flex の生成物を利用することができます。
文法の定義
基本的な Flex の文法は正規表現 {アクション}
という構造をしています。例えば以下は正しい Flex の文法定義です。
"." {return TK_DOT;}
"+" {return TK_PLUS;}
[1-9][0-9]*|0 {return TK_NUM;}
[:alnum:]+ {return TK_ID;}
ここでTK_DOT
やTK_PLUS
などはどこか適切な場所で定義した enum とします。Flex 自体にこの enum を生成する仕組みは備わっていません。あとで見ますが、実はこのトークン種別を表す enum は Bison 側で定義します。
入力が正規表現に一致するとアクションが実行されます。この例ではトークン種別の enum を return していますが、アクションを複数行書くことも、return 以外のことをすることも可能です。
なお、正規表現の間に空白を入れることはできません。空白を挟むと以降すべての文字列がアクションとして解釈されます。実のところ C のコードを囲う{}
はなくても良いのですが、わかりやすさのために書くことにします。
Flex はデフォルトでは文法にマッチしない入力をおこなってもエラーになることはなく、マッチしない文字列を標準出力に吐き出して入力の読み込みを続けます。一方でアクションがないルールは単純に読み捨てられます。
意味値の記録
実は上記の文法には欠陥があります。それは、[1-9][0-9]*|0 {return TK_NUM;}
というルールは数字にマッチするにもかかわらず、その値の情報を捨ててしまっていることです。このままではTK_NUM
という種別はわかりますが、肝心の値がわかりません。
この値を記録するのが先述したYYSTYPE * lvalp
引数です。ここでYYSTYPE
はどこか適切な場所で定義された以下の型とします。
union {
int digit;
char *id;
} YYSTYPE;
typedef union YYSTYPE YYSTYPE;
この引数を用いて上記の文法を書き換えます。
"." {return TK_DOT;}
"+" {return TK_PLUS;}
[1-9][0-9]*|0 {
yylval->digit = atoi(yytext);
return TK_NUM;}
[:alnum:]+ {
yylval->id = strndup(yytext, yyleng);
return TK_ID;}
yytext
とyyleng
はそれぞれマッチした文字列とその長さを表す変数で、実体はscanner->yytext_r
のようなマクロで定義されています。
このようにすることでトークンの意味値を保存することができます。
Start Condition
同じ文字列でも文脈によって別の意味を持つことがあります。C 言語で代表的な例は*
です。
int *a;
int a = 1 * 2;
上記のプログラムでは*
がポインタ宣言と乗算演算子の 2 つの意味を持ちます。つまり*
は、型宣言中はポインタとして、式中では乗算の演算子として解釈されます。
こうした文脈依存のトークン(のある程度)は Start Condition を用いて扱うことができます。Start Condition はルールの on/off を切り替えられる機能で、以下のように宣言します。
%s ID EXPR
%%
<TYPE>"*" {return TK_PTR;}
<EXPR>"*" {return TK_MUL;}
この<TYPE>
と<EXPR>
が Start Condition です。Start Condition が<TYPE>
のときは*
をポインタ宣言トークンとして認識し、<EXPR>
の時は乗算記号として認識します。Flex で提供されるBEGIN
マクロを使って、BEGIN(TYPE);
などのようにアクション内で Start Condition を変更することができます。
詳細はドキュメントをごらんください。
位置の追跡
レキサー にトークンの位置も記録させるようにします。
yylex の引数にYYLTYPE * llocp
があったことを思い出してください。レキサー の中でこの引数を書き換えることでトークンの位置を記録することができます。YYLTYPE
は通常 Bison が生成する以下の型です。
struct YYLTYPE {
int first_line;
int first_column;
int last_line;
int last_column;
};
トークンの位置情報を記録するヘルパーとして以下の関数を定義します。
void yy_update_location(struct YYLTYPE *yylloc, size_t leng) {
yylloc->first_column = yylloc->last_column;
yylloc->last_column = yylloc->last_column + leng;
}
semver では改行はないので行番号の更新は省略していますが、必要な場合は実装するとよいです。
これを使ってアクションを書き換えます。
"." {
yy_update_location(yylloc, yyleng);
return TK_DOT;}
以上のように実装した レキサー を動かしてみます。コードの詳細はリポジトリをご覧ください。
yyscan_t scanner;
yylex_init(&scanner);
int token;
YYSTYPE yylval;
YYLTYPE yylloc;
do {
token = yylex(&yylval, &yylloc, scanner);
print_token(token, &yylval, &yylloc);
} while (token != YYEOF);
1.2.3-alpha.1+linux
'1 (digit)' from line 0, column 0 to line 0, column 1
'.' from line 0, column 1 to line 0, column 2
'2 (digit)' from line 0, column 2 to line 0, column 3
'.' from line 0, column 3 to line 0, column 4
'3 (digit)' from line 0, column 4 to line 0, column 5
'-' from line 0, column 5 to line 0, column 6
'alpha.1 (identifier)' from line 0, column 6 to line 0, column 13
'+' from line 0, column 13 to line 0, column 14
'linux (identifier)' from line 0, column 14 to line 0, column 19
レキサー がトークンの種類、意味値、位置を認識できていることがわかります。
パーサー の実装
Bison の パーサー 定義は.y
拡張子のファイルに記述する慣習があります。
パーサー の reentrant 対応
Bison でパーサーを reentrant にするためには%define api.pure full
を宣言してください。これを宣言すると Bison がyylex
を
int yylex ( YYSTYPE * lvalp, YYLTYPE * llocp );
の型で呼び出すようになります。前章で定義した レキサー には第 3 引数のyyscan_t scanner
がありました。これはパーサーとレキサーの両方の引数として必要なため、%param {yyscan_t scanner}
ディレクティブも追加してください。param
ディレクティブは宣言するとパーサーとレキサーのパラメータを増やします。
以上で Bison は以下のシグネチャを持つyyparse
関数を生成します。
int yyparse(yyscan_t scanner);
返り値はパースが成功したかどうかを表すint
です。
トークンの定義
Bison の文法定義に利用するトークンは%token
ディレクティブを使って以下のように宣言します。
%token TK_HYPHEN
%token TK_DOT "."
%token TK_HYPHEN
の定義はシンプルです。Bison の出力するトークン種別の enum に TK_HYPHEN という宣言を追加し、以降の文法定義でもTK_HYPHEN
という名前でこのトークンを参照できるようにします。
%token TK_DOT "."
はほぼ TK_DOT の宣言と同じですが、TK_DOT
を"."
という名前でも参照できるようになります。
次に意味値を持つトークンを定義します。意味値を持つトークンを定義するにはいくつかの方法がありますが、ここでは私が最も応用が利くと思う手法を解説します。
前節でトークンの意味値の型としてunion YYSTYPE
を定義したことを思い出してください。以下のディレクティブを使うことで、YYSTYPE
の実体を Bison に教えることができます。
%define api.value.type {union YYSTYPE}
ここで union の名前は YYSTYPE でなくても良いです。そもそも union ではなく struct でもよいはずですが検証はしていません。この定義を行うことで、Bison の出力したコードの中で
typedef union YYSTYPE YYSTYPE;
という風に typedef をしてくれます。
意味値を持つトークンは以下のように定義します。
%token <digit> TK_DIG "digit"
新たに出てきたのは<digit>
の部分です。この<digits
は union のタグ名を表しています。このようにすることで、Bison は文法定義のTK_DIG
および"digit"
を、int
として扱うことが可能になります。
YYSTYPE
が struct の場合も全く同じようにできるはずです(検証はしていません)。
Flex からの利用
Bison で生成したトークンの定義を Flex からも利用できるようにする必要があります。Bison はコマンドラインから呼び出すときに-H
オプションを指定するとヘッダファイルを生成します。この中にトークン等が定義されています。これを Flex で include してください。
生成規則の定義
これまででトークンの定義を行いました。この節ではいよいよ文法を定義していきます。形式言語の文法は複数のルールで成り立ち、それぞれのルールを生成規則と言います。
例として、1.2.3
や1.2
などの、桁を 1 つまで欠いたバージョンの文字列をパースすることを考えます。この生成規則をpartial
と名付けることにすると以下のように定義できます。複数の生成規則は|
で区切って並べて書きます。最後にセミコロンがあることに注意してください。
partial
: "digit" "." "digit" "." "digit" { $$ = partial3($1, $3, $5); }
| "digit" "." "digit" { $$ = partial2($1, $3); }
;
"digit"
, "."
は前節で定義したトークンです。それぞれTK_NUM
, TK_DOT
と書いても同じ文法になります。
なお、トークンはそれ以上展開されない文法の行き止まりであるため終端記号と言います。これと対比して、partial
のような生成規則を持つものは非終端記号と言います。終端記号と非終端記号をまとめて**記号(Symbol)**と言います。今後"記号"というときはこの意味なので注意してください。
Action の実装
トークン列の後ろの{}
で囲われた部分は Action 節です。生成規則がマッチしたとき、その Action 節が実行されます。典型的には Action 内で構文木(のパーツ)を作り、それを組み上げていくという実装になります。
Bison の扱う終端記号と非終端記号は意味値を持ちます。例えば"digit"
はint
の意味値を持ちますし、partial
も"その生成規則が表す構文木のパーツ"の値を持ちます。生成規則を構成する記号の意味値を参照するには$n
という記法を用います。n
には記号の出現する順番の数字が入ります。上記の例で言えば、
"digit" "." "digit" "." "digit" { $$ = partial3($1, $3, $5); }
の$1
, $3
, $5
はそれぞれdigit
の意味値を表しています。
生成規則で非終端記号の意味値を記録するには、$$ = ...
のように Action 中で直接代入します。partial
の構文木の型Partial
は例えば以下のように定義できます。
typedef enum { Partial2, Partial3 } PartialTag;
typedef struct {
int nr1;
int nr2;
} Partial2Val;
typedef struct {
int nr1;
int nr2;
int nr3;
} Partial3Val;
typedef union {
Partial2Val partial2;
Partial3Val partial3;
} PartialVal;
typedef struct {
PartialTag tag;
PartialVal val;
} Partial;
Action 中でつかったpartial3
, partial2
は以下の型をもつ、構文木のパーツを組み立てる関数です。実装はリポジトリを見てください。
Partial *partial2(int nr1, int nr2);
Partial *partial3(int nr1, int nr2, int nr3);
ところで、Bison では意味値をYYSTYPE
型の変数で保存することを思い出してください。partial
も"digit"
も他の記号の意味値もすべてこの変数で管理されます。
そこでYYSTYPE
に Partial 型を追加します。Flex の章で定義したYYSTYPE
を以下のように変更します。
union YYSTYPE {
int digit;
char *id;
+ Partial *partial;
};
次にpartial
の意味値の型が、"YYSTYPE
の partial タグの型"であることを以下のように Bison に伝えます。
%nterm <partial> partial
%nterm
は非終端記号の意味値を Bison に指示します。1 つ目の<partial>
はYYSTYPE
のタグ名を表し、2 つ目のpartial
は Bison で定義した非終端記号を表します。%token
の場合と同じで、<>
の中に意味値の型を直接書くのではなくYYSTYPE
のタグ名を書くことに特に注意してください。
この辺りは結構複雑なのですが、実際にパーサーを書くときには
-
Partial
型を定義する -
union YYSTYPE
に Partial 型のメンバを追加する -
%nterm
を宣言する - 生成規則を書く
という流れになるかと思います。
構文木の返却
以上で構文木を構築して記録することができました。この構文木を他のプログラム中で利用するには少し工夫が必要になります。Flex は以下のアクセス関数yyget_lval
を生成します。
YYSTYPE *yyget_lval(yyscan_t yyscanner);
この関数を使えばパースが成功した場合に
int parse_result = yyparse(scanner);
YYSTYPE* yylval = yyget_lval(scanner);
Partial *partial = yylval->partial;
とすれば構文木を取得できそうですが、Bison が yyparse の中でyylval
に何らかの操作をしているため、実際にはこの方法は使えないようです。
代わりに、パースが成功したときには構文木をどこか別の変数に保存することにします。グローバル変数を使えばできるのですが、それではパーサーが reentrant ではなくなるのでyyscan_t yyscanner
の中に完成した構文木を保存する領域を作ることにします。
yyscan_t
は Flex が生成するものであるため、Flex の定義に戻ります。Flex にはyyscan_t
に新しいメンバを追加するextra-type
オプションがあります。以下のオプションを Flex に追加してください。
%option extra-type="RangeSet *"
これを追加すると、Flex は以下の getter/setter 関数を生成します。
#define YY_EXTRA_TYPE RangeSet *
YY_EXTRA_TYPE yyget_extra(yyscan_t yyscanner);
void yyset_extra(YY_EXTRA_TYPE user_defined, yyscan_t yyscanner);
これを用いて、文法の一番上位の Action の中で
yyset_extra($$, scanner);
を行います。構文木を利用するプログラムでは
yyscan_t scanner;
yylex_init_extra(NULL, &scanner);
int parse_result = yyparse(scanner);
Partial* ast = yyget_extra(scanner);
print_partial(ast);
yylex_destroy(scanner);
とすれば良いです。
位置情報の追跡
前章ではレキサーが位置情報を追跡できるよう実装しました。この章ではパーサーが構文木に位置情報も記録するようにします。
まず、位置情報を保存する型を Bison に伝えます。以下のオプションを指定してください。
%define api.location.type {struct YYLTYPE}
struct YYLTYPE
は Flex の章で定義した型です。これを指定しないと Bison デフォルトの型が使われるんだったと思います。
次に構文木にYYLTYPE
も保存するようにします。
typedef enum { Partial2, Partial3 } PartialTag;
typedef struct {
int nr1;
+ struct YYLTYPE nr1_loc;
int nr2;
+ struct YYLTYPE nr2_loc;
} Partial2Val;
typedef struct {
int nr1;
+ struct YYLTYPE nr1_loc;
int nr2;
+ struct YYLTYPE nr2_loc;
int nr3;
+ struct YYLTYPE nr3_loc;
} Partial3Val;
typedef union {
Partial2Val partial2;
Partial3Val partial3;
} PartialVal;
typedef struct {
PartialTag tag;
PartialVal val;
} Partial;
この構文木を組み立てる関数を以下のシグネチャで実装します。詳細はリポジトリをご覧ください。
- Partial *partial2(int nr1, int nr2);
+ Partial *partial2(int nr1, struct YYLTYPE loc1, int nr2, struct YYLTYPE loc2);
- Partial *partial3(int nr1, int nr2, int nr3);
+ Partial *partial3(int nr1, struct YYLTYPE loc1, int nr2, struct YYLTYPE loc2, int nr3, struct YYLTYPE loc3);
これを用いて Action を書き直します。
partial
- : "digit" "." "digit" "." "digit" { $$ = partial3($1, $3, $5); }
+ : "digit" "." "digit" "." "digit" { $$ = partial3($1, @1, $3, @3, $5, @5); }
- | "digit" "." "digit" { $$ = partial2($1, $3); }
+ | "digit" "." "digit" { $$ = partial2($1, @1, $3, @3); }
;
新しく出てきた@n
は記号の位置情報を表します。実態は n に対応する記号のYYLTYPE
です。
まとめ
以上でパーサーの実装が完成しました。実際に構文の解析と表示を行ってみます。本記事で解説していない型や関数は想像で補ってください。
int main(){
yyscan_t scanner;
yylex_init_extra(NULL, &scanner);
int parse_result = yyparse(scanner);
RangeSet* ast = yyget_extra(scanner);
print_range_set(ast, 0);
yylex_destroy(scanner);
if (parse_result == 0) {
printf("parse success\n");
} else {
printf("parse failed\n");
}
return parse_result;
}
>=1.2.3-alpha.1+x86
RangeSet:
Range:
RangeSimples:
Simples:
Simple:
SimplePrimitive:
Primitive
Compare: CompGte
Partial3:
Nr: 1
Nr: 2
Nr: 3
Qualifier:
Parts:
Part:
PartId: "alpha.1"
Location: 0:8-0:15
Parts:
Part:
PartId: "x86"
Location: 0:16-0:19
parse success
パーサーが構文木を生成し、トークンの位置情報を追跡していることがわかります。この実装では位置情報を完全に追跡はしていませんが、具象構文木をつくるときも同じ方法で全ての記号の位置を追跡することができるはずです。
Discussion