OpeLa メインページ

OpeLa Ver.2 の構文木データ構造

OpeLa コンパイラ Ver.2 が内部で用いる各種のデータ構造を詳しく説明します。 AST ノードを表す Node や型を表す Type などについて知りたい方はご覧ください。

データ構造の具体例

まずは hello.opl をコンパイルする際のデータ構造を具体的に見てみます。hello.opl の中身は次の通りです。

func main() int {
  printf("hello, world\n");
}

extern "C" printf func(*byte, ...) int;

これをコンパイルする際、OpeLa コンパイラが内部で構築するデータ構造を可視化した図を次に示します。

まずは図の Node_0 に注目します。Node_n（n は整数）は struct Node 型の変数に対応します。

コンパイラ内部では、コンパイル処理を進める過程で動的に struct Node 型の変数を生成します（NewNode() 関数）。整数 n はこの変数に振った通し番号です。本質的にはポインタ値と同等ですが、ぱっと見の分かりやすさを向上するために連番に変換しています。

struct Node の定義は次の通りです。

struct Node {
  enum Kind {
    《中略》
  } kind;

  Token* token;
  Type* type;

  Node* lhs = nullptr;
  Node* rhs = nullptr;
  Node* cond = nullptr;
  Node* next = nullptr;

  std::variant<VariantDummyType, opela_type::Int, StringIndex, Object*,
               opela_type::Byte, TypedFunc*, TypedFuncMap*> value = {};
  int ershov = 0;
};

Node_n の楕円の 2 行目に kind と token を表示しています。Node_0 であれば、kind=kDefFunc、token=”main” ということになります。type、lhs、rhs、cond、next、value は、それぞれ有効な値を指している場合（null ではない場合）に、その値を矢印で示します。Node_0 からは type と rhs の矢印が出ておらず、この 2 つが null ということが分かります。

ershov はデータ構造の理解には不要な値ですので、図には表示していません。

Node_0 の value を説明します。3 行の情報からなるこの 楕円は struct Object を表します。kind=kFunc、id=”main”、linkage=kGlobal、bp_offset=-1 です。locals は今のところ図に出していません。

type が指す楕円は struct Type です。

Node の仕様リファレンス

struct Node の各フィールドの意味は、そのノードの種類（kind）によって変わります。種類別の仕様を以下に示します。

この中で、特筆すべき仕様は以下に詳述します。

next の用途

Node::next はいくつかの用途で使われます。主な用途について説明します。

宣言を繋ぐ next

プログラム全体は宣言（declaration）の列です。宣言の線形リストを next により構成します。 次のプログラムに対応する抽象構文木は

func main() int {
    return 1;
}
type A int;
func f() { }

下図の通りです。

文を繋ぐ next

複文を構成するステートメントの線形リストを構成します。 次のプログラムに対応する抽象構文木は

func main() int {
    a:=1;
    b:=2;
    if 1 {
        return a+b;
    }
}

下図の通りです。

文法では a:=1; や return a+b; は文（式文、expression statement）です。 しかし、OpeLa コンパイラ内部のデータ構造としては、kDefVar や kRet などの式（expression）として表現されることに注意してください。

仮引数を繋ぐ next

関数の仮引数もリストを形成するので next が使用されます。 次のプログラムに対応する抽象構文木は

func sum(a, b int) int { }

下図の通りです。

仮引数 a、b が next により接続されていることが分かります。 この仮引数リスト自体は、kDefFunc の rhs から接続されています。 ちなみに、kDefFunc の lhs は関数本体の複文 kBlock、cond は関数の戻り値型 kType を指します。

型のデータ構造

抽象構文木のデータ構造と並んで重要なのは型の構造でしょう。OpeLa コンパイラでは、型は struct Type で表します。構造体の定義は次の通りです。

struct Type {
  enum Kind {
    《中略》
  } kind;

  Type* base;
  Type* next;

  std::variant<long, Token*> value;
};

型の種類（kind）に応じて、base や next、value の意味が変わります。

kParam の用途

kParam は次に示す用途に使われます。

• 関数の仮引数
  • 仮引数を左から順に接続した線形リスト。kFunc の next から指される。
  • base: 仮引数の型
  • next: 次の仮引数（kParam）
  • value: 仮引数の名前
• 構造体のフィールド
  • フィールドを上から順に接続した線形リスト。kStruct の next から指される。
  • base: フィールドの型
  • next: 次のフィールド（kParam）
  • value: フィールドの名前
• 初期化リストのフィールド
  • 初期化リスト（{x,y,…}）の要素を接続した線形リスト。kInitList の next から指される。
  • base: 要素の型
  • next: 次の要素
  • value: null
• ジェネリクスの型パラメタ
  • ジェネリックな関数や構造体を具体化する際に使う型パラメタのリスト。kConcrete の next から指される。
  • base: 型パラメタ
  • next: 次の型パラメタ（kParam）
  • value: null

再帰的データ型

自分自身へのポインタを持つような型を再帰的データ型と呼びます。木構造を作る際などによく使います。OpeLa 言語はもちろん再帰的データ型をサポートしています。

次の再帰的データ型により生成される型を

type Node struct {
    v int;
    next *Node;
};

下図に示します。

kPointer の base が自分自身（kUser）を指しているのが再帰的データ型である証拠です。

再帰的データ型を取り扱う際は無限ループしないように注意が必要です。通常、型を処理するプログラムは、再帰的に base と next をたどるように実装します。再帰的データ型に対処するために、「過去にたどったことがある型」を記憶するなど、無限ループを防ぐ工夫が必要です。