💭

FlexとBisonで実用的なパーサーを作る

に公開
C
parser
bison
flex
tech

パーサージェネレーターと言えば 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 で実装したリポジトリはこちらです。

https://github.com/Hagihara-A/practical-parser-in-flex-bison

レキサー の実装

Flex のオプション

まずは レキサー を作っていきます。Flex の文法定義ファイルには.lの拡張子をつけることが一般的です。モダンなmakeでは.lを認識してよしなにやってくれるらしいです。

いきなりですが Flex の option では以下を指定します。

lex.l
%option reentrant header-file="lex.yy.h" noyywrap
%option bison-bridge bison-locations
  1. reentrant: レキサー をスレッドセーフにする。これがないとグローバル変数を多用して治安が悪くなる。
  2. header-file="lex.yy.h": ヘッダファイルを生成する。
  3. noyywrap: 入力が EOF になったときに復帰処理をしない。(単純化のため)
  4. 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のタグ名を書くことに特に注意してください。

この辺りは結構複雑なのですが、実際にパーサーを書くときには

  1. Partial型を定義する
  2. union YYSTYPEに Partial 型のメンバを追加する
  3. %ntermを宣言する
  4. 生成規則を書く

という流れになるかと思います。

構文木の返却

以上で構文木を構築して記録することができました。この構文木を他のプログラム中で利用するには少し工夫が必要になります。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