トップC-Tips > 抽象構文木

抽象構文木

1.抽象構文木とは

元のプログラムの構造をそのまま木構造で表したものを構文木(syntax tree, parse tree)という。 全てのトークン(字句)が構文木に含まれる。 これらのトークンには、"(" や ")" など後の処理(意味解析など)に不要なものも含まれる。 これら不要なトークンを除いたものを、抽象構文木(abstarct syntax tree)という。

構文木と抽象構文木の違いの例を下図に示す。


[出典: http://www.csg.is.titech.ac.jp/~chiba/lecture/os/lang105.html]

C言語で表現する場合、構文木のノードと葉は一般に構造体となるが、 どのように定義するかは、特に定まっていない。後の処理に都合のよいように定義する。

Tiny Cの場合、 リスト構造を採り、次のように表現している。

2項演算子
a + b   => (+ a b)
a - b   => (- a b)

関数呼び出し
foo(i, 3) => (foo i 3)
bar()     => (bar)

配列参照
table[3]  => ([] table 3)

変数宣言:*var* を演算子とする演算処理
int i;      => (*var* i int)
int* i;     => (*var* i int*)
int k[3];   => (*var* k int 3)

式文
foo();      => (; (foo))
foo(1, 2);  => (; (foo 1 2))

その他
a = 1;      => (= a 1)
a = a + 1;  => (= a (+ a 1))
return k;   => (return k)
if(a == 3) a = 3;          => (if (== a 3) (= a 3))
if(c) a = 3; else a = c;   => (if c (= a 3) (= a c))
{ int k; a = 3; }          => ({} (*var* k int) (= a 3))
関数定義
int foo(int k, int j) {
    k = k + j;
    return k - 1;
}
     =>     
(int foo ((*var* k int) (*var* j int))
    (= k (+ k j))
    (return (- k 1)))

2.ノードを表す構造体

NodeBinary, NodeUnary, NodeIf, NodeFor のように、種類別にノードを定義する案もあるが、 まずは、なるべく、少ない構造体定義で対応することを考える。

a + b + c は (+ (+ a b) c) の子供が二つのノードで表す案と (+ a b c) のように任意の数の子ノードを持たせる案がある。 a + b - c のように優先順位は同じでも演算子が異なるケースがあるため、 二項演算子の子ノードは二つとする。 複文における文の数や関数の引数の数のように、元々可変個のものがあるから、 一般には、任意の数の子ノードを持てるとする。

具体例を下に示す。 子ノードを指すポインタは可変長配列としている。 ノード生成時に子ノード数が不明のときは、余裕をみた数とする。 配列サイズが不足した場合、再割り当てで拡張する。

Node *pNode; の左辺(第1子)ノードを指すポインタは pNode->childs[0] 右辺(第2子)ノードを指すポインタは pNode->childs[2] である。

typedef struct _Node {
    char *name;              // ノード名
    struct _Node **childs;   // 子ノード可変長配列
    int size;                // 子ノード配列サイズ(最大ノード数)
    int length;              // 子ノード数
} Node;

子ノードを可変長配列ではなく、リスト構造とする場合、下のようになる。

Node *pNode; の左辺(第1子)ノードを指すポインタは pNode->child 右辺(第2子)ノードを指すポインタは pNode->child->next である。

可変長配列のときの再割り当てはないが、 子ノードの参照が可変長配列よりもほんの僅かであるが分かりにくい。

typedef struct _Node {
    char *name;                 // ノード名
    struct _Node *child;        // 第1子ノード
    struct _Node *next;         // 次ノード(弟妹ノード)
} Node;

この場合、いずれの定義でも大差がないが、一般には、後で、定義を変更する可能性がある。 このため、登録、参照では、直接、データ構造に触れるのではなく、 インタフェース関数を用意しておき、これを使うようにする。 例えば、次のような関数を用意する。

Node *getChild(Node *pNode, int n);
void addChild(Node *pNode, Node *pChild);

一般にひとつのノードの全子ノードに対する処理が行われることが多いため、 リスト構造の場合、毎回、親ノードのポインターを引数にするのは、多少非効率である。

また、プログラム自体も可変長配列の方がシンプルとなる。 下にプログラムを示す。

Node *getChild(Node *pNode, int n) {
    return n < pNode->length ? childs[n] : NULL;
}

void addChild(Node *pNode, Node *pChild) {
    if (pNode->length >= pNode->size) {
        pNode->size = pNode->size * 2;        // 2倍に拡張する
        pNode->childs = realloc(pNode->childs, pNode->size * sizeof(Node*));
        if (pNode->childs == NULL) error("reallocに失敗しました");
    }
    pNode->childs[pNode->length++] = pChild;
}

3.四則演算式の抽象構文木生成プログラム

まず、次の構文規則に従う式の抽象構文木を生成するプログラムを作成する。

   <addsub> ::= <muldiv> ( '+' <muldiv> | '-' <muldiv> )* 
    <muldiv> ::= <factor> ( '*' <factor> | '/' <factor> )* 
    <factor> ::= 数値 | '(' <addsub> ')'

ここで、( V )* は V が 0 個以上繰り返すことを表す。

抽象構文木生成プログラムを以下に示す。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Node {
    char *name;                // ノード名
    struct _Node **childs;     // 子ノード可変長配列
    int size;                  // 子ノード配列サイズ(最大ノード数)
    int length;                // 子ノード数
    double rval;               // 数値
} Node;

char *token[];
int  ix;

Node *addsub();
Node *muldiv();
Node *factor();

void error(char *msg) {
    fprintf(stderr, "error: %s\n", msg);
    exit(1);
}

Node *createNode(char *name) {
    Node *pNode = calloc(1, sizeof(Node));
    if (pNode == NULL) error("メモリが足りません");
    pNode->size = 2;
    pNode->childs = calloc(pNode->size, sizeof(Node*));
    if (pNode->childs == NULL) error("メモリが足りません");
    pNode->name = name;
    return pNode;
}

void addChild(Node *pNode, Node *pChild) {
    if (pNode->length >= pNode->size) {
        pNode->size = pNode->size * 2;        // 2倍に拡張する
        pNode->childs = realloc(pNode->childs, pNode->size * sizeof(Node*));
        if (pNode->childs == NULL) error("reallocに失敗しました");
    }
    pNode->childs[pNode->length++] = pChild;
}

void addChild2(Node *pNode, Node *pChild1, Node *pChild2) {
    addChild(pNode, pChild1);
    addChild(pNode, pChild2);
}

// <addsub> ::= <muldiv> ( '+' <muldiv> | '-' <muldiv> )*
Node *addsub() {
    Node *pLeft = muldiv();
    while (token[ix] != NULL && (*token[ix]=='+' || *token[ix]=='-')) {
        Node *pNode = createNode(token[ix++]);
        Node *pRight = muldiv(); 
        addChild2(pNode, pLeft, pRight);
        pLeft = pNode;
    }
    return pLeft;
}

// <muldiv> ::= <factor> ( '*' <factor> | '/' <factor> )*
Node *muldiv() {        
    Node *pLeft = factor();
    while (token[ix] != NULL && (*token[ix]=='*' || *token[ix]=='/')) {
        Node *pNode = createNode(token[ix++]);
        Node *pRight = factor(); 
        addChild2(pNode, pLeft, pRight);
        pLeft = pNode;
    }
    return pLeft;
}

// <factor> ::= 数値 | '(' <addsub> ')'
Node *factor() {
    Node *pNode;
    if (*token[ix] == '('){
        ix++;
        pNode = addsub();
        if (*token[ix++] != ')') error(")がありません!");
    } else {
        pNode = createNode("num");
        pNode->rval = atof(token[ix++]);
    } 
    return pNode;
}

void printAST(Node *node) {
    int n;
    printf(" (%s", node->name);
    for (n = 0; n < node->length; n++) {
        Node *pChild = node->childs[n];
        if (strcmp(pChild->name, "num") == 0) 
            printf(" %.3f", pChild->rval);
        else printAST(pChild);
    }
    printf(")");
}

void expression(char *in_token[]) {
    int n;

    for (n = 0; in_token[n] != NULL; n++)
        printf(" %s", in_token[n]);
    printf(" ⇒ ");

    token = in_token;
    ix = 0;
    Node *expr = addsub();
    printAST(expr);
    printf("\n");
}

char *token0[] = { "2", "+", "3", "+", "4", NULL };
char *token1[] = { "2", "+", "3", "*", "4", NULL };
char *token2[] = { "(", "2", "+", "3", ")", "*", "4", NULL };

void main() {
    expression(token0);
    expression(token1);
    expression(token2);
}

このプログラムの実行結果を下に示す。

c:\mh\www\c-tips\ast>ast01
 2 + 3 + 4 ⇒  (+ (+ 2.000 3.000) 4.000)
 2 + 3 * 4 ⇒  (+ 2.000 (* 3.000 4.000))
 ( 2 + 3 ) * 4 ⇒  (* (+ 2.000 3.000) 4.000)

4.抽象構文木と最適化処理

TCCや自作コンパイラMCCでは構文木を使わず、直接、中間語コードを生成している。 構文解析では、抽象構文木を生成し、意味解析で、抽象構文木から中間語コードを生成するようにすれば、 構文解析プログラムと意味解析プログラムの分離・独立化が図れる。 ただし、全体のプログラム規模は大きくなり、コンパイラ時間が増える可能性はある。

しかし、定数計算やある程度の最適化処理が抽象構文木レベルで行えるメリットがある。

現在のMCCでは、int n = 2 * 3 + 4; の右辺は定数計算を行い、int n = 10; とするが、 int k = 3, n = k + 2 * 3 + 4; のような場合、一切、定数計算は行われない。

抽象構文木では、n の右辺の最初の + の右辺(第2オペランド)が定数計算であることは自明であるから、 n = k + 10 に縮退できる。変数表の要素として、初期値を持てば、この場合、k の初期値は 3 であるから、 n の初期値は 13 となる。k がもし、関数の仮引数ならば、初期値を持たないため、 n = k + 10 より簡単化はできない。

ただし、通常のプログラムでは、このような最適化による実行時間の短縮は微々たるものである。

MCCでのレジスタ割り当ては二項演算の左辺(第1オペランド)でも右辺(第2オペランド)も全く同じである。 レジスタ再割り当てによる最適化は後から行っている。 効率的なレジスタ割り当てを抽象構文木段階で行う方が分かり易いかもしれない。

MCCでの最適化のもう一つの柱は、if文やfor文、while文などにおける論理演算と分岐の最適化である。 論理演算単独では、結果が真のとき 1 、偽のとき 0 とするが、 if文やfor文、while文などの判定式では、1/0 は不要であり、中間語コードとしては分岐命令だけでよい。

この最適化は抽象構文木段階で行えるのか、あるいは難しいのか未検討である。 代入文 x = a && b; における a && b と if (a && b) stmt1; else stmt0; における a && b は最適化を考えると、生成コードが異なる。同じ代入文でも x = a && b; と x = (a && b) || c; では a && b の扱いが異なる。 抽象構文木では親が明白なため、親によって処理を変えるのが容易であろう。