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

数値の読み込みを実装

ではでは

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

関連記事

Flutter プログラミング

2021/8/2

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

アプリ内で独自の設定を作る場合、そのデータを保持する方法を考える必要があります。 SQL、テキストファイルなど選択肢は多々ありますが、shared_preferencesというパッケージを使えば簡単に実装することができます。 Dart packages  2 Users 40 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. ~備忘録のための技術ブログ~