トップC-Tips > 可変長配列[抽象構文木]

可変長配列[抽象構文木]

1.可変長配列の定義

可変長配列をサポートしているプログラミング言語は多いが、C言語ではサポートしていない。 ここでは、realloc関数を使って可変長配列を実現する例を示す。

下に抽象構文木の作成で用いた Node構造体の定義を示す。 子ノード数(枝数)は一般に可変個である。 ノード種別によっては予め分かるケースもあるが、事前には分からないケースもある。

Node構造体の定義では子ノードポインタ配列を struct Node *sub[0]; と定義しているが、 例えば、3個分の領域を確保しておけば、 struct Node *sub[3]; と定義したのと同じように、 sub[0], sub[1], sub[2] が使用できる。

構造体の場合、末尾の配列要素のみが可変長配列とできる。

typedef struct Node {
    int  type;
    void *val;
    int  nSub, size;    // nSub:子ノード数, size: 最大コード数(メモリが確保された値)
    struct Node *sub[0];
} Node;

2.可変長配列のメモリ割り当て

上で定義したNode構造体の場合、次のようにすれば、size個分の子コードポインタ領域が確保される。 下のプログラムでは size要素のみ有効な値を設定しており、その他の要素の値は不定である。

    Node *pNode = malloc(sizeof(Node) + size*sizeof(Node*));
    pNode->size = size;

抽象構文木の生成では下に示すような関数を用意した。

Node *allocNode(int type, void *val, int size) {
    Node node = { type, val, 0, size };
    Node *pNode = malloc(sizeof(Node) + size*sizeof(Node*));
    if (pNode == NULL) error("allocNode: メモリ確保に失敗しました. size=%d", size);
    return memcpy(pNode, &node, sizeof(Node));
}

Node *genNode(int type, void *val, Node *sub0, ...) {
    Node *pNode;
    Node **pSub = &sub0; // 第3引数以降を配列としてとらえる. pSub[0] と sub0 は同じもの
    int cnt = 0;
    while (pSub[cnt] != NULL) cnt++;    // 子コード数をカウントする
    pNode = allocNode(type, val, cnt);
    memcpy(pNode->sub, pSub, sizeof(Node*) * cnt);
    pNode->nSub = cnt;
    return pNode;
}

Node *addSubNode(Node *pNode, Node *pSub) {
    if (pNode->nSub == pNode->size) {
        pNode->size *= 2;
        pNode = realloc(pNode, sizeof(Node) + pNode->size * sizeof(Node*));
        if (pNode == NULL) error("realloc: メモリ確保に失敗しました. size=%d", pNode->size);
    }
    pNode->sub[pNode->nSub++] = pSub;
    return pNode;
}

void freeNodes(Node *pNode) {
    int n = 0;
    while (n < pNode->nSub) freeNodes(pNode->sub[n++]);
    free(pNode);        // サブノード(子供)を先に解放し、最後に自分(親)を解放する
}

この関数を使用するプログラムの例を下に示す。 genNode関数の最後の引数は必ず NULL とする。 genNode関数では、NULLが現れるまでの子ノードポインタ引数の数をよって子ノード数を求めている。

/// AddExpression ::= MulExpression ( ("+" | "-") MulExpression )*
Node *AddExpressionAST() {  // #5
    int fAdd=0;
    Node *pLeft = MulExpressionAST();    
    while ((fAdd=ispp("+")) || ispp("-")) {
        Node *pRight = MulExpressionAST(); // 右辺の値
        pLeft = genNode(fAdd ? ADD : SUB, 0, pLeft, pRight, NULL);
    }
    return pLeft;
}

関数コールの引数など一部のノードについては構文木生成時に予め子ノード数を知ることはできない。 このため、最初に allocNode関数で適当な子ノード数の領域を確保しておき、 addSubNode関数を使って子ノードポインタを一つずつ登録している。 子ノードポインタ領域が足りなくなったら、addSubNode関数が内部処理で子ノードポインタ領域を 拡張している。

addSubNode関数は使う側では拡張を意識しなくてよいが、 ノードポインタ(第1引数)の値は拡張により元とは変わる可能性があるため、 必ず戻り値を使う必要がある。


実際のプログラムでは genNode関数は子ノードなし、子ノード1、子ノード2、子ノード3で用いている。 従って、下のように、子ノード数別の関数に置き換えることもできる。

Node *genNode0(int type, void *val) {
    return allocNode(type, val, 0);
}

Node *genNode1(int type, void *val, Node *sub0) {
    Node *pNode = allocNode(type, val, 1);
    return addSubNode(pNode, sub0);
}

Node *genNode2(int type, void *val, Node *sub0, Node *sub1) {
    Node *pNode = allocNode(type, val, 2);
    pNode = addSubNode(pNode, sub0);
    return addSubNode(pNode, sub1);
}

Node *genNode3(int type, void *val, Node *sub0, Node *sub1, Node *sub2) {
    Node *pNode = allocNode(type, val, 2);
    pNode = addSubNode(pNode, sub0);
    pNode = addSubNode(pNode, sub1);
    return addSubNode(pNode, sub2);
}

また、

Node *allocNode(int type, void *val, int nSub, int size);
として、サイズだけでなく、初期ノード数を引数で指定し、genNode関数では
Node *genNode(int type, void *val, int nSub, Node *sub0, ...);
のように、子ノードポインタ引数の末尾を NULL とする代わりに、 子ノード数を引数で与えると、genNode関数が少し簡単になる。

下に、変更後のプログラムを示す。

Node *allocNode(int type, void *val, int nSub, int size) {
    Node node = { type, val, nSub, size };
    Node *pNode = malloc(sizeof(Node) + size*sizeof(Node*));
    if (pNode == NULL) error("allocNode: メモリ確保に失敗しました. size=%d", size);
    return memcpy(pNode, &node, sizeof(Node));
}

Node *genNode(int type, void *val, int nSub, ...) {
    Node **pSub = (Node**)((char*)&nSub + sizeof(Node*)); // 第4引数以降を配列としてとらえる.
    Node *pNode = allocNode(type, val, nSub, nSub);
    if (nSub > 0) memcpy(pNode->sub, pSub, sizeof(Node*) * nSub);
    return pNode;
}