21日目: [コンパイラ] 構文解析 (実装編)
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の21日目の記事です。
昨日は人力で構文解析を行った。
今日はその処理をC言語で実装する。
構文解析のアルゴリズム
解析木作成のgifアニメを作った。まずこれを5周ぐらい見て欲しい。
これは再帰下降と呼ばれるアルゴリズムだが、日本語で説明すると
- ノード属性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による構文解析の定義 |
---|---|
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_NODEnt
は、トークン列内を遍歴するための整数。こいつが解析の主役
解析を開始する。
前セクションで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%程度なので、へらへらしよう。