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 を指します。