C++ 自作物

言語処理系をつくろう(第1回):数値を読み込む

前回からはじめた自作の言語処理系開発日記の第1回目です。今回から実際のコードを書いていきたいと思います。

前回の記事でも紹介したとおり、全体の構成は以下のような感じです。

今回は、それぞれの仕組みの骨格と簡単な機能の実装を進めていくことにします。

今回の目標

はじめの1歩として実装するのは、数値の読み込みです。1つの数字を読み込んでそれを実行結果とするだけの機能を実装します。機能としてはシンプルですが、中身自体はしっかりトークナイズ→構文解析→命令生成→実行の流れを踏みます。

ちなみにですが、リポジトリ名は「rook」としました。私のGitHubのアイコンにもしている愛犬の名前です笑

実装してみる

トークナイザ

まずは入力文字列をトークンに分解するトークナイザです。最初にトークンを以下のような構造体で定義します。

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

typedef struct {
	TokenKind kind;	// トークン種別
	char *str;		// トークン文字列
	int len;		// トークン長
} Token;

トークンはその意味や役割に応じて種類が分かれるので、トークン種別(kind)を持たせます。現時点では数値の入力しか考えないので「数値トークン」のみです。strは入力文字列に対するトークンの開始位置、lenはその長さです。

トークナイズ本体の処理は以下のような感じです。欲しいのはトークン列なので、Tokenvectorとして結果を返します(とはいえ、いまは1つのトークンだけ)。ここでも現時点では数値だけを読み取れれば良いので、数字以外はすべてエラー扱いです。

vector<Token> Tokenizer::tokenize(char* input)
{
	vector<Token> tokens;

	while(*input){
		if(isdigit(*input)){
			Token token = { TK_NUM, input, 0 };
			for(; isdigit(*input); input++) token.len++;
			tokens.push_back(token);
		}
		else{
			cerr << "Invalid character : " << *input << endl;
			exit(1);
		}
	}

	tokens.push_back( Token{ TK_EOF, NULL, 0 } );

	return tokens;
};

構文解析器

続いて構文解析器です。ここでは実装の前に、この言語処理系の構文を決めます。構文定義にはBNF記法というものが使われますが、厳密な書き方は特に気にしません。実装に落とし込める形であれば何でもOKとします。

今回は「1つの数字を読み込む」だけなので、現時点での構文は「数値1つだけ」となります。これを表現してみるとこんな感じになります。

program = num

programは入力ソースそのもの、numは数値を表します。つまり「入力ソースは数値である」となります。このようなものを生成規則と呼んだりするそうです。

実装ですが、まずは構文解析の結果を表現するためのノードを定義します。

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

typedef struct Node Node;

struct Node {
	NodeKind kind;	// トークン種別
	Node *left;		// 左辺
	Node *right;	// 右辺
	int val;		// ND_NUMのときに使う
};

ここでもノードの種類を定義していますが、現時点では数値だけです。木構造を表現するために、左木(left)と右木(right)を持たせます。また、数値も1つのノードとして扱う必要があるので、その値(val)も用意します。

続いて構文解析の処理ですが、ここではさきほど定義した構文に対応させる形で実装します。そのため、numというメソッドを実装し、それをprogramというメソッド内で呼び出すようにします。構文が複雑になってきても、この方法であれば比較的素直に実装に落とし込むことができ、再帰的に処理しやすくなるというメリットがあります。

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

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

Node* Parser::parse(vector<Token>& tokens)
{
	token = tokens.begin();
	return program();
};

コード生成器

お次はコード生成器です。ここでは、入力として構文解析の結果(Nodeの木)を受け取って実際の命令に変換します。

今回は「数値を受け取ってそれを実行結果とする」という処理が実現できればOKですが、作成する処理系は「実行結果=スタック」のトップなので、「数値をスタックに積む」という命令1つで事足ります。

まず、命令については以下のような構造体で表現します。本来の命令はバイナリ列ですが、ここでは簡単のためにこうしました。

// 命令関連の定義
typedef enum {
	OP_PUSH,		// Push
} OP_CODE;

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

命令の種類はPUSHだけ、命令の中身もオペコード+オペランドだけです。これを使ってコード生成の処理を書くとこんな感じになります。最終的な出力は命令列(Operationvector)です。

vector<Operation> Generator::codegen(Node* node)
{
	switch(node->kind){
		case ND_NUM:
			operations.push_back( Operation{ OP_PUSH, node->val } );
			break;
		default:
			break;
	}

	return operations;
};

ここでも、現時点では数値1つ(ノードが1つだけ)しか入ってこない想定なので、左右の木の存在は気にしていません。

仮想マシン(実行系)

最後に仮想マシンです。今回はスタックマシンとして実装するので、内部的にスタック用のメモリと、スタックトップを示すポインタ1つを用意しておきます。

DWORD stack[STACK_SIZE];	// スタック
DWORD *sp;					// スタックポインタ

あとは、入力された命令列を読みながら、各命令に対応した処理を行うだけです。

DWORD VM::run(vector<Operation>& code)
{
	vector<Operation>::iterator op = code.begin();

	while(op != code.end()){
		switch(op->opcode){
			case OP_PUSH:
			{
				push(op->operand);
				break;
			}
			default:
				break;
		}
		op++;
	}

	// スタックトップの値を実行結果とする
	return pop();
};

一応、これで数値を読み込んでそれを実行結果とする処理系が実装できました。現時点では言語処理系と言い張るのは無理がありますが、ここから少しづつ育てていきたいと思います。

実装コード全体

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

数値の読み込みを実装

ではでは

関連記事

C言語 自作物 Linux プログラミング

wordleもどきのCUIアプリをつくってみた

最近、wordleという英単語当てゲームで遊んでいます。シンプルなゲームながら、通勤時間の暇つぶしや友人とのスコア比べなど意外と中毒性があり面白いです。 普通に英単語の勉強にもなるので、もっとたくさん ...

RaspberryPi Linux

Raspberry Pi4+Ubuntu ServerでGitLabを動かしてみる

お仕事でGitLabに触れる機会があったので、学習用に自宅にもGitLabが欲しくなりました。 手元にあるRaspberry Pi4+Dockerならお手軽に立ち上げられるはずと着手したものの、意外と ...

Flutter プログラミング

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

アプリ内で独自の設定を作る場合、そのデータを保持する方法を考える必要があります。 SQL、テキストファイルなど選択肢は多々ありますが、shared_preferencesというパッケージを使えば簡単に ...

RaspberryPi Linux

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

昨今、様々なデバイスでLinuxが動くようになっている中、組み込みLinuxのデファクトスタンダードとなりつつあるのが「Yocto」と呼ばれるビルドシステムです。 組み込みの現場ではその名前を聞くこと ...

C++ 自作物

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

自作の言語処理系開発日記の第7回です。前回までで変数の実装が終わったので、ここからはいよいよ制御構文を実装…と思ったのですが、制御のためには比較演算子を実装する必要がありました。 ということで、今回は ...

Ryo Yoneyama

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

    -C++, 自作物