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

抽象構文木(2)

1.抽象構文木による四則演算インタプリタ

先に作成した抽象構文木生成プログラムに定数計算機能を付加した。 追加した関数を下に示す。
プログラム全体はこちら

double calc(Node *pNode) {
    if (strcmp(pNode->name, "num") == 0) return pNode->rval;
    double left  = calc(pNode->childs[0]); 
    double right = calc(pNode->childs[1]);
    if (pNode->name[0] == '+') return left + right;
    if (pNode->name[0] == '-') return left - right;
    if (pNode->name[0] == '*') return left * right;
    if (pNode->name[0] == '/') return left / right;
}

void constExpression(char *in_token[]) {
    token = in_token;
    ix = 0;
    Node *expr = addsub();
    printf("%.3f\n", calc(expr));
}

int main() {
    expression(token0); constExpression(token0);
    expression(token1); constExpression(token1);
    expression(token2); constExpression(token2);
}

実行結果を下に示す。

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

土台となるプログラムast01.cは100行を超えたが、 定数計算の追加は簡単であった。

2.コンパイラにおける定数計算

コンパイラの場合、例えば n + (2.5 * 4 + 3.2) を n + 13.2 のように簡単化したい。

C言語などの四則演算の構文規則は下に示すように、同一優先順位の演算子が二つ以上続いた場合、 左の演算子から順に計算する(左結合性)。

例えば、n + 3 + 2 の場合、(n + 3) + 2 と解釈されるため、n + 5 とはできない。 n + (3 + 2) の場合は、(3 + 2) が先に計算されるために、n + 5 となる。

人間の場合、下の構文規則よりももっと複雑な構文規則で計算を行っているため、 n + 3 + 2 は n + 5 とするわけである。

別の例として 2 < n < 10 は、C言語では (2 < n) < 10 と解釈され、 数学では 2 < n かつ n < 10 (C言語では 2 < n && n < 10)と解釈される。

このように、日常の数式の規則とプログラミング言語における数式の規則は若干異なることに注意を要する。

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

実用Cコンパイラでは、通常、例えば m = n + (2.5 * 4 + 3.2) の場合、予め()内の計算を行い、 m = n + 13.2 に対する機械語コードを生成する。

下に示すプログラムast03.cでは、 reduce関数で二つの子ノードが共に数値ノードのとき、演算を行い、数値ノードに置き換えている。

再帰的呼び出しを使って、先に子ノードの処理を行っている。 これにより、ボトムアップ的に末端ノードから根ノードに向かって、置換処理が進む。 色んな再帰的呼び出しを経験すれば、この動作は容易に理解できよう。

子ノード(数値ノード)を消去する際、メモリを解放している。 中・小規模プログラムを対象とするコンパイラの場合、使われるメモリは僅かであるから、 ここでメモリの解放を行わなくても問題は起こらない。 終日連続運転するようなプログラムの場合、C言語プログラムでは、通常は、 動的に確保したメモリの解放が必須となる。

メモリの獲得よりも、適切な場所でのメモリの解放の方が一般にははるかに面倒である。 解放を考えた設計を行うことが重要となる。

プログラムの実行が終われば、メモリは自動的に解放されるため、 プログラム実行終了時点での解放は実行してもしなくても同じである。

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

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

enum { NUM = 0, VAR };

char **token;
int  ix;
char *NAME[] = { "num", "var" };

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

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

Node *createNode(int type) {
    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->type = type;
    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 if (isdigit(*token[ix])) {
        pNode = createNode(NUM);
        pNode->rval = atof(token[ix++]);
    } else {
        pNode = createNode(VAR);
        pNode->var = token[ix++];
    } 
    return pNode;
}

void printAST(Node *node) {
    int n;
    if (node->type <= VAR) printf(" (%s", NAME[node->type]);
    else  printf(" (%c", node->type);
    for (n = 0; n < node->length; n++) {
        Node *pChild = node->childs[n];
        if (pChild->type == NUM) printf(" %.3f", pChild->rval);
        else if (pChild->type == VAR) printf(" %s", pChild->var);
        else printAST(pChild);
    }
    printf(")");
}

void reduce(Node *pNode);

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();
    reduce(expr);
    printAST(expr);
    printf("\n");
}

void reduce(Node *pNode) {
    int n;
    for (n = 0; n < pNode->length; n++)
        reduce(pNode->childs[n]);
    if (pNode->length==2 && pNode->childs[0]->type==NUM 
                         && pNode->childs[1]->type==NUM) {
        double left = pNode->childs[0]->rval;
        double right = pNode->childs[1]->rval;
        free(pNode->childs[0]);
        free(pNode->childs[1]);
        free(pNode->childs);
        if (pNode->type == '+') pNode->rval = left + right;
        else if (pNode->type == '-') pNode->rval = left - right;
        else if (pNode->type == '*') pNode->rval = left * right;
        else if (pNode->type == '/') pNode->rval = left / right;
        pNode->type = NUM;
        pNode->length = 0;
    }
}

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

int main() {
    expression(token0);
    expression(token1);
    expression(token2);
    expression(token3);
}

このプログラムの実行結果を下に示す。 先に述べた理由により n + 3 + 4 は、決して n + 7 に縮退はしない。 n + (3 + 4) の場合は、(3 + 4) が先に計算されるため、n + 7 に縮退する。 n + 3 * 4 * 5 の場合、+ より * の方が優先順位が高いことにより、n + 60 に縮退する。

c:\mh\www\c-tips\ast>ast03
 n + 3 + 4 ⇒  (+ (+ n 3.000) 4.000)
 n + ( 3 + 4 ) ⇒  (+ n 7.000)
 n + 3 * 4 * 5 ⇒  (+ n 60.000)
 ( 2 + 3 ) * k ⇒  (* 5.000 k)

抽象構文木を生成するまでが、構文解析であり、定数計算は意味解析に属する。 C言語の場合、sizeof演算子による sizeof(int) とか sizeof(data) も定数である。 例えば、次のプログラムでは、sizeof(data) は 20、sizeof(int) は 4 である。 従って、実用C言語コンパイラでは、 n < sizeof(data)/sizeof(int) は n < 5 に置き換えられて、この機械語コードが生成される。

sizeof(data) が 16 であることは、構文解析段階では分からない。 意味解析で '{' から '}' までの要素数をカウントして、 1次元配列dataの要素数が 5 であることが分かる。 ひとつの要素のサイズは 4 バイトであることから、sizeof(data) の値は 20 となる。 data は変数表に登録されるが、 データ型int、および要素数5(またはサイズ 20)などが配列変数dataの属性として登録される。 定数計算では、この変数表に登録された値が使用される。

すなわち、定数計算は意味解析の前処理として実行できるものではなく、 意味解析の一つとして行う処理である。

なお、sizeof は演算子であることから sizeof int、sizeof data のように被演算子を ( ) で括らなくてもよい。

int main() {
    int n, data[] = { 23, -1, 2, 0, 8 };

    for (n = 0; n < sizeof(data)/sizeof(int); n++)
	printf("%d ", data[n]);
}