21日目: [コンパイラ] 構文解析 (実装編)

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の21日目の記事です。

昨日は人力で構文解析を行った。

今日はその処理をC言語で実装する。

構文解析のアルゴリズム

解析木作成のgifアニメを作った。まずこれを5周ぐらい見て欲しい。

f:id:kaitou_ryaku:20171221064438g:plain:w400

これは再帰下降と呼ばれるアルゴリズムだが、日本語で説明すると

ノード属性N0を解析するパーサに、トークンの列[T1, T2, T3, T4, T5]が入力される
N0解析パーサは、N0を定義するBNFを参照し、[T1, T2, T3]がN1のノード属性を持つと特定する
N0のノードの下に、N1のノードを生やす
N1を解析するパーサに、トークンの列[T1, T2, T3]が入力される
N1解析パーサは、N1を定義するBNFを参照し、[T1, T2]がN3のノード属性を持つと特定する
N1のノードの下に、N2のノードを生やす

といった具合にツリーを生成しながら下降し、プログラムを細かく分解していく。

ツリーの下端に到達したら1つ上のノードに戻り、1つ右側のトークンが含まれるノードを特定して、再び下降を開始する。これは深さ優先探索で再帰的にツリーを作成するアルゴリズムになっている。

アルゴリズムの実装に必要なのは、ノード属性毎の解析パーサだ。それらを用意すれば解析木は自動生成されるだろう。

ノードを表す構造体

解析パーサを作る前に、ツリー構造を表現するためのノードを表す構造体を見ておく。

typedef struct __STRUCT_NODE__ {
  int kind; // ノードの種類
  int init; // トークン配列の開始index
  int last; // トークン配列の終了index
  bool arrived; // 走査時に使う

  // 周辺のノードへのポインタ
  struct __STRUCT_NODE__ *left,  *right,  *up,  *down;
} NODE;

構造体のメンバの意味は、さっきのgif動画を見ればわかると思う。

周辺ノードへのポインタ*left, *right, *up, *downは動画中の黒矢印を表している。黒矢印が存在しない場合はNULLにしておく。

このNODE構造体の配列で解析木を表す。例えばgif動画のツリーの左端三段は

NODE node[1000000];

node[0] = { // N0のノード
  kind  = N0; // 列挙型 enum で実装
  init  = T1のindex;
  last  = T5のindex;
  up    = NULL       ;
  left  = NULL       ; right = NULL;
  down  = &(node[1]) ;
}

node[1] = { // N1のノード
  kind  = N1;
  init  = T1のindex;
  last  = T3のindex;
  up    = &(node[0]) ;
  left  = NULL       ; right = &(node[6]);
  down  = &(node[2]) ;
}

node[2] = { // N1のノード
  kind  = N2;
  init  = T1のindex;
  last  = T2のindex;
  up    = &(node[1]) ;
  left  = NULL       ; right = &(node[5]);
  down  = &(node[3]) ;
}

minc解析パーサの挙動

gif動画の例だと、ノード属性N0を解析するパーサは以下の入出力を持つ。

入力	出力
[T1, T2, T3, T4, T5]	N1と[T1, T2, T3]のペア
[T4, T5]	N6と[T4, T5]のペア

シンボリックな例はここまでにする。

例として、minc言語のPROGRAMノードを解析するパーサの挙動を見てみよう。

例としてint a; int func ( int b );というサンプルコードを処理する際の、解析パーサの挙動を解説する。前処理としてサンプルコードを字句解析すると、以下のトークン配列が得られる。

TOKEN token[] = {
  TYPE     , // token[0] -- int
  VARIABLE , // token[1] -- a
  SEMICOLON, // token[2] -- ;
  TYPE     , // token[3] -- int
  VARIABLE , // token[4] -- func
  LPAREN   , // token[5] -- (
  TYPE     , // token[6] -- int
  VARIABLE , // token[7] -- b
  RPAREN   , // token[8] -- )
  SEMICOLON  // token[9] -- ;
}

このトークン配列を解析パーサの find_program に入れる。

構文解析のBNFは以下で与えられる。

ノード種別	BNFによる構文解析の定義
PROGRAM	(V_DEC SEMICOLON \| F_DEC \| PROTOTYPE SEMICOLON)*
PROTOTYPE	TYPE VARIABLE LPAREN (ep \| V_DEC (COMMA V_DEC)*) RPAREN
V_DEC	TYPE VARIABLE
F_DEC	TYPE VARIABLE LPAREN (ep \| V_DEC (COMMA V_DEC)*) RPAREN FUNCTION

まず最初に、token[0]からtoken[9]までの全トークンをパーサに入れると

int init = 0;
int last = 9;
// 入力されるトークン列は
// TYPE, VARIABLE, SEMICOLON, TYPE, VARIABLE, LPAREN, TYPE, VARIABLE, RPAREN, SEMICOLON
// トークン列に対応する入力文字列は
// "int a; int func ( int b );"

// initとlastを参照渡しで書き換える
int find_kind = find_program(&init, &last, token);

// 結果
// find_kind == V_DEC
// init      == 0 つまりV_DECの開始トークンは(TYPE, int)
// last      == 1 つまりV_DECの終了トークンは(VARIABLE, a)

token[0]からtoken[1] を処理し終えたとして、次に token[2]からtoken[9]をパーサに入力すると

int init = 2;
int last = 9;
// 入力されるトークン列は
// SEMICOLON, TYPE, VARIABLE, LPAREN, TYPE, VARIABLE, RPAREN, SEMICOLON
// トークン列に対応する入力文字列は
// "; int func ( int b );"

int find_kind = find_program(&init, &last, token);

// 結果
// find_kind == SKIP_NODE
// init      == 2 つまりSKIP_NODEの開始トークンは(SEMICOLON, ;)
// last      == 2 つまりSKIP_NODEの終了トークンは(SEMICOLON, ;)

token[2] を処理し終えたとして、次に token[3]からtoken[9]をパーサに入力すると

int init = 3;
int last = 9;
// 入力されるトークン列は
// TYPE, VARIABLE, LPAREN, TYPE, VARIABLE, RPAREN, SEMICOLON
// トークン列に対応する入力文字列は
// "int func ( int b );"

int find_kind = find_program(&init, &last, token);

// 結果
// find_kind == PROTOTYPE
// init      == 3 つまりPROTOTYPEの開始トークンは(TYPE, int)
// last      == 8 つまりPROTOTYPEの終了トークンは(RPAREN, 右括弧)

token[3]からtoken[8] を処理し終えたとして、次に token[9]をパーサに入力すると

int init = 9;
int last = 9;
// 入力されるトークン列は
// SEMICOLON
// トークン列に対応する入力文字列は
// ";"

int find_kind = find_program(&init, &last, token);

// 結果
// find_kind == SKIP_NODE
// init      == 9 つまりSKIP_NODEの開始トークンは(SEMICOLON, ;)
// last      == 9 つまりSKIP_NODEの終了トークンは(SEMICOLON, ;)

こうしたパーサを全ノード属性に対し作成すれば、解析木が作成される。

minc解析パーサの実装

続いて find_programの実装を見てみる。

要するに、token[*init]からtoken[*last]までのトークン列が入力された際に、token[*init]を含むノード属性を特定する関数を作りたい。

find_programが呼び出されると

int find_program(int *init, int *last, const TOKEN *token) {

  const int arg_init = *init, arg_last = *last;
  int  kind      = OTHER_NODE;
  int  nt        = *init;

引数の*initや*lastは後々書き換わるので、もとの値をarg_initやarg_lastとして保持
kind はfind_programの返り値で、ノード属性を表す。初期値は解析失敗を表すOTHER_NODE
ntは、トークン列内を遍歴するための整数。こいつが解析の主役

解析を開始する。

前セクションでSEMICOLONだけからなるノードにSKIP_NODEという属性を割り当てていた。あれを先に処理しておく。

if (token[nt].kind == SEMICOLON) {
  *last = *init;
  return SKIP_NODE;
}

ここからが本番だが、その前にBNFを再度貼っておく。

ノード種別	BNFによる構文解析の定義
PROGRAM	(V_DEC SEMICOLON \| F_DEC \| PROTOTYPE SEMICOLON)*
PROTOTYPE	TYPE VARIABLE LPAREN (ep \| V_DEC (COMMA V_DEC)*) RPAREN
V_DEC	TYPE VARIABLE
F_DEC	TYPE VARIABLE LPAREN (ep \| V_DEC (COMMA V_DEC)*) RPAREN FUNCTION

トークン列のノード属性が、V_DECなのかF_DECなのかPROTOTYPEなのか知りたい。これら3種類のノード属性は、全てTYPE と VARIABLEから始まっている。そしてTYPEはTYPE_KEYWORDだけからなるノードで、VARIABLEはDENTIFYだけからなるノードだった。

つまりノード列はTYPE_KEYWORD と IDENTIFYのトークンで始まっているはずだ。このチェックを行いつつ、これら2つのノードを読み飛ばそう。「このトークンが来るはず」というチェックを行う syntax_check関数を作っておくと、処理がスムーズに進む。

// TYPE_KEYWORD ID
syntax_check(__func__,nt,arg_init,arg_last,token,TYPE_KEYWORD);
nt++;
syntax_check(__func__,nt,arg_init,arg_last,token,IDENTIFY);
nt++;

TYPE_KEYWORD と IDENTIFY の次のトークンに着目しよう。これが SEMICOLON ならばグローバル変数なので、ノード属性は V_DEC になる。

// TYPE_KEYWORD ID ;
if      (token[nt].kind == SEMICOLON) {
  kind  = V_DEC;
  *last = nt-1;
}

関数プロトタイプや関数定義の場合、 IDENTIFY の次は RPAREN になる。

その場合、関数プロトタイプか関数定義か見極めるため、対応するLPARENまでntをワープさせる。こうした「対応する括弧へのワープ」は search_next_****系関数で行っている。

そしてワープ先のLPARENの次のトークンを調べて

SEMICOLONならばPROTOTYPE (関数プロトタイプ)
LBRCKETならばF_DEC (関数定義)

として、返り値のkindにノード属性を登録する。

// TYPE_KEYWORD ID (...)
else if (token[nt].kind == LPAREN) {
  nt = search_next_rparen(nt, arg_last, token);
  nt++;

  // TYPE_KEYWORD ID (...) ;
  if      (token[nt].kind == SEMICOLON) {
    kind  = PROTOTYPE;
    *last = nt-1;
  }

  // TYPE_KEYWORD ID (...) {...}
  else if (token[nt].kind == LBRACKET) {
    kind  = F_DEC;
    nt = search_next_rbracket(nt, arg_last, token);
    assert(nt > 0);
    *last = nt;
  }
}

return kind;

*initと*lastの更新について書いておこう。

もしPROTOTYPEだった場合、現在のntはSEMICOLONに対応する。 BNFを見ると、SEMICOLONはPROTOTYPEに含まれないので、*last=nt-1とする。

F_DECだった場合は、関数の内部処理が終了するRBRACKETまでntをワープさせて*lastに代入する。

そして最後に、特定したノード種別(kind)をreturnして、処理終了。

以上でfind_program関数の説明は終了だ。

なお本記事では簡単のためにエラー処理を無視している。ホントの実装はもう少し複雑になるが、本筋は変わらない。

解析木作成の再帰関数

全てのパーサを作っただけでは、解析木は生成されない。それらを統合して再帰的にトークン配列をパースする司令塔が必要だ。

この司令塔は make_down_tree関数が自分自身を再帰的に呼び出すことで実装されている。

この関数の機能を一言でまとめると、入力されたノードAに対し、そのノード以下の全ノードを解析した木を作成し、ノードAに接続して返す関数だ。

NODE *make_down_tree(
  const int init ,  // 最初のトークンのindex
  const int last ,  // 最後のトークンのindex
  NODE *up       ,  // 上のノードへのポインタ。`PROGRAM`ノードなら`NULL`
  NODE *left     ,  // 左のノードへのポインタ。最も左のノードなら`NULL`
  int *node_index,  // ノードの配列のindex。次のノードを登録する場所
  TOKEN *token   ,  // 字句解析の全結果の構造体配列。これとinitやlastを組み合わせて、トークン種別を調べる
  NODE *node        // ノードの配列。これをどんどん成長させていきたい
) {

  NODE *ret = NULL;
  int find_init = init,  find_last = last;
  int find_kind = OTHER_NODE;

  // ノード属性に応じて構文解析
  if (init <= last) {
    if      (up -> kind == PROGRAM   ) find_kind = find_program(   &find_init,  &find_last,  token);
    else if (up -> kind == PROTOTYPE ) find_kind = find_prototype( &find_init,  &find_last,  token);
    else if (up -> kind == F_DEC     ) find_kind = find_f_dec(     &find_init,  &find_last,  token);
    // ... 省略 ...
  }

  // token列内に有効なノードが見つかった場合は登録
  if (find_kind != OTHER_NODE) {
    ret          = &(node[*node_index]);
    ret -> init  = find_init;
    ret -> last  = find_last;
    ret -> kind  = find_kind;
    ret -> up    = up;
    ret -> left  = left;
    *node_index += 1;

    ret -> down  = make_down_tree(find_init,    find_last,  ret,  NULL,  node_index,  token,  node); // retの下の木を作成
    ret -> right = make_down_tree(find_last+1,  last,       up ,  ret ,  node_index,  token,  node); // retの下の木を作成
  }

  return ret;
}

特に重要なのは、ノード属性に応じて解析パーサを呼び出す部分

if      (up -> kind == PROGRAM  )
  find_kind = find_program(  &find_init,  &find_last,  token);

else if (up -> kind == PROTOTYPE)
  find_kind = find_prototype(&find_init,  &find_last,  token);

...

解析パーサの返り値は、make_down_tree関数の返り値の構造体retに格納される。最後にmake_down_tree自身を再帰呼び出ししている。この再帰呼び出しにより、「入力されたノードAに対し、そのノード以下の全てのノードの木を作成し、ノードAに接続して返す」という機能が実現できる。

解析木全体の作成

前節のmake_down_tree関数を main関数内で呼び出すことでツリー全体を作成している。

その際の引数は

make_down_tree(
  0               ,  // 全てのトークンを解析したいので、開始indexは0
  max_token_num-1 ,  // 全てのトークンを解析したいので、終了indexはトークン列の長さ-1
  &(node[0])      ,  // node[0]を`PROGRAM`ノードとしてあらかじめ準備し、この関数に渡した
  NULL            ,  // `PROGRAM`ノードの上のノードは無いのでNULL
  &node_index     ,  // node[1]以降に新たなノードを登録したいので、*node_indexは1になっている
  token           ,  // 字句解析の全結果の構造体配列
  node            ,  // これを成長させて立派な解析木にするぞ
);

要するに、あらかじめPROGRAMノードにトークン配列を詰めておき、それをmake_down_tree関数に渡すことで再帰的にツリー全体を生成している。

どうでもいい話

今までの説明で理論上はツリーが生成されるはずだ。しかしこのまま作り始めると地獄を見る。

僕は何も考えずにいきなりパーサを書き始めて、辛い思いをした。しかしその経験のおかげで、負担を軽減するためのテクニックをいくつか習得したので、一挙に公開しよう。

解析木の図示化

パーサを作るより前に、まずツリーの可視化機能を作る。グラフィカルで見やすいものを作る。 dot言語でツリーを吐き出して、graphvizで即座に確認できる環境を整える。

(僕はdot言語の存在を知らず、ツリー描画機能を自作してしまった)

テスト駆動開発

解析木の図示化と共に、パーサ毎にユニットテストできる環境を整える。たとえばif文の解析パーサを書く時は

"if (a==1) {a=2;}"
"if (func(a)) {;} else {func(c,d);}"

のような文字列と、その構文解析結果をあらかじめ用意しておく。テストパターンはたくさんあるほどよい。「おお、このパターンを見過ごしてた」という気づきのオンパレードになるだろう。

(僕はテストの量が少なくて、後々になって抜け漏れが多数見つかって崩壊した)

特にSENTENCEのようなややこしいパーサを書く時は

char *K = "{{{{a=1;}}}}";
char *J = "{a=1;{a=2;}a=3;}";

みたいな気持ち悪いテストをたくさん用意しておく。

(僕はテストを書かずに雰囲気でパーサを書き始めて崩壊した)

簡単なパーサから書く

ユニットテスト環境を整える最大のメリットは、簡単なパーサから順に書けることだ。テスト環境を後回しにすると、まずPROGRAMのパーサを書いて、次にFUNCTIONの解析パーサを書いて、次にSENTENCEの解析パーサを書いて、というように、パーサを書く順番が固定されてしまう。特にSENTENCEのパーサは難易度が高かった。 5,6個パーサを書くと慣れてくるので、難しいパーサは最後に書こう。

(僕は序盤にSENTENCEの解析パーサを書いて崩壊した)

正しいサンプルコードが正しく解析できれば、よしとする

誤ったサンプルコードに対し、誤っている点を見つけて指摘する機能、すごく魅力的だよね。でもそれすげぇ難しいからな。まずは正しいコードが正しく構文解析される状態を目指すべき。

(僕はパーサ製作の初期にsyntax error機能を頑張って実装したが、メンテ不可能で崩壊した)

紙と鉛筆で入念に設計する

いきなりキーボードを叩くのはヤバい。簡単そうなノードのパーサでも、全てのパターンとその対応法を完璧に準備してからコードを書くのが重要。

(僕は何もかも適当で崩壊した)

設計の失敗

根本的な設計に関してだが、今回作ったパーサの入出力は

入力	出力
[T1, T2, T3, T4, T5]	N1と[T1, T2, T3]のペア
[T4, T5]	N6と[T4, T5]のペア

もしやり直せるなら、以下のようにするだろう。

入力	出力
T1, [T1, T2, T3, T4, T5]	N1と[T1, T2, T3]のペア
T4, [T1, T2, T3, T4, T5]	N6と[T4, T5]のペア

mincは言語仕様が単純なので今回作ったパーサで解析できたが、BNFが複雑になると破綻する。入出力を改良すれば、かなりややこしい言語でも解析できると思う。

さて、コンパイラの作成で一番しんどい部分が終わった。明日は解析木を抽象構文木に変換するが、作業のしんどさは昨日今日の10%程度なので、へらへらしよう。

しかくいさんかく

解答略のメモ