tiny C 処理系のデータ構造

tiny Cの処理系で使われる基本的なデータ構造について説明する。 プログラムでは、

の2つのファイルに定義されている。

構文木(AST)のデータ構造

最初の講義で解説した通り、構文木は最も基本的なデータ構造である。 以下のように定義する。

AST.h 
typedef struct abstract_syntax_tree {
    enum code op;
    int val;
    struct symbol *sym;
    struct abstract_syntax_tree *left,*right;
} AST;
前に解説したASTのものとの違いは、シンボルについての定義が加わっている。 なお、valとsymとleft,rightは同時には使わないので、unionを使ってメモリ を節約することができる。

ASTの生成

ASTのノードを作る関数が、makeASTである。

AST.c 
AST *makeAST(enum code op,AST *left,AST *right)
{
    AST *p;
    p = (AST *)malloc(sizeof(AST));
    p->op = op;
    p->right = right;
    p->left = left;
    return p;
}
また、NUMの数の定数のASTノードを作る関数がmakeNumである。
AST.c 
AST *makeNum(int val)
{
    AST *p;
    p = (AST *)malloc(sizeof(AST));
    p->op = NUM;
    p->val = val;
    return p;
}

ASTのリスト

演算子の構文木は2分木であるが、いくつかの要素をならべて表現するリスト 構造があればいろいろと便利なことがある。そのために、ASTのopがLISTの場 合にリストとしてみなすことにする。

リストの生成は、makeASTを使って、マクロで定義してある。

AST.h 
#define makeList1(x1) makeAST(LIST,x1,NULL)
#define makeList2(x1,x2) makeAST(LIST,x1,makeAST(LIST,x2,NULL))
#define makeList3(x1,x2,x3) makeAST(LIST,x1,makeAST(LIST,x2,makeAST(LIST,x3,NULL)))
リストの最後に要素(AST)を加える関数が、addListである。
AST.c 
AST *addLast(AST *l,AST *p)
{
    AST *q;

    if(l == NULL) return makeAST(LIST,p,NULL);
    q = l;
    while(q->right != NULL) q = q->right;
    q->right = makeAST(LIST,p,NULL);
    return l;
}
最後を見付けて、LISTのASTノードを付け加える。

リストについてのアクセスは、n番目の要素を取り出すgetNthで行う。
AST.c 
AST *getNth(AST *p,int nth)
{
    if(p->op != LIST){
	fprintf(stderr,"bad access to list\n");
	exit(1);
    }
    if(nth > 0) return(getNth(p->right,nth-1));
    else return p->left;
}
これを使えば、1番目をとるのは、getFirstは以下のように定義できる。
AST.h 
#define getFirst(p) getNth(p,0)
また、関数getNextは、最初の要素をとったリストを返す。
AST.c 
AST *getNext(AST *p)
{
    if(p->op != LIST){
	fprintf(stderr,"bad access to list\n");
	exit(1);
    }
    else return p->right;
}
この関数はリストの要素を１つつづ、アクセスするのに用いる。 
AST *list,x;
for(list = ...; list != NULL; list = getNext(list)){
     x = getFirst(list); /* 要素の取り出し */
     xについての処理
}

コード

AST構造体のopに入るコードについては以下の通りである。
AST.h 
enum code {
    LIST,
    NUM,
    SYM,
    EQ_OP,
    PLUS_OP,
    MINUS_OP,
    MUL_OP,
    LT_OP,
    GT_OP,
    GET_ARRAY_OP,
    SET_ARRAY_OP,
    CALL_OP,
    PRINTLN_OP,
    IF_STATEMENT,
    BLOCK_STATEMENT,
    RETURN_STATEMENT,
    WHILE_STATEMENT,
    FOR_STATEMENT
};
PLUS_OP, MINUS_OPなどの演算子の他に、IF_STATEMENTなどの文のためのコー ドが定義しておく。 前は、#defineで定義したが、enumを使っておけば、デバックに便利である。

シンボル構造体とシンボルテーブル

シンボルは同じの名前のシンボルを１つのデータ構造で管理するもので、 以下の様に定義する。

AST.h 
typedef struct symbol {
    char *name;
    int val;
    AST *func_params;
    AST *func_body;
} Symbol;
この構造体を使って、シンボルテーブル、すなわち表にして管理する。
AST.c 
Symbol SymbolTable[MAX_SYMBOLS];
int n_symbols = 0;
同じ名前(識別子)は同じ構造体で管理するが、それを見付けるためにこのプロ グラムでは、単純サーチを使っている。大域変数n_symbolは、その数を数える 変数である。

関数lookupSymbolは、名前を引数にして、それに対応するシンボル構造体を返 す。もしも、名前のシンボルがなかったら、それに対するシンボルを作る。

AST.c 
Symbol *lookupSymbol(char *name)
{
    int i;
    Symbol *sp;

    sp = NULL;
    for(i = 0; i < n_symbols; i++){
	if(strcmp(SymbolTable[i].name,name) == 0){
	    sp = &SymbolTable[i];
	    break;
	}
    }
    if(sp == NULL){
	sp = &SymbolTable[n_symbols++];
	sp->name = strdup(name);
    }
    return sp;
}
シンボルを表すASTは、opがSYMで、symにシンボルへのポインタをいれたもの である。関数makeSymbolは名前を与えて、それに対応するASTを作る。
AST.c 
AST *makeSymbol(char *name)
{
    AST *p;

    p = (AST *)malloc(sizeof(AST));
    p->op = SYM;
    p->sym = lookupSymbol(name);
    return p;
}
逆に、シンボルのASTのノードから、シンボルを取り出すのが関数getSymbolで ある。
AST.c 
Symbol *getSymbol(AST *p)
{
    if(p->op != SYM){
	fprintf(stderr,"bad access to symbol\n");
	exit(1);
    }
    else return p->sym;
}