OpeLa AST Strutures

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）によって変わります。種類別の仕様を以下に示します。

kind の値	ノード種別	type	lhs	rhs	cond	value
kInt	整数リテラル	int64				整数値
kAdd	2項演算子 +	M(L,R)	Expr	Expr
kSub	2項演算子 -	M(L,R)	Expr	Expr
kMul	2項演算子 *	M(L,R)	Expr	Expr
kDiv	2項演算子 /	M(L,R)	Expr	Expr
kEqu	2項演算子 ==	bool	Expr	Expr
kNEqu	2項演算子 !=	bool	Expr	Expr
kGT	2項演算子 >	bool	Expr	Expr
kLE	2項演算子 <=	bool	Expr	Expr
kBlock	複文
kId	識別子（変数、関数、型）	T				Object*
kDefVar	変数定義	T	kId	Expr
kDefFunc	関数定義		kBlock	kParam	kType
kRet	return 文	L	Expr
kIf	if 文		kBlock	kBlock	Expr
kAssign	2項演算子 =	L	Expr	Expr
kLoop	無限ループ		kBlock
kFor	条件付きループ		kBlock		Expr
kCall	関数呼び出し演算子 ( )	L.base	Expr	Expr
kStr	文字列リテラル	[]uint8				文字列
kExtern	extern 宣言	T	kType		kStr
kType	型指定子	T
kParam	関数の仮引数	L	kType			Object*
kVParam	可変長仮引数 ...
kSizeof	1項演算子 sizeof	int64	Expr
kTypedef	型宣言		kType
kCast	2項演算子 @	R	Expr	kType
kAddr	1項演算子 &	*L	Expr
kDeref	1項演算子 *	L.base	Expr
kSubscr	添え字演算子 []	L.base	Expr	Expr
kChar	文字リテラル	uint8				文字コード
kLAnd	2項演算子 &&	bool	Expr	Expr
kLOr	2項演算子	bool	Expr	Expr
kBreak	break キーワード
kCont	continue キーワード
kInc	後置演算子 ++	L	Expr
kDec	後置演算子 --	L	Expr
kInitList	初期値リスト {e1, e2, ...}	{T}	Expr
kDot	構造体アクセス演算子	T	Expr	kId
kArrow	構造体ポインタアクセス演算子	T	Expr	kId
kDefGFunc	ジェネリック関数の定義		kDefFunc	kId		TyedFuncMap*
kTList	パラメタ <T1, T2, ...>		kType

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

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 の意味が変わります。

kind の値	型種別	base	next	value
kUndefined	型という概念がない場合
kUnresolved	ある時点で未解決の型			型名
kInt	符号付き整数型			ビット幅
kUInt	符号無し整数型			ビット幅
kPointer	ポインタ型	指す先の型
kFunc	関数型	戻り値の型	引数リスト
kParam	仮引数など	引数の型	次の kParam	引数名
kVParam	可変長仮引数
kVoid	void型
kUser	ユーザ定義型	ベース型		型名
kBool	真理値型
kArray	配列型	要素の型		要素数
kInitList
kStruct	構造体型		フィールドリスト
kGParam	型変数			型変数名
kGeneric	ジェネリック型	ベース型
kConcrete	具体型	型パラメタ	型パラメタリスト

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 をたどるように実装します。再帰的データ型に対処するために、「過去にたどったことがある型」を記憶するなど、無限ループを防ぐ工夫が必要です。