しかくいさんかく

解答略のメモ

22日目: [コンパイラ] 抽象構文木

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

昨日は頑張って解析木を作った。

今日は解析木の冗長性を省いて、抽象構文木を作る。

抽象構文木とは

昨日は以下のサンプルコードを構文解析した。

// C言語風コード
int main () {
  int a ;
  a = 3 ;
  return 0 ;
}

そして解析木が得られた。

f:id:kaitou_ryaku:20171222225736p:plain

この解析木は冗長すぎるので、簡単化したい。具体的には

  1. 水色で示したSKIP_NODEを削除
  2. 緑色で示した中身1個(つまり直下のノードが1個)のコンテナを、中身で置換
  3. 数式を二分木に変換

SKIP_NODEは、BNFに基いて構文解析する際に無視すべきトークンを、無理やりノード化したものだった。削除しても問題ない。 この辺の詳細は 一昨日の記事 の一番下に書いた。

コンテナは僕が勝手に命名したノード群で、SENTENCE, EXPRESSION, FORMULA, TERM, FACTORの5つを指している。 これらは複数の処理をまとめたノードであり、処理そのものを表すノード(B_OPERATORとかASSIGNとか)とは性質が異なる。 コンテナの中身が一つしかなければ、コンテナは必要ない。

数式の二分岐化については、複雑なのであとで説明する。

これらを処理して解析木をシンプルにしたツリーを抽象構文木という[^1]。

f:id:kaitou_ryaku:20171222225753p:plain:w400

だいぶすっきりした。

抽象構文木の作成命令

まず 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;
}

この関数の中では、前節で紹介した処理

  1. SKIP_NODEの削除
  2. 中身1個のコンテナの削除
  3. 数式の二分木化

を実行し、解析木を簡単化している。順に見ていこう。

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関数 を呼び出して行っている。 この関数は引数で指定されたノードの子孫のノードを全削除する、汎用的な関数だ。

f:id:kaitou_ryaku:20171222225802p:plain:w400

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を削除すると、解析木から水色のノードがなくなる。

f:id:kaitou_ryaku:20171222225814p:plain:w400

2. 中身1個のコンテナを削除

次は緑のノードの削除だ。この処理は abstract_tree関数 から呼び出される

  • eliminate_redundant_sentence(s)
  • eliminate_redundant_math(s)
  • eliminate_container(s)

の3つの関数で行っている。 これらの関数は前節のeliminate_insignificant関数とほぼ同じだ。 唯一の違いは、木の変更操作が「ノードの削除」ではなく「孤立ノードを中身で置換」になるところ。

孤立ノードを置換する際に replace_by_solitary_node関数 を呼び出している。

f:id:kaitou_ryaku:20171222225824p:plain:w400

上図の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個のコンテナを削除すると、緑のノードがなくなり抽象構文木っぽいものが得られる。

f:id:kaitou_ryaku:20171222225753p:plain:w400

3. 数式の二分木化

実はSKIP_NODEと中身1個のコンテナを消しただけだと、抽象構文木としては不完全だ。

数式の処理が残っている。

今まで数式についてほとんど触れてこなかったので、一気に話を進めよう。 簡単のために

a*2*3 + (b*4+5)

という数式について考える。 この数式を字句解析して構文解析すると、以下のような解析木が得られる。

f:id:kaitou_ryaku:20171222225840p:plain

この解析木に対し、水色のSKIP_NODEと緑色の中身1個のコンテナを消すと

f:id:kaitou_ryaku:20171222225854p:plain

かなりシンプルになった。 しかし黄色で示した数式コンテナが生き残っている。 これらのコンテナは中身が複数なので、さっき緑ノードの削除では消えなかったのだ。

ところで、我々の最終目標はx86アセンブラを吐くことだ。 x86の命令セットには、「括弧や加減乗除の優先順位を判断しつつ、イイ感じに計算する命令」などない。 「eaxebxを足す」とか「eaxの値をスタックに詰む」とか「スタックからeaxに値を戻す」 みたいな単純な命令しかなかった。

つまり

  • 登場人物は即値と変数(レジスタとメモリのこと)だけ
  • 演算は2項演算しかない

もっというと

  • 1+3+5は計算できない
  • 1+3なら計算できる

1+3+5をCPUで計算するには

  • 1と3を足す
  • その結果と5を足す

つまり2項演算だけに簡約しなければならない。 これは数式を二分木に変換することと等価である。

さっきの数式を二分木に変換すると

f:id:kaitou_ryaku:20171222225903p:plain:w400

黄色い数式コンテナが消えている。 登場人物は2項演算子B_OPERATOR、即値IMMEDIATE、変数VARIABLEの三人になった。

数式の二分木化の実装

二分木化の手順を知るため、さっきの数式の第一項

a*2*3

を考える。

f:id:kaitou_ryaku:20171222225911p:plain

  1. operator_zipper関数で、右端から順に2項演算の形にする
  2. eliminate_container関数で、数式コンテナを直下の2項演算子に置換

という処理を行えばよい。

以上で、抽象構文木の作成は完了。

計算の優先順位について

二分木化のところで

1+2*3 --> (1+2)*3

という事件が発生しそうだ。

しかし心配はいらない。構文解析BNF

  • 項の加減はFORMULA直下で行う
  • 因子の乗除はTERM直下で行う

と決まっている。 加減と乗除は解析木レベルで分離されているので、両者が交じることはない。

また括弧の優先順位についても解析木のFACTORノードで分離されているので、考えずに済む。

どうでもいい話

このコンパイラ製作の目的は、内部処理と仕組みを理解することだった。 基礎を知りたい。応用はどうでもいい。

そういう目的なので生成コードの最適化には興味がなかった。 しかし今日は抽象構文木の日なので、定数の畳み込みについてだけ言及しておこう。

要するに、コンパイル前のコードに1*2*3+(4*5+6)があれば、それをまるっと35という即値に置き換える最適化を定数の畳み込みという。 1+a+2があれば、和の順番をうまく入れ替えてa+3にする必要がある。

この畳込みはかんたんに実装できるけど、簡単なだけあって、実行時の速さを短縮する効果は薄いらしい(要出典)。 wikipedia を見ると、コンパイラ最適化の手法は山のように列挙されている。 こうした最適化は抽象構文木をどんどん変換する操作に対応するらしい。 (コード生成の段階で行う最適化もある)

また変数の型についても、抽象構文木を走査して不整合がないかチェックするらしい。 ちなみに今作っているminc言語の処理系では、型はintしかないので不整合もへったくれもない。