プログラミング言語開発記Ⅱ - 字句解析

冗談抜きに多忙でしばらく開発がストップしていました。失踪なんてしていません。しませんよ。

1記事目はざっくりとした概要しか書けなかったので、そろそろ具体的な処理にも言及していきます。ちなみに、もう気付いてくれた方もいるかもしれませんが今回から文体がですます調です。公式記事ではなく個人ブログならもっと軽く適当に書いてもいいかなと考え直したので。

一般的にプログラミング言語の処理系がどういった流れで処理しているのかについてはあまり詳しくないのですが、大体これは王道が決まっているかと思います。Laiskは次のような流れです。

Laiskソースコード（string）
↓
↓　＜　字句解析（トークンへの切り分け・トークン種別の判定）
↓
トークン列（vector<token>）
↓
↓　＜　構文解析①（操車場アルゴリズムの応用）
↓
トークン列（vector<token>）
↓
↓　＜　構文解析②（構文木の構築）
↓
構文木（node）
↓
↓　＜　書き下し（深さ優先探索のような何か）
↓
C++ソースコード（string）

この記事では最初の処理である、字句解析について述べます。

今回私が実装した字句解析関数 vector<token> lex(string code) とその補助関数がこんな感じ。
ちなみに、pair<int,string> をtypetokenとしてtypedefしています。first要素がトークン種別（マクロ定数）、second要素が実体の文字列です。

// define types of characters
string bracket_open = "({";
string bracket_close = ")}";
string separator = " ;,\n";
string quotation = "\"\'";
string myoperator = "=+-*/%~";
string number = "0123456789.";
string name_part = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_";

int char_type(char c) { // character -> character type
	if (name_part.find(c) != string::npos) {
		return NAME_PART;
	}
	else if (separator.find(c) != string::npos) {
		return SEPARATOR;
	}
	else if (quotation.find(c) != string::npos) {
		return QUOTATION;
	}
	else if (bracket_open.find(c) != string::npos) {
		return BRACKET_OPEN;
	}
	else if (bracket_close.find(c) != string::npos) {
		return BRACKET_CLOSE;
	}
	else if (number.find(c) != string::npos) {
		return NUMBER;
	}
	else {
		return OPERATOR;
	}
};

map<int, int> char_to_token = // character type -> token type
{
	{NAME_PART,T_NAME},
	{OPERATOR,T_OPERATOR},
	{QUOTATION,T_STRING},
	{BRACKET_OPEN,T_BRACKET_OPEN},
	{BRACKET_CLOSE,T_BRACKET_CLOSE},
	{SEPARATOR,T_SEPARATOR},
	{NUMBER,T_VALUE}
};


vector<typetoken> lex(string code) { // lexical analyze
	int state = T_INITIAL;
	vector<typetoken> result;
	string token = "";
	for (int i = 0; i < code.size(); i++) {
		char c = code[i];
		char type = char_type(c);
		switch (state) {
		case T_INITIAL:
			token += c;
			state = char_to_token[type];
			break;
		case T_NAME:
			switch (type) {
			case NAME_PART:
			case NUMBER:
				token += c;
				break;
			default:
				result.push_back(typetoken(state, token));
				token = c;
				state = char_to_token[type];
				break;
			}
			break;
		case T_STRING:
			switch (type) {
			case QUOTATION:
				token += c;
				result.push_back(typetoken(state, token));
				token = "";
				state = T_INITIAL;
				break;
			default:
				token += c;
				break;
			}
			break;
		case T_VALUE:
			switch (type) {
			case NUMBER:
				token += c;
				break;
			default:
				result.push_back(typetoken(state, token));
				token = c;
				state = char_to_token[type];
				break;
			}
			break;
		case T_OPERATOR:
			switch (type) {
			case OPERATOR:
				token += c;
				break;
			default:
				result.push_back(typetoken(state, token));
				token = c;
				state = char_to_token[type];
				break;
			}
			break;
		default:
			result.push_back(typetoken(state, token));
			token = c;
			state = char_to_token[type];
			break;
		}
	}
	return result;
}

lex関数が処理中で内部的に保持するのは、最終的に出力するトークン列（result）、作成途中のトークン（token）、作成しているトークンの状態（state）のみです。

tokenは空文字列、stateはINITIALの状態から順番にコードのi文字目cを受け取り、stateとcの文字種別に応じて処理を変えながらresultに放り込んでいくだけです。

例えば、b=getint+2; というコードを受け取ったとすると

①stateはT_INITIAL、1文字目の'b'はNAME文字なのでtokenは"b"、stateはT_NAMEへ遷移
②stateはT_NAME、2文字目の'='はOPERATOR文字なので保持しているtoken（"b"）をresultにpushしてtokenは"="に、stateはT_OPERATORに遷移
③stateはT_OPERATOR、3文字目の'g'はNAME文字なので保持しているtoken（"="）をresultにpushしてtokenは"g"に、stateはT_NAMEに遷移
④stateはT_NAME、4文字目の'e'はNAME文字なので保持しているtoken（"g"）に'e'を追加してtokenは"ge"に遷移
⑤stateはT_NAME、5文字目の't'はNAME文字なので保持しているtoken（"ge"）に't'を追加してtokenは"get"に遷移
……
同様に続く
……
⑥stateはT_NAME、9文字目の'+'はOPERATOR文字なので保持しているtoken（"getint"）をresultにpushしてtokenは"+"に、stateはT_OPERATORに遷移
⑦stateはT_OPERATOR、10文字目の'2'はNUMBER文字なので保持しているtoken（"="）をresultにpushしてtokenは"2"に、stateはT_VALUEに遷移
⑧stateはT_VALUE、11文字目の';'はSEPARATOR文字なので保持しているtoken（"2"）をresultにpushしてtokenは""に、stateはT_SEPARATORに遷移

といった具合で切り分けられます。
少し考えればわかりますが、このままのコードでは例えば"a=++b"のようなコードがうまく分解できません。OPERATOR文字が続いていれば一塊として捉えてしまうのです。今回はあくまで雛形を示しているので気にしないことにします。

定数等をまとめているconstants.cppも一応示します。

#include<fstream>
#include<iostream>
#include<map>
#include<sstream>
#include<stack>
#include<string>
#include<vector>
#define T_INITIAL 0
#define T_NAME 1
#define T_STRING 2
#define T_VALUE 3
#define T_BRACKET_OPEN 4
#define T_BRACKET_CLOSE 5
#define T_SEPARATOR 6
#define T_OPERATOR 7
#define NAME_PART 0
#define OPERATOR 1
#define QUOTATION 2
#define BRACKET_OPEN 3
#define BRACKET_CLOSE 4
#define SEPARATOR 5
#define NUMBER 6

using namespace std;

typedef pair<int, string> typetoken;

マクロ定数以外にもいろいろ突っ込んでて相当お行儀が悪いですね。

lexを動作させる例がこんな感じ。

#include "constants.cpp"
#include "lex.cpp"

int main(int argc, char** argv) {
	ifstream ifs(argv[1]);
	stringstream strs;
	strs << ifs.rdbuf();
	string code(strs.str()); // read Laisk source code
	vector<typetoken> tokens = lex(code); // lexical analyze
	for (typetoken tok : tokens) {
		cout << tok.second << " "; // show result of lex
	}
	cout << endl;
}

これに、例えば次のようなファイルを与えると

n=getint;b=getints(n);put(max(b)*2);

次のように空白で切り分けて出力され、めでたく字句解析が出来ました。

n = getint ; b = getints ( n ) ; put ( max ( b ) * 2 )

実用上はこのままではとても動かせませんが大まかに実装したアルゴリズムの説明ということで。本当は構文解析も大体出来てるんですけど今回はこれくらいにします。