妹ちゃんの通う小学校
妹ちゃん「パーサーができたら次はコード生成器ね」
ワイ「なんかいろいろ難しいなぁ・・・」
妹ちゃん「そう？コード生成器はトークン順に中間コードを生成するだけだから、そんなでもないと思う。情報処理の授業でも習うし」
ワイ「！？妹ちゃんの通う学校って・・・」
今回のテーマ
-
コード生成器（ジェネレータ）の実装
- 中置記法から逆ポーランド記法（Reverse Polish Notation）に変換する処理の実装
- 仮想マシンの実装
コード生成器（ジェネレータ）とは
コード生成器（ジェネレータ）は、パーサーによってトークン化されたソースコードを順番に処理して中間コード（バイトコード）を出力するプログラムです。
具体的には、パーサーと同じくグローバルなステート（状態）を１つ用意して
- 状態を【開始状態】に設定
- トークンを１つ取得
- T_VARIABLE（変数）なら変数を変数テーブルに登録し【代入文】状態に遷移
- トークンをさらに１つ取得
- T_EQUAL（=）なら【式】状態に遷移
- トークンをさらに１つ取得
- T_EXPRESSION（式）ならトークン内容（数式）を逆ポーランド記法に変換
- 数式部を順にバイトコード生成（右辺）
- 代入文のバイトコード生成（左辺）
- 文の終端トークン、T_END_OF_STATEMENT(；)を読む
- 状態を【開始状態】に設定、１に戻る
- T_PRINT（print文）なら【print文】状態に遷移
- トークンをさらに１つ取得
- T_VARIABLE（変数）なら変数テーブルから変数IDを取得後、バイトコード生成
- 文の終端トークン、T_END_OF_STATEMENT(；)を読む
- 状態を【開始状態】に設定、１に戻る
- T_VARIABLE（変数）なら変数を変数テーブルに登録し【代入文】状態に遷移
- 不正なトークンがきた場合は文法エラーとする
のように処理します。
UMLのアクティビティ図で描くと以下のようになります。
変数テーブルとは
変数テーブルとは、現在のスコープ（今回はグローバルスコープしかありませんが）において有効な変数を登録するテーブルのことです。
コンパイラが変数テーブルで変数を管理することで、最終的なバイトコード列に変数名を含めなくてよくなります。
今回、変数テーブルは変数名→変数ID(整数)へのマップ（VariableTableクラス）という形で実装しています。
バイトコード
今回作成するVMで使用可能なバイトコードは以下となります。
表１ MikoVm2のバイトコード
| オペコード | オペランド | 説明 |
|---|---|---|
| PUSH | op1=整数値 | 指定した整数値をスタックにPush |
| PUSHV | op1=変数ID | 指定した変数の内容をスタックにPush |
| POPV | なし | スタックから値を１つPopして指定した変数にセット |
| ADD | なし | スタックから２つの値をポップして和を計算、結果をスタックにPush |
| SUB | なし | スタックから２つの値をポップして差を計算、結果をスタックにPush |
| MUL | なし | スタックから２つの値をポップして積を計算、結果をスタックにPush |
| DIV | なし | スタックから２つの値をポップして除算、結果をスタックにPush |
| op1=変数ID | 指定した変数の内容をコンソールに出力する |
CodeGeneratorクラス
CodeGeneratorクラスは、パーサーのパース結果（つまりトークン列）を入力としてバイトコード列を生成します。
T_EXPRESSION（数式）についてはその中身を中置記法から逆ポーランド記法に変換してからオペコード、オペランドを出力します。
逆ポーランド記法を用いる理由については、マインド・エンジンの全貌 ～第４回～ 仮想マシン3分クッキングその２に記載してあります。
それでは実際のCodeGeneratorのコードについてみていきましょう。
namespace MikoVm
{
/**
* 中間コード生成クラス
*/
class CodeGenerator
{
const int STATE_START = 0x0001; // 開始状態
const int STATE_ASSIGN = 0x0002; // 代入文
const int STATE_EXPRESSION = 0x0004; // 式
const int STATE_PRINT = 0x0008; // print文
const int STATE_BEFORE_END = 0x0010; // 文終端（；）の前
/**
* バイトコードを生成
*/
public static Bytecode[] GenerateCodes(Token[] tokens)
{
// 状態変数
int state = STATE_START;
// バイトコードバッファ
var bytecode_buffer = new List<Bytecode>();
// 変数テーブル
var var_tbl = new VariableTable();
// 代入先変数のID
int assign_var_id = 0;
// １トークンずつ処理
foreach (var tk in tokens)
{
// 状態毎の処理
if (state == STATE_START)
{
if (tk.TokenType == Token.EnumTokenType.T_VARIABLE)
{
// 【開始】状態のとき変数が来たら、変数を変数テーブルに登録して【代入文】状態に遷移
assign_var_id = var_tbl.RegisterVariable(tk.TokenString);
state = STATE_ASSIGN;
}
else if (tk.TokenType == Token.EnumTokenType.T_PRINT)
{
// 【開始】状態のときprint文が来たら、【print文】状態に遷移
state = STATE_PRINT;
}
else
{
throw new SyntaxError($"Syntax error found at token({tk})");
}
}
else if (state == STATE_ASSIGN)
{
if (tk.TokenType == Token.EnumTokenType.T_EQUAL)
{
// 【代入文】状態のときイコール（＝）が来たら、【式】状態に遷移
state = STATE_EXPRESSION;
}
else
{
throw new SyntaxError($"Syntax error found at token({tk})");
}
}
else if (state == STATE_EXPRESSION)
{
if (tk.TokenType == Token.EnumTokenType.T_EXPRESSION)
{
// 【式】状態のとき式トークン（四則演算子or数字）が来たら、逆ポーランド記法に変換してバイトコード化する
WriteExpressionCode(tk.TokenString, bytecode_buffer);
// 代入文を出力
var bc = new Bytecode(Bytecode.EnumOpecode.opcPOPV, assign_var_id);
bytecode_buffer.Add(bc);
// 【終端前】状態に遷移
state = STATE_BEFORE_END;
}
else
{
throw new SyntaxError($"Syntax error found at token({tk})");
}
}
else if (state == STATE_PRINT)
{
if (tk.TokenType == Token.EnumTokenType.T_VARIABLE)
{
// 【print文】状態のとき変数がきたら変数テーブルを検索してprint文のバイトコードを出力
int var_id = var_tbl.FindVariable(tk.TokenString);
var bc = new Bytecode(Bytecode.EnumOpecode.opcPRINT, var_id);
bytecode_buffer.Add(bc);
// 【終端前】状態に遷移
state = STATE_BEFORE_END;
}
else
{
throw new SyntaxError($"Syntax error found at token({tk})");
}
}
else if (state == STATE_BEFORE_END)
{
if (tk.TokenType == Token.EnumTokenType.T_END_OF_STATEMENT)
{
// 【開始】状態に遷移
state = STATE_START;
}
else
{
throw new SyntaxError($"Syntax error found at token({tk})");
}
}
}
return bytecode_buffer.ToArray();
}
}
}
GenerateCodesメソッドの中身は、トークンを１つずつ読み込んで状態遷移と文法の確認、そしてバイトコードの出力処理を行っています。
代入文、つまり「a = 3 + 1」のような文が来た場合は変数テーブルに変数を登録し、その変数ID（整数）をassign_var_idに保存します。
T_EQUAL(=)を経てT_EXPRESSION(式)が来ますので、逆ポーランド記法で計算した結果を変数に書き込みます。
次に、中置記法から逆ポーランド記法に変換するメソッドです。
namespace MikoVm
{
class CodeGenerator
{
...
private static void WriteExpressionCode(string expr, List<Bytecode> buffer)
{
// RPNクラスを使って数式を逆ポーランド記法に変換
List<string> rpn = RPN.Convert(expr);
// 逆ポーランド記法の順で処理
foreach(var e in rpn)
{
if (Regex.IsMatch(e, "^[0-9]+$"))
{
// 数値の場合はPush
var bc = new Bytecode(Bytecode.EnumOpecode.opcPUSH, Int32.Parse(e));
buffer.Add(bc);
}
else if (e == "+")
{
buffer.Add(new Bytecode(Bytecode.EnumOpecode.opcADD));
}
else if (e == "-")
{
buffer.Add(new Bytecode(Bytecode.EnumOpecode.opcSUB));
}
else if (e == "*")
{
buffer.Add(new Bytecode(Bytecode.EnumOpecode.opcMUL));
}
else if (e == "/")
{
buffer.Add(new Bytecode(Bytecode.EnumOpecode.opcDIV));
}
}
}
}
}
WriteExpressionCodeメソッド自体はRPNクラス（逆ポーランド記法変換クラス）が変換した字句のリストの順にバイトコードを出力するだけで、逆ポーランド記法への変換はRPNクラスで実装されています。
こちらの実装内容は、マインド・エンジンの全貌 ～第４回～ 仮想マシン3分クッキングその２の「中置記法→逆ポーランド記法への変換」で記述した変換方法をC#で実装したものになります。
CodeGeneratorクラスの使い方は
var tokens = Parser.Parse(src);
Bytecode[] codes = CodeGenerator.GenerateCodes(tokens);
のように、パーサーがパースした結果を渡すとバイトコードの配列を返します。
VMの実装
最後にVMですが、これは表１の内容に従ってオペコードを実行していくだけになります。
namespace MikoVm
{
/**
* 仮想マシン
*/
class MikoVM
{
// 変数テーブルのサイズ
const int VARTBLE_SIZE = 256;
/**
* バイトコードを実行
*/
public static void Run(Bytecode[] codes)
{
// 実行時変数テーブル
var var_tbl = new int[VARTBLE_SIZE];
// 実行時スタック
var stack = new Stack<int>();
foreach(var bc in codes)
{
switch (bc.Opecode)
{
case Bytecode.EnumOpecode.opcPUSH: // 指定した整数値をスタックにPush： オペランド(1)=>整数値
{
int data = bc.Operands[0];
stack.Push(data);
}
break;
case Bytecode.EnumOpecode.opcPUSHV: // 指定した変数の内容をスタックにPush： オペランド(1)=>変数ID
{
int data = var_tbl[bc.Operands[0]];
stack.Push(data);
}
break;
case Bytecode.EnumOpecode.opcPOPV: // スタックから値を１つPopして指定した変数にセット： オペランド(1)=>変数ID
{
if (stack.Count == 0)
{
throw new VmRuntimeError("Stack empty!");
}
var data = stack.Pop();
int var_id = bc.Operands[0];
var_tbl[var_id] = data;
}
break;
case Bytecode.EnumOpecode.opcADD: // スタックから２つの値をポップして和を計算、結果をスタックにPush： オペランドなし
{
if (stack.Count < 2)
{
throw new VmRuntimeError("Stack empty!");
}
var data1 = stack.Pop();
var data2 = stack.Pop();
stack.Push(data1 + data2);
}
break;
case Bytecode.EnumOpecode.opcSUB: // スタックから２つの値をポップして差を計算、結果をスタックにPush： オペランドなし
{
if (stack.Count < 2)
{
throw new VmRuntimeError("Stack empty!");
}
var data1 = stack.Pop();
var data2 = stack.Pop();
stack.Push(data2 - data1);
}
break;
case Bytecode.EnumOpecode.opcMUL: // スタックから２つの値をポップして積を計算、結果をスタックにPush： オペランドなし
{
if (stack.Count < 2)
{
throw new VmRuntimeError("Stack empty!");
}
var data1 = stack.Pop();
var data2 = stack.Pop();
stack.Push(data1 * data2);
}
break;
case Bytecode.EnumOpecode.opcDIV: // スタックから２つの値をポップして除算、結果をスタックにPush： オペランドなし
{
if (stack.Count < 2)
{
throw new VmRuntimeError("Stack empty!");
}
var data1 = stack.Pop();
var data2 = stack.Pop();
if (data1 == 0)
{
throw new VmRuntimeError("Divided by zero");
}
stack.Push(data2 / data1);
}
break;
case Bytecode.EnumOpecode.opcPRINT: // 指定した変数の内容をコンソールに出力する： オペランド(1)=>変数ID
{
int data = var_tbl[bc.Operands[0]];
Console.WriteLine(data);
}
break;
}
}
}
}
}
Runメソッドの最初でまず必要な実行時変数テーブルとスタックを用意しています。
実行時変数テーブルのサイズは固定長（256個）ですが、これはVMの制限というわけではなく実装をシンプルにするため限定してあります。
opcDIVとopcSUBの２オペコードだけ、スタックに乗っている順番と演算の順番が逆になりますので注意してください。
opcPRINTは単純にコンソールに文字を出力しています。
以上で、超シンプルな仮想マシンの実装ができました。
数式の変数対応とか、配列変数、クラスの実装など、足りない機能だらけですが、とりあえず独自のスクリプト言語のコンパイル＆実行環境を作る雰囲気だけでも味わってもらえれば光栄です。
全体のソースコードは以下の場所にあります。
Visual Studioで実際にビルド、実行してみたい方は、こちらからcloneしてみてください。
git clone git@github.com:ROBOmindProject/MikoVm2.git
まとめ
- コード生成器（ジェネレータ）は、中間コード（バイトコード）を出力する
- 式の出力には逆ポーランド記法を用いる
- 変数テーブルを使って変数管理する
- 仮想マシン（VM）はバイトコードを順番に実行する
最後に
株式会社ロボマインドではこれまでにないAI、『マインド・エンジン』の制作に一緒に携わっていただける開発者の方を募集しています。下記に興味または実績がある方はふるってご応募ください。お待ちしています！
- ディープラーニングの知識または技術をお持ちの方
- ディープラーニングに詳しくなくても、AIの開発に興味のある方
- 自然言語処理の知識または技術をお持ちの方
- AI技術の応用（メタバースやロボット等）に関心のある方
- C#、Java等オブジェクト指向プログラミングの経験のある方
ご応募は会社の採用応募フォームまたは私のTwitterまでDMをお願いします。
次の記事
執筆中
前の記事