22日目: [コンパイラ] 抽象構文木
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の22日目の記事です。
昨日は頑張って解析木を作った。
今日は解析木の冗長性を省いて、抽象構文木を作る。
抽象構文木とは
昨日は以下のサンプルコードを構文解析した。
// C言語風コード int main () { int a ; a = 3 ; return 0 ; }
そして解析木が得られた。
この解析木は冗長すぎるので、簡単化したい。具体的には
- 水色で示したSKIP_NODEを削除
- 緑色で示した中身1個(つまり直下のノードが1個)のコンテナを、中身で置換
- 数式を二分木に変換
SKIP_NODEは、BNFに基いて構文解析する際に無視すべきトークンを、無理やりノード化したものだった。削除しても問題ない。 この辺の詳細は 一昨日の記事 の一番下に書いた。
コンテナは僕が勝手に命名したノード群で、SENTENCE, EXPRESSION, FORMULA, TERM, FACTORの5つを指している。 これらは複数の処理をまとめたノードであり、処理そのものを表すノード(B_OPERATORとかASSIGNとか)とは性質が異なる。 コンテナの中身が一つしかなければ、コンテナは必要ない。
数式の二分岐化については、複雑なのであとで説明する。
これらを処理して解析木をシンプルにしたツリーを抽象構文木という[^1]。
だいぶすっきりした。
抽象構文木の作成命令
まず
main
関数
の中で、
昨日作ったPROGRAMノードをSOURCE
構造体でラップした。
SOURCE src; src.program = node; src.max_node_num = node_index; src.token = token; src.max_token_num = max_token_num;
SOURCE src
は解析木を走査するための構造体だ。
解析木を構成するNODE
構造体に、配列長などの走査時に必要な情報を付け加えたものになっており、
common.h
で宣言されている。
本質はNODE
の構造体と同じだ。
typedef struct { NODE *program; // 木の最上段のPROGRAMノード int max_node_num; // NODE配列のサイズ TOKEN *token; // 字句解析結果のトークン配列 int max_token_num; // トークン配列のサイズ } SOURCE;
その後
main
関数
から
abstract_tree
関数
を呼び出し、NODE
配列を解析木から抽象構文木へと上書きしている。
SOURCE abstract_tree(SOURCE s) { eliminate_insignificant(s); // SKIP_NODEの削除 eliminate_redundant_sentence(s); // 中身1個のコンテナの削除 eliminate_redundant_math(s); // 中身1個のコンテナの削除 operator_zipper(&s); // 数式の二分木化 eliminate_container(s); // 数式の二分木化 return s; }
この関数の中では、前節で紹介した処理
- SKIP_NODEの削除
- 中身1個のコンテナの削除
- 数式の二分木化
を実行し、解析木を簡単化している。順に見ていこう。
1. SKIP_NODEの削除
abstract_tree
関数
内で最初に呼び出されているのは
eliminate_insignificant
関数。
これはSKIP_NODEを削除する関数だ。
void eliminate_insignificant(SOURCE s) { // SKIP_NODE と ; だけの命令を全削除する関数 // 走査準備 NODE *node = s.program; for (int i=0; i<s.max_node_num; i++) { s.program[i].arrived = false; } // 走査開始 while (node != NULL) { if (node -> kind == SKIP_NODE) delete_node_recursive(node); node = go_next_node(node); } }
ノードの削除は
delete_node_recursive
関数
を呼び出して行っている。
この関数は引数で指定されたノードの子孫のノードを全削除する、汎用的な関数だ。
void delete_node_recursive(NODE *node) { NODE *up = node -> up; assert(up != NULL); // node[0]のPROGRAMは消せない仕様 NODE *left = node -> left; NODE *right = node -> right; if (left != NULL && right != NULL) { left -> right = right; right -> left = left; } else if (left != NULL && right == NULL) { left -> right = NULL; } else if (left == NULL && right != NULL) { up -> down = right; right -> left = NULL; } else if (left == NULL && right == NULL) { up -> down = NULL; } }
こうしてSKIP_NODEを削除すると、解析木から水色のノードがなくなる。
2. 中身1個のコンテナを削除
次は緑のノードの削除だ。この処理は
abstract_tree
関数
から呼び出される
eliminate_redundant_sentence(s)
eliminate_redundant_math(s)
eliminate_container(s)
の3つの関数で行っている。
これらの関数は前節のeliminate_insignificant
関数とほぼ同じだ。
唯一の違いは、木の変更操作が「ノードの削除」ではなく「孤立ノードを中身で置換」になるところ。
孤立ノードを置換する際に
replace_by_solitary_node
関数
を呼び出している。
上図のN4のノードが、
replace_by_solitary_node
関数の引数に対応している。
void replace_by_solitary_node(NODE *node) { NODE *up = node -> up; if ((up != NULL) && (node -> left == NULL) && (node -> right == NULL)) { up -> kind = node -> kind; // 上を孤独な自分で置き換えて、自分を削除 up -> init = node -> init; up -> last = node -> last; up -> down = node -> down; // 関数コールの場合は引数を上にコピーする必要がある NODE *down = node -> down; while (down != NULL) { down -> up = up; down = down -> right; } } }
こうして中身1個のコンテナを削除すると、緑のノードがなくなり抽象構文木っぽいものが得られる。
3. 数式の二分木化
実はSKIP_NODEと中身1個のコンテナを消しただけだと、抽象構文木としては不完全だ。
数式の処理が残っている。
今まで数式についてほとんど触れてこなかったので、一気に話を進めよう。 簡単のために
a*2*3 + (b*4+5)
という数式について考える。 この数式を字句解析して構文解析すると、以下のような解析木が得られる。
この解析木に対し、水色のSKIP_NODEと緑色の中身1個のコンテナを消すと
かなりシンプルになった。 しかし黄色で示した数式コンテナが生き残っている。 これらのコンテナは中身が複数なので、さっき緑ノードの削除では消えなかったのだ。
ところで、我々の最終目標はx86のアセンブラを吐くことだ。
x86の命令セットには、「括弧や加減乗除の優先順位を判断しつつ、イイ感じに計算する命令」などない。
「eax
とebx
を足す」とか「eax
の値をスタックに詰む」とか「スタックからeax
に値を戻す」
みたいな単純な命令しかなかった。
つまり
- 登場人物は即値と変数(レジスタとメモリのこと)だけ
- 演算は2項演算しかない
もっというと
1+3+5
は計算できない1+3
なら計算できる
1+3+5
をCPUで計算するには
- 1と3を足す
- その結果と5を足す
つまり2項演算だけに簡約しなければならない。 これは数式を二分木に変換することと等価である。
さっきの数式を二分木に変換すると
黄色い数式コンテナが消えている。
登場人物は2項演算子B_OPERATOR
、即値IMMEDIATE
、変数VARIABLE
の三人になった。
数式の二分木化の実装
二分木化の手順を知るため、さっきの数式の第一項
a*2*3
を考える。
operator_zipper
関数で、右端から順に2項演算の形にするeliminate_container
関数で、数式コンテナを直下の2項演算子に置換
という処理を行えばよい。
以上で、抽象構文木の作成は完了。
計算の優先順位について
二分木化のところで
1+2*3 --> (1+2)*3
という事件が発生しそうだ。
- 項の加減は
FORMULA
直下で行う - 因子の乗除は
TERM
直下で行う
と決まっている。 加減と乗除は解析木レベルで分離されているので、両者が交じることはない。
また括弧の優先順位についても解析木のFACTORノードで分離されているので、考えずに済む。
どうでもいい話
このコンパイラ製作の目的は、内部処理と仕組みを理解することだった。 基礎を知りたい。応用はどうでもいい。
そういう目的なので生成コードの最適化には興味がなかった。 しかし今日は抽象構文木の日なので、定数の畳み込みについてだけ言及しておこう。
要するに、コンパイル前のコードに1*2*3+(4*5+6)
があれば、それをまるっと35
という即値に置き換える最適化を定数の畳み込みという。
1+a+2
があれば、和の順番をうまく入れ替えてa+3
にする必要がある。
この畳込みはかんたんに実装できるけど、簡単なだけあって、実行時の速さを短縮する効果は薄いらしい(要出典)。 wikipedia を見ると、コンパイラ最適化の手法は山のように列挙されている。 こうした最適化は抽象構文木をどんどん変換する操作に対応するらしい。 (コード生成の段階で行う最適化もある)
また変数の型についても、抽象構文木を走査して不整合がないかチェックするらしい。
ちなみに今作っているminc言語の処理系では、型はint
しかないので不整合もへったくれもない。