自作の言語処理系開発日記の第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（っぽいもの）を使って書くとこんな感じです。
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
ではでは
