言語処理系をつくろう（第6回）：変数を実装する

自作の言語処理系開発日記、第6回です。

これまでは四則演算など、電卓レベルの機能実装に取り組んでいましたが、いよいよ変数を扱えるようにしていきたいと思います。これでかなりプログラミング言語っぽくなるかも(・∀・)

今回は新しい仕組みを入れたりと、割と修正がごちゃごちゃしてしまったので、うまくまとめきれていません。ごめんなさい…。

変数の実装について

これまでは即値しか扱っていなかったので、「値が登場すればそれをスタックに積む」という単純な仕組みで事足りていました。しかし、変数を扱うためには、どこかに値を覚えておいて、それを読み書きする仕組みが必要になります。

まず、変数の保存場所ですが、今回はスタックを使います。ただ、変数自体をPush/Popするのではなく、スタックの先頭領域を変数置き場として間借りします（下図）。

「C言語のローカル変数はスタックにある」なんていう話を聞きますが、それとほぼ同等の仕組みです。読み書きについては、各変数のスタック中のアドレスに対して行うようにします。

実装してみる

トークナイザ

この処理系では、変数名のルールを以下のようにします。

• 開始文字がa~z, A~Z, _のいずれかであること
• 途中の文字はa~z, A~Z, 0~9, _のいずれかであること
• 他の予約語と一致しないこと

実装自体は難しくないので割愛します。「他の予約語と一致しないこと」というルールがあるので、変数は最後にトークナイズするように注意します。

構文解析器

今回は変数の宣言と代入を実現したいので、生成規則は以下のようにしました。

変数を表すidentという記号を定義して、exprという新しい生成規則を追加しました。これで、変数＝式という代入式を扱えるようになります。

実装としては、変数そのものを表すノード（ND_IDENT）と、代入を表すノード（ND_ASSIGN）の2つを新規に定義します。

// ノード関連の定義
typedef enum {
	ND_NUM,			// 数値
	ND_ADD,			// +
	ND_SUB,			// -
	ND_MUL,			// *
	ND_DIV,			// /
	ND_ASSIGN,		// =
	ND_IDENT,		// 識別子
} NodeKind;

あとは生成規則に従って解析処理を実装すればOK。ここまでは割と単純です。

コード生成器

コード生成に関しては、変数の扱いがややこしいです。というのも、変数は置き場所（式の左辺 or 右辺）や、前後の文脈次第でその意味が変わります。

例えば、num=1という式の場合、numは代入先として解釈されるので、その評価値はアドレスです。一方、ret = num+1という式の場合は、numの評価値はそれが保持する値になります。

いま現在の生成規則では、代入式の左辺に来たときだけ変数をアドレスとして解釈すれば良さそうです。それ以外は全て値として解釈します。

ここからは実装です。まず、変数を表す構造体を以下のように定義します。変数名とその長さに加え、その変数のスタック上での位置（アドレス相当）を持たせました。そして、同一変数に対しては同じアドレスでアクセスできるように、変数のリストも定義しておきます。

// 変数定義
typedef struct {
	char* name;		// 変数名
	int len;		// 名前長
	int	offset;		// データ格納先のオフセット
} Variable;

vector vars;

また、変数に対する読み書きを実現するために、新しい命令としてLOADとSTOREを定義します。LOADはメモリ（スタック中）からレジスタへの値コピー、STOREはその逆です。

typedef enum {
	OP_PUSH,		// Push（レジスタ値）
	OP_PUSH_I,		// Push（即値）
	OP_POP,			// Pop
	OP_ADD,			// 加算
	OP_SUB,			// 減算
	OP_MUL,			// 乗算
	OP_DIV,			// 除算
	OP_STORE,		// レジスタ→メモリへの書き込み
	OP_LOAD,		// メモリ→レジスタへの読み込み
} OP_CODE;

そして、代入と識別子に対するコード生成を抜き出すと以下のようになります。

case ND_ASSIGN:
	gen_var(node->left);
	gen(node->right);

	operations.push_back( Operation{ OP_POP, REG_GR1 } );
	operations.push_back( Operation{ OP_POP, REG_GR0 } );
	operations.push_back( Operation{ OP_STORE, REG_GR0, REG_GR1 } );
	operations.push_back( Operation{ OP_PUSH, REG_GR1 } );

	break;

case ND_IDENT:
	gen_var(node);

	operations.push_back( Operation{ OP_POP, REG_GR0 } );
	operations.push_back( Operation{ OP_LOAD, REG_GR1, REG_GR0 } );
	operations.push_back( Operation{ OP_PUSH, REG_GR1 } );

	break;

途中に登場するgen_varという関数は識別子ノード専用の関数です。そのノードが示す変数のアドレスをスタックに積みます。

それ以降は、代入式であればアドレスに対するSTORE、それ以外であればアドレスからの値のLOADという形で命令列を出力します。

実行系（仮想マシン）

最後に実行系ですが、今回はスタックを変数領域とそれ以外で分けることにしたので、その境目を示す値が必要です。そこで、その値をベースポインタという名前で扱うことにし、いまは固定でスタックの先頭から16個先としました。つまり、使える変数は最大で16個までです。

DWORD* bp;					// ベースポインタ
sp = &stack[16];

途中、解説をかなり端折ったところもありますが、これで変数を扱うことができるようになりました。まだまだ実装は粗いですが、これで1つのチェックポイントは通過できたかなと思います。

今回の実装は以下のコミットになります。コード全体はこちらをご覧くださいm(_ _)m

変数の実装（dd7ed9e）

次回以降は制御構文の実装を視野に機能を追加していく予定です。

ではでは