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

抽象構文木(3)

簡単な(言語仕様が限定された)プログラムを対象として、抽象構文木を生成する。

1.基本方針

コンパイラ全体では数多くの変数、定数、構造体を定義することになる。 この数の多さがプログラムの理解を難しくするので、なるべく使用数を減らしたい。

2.演算子、変数名等の識別番号

1文字および2文字の演算子(記号)には名前をつけない。 1文字の場合、ASCIIコードをその演算子の識別番号とする。 例えば、'+', '=' の ASCIIコードは 0x2B, 0x3D であり、これを識別番号とする。 2文字演算子 "+=" の識別番号を 0x3D2B とする。 2文字演算子 "+=" の識別番号は次の簡単な関数により算出できる。

 int op2(char *s) { return *((short*)s); }

関数コールのオーバヘッドが問題になる場合には、次のようなマクロを使えばいい。

  #define OP2(s)  (*((short*)s))

if, for など予約語や変数名、関数名などの識別番号は 0x10000 の値とする。 3文字記号 "..." や 演算子 "<<=" などには予約語と同様に、名前を付ける。 識別番号は 0xFFFF までの空き番号を割り当てるか、または、 変数名などと同じルールで識別番号を割り当てればよい。

3.抽象構文木の生成

C言語では、変数宣言ひとつをとっても、次のように、複雑な記述が可能である。

  int n = 0, *pData, data[] = { 23, -1, 2 };

抽象構文木は字句解析に使うものであり、元の形を保存する必要はない。 上の変数宣言文は、次の3文と等価である。 仮に、上の1文を忠実に木構造で表現しても、意味解析は簡単ではない。 下のように、3文に分けた方が構文木の定義も簡単となり、意味解析も楽になる。

  int n = 0;
  int *pData;
  int data[] = { 23, -1, 2 };

抽象構文木は、極力、構文規則のみから生成し、意味規則に依存する部分を最小に留めなければならない。

初期値部を除き、変数宣言は変数表に登録するものである。従って、その全体を一つのノードとした方がいい。 例えば、次のような木構造とする。 ここで一つのノードを (ノードタイプ 子ノード1 子ノード2 ・・・ 子ノードN) で表す。

配列宣言で要素数を省略した場合、右辺の初期化子の数を数えて、求める。 この例では int data[3] である。これを (VARDECL data int [3]) で表す。

( = (VARDECL  n int) (CONST 0) )
(VARDECL pData int *)
( = (VARDECL data int [3]) ({} (CONST 23) (CONST -1) (CONST 2)) )

この例では、初期化付き変数宣言を代入文としているが、通常の代入文 n = 0; は ( = (VAR n) (CONST 0) ) である。

typedef struct _Node {
    int type;                // ノード種別
    int length;        	     // 子ノード数
    void *childs[1];         // 子ノード可変長配列
} Node;
typedef struct _Variable {   //   例:        int *data[2][5][10]
    int type;                           // アイテム種別        VARDECL
    int name;                           // 名前                data
    int datatype;                       // データ型            int
    int pointers;                       // * の数              1
    int dimension;                      // 次元数              3
    int sizes[1];                       // 要素数可変長配列    { 10, 5, 2 }
} Variable;

typedef struct _Variable { 
    int type;                // アイテム種別        VARIABLE
    int name;                // 名前
} Variable;

typedef struct _Constant { 
    int type;                // アイテム種別        CONSTANT
    char *value;             // 値(数値も文字列表現)
} Constant;