C++ 自作物

言語処理系をつくろう(第2回):加減算を実装する

自作の言語処理系開発日記の第2回です。前回は処理系全体の骨格と、数値の読み込みを実装しました。今回は次のステップとして、加減算を扱えるようにしたいと思います。

実装してみる

トークナイザ

前回までのトークナイザでは数値しか扱うことができないので、「+」や「-」などの記号をトークン化できるようにします。

まずは、トークン定義を追加します。加算と減算それぞれで追加しても良いのですが、後段の構文解析で特に区別する必要がないので、演算子という形で一括りにします。

// トークン関連の定義
typedef enum {
	TK_NUM,			// 数値
	TK_OP,			// 演算子
	TK_EOF,			// 終端
} TokenKind;

続いて、トークナイズの実処理です。「+」や「-」などの記号を見つけたらそこでトークン化するだけなので、以下のようなコードを追加します。

if(strncmp(input, "+", 1) == 0){
	Token token = { TK_OP, input, 1 };
	tokens.push_back(token);
	input++;
}

構文解析器

次は構文解析です。ここも前回は数値1つだけでしたが、今回は左辺と右辺を持った木構造を作る必要があります。

まずは、加減算を考慮した生成規則を考えます。BNF(っぽいもの)を使って書くとこんな感じです。

program = add
add = num ("+" num | "-" num)*

今回は新たにaddという規則を追加しました。定義の中に出てくるは「OR」の意味、は0回以上の繰り返しの意味です。加減算を含む式は、「数値+数値」か「数値-数値」が連続している形になるので、この定義で表現できることになります。

このあたりの考え方は、私が参考にしているオンラインブック「低レイヤを知りたい人のためのCコンパイラ作成入門」がとてもわかりやすいので、ぜひ読んでみてください。

生成規則が定義できたら、それに従ってトークン列をパースする処理を実装します。まずはノードとして、加算・減算それぞれの定義を追加します。

// ノード関連の定義
typedef enum {
	ND_NUM,			// 数値
	ND_ADD,			// +
	ND_SUB,			// -
} NodeKind;

続いてパース処理です。前回同様、生成規則をそのまま落とし込む形で実装します。

Node* Parser::program(void)
{
	return add();
};

Node* Parser::num(void)
{
	Node* node = new Node();
	node->kind = ND_NUM;
	node->val = atoi(token->str);
	token++;
	return node;
};

Node* Parser::add(void)
{
	Node* node = num();

	while(1){
		if(consume("+")){
			node = new Node{ ND_ADD, node, num() };
		}
		else if(consume("-")){
			node = new Node{ ND_SUB, node, num() };
		}
		else{
			return node;
		}
	}
};

正直なところ、ここも先述したオンラインブックの実装を参考(というか、ほぼ丸パクリ)にしました。

どうしてこの実装で構文木が作れるのかしばらく分からなかったのですが、「左結合=左の枝が深くなっていくように木を伸ばす」という視点で見たら、なんとなく納得がいきました。う〜ん、難しい…。

コード生成器+実行系(仮想マシン)

次はコード生成と実行系(仮想マシン)です。スタックマシンにおいて加減算は、

  • スタックの上から2つ値を取り出す(ポップする)
  • 取り出した値を加算・減算した結果をスタックに積む

という流れで処理されます。前回まではスタックに積む(プッシュ)しか実装していないので、ポップ・加算・減算の3つを新規に実装する必要があります。

まず、仮想マシンに新しい仕組みを実装します。先述したように、加減算は「スタックからデータを取り出す」という処理が入るので、取り出した値を記憶する仕組みが必要です。

実際のCPUでは、こうした用途のために汎用レジスタというものがあります。そこで、今回は仮想マシンに汎用レジスタを実装します。いまのところ、加減算の左辺用と右辺用の2つがあれば良いので、以下のようなレジスタ定義を追加しておきます。

// レジスタ関連定義
typedef enum {
	REG_GR0 = 0,
	REG_GR1,
	REG_NUM,		// レジスタ数
} REG_NAME;

そして、仮想マシン内に汎用レジスタとして使える領域を実装すれば準備OKです。

DWORD reg[REG_NUM];	// レジスタ

続いて命令まわりです。命令定義の追加に加えて、命令そのものに第2のオペランドを追加します。加減算の右辺値を指定するためです。

// 命令関連の定義
typedef enum {
	OP_PUSH,		// Push
	OP_POP,			// Pop
	OP_ADD,			// 加算
	OP_SUB,			// 減算
} OP_CODE;

typedef struct {
	BYTE opcode;	// オペコード
	DWORD operand;	// オペランド
	DWORD operand2;	// 第2オペランド
} Operation;

これを踏まえての命令生成処理ですが、加算の場合は以下のような実装を追加すればOKです。

case ND_ADD:
	codegen(node->left);
	codegen(node->right);

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

	break;

ノードの左辺値と右辺値を先に展開することがポイントです。こうすることで、実行時にスタックに左辺値と右辺値の評価結果が積まれている状態にできるので、あとはポップ命令と加算命令を出力すればOKです。

最後に仮想マシン内で、追加した命令に対する実処理を実装します。例えば、加算は以下のような感じです。オペランドで指定された2つのレジスタを足してスタックに積みます。

case OP_ADD:
{
	push(reg[op->operand] + reg[op->operand2]);
	break;
}

これで加減算を処理できるようになりました。ちょっとは言語処理系っぽくなったかなと思います。

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

加減算を実装(5be1d97)

ではでは

広告の表示がブロックされています。
広告の表示がブロックされています。

関連記事

Flutter プログラミング

2021/8/2

【Flutter】アプリ内の設定値を実装する方法

アプリ内で独自の設定を作る場合、そのデータを保持する方法を考える必要があります。 SQL、テキストファイルなど選択肢は多々ありますが、shared_preferencesというパッケージを使えば簡単に実装することができます。 Dart packages  1 User 29 Pocketsshared_preferences | Flutter PackageFlutter plugin for reading and writing simple key-value pairs. Wraps ...

この記事を読む

RaspberryPi Linux

2021/4/18

YoctoでRaspberryPi4のイメージをビルドしてみた

昨今、様々なデバイスでLinuxが動くようになっている中、組み込みLinuxのデファクトスタンダードとなりつつあるのが「Yocto」と呼ばれるビルドシステムです。 組み込みの現場ではその名前を聞くことが増えましたが、まだまだ日本ではドキュメントも乏しくイマイチ掴み所がありません。そこで、まずは使ってみようということでRaspberry Pi4のイメージをビルドしてみることにしました。 目次1 Yoctoとは?2 Raspberry Pi4のイメージを作ってみる2.1 下準備2.2 Yocto本体+ラズパイ ...

この記事を読む

C++ 自作物

2021/8/1

言語処理系をつくろう(第7回):比較演算子を実装する

自作の言語処理系開発日記の第7回です。前回までで変数の実装が終わったので、ここからはいよいよ制御構文を実装…と思ったのですが、制御のためには比較演算子を実装する必要がありました。 ということで、今回は比較演算子を実装していきます。基本的には四則演算と変わりないのであまり難しくはありません。 目次1 比較演算子の仕様2 実装してみる2.1 トークナイザ2.2 構文解析器2.3 コード生成器2.4 実行系(仮想マシン) 比較演算子の仕様 比較演算子を実装する前に、その仕様について少し考えておきます。 比較演算 ...

この記事を読む

C++ 自作物

2021/8/1

言語処理系をつくろう(第6回):変数を実装する

自作の言語処理系開発日記、第6回です。 これまでは四則演算など、電卓レベルの機能実装に取り組んでいましたが、いよいよ変数を扱えるようにしていきたいと思います。これでかなりプログラミング言語っぽくなるかも(・∀・) 今回は新しい仕組みを入れたりと、割と修正がごちゃごちゃしてしまったので、うまくまとめきれていません。ごめんなさい…。 目次1 変数の実装について2 実装してみる2.1 トークナイザ2.2 構文解析器2.3 コード生成器2.4 実行系(仮想マシン) 変数の実装について これまでは即値しか扱っていな ...

この記事を読む

C++ 自作物

2021/8/1

言語処理系をつくろう(第5回):連続した式の実行

自作の言語処理系開発日記の第5回です。 前回までで括弧を含んだ四則演算ができるようになりましたが、このままでは単なる電卓止まりです。ということで、今回は複数の式を連続して実行できる仕組みを実装していきたいと思います。 目次1 生成規則を考える2 実装してみる2.1 構文解析器2.2 コード生成 生成規則を考える これまでは入力全体を1つの式として解釈していましたが、今回は式の区切りを定義して複数の式として解釈できるようにします。 C言語だと「;」や「,」が区切り文字として使われますが、開発中の言語(roo ...

この記事を読む

  • このブログの中の人

Ryo Yoneyama

とある会社でソフトウェアエンジニアをしています。技術的な備忘録を中心にまとめてます。ネタがあれば日記も書きます。

-C++, 自作物

© 2021 Corgi Lab. ~備忘録のための技術ブログ~