トップC-Tips > 可変長配列[トークン配列]

可変長配列[トークン配列]

1.固定長配列

例えば、コンパイラにおける字句解析結果であるトークン列は下に示すように、固定長配列で管理するのが一番簡単である。 しかし、そのサイズ(NTOKEN)の決め方が問題である。 大きくとりすぎると小さなプログラムのコンパイラでは無駄が多く、 NTOKENの値が小さい場合、大きなプログラムのコンパイルが出来ない。

C言語では可変長配列をサポートしていないが、多くのプログラミング言語が可変長配列をサポートしている。 リスト構造(チェイン)で実装する方法もあるが、配列構造で実装する場合には、 最初は比較的小さい配列領域を確保しておき、足りなくなったとき、領域を例えば2倍に拡張する。 これを繰り返すことにより、任意のサイズに対応できる。

typedef struct {
    char    *str;       // トークン文字列
    // 各種情報は省略
} Token;

#define   NTOKEN        100000

Token tokens[NTOKEN];   // トークン配列
int   nToken;           // トークン数

//============= 初期化 =============//
    nToken = 0;

//========== 字句解析処理 ==========//
    Token *pTk = tokens[nToken++];
    pTk->str = <トークン文字列>
    // その他の情報をセット

具体的には、次のようにすればよい。

typedef struct {
    char    *str;       // トークン文字列
    // 各種情報は省略
} Token;

Token *tokens;          // トークン配列(可変長)
int   size;             // 確保済みサイズ
int   nToken;           // トークン数


//============= 初期化 =============//
    nToken = 0;
    size = 100;         // 適当な値でよい
    tokens = malloc(sizeof(Token)*size);
    if (tokens == NULL) {
        fprintf(stderr, "メモリが確保できませんでした");
        exit(1);
    }

//========== 字句解析処理 ==========//
    if (nToken >= size) {
        size *= 2;
        tokens = realloc(tokens, sizeof(Token)*size);
        if (tokens == NULL) {
            fprintf(stderr, "メモリが確保できませんでした");
            exit(1);
        }
    }
    Token *pTk = &tokens[nToken++];
    pTk->str = <トークン文字列>
    // その他の情報をセット

//========== 終了処理 ==========//
    free(tokens);

2.テストプログラム

プログラム全体の動きを示すために、簡単な字句解析プログラムを下に示す。 可変長配列が主題のため、字句解析自体はスペース区切りの簡単なモデルとした。 実際のコンパイラの字句解析はもっと複雑な処理となる。

メモリ拡張の様子を示すために、最初のサイズは5個分という小さい値にしている。 実際のプログラムではもっと大きな値にすることが多い。

// array01.c
// 可変長配列テストプログラム 2014.12.26
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char    *str;       // トークン文字列
    // 各種情報は省略
} Token;

Token *tokens;          // トークン配列(可変長)
int   size;             // 確保済みサイズ
int   nToken;           // トークン数

// 字句解析
int lex(char *src) {
    char *p;

    //============= 初期化 =============//
    size = 5;         // 適当な値でよい
    tokens = malloc(sizeof(Token)*size);
    if (tokens == NULL) return 1;
    printf ("\t\tメモリ領域をトークン%d個分確保しました\n", size);

    //========== 字句解析処理 ==========//
    p = strtok(src, " ");       // 最初のトークンを切り出す
    for (nToken = 0; p != NULL; nToken++) {
        if (nToken >= size) {   // 満杯かチェックする。
            // 満杯の時、領域を広げる
            size *= 2;
            tokens = realloc(tokens, sizeof(Token)*size);
            if (tokens == NULL) return 1;
            printf ("\t\tメモリ領域をトークン%d個分に拡大しました\n", size);
        }

        Token *pTk = &tokens[nToken];
        pTk->str = p;   // トークン文字列を str 要素にセット
        // その他の情報をセット

        printf("%2d: %s\n", nToken+1, tokens[nToken].str);

        p = strtok(NULL, " ");  // 次のトークンを切り出す
    }

    return 0;   // 正常終了
}

int main() {
    int n;
    char src[] = "int main ( ) { printf ( \"1+2=%d\\n\" , 1 + 2 ) ; }";

    int rtn = lex(src);
    if (rtn == 1) {
        fprintf(stderr, "メモリが確保できませんでした");
    }

    //========== 終了処理 ==========//
    free(tokens);       // プログラム終了時での解放は省略できる
    return rtn;
}

このプログラムの実行結果を下に示す。最初に、5個分の配列領域が確保され、 6個目のトークンの登録の直前で10個分の領域に拡大され、 11個目のトークンの登録の直前で20個分の領域に拡大されている。

                メモリ領域をトークン5個分確保しました
 1: int
 2: main
 3: (
 4: )
 5: {
                メモリ領域をトークン10個分に拡大しました
 6: printf
 7: (
 8: "1+2=%d\n"
 9: ,
10: 1
                メモリ領域をトークン20個分に拡大しました
11: +
12: 2
13: )
14: ;
15: }

以上のように、トークン配列への登録処理は固定長配列より少し面倒になるが、 構文解析フェーズ以降でトークン配列を参照するプログラムは何ら修正は要らず、 固定長配列の場合と全く同じである。このため、全体的にはそれほど大きな負担とはならない。

コンパイラではトークン配列の他に、多くの配列が使用されるため、 可変長配列の基本処理は共通化する。 従って、プログラム行数の増加は全体的には、ごくわずかな比率に過ぎない。