前回までのあらすじ
- 自作PCを作ろう！
- まずメモリを作ったよ！
- ISAを作ったよ！(コンパイラはまだ)
- アセンブリ言語を作ったよ！(アセンブラ作成済み．コンパイラはまだ)
- CPUを作ったよ！
- 任意のプログラムを実行できるようになったよ！
- キーボード入力を受け付けられるようになったよ！(ただし独力ではない)
- 複数桁+複数桁の足し算が行えるようになったよ！
-
CALL命令とRET命令を実装して，関数呼び出しが可能になったよ！
今回の目標
前回の記事でアセンブラを作成しました．
これで，機械語のソースを手で書かなくてもよくなりました．
ただ，アセンブリ言語のソースを書くのもそれはそれで面倒です．
という事でこの記事では，C言語プログラムをアセンブリ言語に翻訳するコード生成器(っていうのか？)を作成することにしました．
前回の記事で作成したアセンブラと合わせてコンパイラが完成します．
ちなみに記事タイトルに「1」とついているのは，今回作成したのが制限ありのシンプルめの実装だからです．
今後機能拡張する可能性があります．
というか，機能拡張しないと今回の記事の内容ではOSは作れません．
アセンブラの変更点
今回コンパイラを作るにあたって，アセンブリ言語の仕様を一部変更しました．
分岐の際，ジャンプ先をラベルで指定するように変更しています．
具体的には，以下のような書き方になります．
例えばfor文ではこんな感じになります．
.L1: ; → index 0 (ループ先頭)
mov fh r0 r0 1 ; index 0 \ x = 1 (本体)
wm fh r0 r0 12 ; index 1 /
rm fh r0 r0 4 ; index 2: r0 = a
rm fh r0 r1 8 ; index 3: r1 = b
lt r0 r1 .L1 ; index 4: a<b なら先頭へ戻る → imm = 0 - 4 = -4 (負)
なおジャンプ命令では，ジャンプ先をイミディエイトデータだけではなくレジスタ値からも指定できるという仕様がありましたが，アセンブリ言語ではこれはオミットします．機械語には残すので不可能ではないんですけどね．
アセンブリ言語でここまでの自由度を持つことのメリットがないので縛ります．
で，これらを機械語にするアセンブラのソースがこんな感じ．
asm2bin
asm2bin.hpp
#pragma once
#include <map>
#include <string>
#include <vector>
// 命令に与えられる引数の種類
enum class arg_t {
REGISTER, // レジスタの番地
RAW_DATA, // イミディエイトデータ (イミディエイトデータの使用フラグも含む)
FUNC_NAME, // 関数名
LABEL, // 局所ラベル名 (jmpは絶対index，F系は相対オフセットに解決される)
MASK, // ビットマスク
};
// 各命令の引数情報
typedef struct {
const int arg_num_min; // とりうる引数の最小の個数(イミディエイトデータがある場合は引数の数はこれプラス1になる)
const std::vector<arg_t> arg_types; // それぞれの引数の種類
const bool imm_required; // 機械語側でイミディエイトデータが必須かどうか(必須な場合，引数の個数はarg_num_minから変動しない)
const bool has_imm; // machine.svh関数のimmパラメータを持つか(falseの場合，immは出力しない)
} command_arg_t;
// 機械語の命令一覧
const std::map<std::string, command_arg_t> commands = {
// 処理を実行しない(N系)
{"nop" , {0, { }, false, false}},
// 演算系(P系)
{"and" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER }, false, false}},
{"or" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER }, false, false}},
{"xor" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER }, false, false}},
{"not" , {2, {arg_t::REGISTER, arg_t::REGISTER, }, false, false}},
{"nand" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER }, false, false}},
{"add" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER }, false, false}},
{"sub" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER }, false, false}},
{"mul" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER }, false, false}},
{"div" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
// シフト系(S系)
{"sll" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
{"srl" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
{"sla" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
{"sra" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
// 代入系(A系)
{"mov" , {3, {arg_t::MASK , arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
// 分岐系(F系)
// 飛び先は局所ラベルのみ(相対オフセットに解決される)
{"eq" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::LABEL }, true , true }},
{"ne" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::LABEL }, true , true }},
{"lt" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::LABEL }, true , true }},
{"gt" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::LABEL }, true , true }},
{"elt" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::LABEL }, true , true }},
{"egt" , {3, {arg_t::REGISTER, arg_t::REGISTER, arg_t::LABEL }, true , true }},
// ジャンプ系(J系)
// 飛び先は局所ラベルのみ(絶対indexに解決される)．レジスタ・数値による飛び先指定は持たない
{"jmp" , {1, {arg_t::LABEL }, true , true }},
{"call" , {1, {arg_t::FUNC_NAME }, false, false}}, // 引数は呼び出し先関数名。出力は output_bin_line で特別に組み立てる(rs1=0 + 即値ターゲット)
{"ret" , {0, { }, false, false}}, // 引数なし。汎用経路が machine::ret() を生成する
// メモリ系(M系)
{"rm" , {3, {arg_t::MASK , arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
{"wm" , {3, {arg_t::MASK , arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
{"brm" , {4, {arg_t::MASK , arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
{"bwm" , {4, {arg_t::MASK , arg_t::REGISTER, arg_t::REGISTER, arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
// 標準入出力系(IO系)
{"scan" , {1, { arg_t::REGISTER}, false, false}},
{"print", {1, {arg_t::REGISTER, arg_t::RAW_DATA}, false, true }},
};
// 引数タイプごとのビット数を返す
std::string get_bit_length_of_command(const arg_t arg) {
switch (arg) {
case arg_t::REGISTER:
return std::to_string(6);
case arg_t::RAW_DATA:
return std::to_string(32);
case arg_t::FUNC_NAME:
return std::to_string(6);
case arg_t::LABEL:
return std::to_string(32);
case arg_t::MASK:
return std::to_string(4);
default:
// 起きないはずのエラーなのでエラーメッセージは適当
throw std::string("asm syntax error: arg type is fail");
return "";
}
}
asm2bin.cpp
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include "asm2bin.hpp"
#include "util.hpp"
// コマンドライン引数情報
typedef struct {
std::string asm_file_name; // アセンブリファイル名
std::string sv_file_name; // 出力ファイル名
} args_t;
// 関数
void get_args(int argc, char **argv, args_t &args); // コマンドライン引数を取得
void asm2bin(std::ifstream &asm_file, std::ofstream &sv_file); // アセンブリをバイナリに変換する
void output_header(std::ofstream &sv_file); // svファイルのヘッダーを出力する
void output_bin(std::ifstream &asm_file, std::ofstream &sv_file); // バイナリ部分を出力する
std::string read_global_line(std::ifstream &asm_file); // .global行まで読み飛ばして返す
void get_function_names( // プログラムに存在する関数の名前を取得する
std::map<std::string, std::size_t> &functions, std::string line
);
void assemble_body( // 本体をアセンブルしfunctions/local_labels/instructionsを埋める
std::ifstream &asm_file, std::map<std::string, std::size_t> &functions,
std::map<std::string, std::size_t> &local_labels,
std::vector<std::string> &instructions
);
void output_bin_line( // アセンブリ一行を機械語化しinstructionsへ追加
std::vector<std::string> &instructions,
const std::map<std::string, std::size_t> &functions, std::string line
);
std::string convert_arg( // 機械語関数の引数を加工して返す
const std::map<std::string, std::size_t> &functions,
const std::string &arg, const command_arg_t &command_arg, const int arg_num,
const std::string &command
);
void validate_arg_count( // 引数の個数が命令の仕様に合うか検証する
const command_arg_t &command_arg, const int arg_num, const std::string &command
);
std::string get_machine_function_name(const std::string &command); // machine.svh側の関数名へ変換する
void throw_if_tab(const std::string &line); // タブ文字があればエラーにする
void resolve_labels( // 局所ラベル参照を絶対index/相対オフセットに解決する
std::vector<std::string> &instructions,
const std::map<std::string, std::size_t> &local_labels
);
std::string offset2imm(const long offset); // 相対オフセットをイミディエイト表記にする（負は32bit2の補数）
void apply_main_self_loop( // mainが到達する最初のretを自己ループに置換する
std::vector<std::string> &instructions
);
std::string join_instructions( // 命令を結合する（末尾カンマ無し）
const std::vector<std::string> &instructions
);
std::string function_name2line_num( // 関数参照を行番号に置換する
const std::map<std::string, std::size_t> &functions, const std::string &bin
);
void output_footer(std::ofstream &sv_file); // svファイルのフッターを出力する
const int MAX_LINE_NUM = 255; // 出力されるアセンブリプログラムの最大行数
const char FUNC_REF_DELIM = '@'; // 出力本体で関数参照を囲む区切り文字（命令名や数値との衝突を防ぐ）
// 局所ラベル参照の仮文字列（プレースホルダ）
// jmp/F系の飛び先ラベルは，いったんこの仮文字列で囲んで出力本体に埋め込み，
// 全命令の変換後に resolve_labels が実値（jmp=絶対index，F系=相対オフセット）へ置換する
const std::string LABEL_REF_ABS = "<<ABS:"; // jmp用ラベル参照の開始（絶対indexに解決される）
const std::string LABEL_REF_REL = "<<REL:"; // F系用ラベル参照の開始（相対オフセットに解決される）
const std::string LABEL_REF_CLOSE = ">>"; // ラベル参照の終端
// メイン関数
// 処理に成功したら0，失敗したら1を返り値にする
int main(int argc, char **argv) {
args_t args; // コマンドライン引数
std::ifstream asm_file; // アセンブリファイル
std::ofstream sv_file; // 出力ファイル
// コマンドライン引数を取得
get_args(argc, argv, args);
// コマンドライン引数の取得に失敗していれば
if (
// アセンブリファイル名
args.asm_file_name.empty()
// 出力ファイル名
|| args.sv_file_name.empty()
) {
std::cout << "fail args" << std::endl;
return 1;
}
// アセンブリファイルを開く
asm_file.open(args.asm_file_name);
if (!asm_file) {
std::cout << "cannot open asm file: " << args.asm_file_name << std::endl;
return 1;
}
// 出力ファイルを開く
sv_file.open(args.sv_file_name);
if (!sv_file) {
std::cout << "cannot open sv file: " << args.sv_file_name << std::endl;
return 1;
}
// アセンブリ言語をバイナリに変換する
try {
asm2bin(asm_file, sv_file);
// 正常終了を報告
std::cout << "assembled: " << args.sv_file_name << std::endl;
// ファイルを閉じる
asm_file.close();
sv_file.close();
return 0;
}
catch (std::string msg) {
std::cout << msg << std::endl;
return 1;
}
}
// コマンドライン引数を取得
// -a: 必須引数．アセンブリファイル名．
// -o: 出力ファイル名．省略した場合，アセンブリファイル名の拡張子を変更して同階層に出力される．
// 何も指定せずに引数を置いた場合，アセンブリファイル名と解釈される．
void get_args(int argc, char **argv, args_t &args) {
// 全ての引数でループ(コマンド名は飛ばす)
for (int i = 1; i < argc; i++) {
const char *arg = argv[i]; // 引数一つ
// 指定子なら
if (arg[0] == '-') {
std::string kind = arg; // 指定を保存
// インクリメントして次のパラメータを取得
i++;
if (i >= argc) break;
arg = argv[i];
// 指定されたパラメータを保存
if (kind == "-a") args.asm_file_name = argv[i];
else if (kind == "-o") args.sv_file_name = argv[i];
}
// 指定子の直後ではないなら
else {
args.asm_file_name = argv[i];
}
}
// アセンブリファイル名が .asm で終わっているか（短い名前での範囲外アクセスを防ぐ）
const bool asm_name_ok =
args.asm_file_name.length() >= 4
&& args.asm_file_name.substr(args.asm_file_name.length() - 4) == ".asm";
// 出力ファイル名が指定されていないなら，アセンブリ名の拡張子を .sv にして使う
if (asm_name_ok && args.sv_file_name.empty()) {
// いったんアセンブリファイル名を入れる
args.sv_file_name = args.asm_file_name;
// 拡張子を更新
args.sv_file_name.replace(
args.sv_file_name.length() - 3, // 置換するのは後ろから三文字
3, // 置換する文字数
"sv" // 拡張子は「.sv」にする
);
}
// 出力ファイル名が .sv で終わっているか
const bool sv_name_ok =
args.sv_file_name.length() >= 3
&& args.sv_file_name.substr(args.sv_file_name.length() - 3) == ".sv";
// コマンドライン引数が不正ではないことをチェック
if (!asm_name_ok || !sv_name_ok) {
// メッセージ出力
std::cout << "args fail" << std::endl
<< "-a: asm file name. e.g. ~~.asm" << std::endl
<< " actual: " << args.asm_file_name << std::endl
<< "-o: output file name. e.g. ~~.sv" << std::endl
<< " actual: " << args.sv_file_name << std::endl;
// 後の処理でエラーになるよう，コマンドライン引数をクリア
args.asm_file_name.clear();
args.sv_file_name.clear();
}
}
// アセンブリをバイナリに変換する
void asm2bin(std::ifstream &asm_file, std::ofstream &sv_file) {
// ヘッダーを出力する
output_header(sv_file);
// バイナリ部分を出力する
output_bin(asm_file, sv_file);
// フッターを出力する
output_footer(sv_file);
// バッファに溜まっている分を出力
sv_file.flush();
}
// svファイルのヘッダーを出力する
void output_header(std::ofstream &sv_file) {
sv_file << "`include \"rom.svh\"\n"
<< "`include \"machine.svh\"\n"
<< "\n"
<< "module rom_sv(\n"
<< " rom_read_if.slave rom_read\n"
<< " );\n"
<< " import machine_p::*;\n"
<< "\n";
}
// バイナリ部分を出力する
void output_bin(std::ifstream &asm_file, std::ofstream &sv_file) {
std::map<std::string, std::size_t> functions; // 関数とその開始pc
std::map<std::string, std::size_t> local_labels; // 局所ラベルとその位置（直後の命令のindex）
std::vector<std::string> instructions; // 機械語にした命令一覧（1要素=1命令）
// .global 行を取得し，宣言された関数名を読み込む
std::string global_line = read_global_line(asm_file);
get_function_names(functions, global_line);
// main関数が指定されていなければ
if (functions.find("main") == functions.end()) {
throw std::string("asm syntax error: main function not found");
}
// 本体をアセンブルする（functions/local_labels のpc確定 + instructions 生成）
assemble_body(asm_file, functions, local_labels, instructions);
// .global で宣言された関数がすべて定義されているか確認する
// pcがnposのまま残っていれば，宣言だけで定義(ラベル)がない関数
for (const auto &function : functions) {
if (function.second == std::string::npos) {
throw "asm syntax error: declared but not defined function '" + function.first + "'";
}
}
// 局所ラベル参照を解決する（絶対index/相対オフセット）
resolve_labels(instructions, local_labels);
// mainが到達する最初のretを自己ループに置き換える
apply_main_self_loop(instructions);
// 命令数をlocalparam，machine_t配列として出力する
const std::string body = function_name2line_num(functions, join_instructions(instructions));
sv_file << " localparam integer ROM_SIZE = " << instructions.size() << ";\n\n";
sv_file << " machine_t machines[0:ROM_SIZE - 1] = {\n";
sv_file << body;
sv_file << " };\n";
}
// .global行まで読み飛ばして返す
// .global より前は空行とコメント行(;)のみ許可し，それ以外はエラーにする
std::string read_global_line(std::ifstream &asm_file) {
std::string line;
while (getline(asm_file, line)) {
// .global 行が見つかったら（タブ非対応を確認して）返す
if (strncmp(".global ", line.c_str(), strlen(".global ")) == 0) {
throw_if_tab(line);
return line;
}
// 空行でもコメント行でもなければ，.global より前のコードとしてエラー
std::string trimmed = ltrim(line);
if (!trimmed.empty() && trimmed[0] != ';') {
throw "asm syntax error: code before .global '" + line + "'";
}
}
// .global 宣言が無いままEOFに達した
throw std::string("asm syntax error: .global not found");
}
// プログラムに存在する関数の名前を取得する
void get_function_names(
std::map<std::string, std::size_t> &functions, std::string line
) {
// 関数指定が正しくなければ
if (strncmp(".global ", line.c_str(), strlen(".global ")) != 0) {
throw std::string("asm syntax error: .global fail");
}
// 関数の羅列部分を取得
line = line.substr(strlen(".global "));
// 関数名一覧を取得
for (int i = 0; i < static_cast<int>(line.length()); i++) {
// スペースならスキップ
if (line[i] == ' ') continue;
// スペース以外なら，カンマまでを関数名として記録
std::string word = line.substr(i); // 厳密には一単語ではないが便宜上wordと呼ぶ
int last_index = str_find_first_of(word, ',');
std::string function_name = word.substr(0, last_index);
// 末尾の空白を除去（カンマの前に空白がある場合に備える）
while (!function_name.empty() && function_name.back() == ' ') {
function_name.pop_back();
}
// すでにその名前の関数が登録されていれば
if (functions.find(function_name) != functions.end()) {
throw "asm syntax error: function name fail '" + function_name + "'";
}
functions[function_name] = std::string::npos; // いったんnposを入れる
// 関数名の長さぶんiに加算
i += last_index;
}
}
// 本体をアセンブルしfunctionsとinstructionsを埋める
// 命令のpcは instructions のインデックスに対応する
void assemble_body(
std::ifstream &asm_file, std::map<std::string, std::size_t> &functions,
std::map<std::string, std::size_t> &local_labels,
std::vector<std::string> &instructions
) {
std::string line; // アセンブリファイルの一文
std::string current_function; // 現在変換中の関数名
bool current_has_ret = false; // 現在の関数が ret を含むか
while (getline(asm_file, line)) {
// 空行はスキップ
if (line == "") continue;
// 空白のみの行・コメント行はスキップ（コメント内のコロンをラベルと誤認しないため）
std::string trimmed = ltrim(line);
if (trimmed.empty() || trimmed[0] == ';') continue;
// ラベル宣言なら
std::size_t colon_index = line.find_first_of(':');
if (colon_index != std::string::npos) {
std::string label_name = line.substr(0, colon_index);
// 局所ラベル（先頭が '.'）なら，関数とは別に位置だけ記録する
// 命令は生成せず，.global 照合・main先頭チェック・ret追跡の対象外
if (!label_name.empty() && label_name[0] == '.') {
// すでに定義済みなら（ラベルはプログラム全体で一意）
if (local_labels.find(label_name) != local_labels.end()) {
throw "asm syntax error: label overlapping definition '" + label_name + "'";
}
// ラベル位置（直後の命令のindex）を記録する
local_labels[label_name] = instructions.size();
continue;
}
// 以降は関数ラベルの処理
std::string function_name = label_name;
// 関数一覧にないなら
if (functions.find(function_name) == functions.end()) {
throw "asm syntax error: not defined function '" + function_name + "'";
}
// すでにセット済みなら
if (functions[function_name] != std::string::npos) {
throw "asm syntax error: function overlapping definition '" + function_name + "'";
}
// 最初に宣言された関数がmainではない
if (instructions.empty() && function_name != "main") {
throw "asm syntax error: first function is not main '" + function_name + "'";
}
// 直前の関数が ret を1つも持たないならエラー
if (!current_function.empty() && !current_has_ret) {
throw "asm syntax error: function without ret '" + current_function + "'";
}
// 関数の先頭pcを記録し，現在の関数を更新する
functions[function_name] = instructions.size();
current_function = function_name;
current_has_ret = false;
continue;
}
// main関数の宣言前にコードがある
if (functions["main"] == std::string::npos) {
throw std::string("asm syntax error: not found main function");
}
// 現在の関数が ret を含むか記録する
std::string command = trimmed.substr(0, str_find_first_of(trimmed, ' '));
if (command == "ret") current_has_ret = true;
// アセンブリを機械語にしてinstructionsに追加する
output_bin_line(instructions, functions, line);
// 最大行数を超えた
if (static_cast<int>(instructions.size()) >= MAX_LINE_NUM) {
throw std::string("asm syntax error: line more than 255");
}
}
// 最後の関数が ret を1つも持たないならエラー
if (!current_function.empty() && !current_has_ret) {
throw "asm syntax error: function without ret '" + current_function + "'";
}
}
// アセンブリ一行を機械語化しinstructionsへ追加する
void output_bin_line(
std::vector<std::string> &instructions,
const std::map<std::string, std::size_t> &functions, std::string line
) {
// タブ文字は非対応
throw_if_tab(line);
// 先頭のスペースを除去する
line = ltrim(line);
// セミコロンなら
if (line[0] == ';') return;
// 命令を取得
std::string command = line.substr(0, str_find_first_of(line, ' '));
// 命令が不正なら
if (commands.find(command) == commands.end()) {
throw "asm syntax error: fail command '" + command + "'";
}
// 命令がcall/jmpなら
// どちらも「rs1=0 + 即値ターゲット」という特殊な出力形のため，汎用経路に乗らない
// call: 呼び出し先pcを即値で渡す（戻り先保存やSP更新はCPU側が行う）
// jmp : 飛び先（局所ラベルの絶対index）を即値で渡す
if (command == "call" || command == "jmp") {
// 引数前のスペースを除去してターゲット（呼び出し先関数名／飛び先ラベル）を取得
line = ltrim(line.substr(std::min(command.length() + 1, line.length())));
const int first_space = str_find_first_of(line, ' ');
const std::string target = convert_arg(
functions, line.substr(0, first_space), commands.at(command), 0, command
);
// 引数は1つだけ．ターゲットの後に（コメント以外の）余分な引数があればエラー
const std::string rest = ltrim(line.substr(first_space));
if (!rest.empty() && rest[0] != ';') {
throw "asm syntax error: too many arguments '" + command + "'";
}
// callは関数参照(@func@)に即値プレフィックスを付ける
// jmpはconvert_argが既にプレフィックス付きのラベル参照を返す
if (command == "call") {
instructions.push_back("call(0, 33'h1_0000_0000 + " + target + ")");
}
else {
instructions.push_back("jmp(0, " + target + ")");
}
return;
}
// 命令の引数仕様
const command_arg_t &command_arg = commands.at(command);
// 命令本体を組み立てる
std::string instr = get_machine_function_name(command) + "(";
// 引数を取得
int arg_num = 0;
line = line.substr(std::min(command.length() + 1, line.length())); // 引数がなかった時のためstd::min
while (!line.empty() && line[0] != ';') {
// スペースを飛ばす
if (line[0] == ' ') {
line = line.substr(1);
continue;
}
// 引数が引数仕様の個数より多い（arg_typesの範囲外アクセスを防ぐ）
if (arg_num >= static_cast<int>(command_arg.arg_types.size())) {
throw "asm syntax error: too many arguments '" + command + "'";
}
// 引数を追加
if (arg_num != 0) instr += ", ";
int first_space = str_find_first_of(line, ' ');
instr += convert_arg(
functions, line.substr(0, first_space), command_arg, arg_num, command
);
// 次のループの準備
line = line.substr(first_space); // 引数直後のスペースは飛ばさない．最後の引数である可能性があるため
arg_num++;
}
// 引数の数があっているか確認
validate_arg_count(command_arg, arg_num, command);
// immあり・未出力なら，0にしておく
if (command_arg.has_imm && !command_arg.imm_required && (arg_num == command_arg.arg_num_min)) {
instr += ", 0";
}
// 命令を閉じて追加する
instr += ")";
instructions.push_back(instr);
}
// ニーモニックをmachine.svh側の関数名に変換する
// SystemVerilog予約語と衝突するand/or/xor/not/nandは末尾に_を付ける
std::string get_machine_function_name(const std::string &command) {
if (command == "and") return "and_";
if (command == "or") return "or_";
if (command == "xor") return "xor_";
if (command == "not") return "not_";
if (command == "nand") return "nand_";
return command;
}
// 機械語関数の引数を加工して返す
std::string convert_arg(
const std::map<std::string, std::size_t> &functions,
const std::string &arg, const command_arg_t &command_arg, const int arg_num,
const std::string &command
) {
std::string converted_arg = arg; // 引数は加工できないので，加工用の変数を用意
// 引数が局所ラベルなら (jmp/F系の飛び先)
// 飛び先は局所ラベルのみ．ここではプレースホルダを埋め，resolve_labelsで実値に解決する
if (command_arg.arg_types[arg_num] == arg_t::LABEL) {
// ラベルは先頭が '.'
if (converted_arg.empty() || converted_arg[0] != '.') {
throw "asm syntax error: jump target must be a local label '" + arg + "'";
}
// jmpは絶対index，F系は相対オフセットに解決する（命令名で区別）
// 後で resolve_labels が置換する仮文字列で囲んで埋め込む
const std::string open = (command == "jmp") ? LABEL_REF_ABS : LABEL_REF_REL;
return "33'h1_0000_0000 + " + open + converted_arg + LABEL_REF_CLOSE;
}
// 引数が関数名なら (命令がcallの場合は関数名が引数になる)
if (functions.find(converted_arg) != functions.end()) {
// 関数名を区切り文字で囲んで返す
// function_name2line_num が囲まれたトークンだけを行番号へ置換するため，
// 関数名が命令名や数値の一部と一致して誤置換されることを防げる
return FUNC_REF_DELIM + converted_arg + FUNC_REF_DELIM;
}
// 引数がレジスタなら
if (converted_arg[0] == 'r') {
// 引数タイプが違うなら
if (command_arg.arg_types[arg_num] != arg_t::REGISTER) {
throw "asm syntax error: arg register address fail '" + arg + "'";
}
converted_arg = arg.substr(1);
}
else {
// 引数タイプがマスクまたは生の値ではないなら
if (command_arg.arg_types[arg_num] != arg_t::MASK && command_arg.arg_types[arg_num] != arg_t::RAW_DATA) {
throw "asm syntax error: arg mask or raw data fail '" + arg + "'";
}
}
// 加工後に空文字列なら不正な引数（例: 番号のない "r"）
if (converted_arg.empty()) {
throw "asm syntax error: fail arg '" + arg + "'";
}
// 引数が十進数表記ではないなら
const char last = converted_arg[converted_arg.length() - 1];
if (last < '0' || last > '9') {
switch (last) {
case 'b': case 'o': case 'h': // 2進数，8進数，16進数
// Verilogでの表記に書き直す
converted_arg = get_bit_length_of_command(command_arg.arg_types[arg_num])
+ '\'' + last
+ converted_arg.substr(0, converted_arg.length() - 1);
break;
default:
throw std::string("asm syntax error: fail base number '") + last + "'";
}
}
// イミディエイトデータを使用するなら
if (command_arg.arg_types[arg_num] == arg_t::RAW_DATA) {
converted_arg = "33'h1_0000_0000 + " + converted_arg;
}
// 加工した引数を返す
return converted_arg;
}
// 引数の個数が命令の仕様に合うか検証する
void validate_arg_count(
const command_arg_t &command_arg, const int arg_num, const std::string &command
) {
if (
// イミディエイトデータが必須で，引数の個数が違う
(command_arg.imm_required && arg_num != command_arg.arg_num_min)
// immあり・省略可で，引数の個数が違う（arg_num_min または arg_num_min+1 が有効）
|| (!command_arg.imm_required && command_arg.has_imm && arg_num != command_arg.arg_num_min && arg_num != command_arg.arg_num_min + 1)
// immなしで，引数の個数が違う（arg_num_min のみ有効）
|| (!command_arg.imm_required && !command_arg.has_imm && arg_num != command_arg.arg_num_min)
) {
throw "asm syntax error: fail program " + command + " " + std::to_string(arg_num);
}
}
// タブ文字があればエラーにする
void throw_if_tab(const std::string &line) {
if (line.find('\t') != std::string::npos) {
throw "asm syntax error: tab character is not supported '" + line + "'";
}
}
// 局所ラベル参照を絶対index/相対オフセットに解決する
// 各命令のインデックスがそのまま自命令のpcになるため，ループのpcを使って計算できる
// jmp（絶対）はラベルのindex，F系（相対）は「ラベルのindex − 自命令pc」に置換する
void resolve_labels(
std::vector<std::string> &instructions,
const std::map<std::string, std::size_t> &local_labels
) {
for (std::size_t pc = 0; pc < instructions.size(); pc++) {
std::string &instr = instructions[pc];
// 開きタグを探し，ラベル参照の有無と種別（絶対/相対）を判定する
bool is_abs = true;
std::size_t open_pos = instr.find(LABEL_REF_ABS);
if (open_pos == std::string::npos) {
open_pos = instr.find(LABEL_REF_REL);
is_abs = false;
}
// ラベル参照を持たない命令は何もしない（大多数はここで抜ける）
if (open_pos == std::string::npos) continue;
// 開きタグと終端タグの間からラベル名を取り出す
const std::size_t name_start =
open_pos + (is_abs ? LABEL_REF_ABS : LABEL_REF_REL).length();
const std::size_t close_pos = instr.find(LABEL_REF_CLOSE, name_start);
const std::string label_name = instr.substr(name_start, close_pos - name_start);
// 参照先ラベルが定義されているか
auto label = local_labels.find(label_name);
if (label == local_labels.end()) {
throw "asm syntax error: undefined label reference '" + label_name + "'";
}
// jmp（絶対）はラベルのindex，F系（相対）は「ラベルのindex − 自命令pc」に解決する
std::string value;
if (is_abs) {
value = std::to_string(label->second);
}
else {
const long offset = static_cast<long>(label->second) - static_cast<long>(pc);
value = offset2imm(offset);
}
// 仮文字列（開きタグ〜終端タグ）を実値に置換する
instr.replace(open_pos, close_pos + LABEL_REF_CLOSE.length() - open_pos, value);
}
}
// 相対オフセットをイミディエイト表記にする
// 負のオフセットは32bit2の補数のhexにする（33bit目の即値使用フラグを落とさないため）
std::string offset2imm(const long offset) {
// 0以上ならそのまま10進で出力する
if (offset >= 0) return std::to_string(offset);
// 負なら32bit2の補数（例: -4 → 32'hfffffffc）にする
char buf[16];
snprintf(buf, sizeof(buf), "32'h%08x", static_cast<unsigned int>(offset));
return std::string(buf);
}
// mainが到達する最初のretを自己ループに置換する
// プログラムはmain(pc=0)から実行されるため，先頭から線形に見て最初に現れるretが
// mainがCALLされずに到達するret＝戻り先の無いretになる．これを自分自身へのjmp(無限ループ)に
// 置き換えてmainを停止させる（mainは必ずretを持つので必ず見つかる）
void apply_main_self_loop(std::vector<std::string> &instructions) {
for (std::size_t pc = 0; pc < instructions.size(); pc++) {
if (instructions[pc] == "ret()") {
instructions[pc] =
"jmp(0, 33'h1_0000_0000 + " + std::to_string(pc) + ")";
return; // 最初の1つだけ置換する
}
}
}
// 命令を結合する（各命令を8スペースインデントし，カンマ区切りで並べる）
// SystemVerilogの配列初期化子では末尾カンマが構文エラーになるため，末尾要素にはカンマを付けない
std::string join_instructions(const std::vector<std::string> &instructions) {
std::string body;
for (std::size_t i = 0; i < instructions.size(); i++) {
body += " " + instructions[i];
if (i + 1 < instructions.size()) body += ",";
body += "\n";
}
return body;
}
// 関数参照を行番号に置換する
std::string function_name2line_num(
const std::map<std::string, std::size_t> &functions, const std::string &bin
) {
std::string rtn = bin; // 引数は加工できないので，加工用の変数を用意
// 区切り文字で囲まれた関数参照（@func@ など）を対応する行番号に置換する
// 区切り文字で囲んでいるため，f1 と f11 のような接頭辞の衝突や，
// 関数名が命令名・数値の一部に一致することによる誤置換が起きない
for (const auto &function : functions) {
replace(
rtn,
FUNC_REF_DELIM + function.first + FUNC_REF_DELIM,
std::to_string(function.second)
);
}
return rtn;
}
// svファイルのフッターを出力する
void output_footer(std::ofstream &sv_file) {
sv_file << "\n"
<< " always_comb begin\n"
<< " if (rom_read.pc >= ROM_SIZE) begin\n"
<< " rom_read.machine = nop();\n"
<< " end else begin\n"
<< " rom_read.machine = machines[rom_read.pc];\n"
<< " end\n"
<< " end\n"
<< "\n"
<< "endmodule\n";
}
ここから本題
「コード生成器」は長いし一般的じゃないので，これ以降では特に明示しない限りC言語プログラムからアセンブリ言語プログラムを生成するプログラムを「コンパイラ」と呼ぶことにします．
また，冒頭で「C言語」と言いましたが，色々ありまして結局「C言語に似てるけど全然違う独自の言語」ということになりました．
プログラミング言語の仕様
さて，C言語に似ているだけの独自言語なので，まずその仕様について簡単にまとめたいと思います．
作成するコンパイラの仕様
ここでは，まず簡単なコンパイラを作成することを目指します．
複雑な事には対応せず，簡単なコードのコンパイルを完了させるところがゴールです．
簡単に説明すると以下のような仕様になっています．
- 対応するのは単一の
.cファイル - 出力は単一の
.asmファイル(自作アセンブリ言語でのソースコード) - 対応するのは基本的な型および構文のみ
- データ型は
char,short,intのそれぞれsignedとunsigned - グローバル変数とローカル変数の両方に対応する
- ブロックスコープに対応する
- C言語に存在するすべての演算子に対応する
-
ifやforなどすべての構文に対応する - 関数に対応する
- スコープが違うなら同名の関数であっても異なる関数として扱う
- データ型は
- C言語の基本的な構文であっても，複雑なものにはひとまず対応しない
- 配列には対応しない
- ポインタ変数には対応しない
- 構造体や共同体，列挙体には対応しない
-
staticなグローバル変数には対応しない(そもそも複数ファイルにならない) -
staticなローカル変数には対応しない - 関数の引数及び返り値には対応しない
- 標準ライブラリ上の関数には対応しない
-
#includeや#defineなど，#から始まるやつには対応しない -
longには対応しない -
floatなど浮動小数点には対応しない - 動的メモリ管理には対応しない(そもそもポインタ変数に対応しないので)
-
gotoには対応しない(対応してもどうせ使わないので) -
unsignedには対応しない(unsigned charなど，int以外の符号なし整数への対応が面倒くさい．現状，全ての変数は4バイト空間内に保存している．charの値を保存する時は下位1バイト以外をマスクして格納するが，取り出すときに問題が生じる．下位1バイトだけ取りだすと0xffになってしまい，intと演算する時に-1ではなく255になってしまう) - 再帰関数には対応しない(現状できない．ローカル変数は全て，アセンブリ言語の時点で決め打ちのメモリ番地に配置する)
- すべての変数はメモリ上に展開する
- 組み込み関数として，機械語命令の
printとscanに対応する関数を実装する．この二つだけ特別でprint(x),scan(&x)という書き方を許容する - ハードウェアへのアクセスは，あらかじめ定義された変数の値を直接読み書きすることで行う(
errnoみたいな感じ) - C言語と仕様が違う点
- 関数を実装する前に関数宣言する必要はない
ちなみに復習になりますが，LEDなどのハードウェアは，CPU上のレジスタと直結しています．
機械語的には，そのレジスタの値をいじることでLEDやスライドスイッチなどの値を直接いじったり取得したりします．
今回使用するコンパイラで扱うC言語的なプログラムにはレジスタはないので，LEDなどのようなあらかじめ定義された変数の値を取得したり変更したりする，ということです．
コンパイラの大体の流れ
ここで作成するコンパイラは以下の動作を行います．
- ソースファイル(C言語みたいなプログラムのこと)を読み込み，コメントを消したりスペースを消したりしたうえで，トークン列に分割する
- 構文解析を行い，ASTを生成する
- 意味解析を行い，シンボルテーブルを構築する
- アセンブリコードを生成する
トークン列作成
ではここから実装の話です．
コンパイルにはいくつかの段階がありますが，まずここではソースコードをトークンごとに分割します．
ここで言うトークンとは，{のような各種括弧，intのような予約語，0みたいなリテラル，あるいは識別子fugaとかそういう，プログラムとしてそれ以上分割できない最小単位です．
これをベクトル状に並べていきます．
lexer
lexer.hpp
#pragma once
#include <string>
#include <vector>
// トークン種別
typedef enum {
// 型キーワード
TK_INT, TK_CHAR, TK_SHORT, TK_VOID, TK_SIGNED, TK_UNSIGNED,
// 制御構文キーワード
TK_IF, TK_ELSE, TK_FOR, TK_WHILE, TK_DO,
TK_SWITCH, TK_CASE, TK_DEFAULT,
TK_BREAK, TK_CONTINUE, TK_RETURN,
// その他キーワード
TK_SIZEOF,
// リテラル
TK_INT_LIT, // 整数リテラル
TK_CHAR_LIT, // 文字リテラル
// 識別子
TK_IDENT,
// 算術演算子
TK_PLUS, // +
TK_MINUS, // -
TK_STAR, // *
TK_SLASH, // /
TK_PERCENT, // %
// ビット演算子
TK_AMP, // &
TK_PIPE, // |
TK_CARET, // ^
TK_TILDE, // ~
TK_LSHIFT, // <<
TK_RSHIFT, // >>
// 論理演算子
TK_AMPAMP, // &&
TK_PIPEPIPE, // ||
TK_BANG, // !
// 比較演算子
TK_EQEQ, // ==
TK_NEQ, // !=
TK_LT, // <
TK_GT, // >
TK_LEQ, // <=
TK_GEQ, // >=
// 代入演算子
TK_ASSIGN, // =
TK_PLUS_ASSIGN, // +=
TK_MINUS_ASSIGN, // -=
TK_STAR_ASSIGN, // *=
TK_SLASH_ASSIGN, // /=
TK_PCT_ASSIGN, // %=
TK_AMP_ASSIGN, // &=
TK_PIPE_ASSIGN, // |=
TK_CARET_ASSIGN, // ^=
TK_LSHIFT_ASSIGN, // <<=
TK_RSHIFT_ASSIGN, // >>=
// インクリメント・デクリメント
TK_PLUSPLUS, // ++
TK_MINUSMINUS, // --
// 三項演算子
TK_QUESTION, // ?
TK_COLON, // :
// 区切り文字
TK_LPAREN, // (
TK_RPAREN, // )
TK_LBRACE, // {
TK_RBRACE, // }
TK_SEMICOLON, // ;
TK_COMMA, // ,
// ファイル末尾
TK_EOF,
} token_kind_t;
// トークン
typedef struct {
token_kind_t kind; // 種別
std::string value; // 文字列値
int line; // 行番号
} token_t;
// 字句解析してトークン列を生成する
void lex(const std::string &src, std::vector<token_t> &tokens);
lexer.cpp
#include <cctype>
#include <map>
#include "lexer.hpp"
// 前宣言 (ファイル内部でのみ使用)
static token_kind_t get_keyword_kind(const std::string &word); // 識別子がキーワードならその種別を，そうでなければ TK_IDENT を返す
// キーワード文字列からトークン種別への変換表
const std::map<std::string, token_kind_t> g_keywords = {
{"int", TK_INT}, {"char", TK_CHAR}, {"short", TK_SHORT},
{"void", TK_VOID}, {"signed", TK_SIGNED}, {"unsigned", TK_UNSIGNED},
{"if", TK_IF}, {"else", TK_ELSE}, {"for", TK_FOR},
{"while", TK_WHILE}, {"do", TK_DO},
{"switch", TK_SWITCH}, {"case", TK_CASE}, {"default", TK_DEFAULT},
{"break", TK_BREAK}, {"continue", TK_CONTINUE},
{"return", TK_RETURN}, {"sizeof", TK_SIZEOF},
};
// 演算子・区切り文字文字列からトークン種別への変換表
const std::map<std::string, token_kind_t> g_operators = {
{"<<=", TK_LSHIFT_ASSIGN}, {">>=", TK_RSHIFT_ASSIGN},
{"==", TK_EQEQ}, {"!=", TK_NEQ}, {"<=", TK_LEQ}, {">=", TK_GEQ},
{"<<", TK_LSHIFT}, {">>", TK_RSHIFT}, {"&&", TK_AMPAMP}, {"||", TK_PIPEPIPE},
{"++", TK_PLUSPLUS},{"--", TK_MINUSMINUS},
{"+=", TK_PLUS_ASSIGN}, {"-=", TK_MINUS_ASSIGN}, {"*=", TK_STAR_ASSIGN},
{"/=", TK_SLASH_ASSIGN},{"%=", TK_PCT_ASSIGN},
{"&=", TK_AMP_ASSIGN}, {"|=", TK_PIPE_ASSIGN}, {"^=", TK_CARET_ASSIGN},
{"+", TK_PLUS}, {"-", TK_MINUS}, {"*", TK_STAR}, {"/", TK_SLASH},
{"%", TK_PERCENT}, {"&", TK_AMP}, {"|", TK_PIPE}, {"^", TK_CARET},
{"~", TK_TILDE}, {"!", TK_BANG}, {"<", TK_LT}, {">", TK_GT},
{"=", TK_ASSIGN}, {"?", TK_QUESTION}, {":", TK_COLON},
{"(", TK_LPAREN}, {")", TK_RPAREN}, {"{", TK_LBRACE}, {"}", TK_RBRACE},
{";", TK_SEMICOLON},{",", TK_COMMA},
};
// ソースコードをトークン列に変換する
void lex(const std::string &src, std::vector<token_t> &tokens) {
int i = 0; // 現在の読み取り位置
int line = 1; // 現在の行番号
int src_size = static_cast<int>(src.size()); // ソース全体のサイズ
while (i < src_size) {
const char c = src[i];
// 改行: 行番号をインクリメントする
if (c == '\n') { line++; i++; continue; }
// 空白文字: スキップする
if (c == ' ' || c == '\t' || c == '\r') { i++; continue; }
// 行コメント (//): 行末までスキップする
if (c == '/' && i + 1 < src_size && src[i + 1] == '/') {
while (i < src_size && src[i] != '\n') i++;
// lineのインクリメントは外部whileループの次のループで行う
continue;
}
// ブロックコメント (/* */): 閉じるまでスキップする
if (c == '/' && i + 1 < src_size && src[i + 1] == '*') {
i += 2;
while (i + 1 < src_size) {
if (src[i] == '\n') line++;
if (src[i] == '*' && src[i + 1] == '/') { i += 2; break; }
i++;
}
continue;
}
// 識別子または予約語: アルファベットか _ で始まる
if (isalpha(static_cast<unsigned char>(c)) || c == '_') {
int start = i;
while (i < src_size
&& (isalnum(static_cast<unsigned char>(src[i])) || src[i] == '_')) {
i++;
}
const std::string word = src.substr(start, i - start);
tokens.push_back({get_keyword_kind(word), word, line});
continue;
}
// 整数リテラル: 数字で始まる
if (isdigit(static_cast<unsigned char>(c))) {
int start = i;
// 16進数 (0x...) の場合
if (c == '0' && i + 1 < src_size
&& (src[i + 1] == 'x' || src[i + 1] == 'X')) {
i += 2;
while (i < src_size
&& isxdigit(static_cast<unsigned char>(src[i]))) {
i++;
}
}
// 10進数の場合
else {
while (i < src_size
&& isdigit(static_cast<unsigned char>(src[i]))) {
i++;
}
}
tokens.push_back({TK_INT_LIT, src.substr(start, i - start), line});
continue;
}
// 文字リテラル: ' で始まる
if (c == '\'') {
int start = i;
i++; // 開き ' をスキップする
// エスケープシーケンスの場合，バックスラッシュの次の文字もスキップする
if (i < src_size && src[i] == '\\') i++;
i++; // 文字本体をスキップする
// 閉じ ' を確認する
if (i >= src_size || src[i] != '\'') {
throw std::string("compiler error: unterminated char literal at line ")
+ std::to_string(line);
}
i++; // 閉じ ' をスキップする
tokens.push_back({TK_CHAR_LIT, src.substr(start, i - start), line});
continue;
}
// 演算子・区切り文字: 3文字→2文字→1文字の順に最長一致を試みる
bool matched = false;
for (int len = 3; len >= 1; len--) {
if (i + len > src_size) continue;
const std::string token = src.substr(i, len);
const auto it = g_operators.find(token);
if (it != g_operators.end()) {
tokens.push_back({it->second, token, line});
i += len;
matched = true;
break;
}
}
if (!matched) {
throw std::string("compiler error: unknown character '")
+ c + "' at line " + std::to_string(line);
}
}
// ファイル末尾トークンを追加する
tokens.push_back({TK_EOF, "", line});
}
// 識別子がキーワードならその種別を，そうでなければ TK_IDENT を返す
static token_kind_t get_keyword_kind(const std::string &word) {
const auto it = g_keywords.find(word);
if (it != g_keywords.end()) return it->second;
return TK_IDENT;
}
構文解析
次に行うのが構文解析です．
トークン列はあくまで平たいただの列．
これにネストを付けていく作業を行います．
例えばi = 2 + 3 * 4は以下のようなネスト構造になりますね．
- i
- =
- +
- 2
- *
- 3
- 4
- +
- =
これをソースコード全体に対して施していきます．
また，ソースコードに構文エラーがないかどうかについてもこの時点でチェックすることになります．
上記の木構造を上手く作れなかったら構文エラーってことです．
ちなみに，優先度が高い演算子ほど木構造の葉に近い位置に来ます．
それを先に計算するからですね．
逆に，優先度が低い演算子ほど木構造の根に近い位置に来ます．
もちろん，それが後に計算されるものだからです．
また，組み込み関数が変数として使われているみたいな構文エラーはこの時点で出ます．
parser
parser.hpp
#pragma once
#include <string>
#include <vector>
#include "lexer.hpp"
// 基本型種別
typedef enum {
BASE_CHAR, BASE_SHORT, BASE_INT, BASE_VOID,
} base_type_t;
// 型情報
typedef struct {
base_type_t base; // 基本型
bool is_signed; // signed/unsigned
} type_t;
// ASTノード種別
typedef enum {
// プログラム構造
ND_PROGRAM, // プログラム全体
ND_FUNC_DEF, // 関数定義
ND_BLOCK, // ブロック文 { ... }
// 宣言
ND_VAR_DECL, // 変数宣言
// 制御構文
ND_IF, // if文
ND_WHILE, // while文
ND_FOR, // for文
ND_DO_WHILE, // do-while文
ND_SWITCH, // switch文
ND_CASE, // case節
ND_DEFAULT, // default節
ND_BREAK, // break文
ND_CONTINUE, // continue文
ND_RETURN, // return文
// 式
ND_CALL, // 関数呼び出し
ND_PRINT, // 組み込み関数print (標準出力)
ND_SCAN, // 組み込み関数scan (標準入力)
ND_ASSIGN, // 代入式
ND_BINOP, // 二項演算
ND_UNOP, // 前置単項演算
ND_POST_UNOP, // 後置単項演算 (++/--)
ND_TERNARY, // 三項演算子
ND_SIZEOF, // sizeof式
ND_INT_LIT, // 整数リテラル
ND_CHAR_LIT, // 文字リテラル
ND_VAR, // 変数参照
} node_kind_t;
// シンボル情報 (実体はanalyzer.hppで定義．node_tはポインタで参照するため前方宣言する)
struct symbol_t;
// ASTノード
struct node_t {
node_kind_t kind; // ノード種別
std::vector<node_t *> children; // 子ノード
std::string sval; // 文字列値 (識別子名・演算子文字列)
long long ival; // 整数値 (リテラル)
type_t type; // 型情報 (意味解析後に確定)
int line; // 行番号 (エラー報告用)
const symbol_t *sym = nullptr; // 名前解決の結果 (ND_VAR等がどの宣言を指すか，意味解析後に確定)
};
// トークン列を受け取り，ASTを生成するパーサ
//
// パーサの責務は「トークンの並びが文法に合っているか」のチェックまで．
// エラーにするもの: 期待したトークンが来ない (例: 閉じ括弧がない，式が来るべき場所に ; がある)
// 見逃すもの: 構文としては正しいが意味的に不正な式．後段の意味解析で検査する．
// 例: 代入の左辺が変数でない (1 + 2 = x)，未宣言の変数参照，未定義関数の呼び出し
class Parser {
public:
explicit Parser(const std::vector<token_t> &tokens);
node_t *operator()(); // 構文解析を実行してASTのルートを返す
private:
const std::vector<token_t> &tokens_; // トークン列
int pos_; // 現在の読み取り位置
// ヘルパー
const token_t &peek_token() const; // 現在のトークンを覗き見る (消費しない)
bool token_kind_is(token_kind_t kind) const; // 現在のトークンの種別が一致するか調べる (消費しない)
token_t get_token(); // トークンを取得して進める (検証なし)
token_t get_token(token_kind_t kind); // 指定種別のトークンを取得して進める，違えばエラー
node_t *new_node(node_kind_t kind); // 現在のトークンの行番号でASTノードを生成する
static bool is_type_start(token_kind_t kind); // 型の先頭になりうるトークン種別かどうか返す
static bool is_assign_op(token_kind_t kind); // 代入演算子のトークン種別かどうか返す
static std::string token_kind_name(token_kind_t kind); // トークン種別をエラーメッセージ用の文字列に変換する
static long long parse_int_literal(const std::string &text); // 整数リテラル文字列を数値に変換する
static long long parse_char_literal(const std::string &text); // 文字リテラル文字列を文字コードに変換する
// 構文解析メソッド (parse_で始まる)
node_t *parse_program(); // プログラム全体
node_t *parse_func_def(); // 関数定義
node_t *parse_block(); // ブロック { ... }
node_t *parse_stmt(); // 文
node_t *parse_var_decl(); // 変数宣言
node_t *parse_return(); // return文
node_t *parse_if(); // if文 (else if / else を含む)
node_t *parse_while(); // while文
node_t *parse_for(); // for文
node_t *parse_do_while(); // do-while文
node_t *parse_switch(); // switch文
node_t *parse_case(); // case節
node_t *parse_default(); // default節
node_t *parse_break(); // break文
node_t *parse_continue(); // continue文
node_t *parse_print(); // 組み込み関数print(式)
node_t *parse_scan(); // 組み込み関数scan(&変数)
node_t *parse_expr_stmt(); // 式文 (式 ;)
// 式解析メソッド群
// 優先順位の低い演算子ほど浅い関数が担当し，下記の順に呼び出しが連鎖する．
// parse_expr → parse_assign → parse_ternary → parse_binary → parse_unary → parse_postfix → parse_primary
// 各関数は「自分の担当演算子を含むかもしれない式」を解析する．
// 担当演算子が見つかればノードを作って包み，なければ下位の解析結果をそのまま返す(パススルー)．
// つまり各関数が返す木のルートは「担当演算子か，それより優先順位の高いもの」のいずれかであり，
// 自分より優先順位の低い演算子がルートになることはない(それは呼び出し元の浅い関数が担当する)．
node_t *parse_expr(); // 式 (エントリポイント)
node_t *parse_assign(); // 代入式 x = 式, x += 式 等
node_t *parse_ternary(); // 三項演算子 a ? b : c
node_t *parse_binary(int min_prec); // 二項演算子を含む式 (優先順位min_prec以上を処理)
node_t *parse_unary(); // 前置単項演算子を含む式
node_t *parse_postfix(); // 後置演算子・関数呼び出しを含む式
node_t *parse_primary(); // 基本式 (リテラル・変数参照・括弧式)
};
parser.cpp
#include <map>
#include "parser.hpp"
// 二項演算子の優先順位表 (数値が大きいほど強く結合する)
const std::map<token_kind_t, int> g_binop_prec = {
{TK_PIPEPIPE, 1}, // ||
{TK_AMPAMP, 2}, // &&
{TK_PIPE, 3}, // |
{TK_CARET, 4}, // ^
{TK_AMP, 5}, // &
{TK_EQEQ, 6}, {TK_NEQ, 6}, // == !=
{TK_LT, 7}, {TK_GT, 7}, {TK_LEQ, 7}, {TK_GEQ, 7}, // < > <= >=
{TK_LSHIFT, 8}, {TK_RSHIFT, 8}, // << >>
{TK_PLUS, 9}, {TK_MINUS, 9}, // + -
{TK_STAR, 10}, {TK_SLASH, 10}, {TK_PERCENT, 10}, // * / %
};
// コンストラクタ: トークン列を受け取り，読み取り位置を初期化する
Parser::Parser(const std::vector<token_t> &tokens)
: tokens_(tokens), pos_(0) {}
// 構文解析を実行してASTのルートを返す
node_t *Parser::operator()() {
return this->parse_program();
}
// 現在のトークンを覗き見る (posを進めない)
const token_t &Parser::peek_token() const {
return this->tokens_[this->pos_];
}
// 現在のトークンの種別が一致するか調べる (消費しない)
bool Parser::token_kind_is(token_kind_t kind) const {
return this->tokens_[this->pos_].kind == kind;
}
// トークンを取得して進める (検証なし)
token_t Parser::get_token() {
return this->tokens_[this->pos_++];
}
// 指定種別のトークンを取得して進める，違えばエラーを投げる
token_t Parser::get_token(token_kind_t kind) {
const token_t &actual = this->tokens_[this->pos_];
if (actual.kind != kind) {
// EOFはvalueが空文字列のため，EOFであることを明示した表示にする
const std::string actual_name = (actual.kind == TK_EOF) ? "EOF" : "'" + actual.value + "'";
throw std::string("compiler error: expected ") + Parser::token_kind_name(kind)
+ " but got " + actual_name
+ " at line " + std::to_string(actual.line);
}
return this->tokens_[this->pos_++];
}
// 現在のトークンの行番号でASTノードを生成する
node_t *Parser::new_node(node_kind_t kind) {
node_t *node = new node_t;
node->kind = kind;
node->line = this->peek_token().line;
node->ival = 0;
return node;
}
// 型の先頭になりうるトークン種別かどうか返す
bool Parser::is_type_start(token_kind_t kind) {
return kind == TK_INT || kind == TK_CHAR || kind == TK_SHORT
|| kind == TK_SIGNED || kind == TK_UNSIGNED;
}
// 代入演算子のトークン種別かどうか返す
bool Parser::is_assign_op(token_kind_t kind) {
return kind == TK_ASSIGN
|| kind == TK_PLUS_ASSIGN || kind == TK_MINUS_ASSIGN
|| kind == TK_STAR_ASSIGN || kind == TK_SLASH_ASSIGN || kind == TK_PCT_ASSIGN
|| kind == TK_AMP_ASSIGN || kind == TK_PIPE_ASSIGN || kind == TK_CARET_ASSIGN
|| kind == TK_LSHIFT_ASSIGN || kind == TK_RSHIFT_ASSIGN;
}
// トークン種別をエラーメッセージ用の文字列に変換する
std::string Parser::token_kind_name(token_kind_t kind) {
switch (kind) {
case TK_SEMICOLON: return "';'";
case TK_LPAREN: return "'('";
case TK_RPAREN: return "')'";
case TK_LBRACE: return "'{'";
case TK_RBRACE: return "'}'";
case TK_VOID: return "'void'";
case TK_IDENT: return "identifier";
case TK_EOF: return "EOF";
default: return "token";
}
}
// プログラム全体を解析してND_PROGRAMを返す
// 単なるトークン列を木構造に起こして返す
node_t *Parser::parse_program() {
node_t *node = this->new_node(ND_PROGRAM); // 木構造のルート
//
// メンバ変数にトークン列を持つ
// これを前から順番に呼んでいきながら，
// 木構造に起こして上記node変数に格納していく
//
// ファイル終端まで繰り返す
while (!this->token_kind_is(TK_EOF)) {
// 関数定義なら関数追加(返り値はvoid固定)
if (this->token_kind_is(TK_VOID)) {
node->children.push_back(this->parse_func_def());
}
// グローバル変数宣言なら変数追加
else if (Parser::is_type_start(this->peek_token().kind)) {
node->children.push_back(this->parse_var_decl());
}
// それ以外がファイル直下にあるならエラー
else {
throw std::string("compiler error: expected function or variable declaration at line ")
+ std::to_string(this->peek_token().line);
}
}
return node;
}
// 関数定義を解析してND_FUNC_DEFを返す
// 構文: void 関数名(void) ブロック
node_t *Parser::parse_func_def() {
node_t *node = this->new_node(ND_FUNC_DEF); // 関数ノード
// 関数の基本的な情報
this->get_token(TK_VOID); // 返り値(void固定)
node->sval = this->get_token(TK_IDENT).value; // 関数名
this->get_token(TK_LPAREN); // 開きカッコ
this->get_token(TK_VOID); // 引数(void固定)
this->get_token(TK_RPAREN); // 閉じ括弧
// 関数の中身を追加する
node->children.push_back(this->parse_block());
return node;
}
// ブロックを解析してND_BLOCKを返す
// 構文: { 文... }
node_t *Parser::parse_block() {
node_t *node = this->new_node(ND_BLOCK); // ブロックのルート
// 開き波括弧
this->get_token(TK_LBRACE);
// } が来るまで文を繰り返し読む
while (!this->token_kind_is(TK_RBRACE) && !this->token_kind_is(TK_EOF)) {
node->children.push_back(this->parse_stmt());
}
// 閉じ波括弧
this->get_token(TK_RBRACE);
return node;
}
// 文を解析してASTノードを返す
node_t *Parser::parse_stmt() {
// 型キーワードで始まれば変数宣言
if (Parser::is_type_start(this->peek_token().kind)) {
return this->parse_var_decl();
}
// ブロック { ... }
if (this->token_kind_is(TK_LBRACE)) {
return this->parse_block();
}
// return文
if (this->token_kind_is(TK_RETURN)) {
return this->parse_return();
}
// if文
if (this->token_kind_is(TK_IF)) {
return this->parse_if();
}
// while文
if (this->token_kind_is(TK_WHILE)) {
return this->parse_while();
}
// for文
if (this->token_kind_is(TK_FOR)) {
return this->parse_for();
}
// do-while文
if (this->token_kind_is(TK_DO)) {
return this->parse_do_while();
}
// switch文
if (this->token_kind_is(TK_SWITCH)) {
return this->parse_switch();
}
// break文
if (this->token_kind_is(TK_BREAK)) {
return this->parse_break();
}
// continue文
if (this->token_kind_is(TK_CONTINUE)) {
return this->parse_continue();
}
// 空文 ; (何もしない文．空ブロックとして表現する)
if (this->token_kind_is(TK_SEMICOLON)) {
node_t *node = this->new_node(ND_BLOCK);
this->get_token(TK_SEMICOLON);
return node;
}
// それ以外は式文 (式 ;)
return this->parse_expr_stmt();
}
// return文を解析してND_RETURNを返す
// 構文: return ; (値を返すreturnには非対応)
node_t *Parser::parse_return() {
node_t *node = this->new_node(ND_RETURN);
this->get_token(TK_RETURN);
this->get_token(TK_SEMICOLON);
return node;
}
// 式文を解析する
// 構文: 式 ;
node_t *Parser::parse_expr_stmt() {
node_t *node = this->parse_expr();
this->get_token(TK_SEMICOLON);
return node;
}
// if文を解析してND_IFを返す
// 構文: if ( 条件 ) 文 [else 文] (本体は単文でもブロックでも可)
// 子ノードは [条件, then節] または [条件, then節, else節]
node_t *Parser::parse_if() {
node_t *node = this->new_node(ND_IF);
this->get_token(TK_IF);
this->get_token(TK_LPAREN);
node->children.push_back(this->parse_expr()); // 条件
this->get_token(TK_RPAREN);
node->children.push_back(this->parse_stmt()); // then節
// elseがあれば読む (else直後にifが来ればelse ifの連鎖になる)
if (this->token_kind_is(TK_ELSE)) {
this->get_token(TK_ELSE);
node->children.push_back(this->parse_stmt()); // else節
}
return node;
}
// while文を解析してND_WHILEを返す
// 構文: while ( 条件 ) 文 (本体は単文でもブロックでも可)
// 子ノードは [条件, 本体]
node_t *Parser::parse_while() {
node_t *node = this->new_node(ND_WHILE);
this->get_token(TK_WHILE);
this->get_token(TK_LPAREN);
node->children.push_back(this->parse_expr()); // 条件
this->get_token(TK_RPAREN);
node->children.push_back(this->parse_stmt()); // 本体
return node;
}
// for文を解析してND_FORを返す
// 構文: for ( 初期化; 条件; 更新 ) 文 (各部は省略可能，本体は単文でもブロックでも可)
// 子ノードは [初期化, 条件, 更新, 本体]．省略された部分はnullptrを入れて常に4子に固定する
node_t *Parser::parse_for() {
node_t *node = this->new_node(ND_FOR);
this->get_token(TK_FOR);
this->get_token(TK_LPAREN);
// 初期化部: 型で始まれば変数宣言(；まで消費)，空なら nullptr，それ以外は式
if (this->token_kind_is(TK_SEMICOLON)) {
node->children.push_back(nullptr);
this->get_token(TK_SEMICOLON);
} else if (Parser::is_type_start(this->peek_token().kind)) {
node->children.push_back(this->parse_var_decl()); // 末尾の ; まで消費する
} else {
node->children.push_back(this->parse_expr());
this->get_token(TK_SEMICOLON);
}
// 条件部: 空なら nullptr
if (this->token_kind_is(TK_SEMICOLON)) {
node->children.push_back(nullptr);
} else {
node->children.push_back(this->parse_expr());
}
this->get_token(TK_SEMICOLON);
// 更新部: 空なら nullptr
if (this->token_kind_is(TK_RPAREN)) {
node->children.push_back(nullptr);
} else {
node->children.push_back(this->parse_expr());
}
this->get_token(TK_RPAREN);
// 本体
node->children.push_back(this->parse_stmt());
return node;
}
// do-while文を解析してND_DO_WHILEを返す
// 構文: do 文 while ( 条件 ) ; (本体は単文でもブロックでも可)
// 子ノードは [本体, 条件]
node_t *Parser::parse_do_while() {
node_t *node = this->new_node(ND_DO_WHILE);
this->get_token(TK_DO);
node->children.push_back(this->parse_stmt()); // 本体
this->get_token(TK_WHILE);
this->get_token(TK_LPAREN);
node->children.push_back(this->parse_expr()); // 条件
this->get_token(TK_RPAREN);
this->get_token(TK_SEMICOLON);
return node;
}
// switch文を解析してND_SWITCHを返す
// 構文: switch ( 条件 ) { case節・default節・文を並べる }
// 子ノードは [条件式, 本体の文とcase/defaultラベルを平坦に並べたもの]
// case/defaultはラベルとして文の列に混ざる(フォールスルーをそのまま表現するため)
node_t *Parser::parse_switch() {
node_t *node = this->new_node(ND_SWITCH);
this->get_token(TK_SWITCH);
this->get_token(TK_LPAREN);
node->children.push_back(this->parse_expr()); // 条件式
this->get_token(TK_RPAREN);
this->get_token(TK_LBRACE);
// } までcase節・default節・文を平坦に読む
while (!this->token_kind_is(TK_RBRACE) && !this->token_kind_is(TK_EOF)) {
if (this->token_kind_is(TK_CASE)) {
node->children.push_back(this->parse_case());
} else if (this->token_kind_is(TK_DEFAULT)) {
node->children.push_back(this->parse_default());
} else {
node->children.push_back(this->parse_stmt());
}
}
this->get_token(TK_RBRACE);
return node;
}
// case節を解析してND_CASEを返す
// 構文: case 定数式 : (値は子ノードの式．意味解析で定数畳み込みする)
node_t *Parser::parse_case() {
node_t *node = this->new_node(ND_CASE);
this->get_token(TK_CASE);
node->children.push_back(this->parse_expr()); // caseの値 (定数式)
this->get_token(TK_COLON);
return node;
}
// default節を解析してND_DEFAULTを返す
// 構文: default :
node_t *Parser::parse_default() {
node_t *node = this->new_node(ND_DEFAULT);
this->get_token(TK_DEFAULT);
this->get_token(TK_COLON);
return node;
}
// break文を解析してND_BREAKを返す
// 構文: break ;
node_t *Parser::parse_break() {
node_t *node = this->new_node(ND_BREAK);
this->get_token(TK_BREAK);
this->get_token(TK_SEMICOLON);
return node;
}
// continue文を解析してND_CONTINUEを返す
// 構文: continue ;
node_t *Parser::parse_continue() {
node_t *node = this->new_node(ND_CONTINUE);
this->get_token(TK_CONTINUE);
this->get_token(TK_SEMICOLON);
return node;
}
// 組み込み関数printを解析してND_PRINTを返す
// 構文: print ( 式 )
node_t *Parser::parse_print() {
node_t *node = this->new_node(ND_PRINT);
this->get_token(TK_IDENT); // print
this->get_token(TK_LPAREN); // (
node->children.push_back(this->parse_expr()); // 出力する式
this->get_token(TK_RPAREN); // )
return node;
}
// 組み込み関数scanを解析してND_SCANを返す
// 構文: scan ( & 変数 ) ※ & はscan専用の特殊構文 (一般のポインタ演算子ではない)
node_t *Parser::parse_scan() {
node_t *node = this->new_node(ND_SCAN);
this->get_token(TK_IDENT); // scan
this->get_token(TK_LPAREN); // (
this->get_token(TK_AMP); // & (格納先を指す専用構文)
node_t *var = this->new_node(ND_VAR); // 格納先変数
var->sval = this->get_token(TK_IDENT).value;
node->children.push_back(var);
this->get_token(TK_RPAREN); // )
return node;
}
// 変数宣言を解析してND_VAR_DECLを返す
// 構文: [signed|unsigned] 型 変数名 [= 式] ;
node_t *Parser::parse_var_decl() {
node_t *node = this->new_node(ND_VAR_DECL); // 変数宣言部
// signed/unsigned 修飾子を読む (デフォルトは signed)
// unsignedは予約語として受理するが当面未対応 (将来対応予定．is_signed等の符号情報の機構は残してある)
bool is_signed = true;
if (this->token_kind_is(TK_SIGNED)) {
this->get_token();
} else if (this->token_kind_is(TK_UNSIGNED)) {
// this->get_token();
// is_signed = false;
throw std::string("compiler error: 'unsigned' is not supported yet at line ")
+ std::to_string(this->peek_token().line);
}
// 型キーワードを読む
base_type_t base;
const token_kind_t base_kind = this->peek_token().kind;
if (base_kind == TK_INT) { base = BASE_INT; this->get_token(); }
else if (base_kind == TK_CHAR) { base = BASE_CHAR; this->get_token(); }
else if (base_kind == TK_SHORT) { base = BASE_SHORT; this->get_token(); }
else {
throw std::string("compiler error: expected type at line ")
+ std::to_string(this->peek_token().line);
}
// 型情報と符号情報を保存
node->type = {base, is_signed};
// 変数名を読む
node->sval = this->get_token(TK_IDENT).value;
// 初期化式があれば読む
if (this->token_kind_is(TK_ASSIGN)) {
this->get_token();
node->children.push_back(this->parse_expr());
}
// 文末のセミコロン
this->get_token(TK_SEMICOLON);
return node;
}
// 式を解析してASTノードを返す
node_t *Parser::parse_expr() {
// 最も優先順位の低い代入式から解析を開始する
return this->parse_assign();
}
// 代入式 x = 式 (複合代入含む) を解析してASTノードを返す
// まず三項演算子以下の式として解析し，後ろに代入演算子が来ていたら代入式と判断する
node_t *Parser::parse_assign() {
node_t *left = this->parse_ternary();
// 代入演算子が来なければ代入式ではないのでそのまま返す(パススルー)
if (!Parser::is_assign_op(this->peek_token().kind)) {
return left;
}
// 代入式として処理する (右辺は再帰解析により右結合になる)
// 左辺が代入できない式((a?b:c)=1 や (1+2)=x 等)でも，ここでは構文として通す．
// 左辺が代入可能か(変数か)の検査は意味解析(analyze_exprのND_ASSIGN)に委ねる
const token_t op = this->get_token();
node_t *node = this->new_node(ND_ASSIGN);
node->line = op.line; // 演算子の行番号を使う
node->sval = op.value; // 演算子の文字列 ("=", "+=" 等)
node->children = {left, this->parse_assign()};
return node;
}
// 三項演算子 a ? b : c を解析してASTノードを返す
// まず二項演算子の式として解析し，後ろに?が来ていたら三項演算子と判断する
node_t *Parser::parse_ternary() {
node_t *cond = this->parse_binary(0);
// ?が来なければ三項演算子ではないのでそのまま返す(パススルー)
if (!this->token_kind_is(TK_QUESTION)) {
return cond;
}
// 三項演算子として処理する (then/elseは再帰解析により右結合になる)
node_t *node = this->new_node(ND_TERNARY);
this->get_token(); // ? を消費
node_t *then_expr = this->parse_ternary(); // then節
this->get_token(TK_COLON); // : を消費
node_t *else_expr = this->parse_ternary(); // else節
node->children = {cond, then_expr, else_expr};
return node;
}
// 二項演算子を含む式を解析してASTノードを返す (優先順位min_prec以上の演算子を処理)
// 優先順位climbing法: 左辺を解析した後，min_prec以上の優先順位を持つ演算子が
// 続く限り読み進め，右辺は「演算子の優先順位+1」で再帰させることで左結合にする
node_t *Parser::parse_binary(int min_prec) {
node_t *left = this->parse_unary();
while (true) {
// 現在のトークンが二項演算子か，優先順位表で調べる
const auto it = g_binop_prec.find(this->peek_token().kind);
// 優先順位表にないか，優先順位が探索対象の最低ラインよりも低いならスルー(ネストしない)
if (it == g_binop_prec.end() || it->second < min_prec) break;
// 演算子トークンを取得する
const token_t op = this->get_token();
// 右辺を「この演算子の優先順位+1」で解析する (左結合)
node_t *right = this->parse_binary(it->second + 1);
// 二項演算ノードにまとめ，新しい左辺とする
node_t *node = this->new_node(ND_BINOP);
node->line = op.line; // 演算子の行番号を使う
node->sval = op.value; // 演算子の文字列
node->children = { left, right };
left = node;
}
return left;
}
// 前置単項演算子を含む式を解析してASTノードを返す
// 演算子があれば消費してオペランドを再帰的に解析する
// (!!x や +-x のような連続にも対応するため．また，前置演算子と後置演算子が両方ついていた場合に対応するため)
node_t *Parser::parse_unary() {
// 前置単項演算子かどうか調べる
const token_kind_t kind = this->peek_token().kind;
if (kind == TK_MINUS || kind == TK_PLUS
|| kind == TK_BANG || kind == TK_TILDE
|| kind == TK_PLUSPLUS || kind == TK_MINUSMINUS) {
const token_t op = this->get_token();
node_t *node = this->new_node(ND_UNOP);
node->line = op.line;
node->sval = op.value;
node->children = { this->parse_unary() }; // オペランドを再帰解析
return node;
}
// 前置演算子でなければ後置演算子・関数呼び出しの解析に委譲する
return this->parse_postfix();
}
// 後置演算子・関数呼び出しを解析してASTノードを返す
node_t *Parser::parse_postfix() {
node_t *node = this->parse_primary();
// 後置インクリメント・デクリメント
if (this->token_kind_is(TK_PLUSPLUS) || this->token_kind_is(TK_MINUSMINUS)) {
const token_t op = this->get_token();
node_t *post = this->new_node(ND_POST_UNOP);
post->line = op.line;
post->sval = op.value;
post->children = { node };
return post;
}
// 関数呼び出し: void func(void) 形式のみ対応するため引数なし
if (this->token_kind_is(TK_LPAREN)) {
this->get_token(); // (
this->get_token(TK_RPAREN); // )
node_t *call = this->new_node(ND_CALL);
call->line = node->line;
call->sval = node->sval; // 関数名
return call;
}
return node;
}
// 基本式を解析してASTノードを返す
// 対応するもの: 整数リテラル・文字リテラル・変数参照・括弧式
node_t *Parser::parse_primary() {
// 整数リテラル
if (this->token_kind_is(TK_INT_LIT)) {
node_t *node = this->new_node(ND_INT_LIT);
node->ival = Parser::parse_int_literal(this->get_token().value);
return node;
}
// 文字リテラル
if (this->token_kind_is(TK_CHAR_LIT)) {
node_t *node = this->new_node(ND_CHAR_LIT);
node->ival = Parser::parse_char_literal(this->get_token().value);
return node;
}
// 変数参照・組み込み関数呼び出し
if (this->token_kind_is(TK_IDENT)) {
// 組み込み関数 print/scan は引数を取る専用構文として解析する
const std::string &name = this->peek_token().value;
if (name == "print") return this->parse_print();
if (name == "scan") return this->parse_scan();
node_t *node = this->new_node(ND_VAR);
node->sval = this->get_token().value;
return node;
}
// 括弧式: ( 式 )
if (this->token_kind_is(TK_LPAREN)) {
this->get_token();
node_t *node = this->parse_expr();
this->get_token(TK_RPAREN);
return node;
}
throw std::string("compiler error: expected expression but got '")
+ this->peek_token().value + "' at line " + std::to_string(this->peek_token().line);
}
// 整数リテラル文字列を数値に変換する (0x/0X接頭辞があれば16進数，無ければ10進数)
long long Parser::parse_int_literal(const std::string &text) {
if (text.size() >= 2 && text[0] == '0' && (text[1] == 'x' || text[1] == 'X')) {
return std::stoll(text.substr(2), nullptr, 16);
}
return std::stoll(text, nullptr, 10);
}
// 文字リテラル文字列 ('a' や '\n' 等) を文字コードに変換する
long long Parser::parse_char_literal(const std::string &text) {
// 引用符を取り除いた中身を取得する
const std::string content = text.substr(1, text.size() - 2);
// エスケープシーケンスでなければそのままの文字コードを返す
if (content.size() == 1) {
return static_cast<unsigned char>(content[0]);
}
// エスケープシーケンスを変換する
switch (content[1]) {
case 'n': return '\n';
case 't': return '\t';
case 'r': return '\r';
case '0': return '\0';
case '\\': return '\\';
case '\'': return '\'';
case '"': return '"';
default: return static_cast<unsigned char>(content[1]);
}
}
意味解析
大層なことを言っていますが，やりたいこととしては変数とメモリ番地を対応付けることです．
今までは変数の名前はただの名前でした．
しかしこれをアセンブリ言語にするには実際のアドレスに変換する必要があるわけで，その変換処理を行うのがこの段階です．
変数名と番地の対応表を作ります．
また，このプログラミング言語には組み込み変数があります．
LEDを制御したりボタンから値を取得してくるのは，この言語では組み込み変数の値を直接読み書きすることで行います．
それら組み込み変数を実際のレジスタの番地と対応付けることもこの段階で行います．
ちなみに，実際のプログラムではグローバル変数は相対アドレスで指定されますが，現在僕が作っているPCにはそもそも相対アドレスに対応する仕組みがないので絶対アドレスとします．
ただし，ローカル変数はSPからの相対パスになります．
ちなみに，以下の二段階で進めていきます．
- ルート階層に宣言されている変数(グローバル変数)と関数を走査する．この言語では，宣言の順序は関係ない(C言語のような，使用する前に宣言しておかなければならないみたいな制限は存在しない)
- ローカル変数を走査する
あと知らなかったので追記するんですが，ここでやるべき仕事は変数とメモリ番地の対応付けだけではありません．
構文の正しさについてもある程度は確認する必要があります．
例えば，continueが書かれているのがちゃんとループの中なのか，など．
analyzer
analyzer.hpp
#pragma once
#include <map>
#include <set>
#include <string>
#include <vector>
#include "parser.hpp"
// 変数の置き場所の種別
typedef enum {
LOC_REGISTER, // レジスタ直結 (LED等のハードウェア変数)
LOC_GLOBAL, // メモリ上の絶対番地 (グローバル変数)
LOC_LOCAL, // 関数ローカルなメモリ領域 (現状は静的割り当ての固定番地，将来は相対アドレス)
} location_t;
// シンボル情報
struct symbol_t {
std::string name; // 変数名
type_t type; // 型情報
location_t location; // 置き場所の種別
int address; // レジスタ番地 / メモリ絶対番地 / SPオフセット (locationに応じて解釈)
bool readable; // 読み込み可能かどうか (falseの参照はコンパイルエラー)
bool writable; // 書き込み可能かどうか (falseへの代入はコンパイルエラー)
};
// ASTを受け取り，意味検査とシンボルテーブル構築を行うアナライザ
class Analyzer {
public:
explicit Analyzer(node_t *root);
std::map<std::string, const symbol_t *> operator()(); // 意味解析を実行してシンボルテーブルを返す
private:
node_t *root_; // AST
std::map<std::string, const symbol_t *> symbols_; // シンボルテーブル (変数名→保存先番地等の対応表)
std::set<std::string> func_names_; // 定義済み関数名の集合
int next_addr_; // 次に割り当てるメモリ番地 (グローバル→ローカルで連番)
std::vector<std::map<std::string, const symbol_t *>> scopes_; // ローカル変数のスコープスタック (内側ほど後ろ)
int loop_depth_ = 0; // ループの入れ子の深さ (break/continueの検査用)
int switch_depth_ = 0; // switchの入れ子の深さ (breakの検査用)
// 解析メソッド
void collect_globals(); // 1パス目: グローバル変数の登録と関数名の収集
static long long eval_const_expr(const node_t *expr); // グローバル変数の初期化式を計算する
void analyze_functions(); // 2パス目: 各関数本体を検査する
void analyze_block(node_t *block); // ブロックを検査する (新しいスコープを積む)
void analyze_stmt(node_t *stmt); // 文を検査する
void analyze_switch(node_t *stmt); // switch文を検査する
void analyze_local_decl(node_t *decl); // ローカル変数宣言を検査し登録する
void analyze_expr(node_t *expr); // 式を検査し名前解決・型注釈する
const symbol_t *lookup_symbol(const std::string &name) const; // 名前からシンボルを探す (スコープ→グローバル)
};
analyzer.cpp
#include <vector>
#include "analyzer.hpp"
// グローバル変数の配置開始アドレス (1変数=1ワード(4バイト)で順次割り当てる)
static const int g_global_base_addr = 0x0000000;
// ハードウェア変数の定義表 (ボードI/Oレジスタのみ公開，CPU内部レジスタは非公開)
// 読み書き可否はハードウェア実装(mypc/alu.svh)に従う．型は全てunsigned int扱い
static const std::vector<symbol_t> g_hw_vars = {
// 名前 型 置き場所 番地 読み 書き
{"BTN", {BASE_INT, false}, LOC_REGISTER, 0x20, true, false}, // タクトスイッチ
{"DIPSW", {BASE_INT, false}, LOC_REGISTER, 0x21, true, false}, // DIPスイッチ
{"LED", {BASE_INT, false}, LOC_REGISTER, 0x22, false, true}, // LED
{"RGBLED", {BASE_INT, false}, LOC_REGISTER, 0x23, false, true}, // RGB LED
{"PMOD_A", {BASE_INT, false}, LOC_REGISTER, 0x24, true, true}, // Pmod A
{"PMOD_B", {BASE_INT, false}, LOC_REGISTER, 0x25, true, true}, // Pmod B
{"AR8_13", {BASE_INT, false}, LOC_REGISTER, 0x26, true, true}, // Arduinoピン AR8～AR13
{"AR_I2C", {BASE_INT, false}, LOC_REGISTER, 0x27, true, true}, // A，AR_SDA，AR_SCL
{"AR0_7", {BASE_INT, false}, LOC_REGISTER, 0x28, true, true}, // Arduinoピン AR0～AR7
{"AR_RST", {BASE_INT, false}, LOC_REGISTER, 0x29, true, false}, // Arduinoリセット
{"AR_SPI", {BASE_INT, false}, LOC_REGISTER, 0x2a, true, true}, // AR_MISO，AR_SCK，AR_MOSI，AR_SS
{"GPIO0_7", {BASE_INT, false}, LOC_REGISTER, 0x2d, true, true}, // GPIO0～7
{"GPIO8_15", {BASE_INT, false}, LOC_REGISTER, 0x2e, true, true}, // GPIO8～15
{"GPIO16_23", {BASE_INT, false}, LOC_REGISTER, 0x2f, true, true}, // GPIO16～23
{"GPIO24_27", {BASE_INT, false}, LOC_REGISTER, 0x30, true, true}, // GPIO24～27
};
// コンストラクタ: ASTを受け取る
Analyzer::Analyzer(node_t *root) : root_(root), next_addr_(g_global_base_addr) {}
// 意味解析を実行してシンボルテーブルを返す
std::map<std::string, const symbol_t *> Analyzer::operator()() {
// ハードウェア変数をあらかじめシンボルテーブルに登録する (静的領域の実体を直接指す)
for (const symbol_t &hw : g_hw_vars) {
this->symbols_[hw.name] = &hw;
}
// 1パス目: グローバル変数の登録と関数名の収集を行う
this->collect_globals();
// プログラムの開始点となるmain関数が必要
if (this->func_names_.find("main") == this->func_names_.end()) {
throw std::string("compiler error: 'main' function is not defined");
}
// 2パス目: 各関数本体を検査する
this->analyze_functions();
return this->symbols_;
}
// 1パス目: プログラム直下を走査し，グローバル変数の登録と関数名の収集を行う
// 先に全グローバルを登録することで，関数本体からの前方参照(後ろで宣言された変数の使用)を可能にする
void Analyzer::collect_globals() {
for (node_t *child : this->root_->children) {
// 名前の重複チェック (変数・関数・ハードウェア変数の全てと衝突しないこと)
if (this->symbols_.count(child->sval) || this->func_names_.count(child->sval)) {
throw std::string("compiler error: redefinition of '") + child->sval
+ "' at line " + std::to_string(child->line);
}
// グローバル変数宣言: 初期化子を評価し，アドレスを割り当てて登録する
if (child->kind == ND_VAR_DECL) {
// 初期化子があればコンパイル時に計算し，結果のリテラルノードに置き換える(定数畳み込み)
if (!child->children.empty()) {
node_t *folded = new node_t;
folded->kind = ND_INT_LIT;
folded->ival = Analyzer::eval_const_expr(child->children[0]);
folded->line = child->children[0]->line;
// 差し替え前の旧部分木はあえて解放しない
// (ASTは全ノードをdeleteせず，プロセス終了時のOS回収に任せる方針のため)
child->children[0] = folded; // 初期化式の子要素を計算済みのリテラルで更新する
}
// ソース宣言のグローバル変数はnewでヒープ確保し解放しない
symbol_t *sym =
new symbol_t{child->sval, child->type, LOC_GLOBAL, this->next_addr_, true, true};
this->symbols_[child->sval] = sym;
child->sym = sym; // 宣言ノード自身もシンボルを指す (コード生成でアドレス参照に使う)
this->next_addr_ += 4; // 型に関係なく1変数=1ワード(4バイト)使う
}
// 関数定義: 関数名を集合に追加する
else if (child->kind == ND_FUNC_DEF) {
this->func_names_.insert(child->sval);
}
}
}
// グローバル変数の初期化式(定数式)をコンパイル時に計算して値を返す (定数畳み込み)
// 変数参照や関数呼び出しなど，コンパイル時に値が確定しない式を含む場合はエラー
long long Analyzer::eval_const_expr(const node_t *expr) {
// リテラルはそのまま値を返す
if (expr->kind == ND_INT_LIT || expr->kind == ND_CHAR_LIT) {
return expr->ival;
}
// 前置単項演算
if (expr->kind == ND_UNOP) {
const long long v = Analyzer::eval_const_expr(expr->children[0]);
if (expr->sval == "-") return -v;
else if (expr->sval == "+") return v;
else if (expr->sval == "~") return ~v;
else if (expr->sval == "!") return (v == 0) ? 1 : 0;
// ++/-- は変数にしか使えないので定数式では不可 (下のエラーに落ちる)
}
// 二項演算
if (expr->kind == ND_BINOP) {
const long long l = Analyzer::eval_const_expr(expr->children[0]);
const long long r = Analyzer::eval_const_expr(expr->children[1]);
// ゼロ除算はコンパイル時に検出する
if ((expr->sval == "/" || expr->sval == "%") && r == 0) {
throw std::string("compiler error: division by zero at line ")
+ std::to_string(expr->line);
}
if (expr->sval == "+") return l + r;
else if (expr->sval == "-") return l - r;
else if (expr->sval == "*") return l * r;
else if (expr->sval == "/") return l / r;
else if (expr->sval == "%") return l % r;
else if (expr->sval == "&") return l & r;
else if (expr->sval == "|") return l | r;
else if (expr->sval == "^") return l ^ r;
else if (expr->sval == "<<") return l << r;
else if (expr->sval == ">>") return l >> r;
else if (expr->sval == "&&") return (l != 0 && r != 0) ? 1 : 0;
else if (expr->sval == "||") return (l != 0 || r != 0) ? 1 : 0;
else if (expr->sval == "==") return (l == r) ? 1 : 0;
else if (expr->sval == "!=") return (l != r) ? 1 : 0;
else if (expr->sval == "<") return (l < r) ? 1 : 0;
else if (expr->sval == ">") return (l > r) ? 1 : 0;
else if (expr->sval == "<=") return (l <= r) ? 1 : 0;
else if (expr->sval == ">=") return (l >= r) ? 1 : 0;
}
// 三項演算
if (expr->kind == ND_TERNARY) {
return Analyzer::eval_const_expr(expr->children[0])
? Analyzer::eval_const_expr(expr->children[1])
: Analyzer::eval_const_expr(expr->children[2]);
}
// 変数参照・関数呼び出し等はコンパイル時に値が確定しないのでエラー
throw std::string("compiler error: global variable initializer must be a constant expression at line ")
+ std::to_string(expr->line);
}
// 2パス目: 各関数本体を検査する
void Analyzer::analyze_functions() {
for (node_t *child : this->root_->children) {
if (child->kind != ND_FUNC_DEF) continue;
// 関数本体ブロック(children[0])を検査する
// TODO: 関数呼び出しが式文として書けるようになったら再帰呼び出しを検出してエラーにする
this->analyze_block(child->children[0]);
}
}
// ブロックを検査する (新しいローカルスコープを積み，抜けるときに捨てる)
void Analyzer::analyze_block(node_t *block) {
this->scopes_.push_back({}); // 新しいスコープを積む
for (node_t *stmt : block->children) {
this->analyze_stmt(stmt);
}
this->scopes_.pop_back(); // スコープを捨てる
}
// 文を検査する
void Analyzer::analyze_stmt(node_t *stmt) {
// 変数宣言
if (stmt->kind == ND_VAR_DECL) {
this->analyze_local_decl(stmt);
}
// ブロック (入れ子の { ... })
else if (stmt->kind == ND_BLOCK) {
this->analyze_block(stmt);
}
// return文 (値なしなので検査するものはない)
else if (stmt->kind == ND_RETURN) {
// 何もしない
}
// if文 (children: 条件, then節, [else節])
else if (stmt->kind == ND_IF) {
this->analyze_expr(stmt->children[0]); // 条件
this->analyze_stmt(stmt->children[1]); // then節
if (stmt->children.size() == 3) {
this->analyze_stmt(stmt->children[2]); // else節
}
}
// while文 (children: 条件, 本体)
else if (stmt->kind == ND_WHILE) {
this->analyze_expr(stmt->children[0]); // 条件
this->loop_depth_++;
this->analyze_stmt(stmt->children[1]); // 本体
this->loop_depth_--;
}
// for文 (children: 初期化, 条件, 更新, 本体．省略された部分はnullptr)
else if (stmt->kind == ND_FOR) {
// for全体で1つのスコープを張る (初期化部で宣言した変数を条件・更新・本体から見えるようにする)
this->scopes_.push_back({});
if (stmt->children[0]) this->analyze_stmt(stmt->children[0]); // 初期化
if (stmt->children[1]) this->analyze_expr(stmt->children[1]); // 条件
if (stmt->children[2]) this->analyze_expr(stmt->children[2]); // 更新
this->loop_depth_++;
this->analyze_stmt(stmt->children[3]); // 本体
this->loop_depth_--;
this->scopes_.pop_back();
}
// do-while文 (children: 本体, 条件)
else if (stmt->kind == ND_DO_WHILE) {
this->loop_depth_++;
this->analyze_stmt(stmt->children[0]); // 本体
this->loop_depth_--;
this->analyze_expr(stmt->children[1]); // 条件
}
// switch文
else if (stmt->kind == ND_SWITCH) {
this->analyze_switch(stmt);
}
// break文 (ループまたはswitchの中でのみ許される)
else if (stmt->kind == ND_BREAK) {
if (this->loop_depth_ == 0 && this->switch_depth_ == 0) {
throw std::string("compiler error: 'break' outside loop or switch at line ")
+ std::to_string(stmt->line);
}
}
// continue文 (ループの中でのみ許される)
else if (stmt->kind == ND_CONTINUE) {
if (this->loop_depth_ == 0) {
throw std::string("compiler error: 'continue' outside loop at line ")
+ std::to_string(stmt->line);
}
}
// それ以外は式文として検査する
else {
this->analyze_expr(stmt);
}
}
// switch文を検査する (children: 条件式, 本体の文とcase/defaultラベルが平坦に並ぶ)
void Analyzer::analyze_switch(node_t *stmt) {
this->analyze_expr(stmt->children[0]); // 条件式
this->switch_depth_++; // switchの中ではbreakが許される
this->scopes_.push_back({}); // switch本体のスコープ
std::set<long long> case_values; // case値の重複検出用
bool has_default = false; // defaultの重複検出用
// 本体(children[1..])を順に検査する
for (size_t i = 1; i < stmt->children.size(); i++) {
node_t *child = stmt->children[i];
// case節: 値は定数式．畳み込んで重複チェックし，結果をivalに保存する
if (child->kind == ND_CASE) {
const long long v = Analyzer::eval_const_expr(child->children[0]);
if (case_values.count(v)) {
throw std::string("compiler error: duplicate case value at line ")
+ std::to_string(child->line);
}
case_values.insert(v);
child->ival = v; // コード生成器が参照できるよう畳み込み結果を保存する
}
// default節: 重複は不可
else if (child->kind == ND_DEFAULT) {
if (has_default) {
throw std::string("compiler error: multiple default labels at line ")
+ std::to_string(child->line);
}
has_default = true;
}
// それ以外は通常の文として検査する
else {
this->analyze_stmt(child);
}
}
this->scopes_.pop_back();
this->switch_depth_--;
}
// ローカル変数宣言を検査し，現在のスコープに登録する
void Analyzer::analyze_local_decl(node_t *decl) {
// 同一スコープ内での二重宣言はエラー (外側スコープの同名はシャドーイングとして許容)
if (this->scopes_.back().count(decl->sval)) {
throw std::string("compiler error: redefinition of '") + decl->sval
+ "' at line " + std::to_string(decl->line);
}
// ハードウェア変数と同名のローカル変数は宣言できない (I/Oレジスタを上書きしないように禁止する)
const symbol_t *shadowed = this->lookup_symbol(decl->sval);
if (shadowed != nullptr && shadowed->location == LOC_REGISTER) {
throw std::string("compiler error: cannot redeclare hardware register '") + decl->sval
+ "' at line " + std::to_string(decl->line);
}
// 初期化式があれば先に検査する (登録より前に行い，自己参照 int x = x; では外側のxを参照させる)
if (!decl->children.empty()) {
this->analyze_expr(decl->children[0]);
}
// メモリ番地を割り当てて登録する (ローカルも静的割り当てで固定番地)
symbol_t *sym = new symbol_t{decl->sval, decl->type, LOC_LOCAL, this->next_addr_, true, true};
this->next_addr_ += 4;
this->scopes_.back()[decl->sval] = sym;
decl->sym = sym; // 宣言ノード自身もシンボルを指す
}
// 式を検査し，名前解決と型注釈を行う
// ノード種別ごとに固有の検査を行い，子を持つノードは子へ再帰する．
// リテラル: 末端なので何もしない
// 変数参照・代入・インクリメント/デクリメント・関数呼び出し: それぞれ固有の検査を行う
// 二項演算・三項演算など(default): 固有の検査はなく，子を再帰検査するだけ
// 式文(a + b; のような文)もanalyze_stmtからこの関数で検査される
void Analyzer::analyze_expr(node_t *expr) {
switch (expr->kind) {
// リテラル: 検査は不要だが，後段のコード生成のため型を注釈する
case ND_INT_LIT:
expr->type = type_t{BASE_INT, true}; // 整数リテラルはint(符号付き)
return;
case ND_CHAR_LIT:
expr->type = type_t{BASE_CHAR, true}; // 文字リテラルはchar(符号付き)
return;
// 変数参照: 名前を解決し，読み取り可能か確認する
case ND_VAR: {
const symbol_t *sym = this->lookup_symbol(expr->sval);
if (sym == nullptr) {
throw std::string("compiler error: use of undeclared identifier '")
+ expr->sval + "' at line " + std::to_string(expr->line);
}
if (!sym->readable) {
throw std::string("compiler error: '") + expr->sval
+ "' is not readable at line " + std::to_string(expr->line);
}
expr->sym = sym; // 名前解決の結果を結びつける
expr->type = sym->type; // 型を注釈する
return;
}
// 代入: 左辺は書き込み可能な変数でなければならない
case ND_ASSIGN: {
node_t *lhs = expr->children[0];
if (lhs->kind != ND_VAR) {
throw std::string("compiler error: left side of assignment must be a variable at line ")
+ std::to_string(expr->line);
}
const symbol_t *sym = this->lookup_symbol(lhs->sval);
if (sym == nullptr) {
throw std::string("compiler error: use of undeclared identifier '")
+ lhs->sval + "' at line " + std::to_string(lhs->line);
}
if (!sym->writable) {
throw std::string("compiler error: '") + lhs->sval
+ "' is not writable at line " + std::to_string(lhs->line);
}
// 複合代入(+=等)は左辺を読みもするので，読み取り可能でもなければならない
if (expr->sval != "=" && !sym->readable) {
throw std::string("compiler error: '") + lhs->sval
+ "' is not readable at line " + std::to_string(lhs->line);
}
lhs->sym = sym;
lhs->type = sym->type;
this->analyze_expr(expr->children[1]); // 右辺を検査する
expr->type = sym->type;
return;
}
// インクリメント・デクリメント: 対象は読み書き両方可能な変数でなければならない
case ND_UNOP:
case ND_POST_UNOP:
if (expr->sval == "++" || expr->sval == "--") {
node_t *operand = expr->children[0];
if (operand->kind != ND_VAR) {
throw std::string("compiler error: operand of '") + expr->sval
+ "' must be a variable at line " + std::to_string(expr->line);
}
const symbol_t *sym = this->lookup_symbol(operand->sval);
if (sym == nullptr) {
throw std::string("compiler error: use of undeclared identifier '")
+ operand->sval + "' at line " + std::to_string(operand->line);
}
if (!sym->readable || !sym->writable) {
throw std::string("compiler error: '") + operand->sval
+ "' is not readable and writable at line " + std::to_string(operand->line);
}
operand->sym = sym;
operand->type = sym->type;
expr->type = sym->type;
return;
}
// その他の前置単項演算子(-, +, !, ~)は子を検査する
this->analyze_expr(expr->children[0]);
return;
// 関数呼び出し: その名前の関数が定義されているか確認する
case ND_CALL:
if (this->func_names_.find(expr->sval) == this->func_names_.end()) {
throw std::string("compiler error: call to undefined function '")
+ expr->sval + "' at line " + std::to_string(expr->line);
}
return;
// 組み込み関数print: 出力する式を検査する (読み取り可能性も式の検査で確認される)
case ND_PRINT:
this->analyze_expr(expr->children[0]);
return;
// 組み込み関数scan: 格納先は書き込み可能な変数でなければならない (代入の左辺と同様)
case ND_SCAN: {
node_t *target = expr->children[0]; // 格納先変数 (parserがND_VARで構築)
const symbol_t *sym = this->lookup_symbol(target->sval);
if (sym == nullptr) {
throw std::string("compiler error: use of undeclared identifier '")
+ target->sval + "' at line " + std::to_string(target->line);
}
if (!sym->writable) {
throw std::string("compiler error: '") + target->sval
+ "' is not writable at line " + std::to_string(target->line);
}
target->sym = sym; // 名前解決の結果を結びつける
target->type = sym->type;
return;
}
// 二項演算・三項演算など: 子を再帰的に検査する
default:
for (node_t *child : expr->children) {
this->analyze_expr(child);
}
return;
}
}
// 名前からシンボルを探す (内側のローカルスコープから順に，最後にグローバル・ハードウェア変数)
const symbol_t *Analyzer::lookup_symbol(const std::string &name) const {
// ローカルスコープを内側から外側へ探す
for (auto it = this->scopes_.rbegin(); it != this->scopes_.rend(); ++it) {
const auto found = it->find(name);
if (found != it->end()) return found->second;
}
// グローバル変数・ハードウェア変数を探す
const auto found = this->symbols_.find(name);
if (found != this->symbols_.end()) return found->second;
return nullptr;
}
アセンブリコードを生成する
さて，ここまで来たらあとはアセンブリコードを生成して終わりです．
と言っても簡単に生成できるわけではないのですが．
まず，今までで作ったのは以下です．
- 補足情報付きの木構造．パーサによって，構文構造で木構造になったグラフです．で，その後，意味解析によって補足情報が足されています．どの変数を呼び出してるとか，それが足し算なのか掛け算なのかとかですね(後者についてはパーサの時点でついていますが)
- 変数とメモリ番地の対応表．これは構文解析で作ったものです
また，構文解析によってソースに構文の間違いがないかどうかについてもチェックしているので，アセンブリコード生成時点では木構造になったものをただ舐めるだけですね．
ここでやることは，木構造を深さ優先探索しながらアセンブリのコードに変換していくだけです．
ただプログラミング言語とアセンブリ言語の言語仕様には若干の違いがあるので，それを吸収する必要はあります．
- プログラミング言語では関数の定義順に縛りはないが，アセンブリ言語ではmain関数をまず定義しなければならない．また，定義する前の関数を呼び出すことは出来ない
- プログラミング言語では関数は定義のみすればいいが，アセンブリ言語では登場する関数すべてを事前に宣言しなければならない
generator
generator.hpp
#pragma once
#include <fstream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "analyzer.hpp"
// 注釈付きASTとシンボルテーブルを受け取り，アセンブリコードを生成するジェネレータ
class Generator {
public:
Generator(node_t *root, const std::map<std::string, const symbol_t *> &symbols,
std::ofstream &asm_file);
void operator()(); // コード生成を実行して .asm に書き出す
private:
node_t *root_; // 注釈付きAST
const std::map<std::string, const symbol_t *> &symbols_; // シンボルテーブル (変数名→番地)
std::ofstream &asm_file_; // 出力先アセンブリファイル
int label_count_ = 0; // 局所ラベルの連番カウンタ (.L0, .L1, ...)
// break/continueの飛び先ラベルのスタック (最内が末尾)
// continueはループのみ，breakはループとswitchの両方が積む
std::vector<std::string> break_labels_;
std::vector<std::string> continue_labels_;
// 生成メソッド (gen_で始まる)
void gen_program(); // プログラム全体 (.global宣言 + main優先で各関数を出力)
void gen_global_inits(); // グローバル変数の初期化 (mainの先頭に出力)
void gen_func(node_t *func); // 関数定義 (ラベル + 本体)
void gen_block(node_t *block); // ブロック (中の文を順に生成)
void gen_stmt(node_t *stmt); // 文 (種別ごとに振り分け)
void gen_var_decl(node_t *decl); // 変数宣言 (初期化子があれば代入コードを生成)
void gen_if(node_t *stmt); // if文 (条件分岐)
void gen_while(node_t *stmt); // while文 (ループ)
void gen_for(node_t *stmt); // for文 (ループ)
void gen_do_while(node_t *stmt); // do-while文 (末尾判定ループ)
void gen_switch(node_t *stmt); // switch文 (多分岐)
void gen_expr(node_t *expr, int reg); // 式を評価し結果をr{reg}に残す (レジスタスタック方式)
void gen_binop_instr(const std::string &op, int dst, int lhs, int rhs); // r{dst}=r{lhs} op r{rhs}を出力
void gen_load(int reg, const symbol_t *sym); // 変数をr{reg}へ読み込む (レジスタ直結ならmov・メモリならrm)
void gen_store(int reg, const symbol_t *sym); // r{reg}を変数へ書き込む (レジスタ直結ならmov・メモリならwm)
void gen_compare(node_t *expr, int reg); // 比較演算を0/1の値としてr{reg}に生成
void gen_logical(node_t *expr, int reg); // 論理 && / || を短絡評価しr{reg}に0/1を生成
void gen_ternary(node_t *expr, int reg); // 三項演算子 ?: の結果をr{reg}に生成
void gen_incdec(node_t *expr, int reg, bool is_prefix); // ++/-- (前置は新値・後置は旧値をr{reg}に残す)
void gen_unary(node_t *expr, int reg); // 単項 -/+/~/! の結果をr{reg}に生成
// condが偽/真ならlabelへ分岐 (評価にr{reg}・r{reg+1}を使う．制御構文からはreg=0で呼ぶ)
void gen_branch_if_false(node_t *cond, const std::string &label, int reg = 0);
void gen_branch_if_true(node_t *cond, const std::string &label, int reg = 0);
std::string new_label(); // 一意な局所ラベル (.Ln) を生成する
};
generator.cpp
#include "generator.hpp"
// 二項演算子の文字列を対応するアセンブリ命令に変換する
static std::string binop_mnemonic(const std::string &op) {
if (op == "+") return "add";
if (op == "-") return "sub";
if (op == "*") return "mul";
if (op == "&") return "and";
if (op == "|") return "or";
if (op == "^") return "xor";
if (op == "/") return "div"; // 商 (符号付き除算．余りは捨てる)
if (op == "<<") return "sll"; // 左シフト
if (op == ">>") return "sra"; // 右シフト: unsigned非対応のため常に算術シフト(将来srlを符号で選択)
// % は div の4引数形式で別途生成する．比較・論理演算子は分岐の段階で対応する
throw std::string("compiler error: unsupported binary operator '") + op + "'";
}
// 比較演算子かどうかを返す
static bool is_comparison(const std::string &op) {
return op == "==" || op == "!=" || op == "<" || op == ">" || op == "<=" || op == ">=";
}
// 比較演算子の「否定」に対応するF系命令を返す (偽のとき分岐させるのに使う)
static std::string negated_branch(const std::string &op) {
if (op == "==") return "ne"; // ==の否定は!=
if (op == "!=") return "eq"; // !=の否定は==
if (op == "<") return "egt"; // <の否定は>=
if (op == ">") return "elt"; // >の否定は<=
if (op == "<=") return "gt"; // <=の否定は>
if (op == ">=") return "lt"; // >=の否定は<
throw std::string("compiler error: not a comparison operator '") + op + "'";
}
// 比較演算子に「そのまま」対応するF系命令を返す (真のとき分岐させるのに使う)
static std::string comparison_branch(const std::string &op) {
if (op == "==") return "eq";
if (op == "!=") return "ne";
if (op == "<") return "lt";
if (op == ">") return "gt";
if (op == "<=") return "elt";
if (op == ">=") return "egt";
throw std::string("compiler error: not a comparison operator '") + op + "'";
}
// 命令出力の慣例:
// mov/rm/wm の即値モードではrs1(第1レジスタ)が無視される．
// 以降のコードでrs1の位置に書く r0 は値を持たないダミーであり，r0の値は読まれも書かれもしない．
// (例外: switchのディスパッチでは r0 に条件値を入れて実際に使う)
// コンストラクタ: AST・シンボルテーブル・出力先を受け取る
Generator::Generator(node_t *root, const std::map<std::string, const symbol_t *> &symbols,
std::ofstream &asm_file)
: root_(root), symbols_(symbols), asm_file_(asm_file) {}
// コード生成を実行して .asm に書き出す
void Generator::operator()() {
this->gen_program();
}
// プログラム全体を生成する
// .global宣言で全関数名を列挙し，main関数を先頭に各関数を出力する
void Generator::gen_program() {
// .global宣言: 子を走査して全関数名を集める (アセンブリは定義前に全関数の宣言が必要)
bool first = true;
this->asm_file_ << ".global ";
for (node_t *child : this->root_->children) {
if (child->kind != ND_FUNC_DEF) continue; // 関数定義のみ対象 (グローバル変数は除く)
if (!first) this->asm_file_ << ", ";
this->asm_file_ << child->sval;
first = false;
}
this->asm_file_ << "\n";
// main関数を先頭に出力する (アセンブリはmainを一番最初に書く必要がある)
for (node_t *child : this->root_->children) {
if (child->kind == ND_FUNC_DEF && child->sval == "main") {
this->asm_file_ << "\n";
this->gen_func(child);
break;
}
}
// main以外の関数を出力する
for (node_t *child : this->root_->children) {
if (child->kind == ND_FUNC_DEF && child->sval != "main") {
this->asm_file_ << "\n";
this->gen_func(child);
}
}
}
// グローバル変数の初期化コードを生成する
// プログラム直下の変数宣言を走査し，初期化子があるものの初期化命令を出力する
// (mainが最初に実行されるため，mainの先頭で呼び出す)
void Generator::gen_global_inits() {
for (node_t *child : this->root_->children) {
if (child->kind == ND_VAR_DECL) {
this->gen_var_decl(child);
}
}
}
// 関数定義を生成する
// 関数ラベルを出力し，本体ブロックの文を生成して，末尾にretを置く
void Generator::gen_func(node_t *func) {
this->asm_file_ << func->sval << ":\n";
// mainの先頭でグローバル変数を初期化する (mainが最初に実行されるため)
if (func->sval == "main") {
this->gen_global_inits();
}
this->gen_block(func->children[0]); // 本体ブロック(children[0])の文を生成する
this->asm_file_ << " ret\n"; // 関数末尾のret (全関数にretが1つ以上必要)
}
// ブロックを生成する
// 中の文を上から順に生成する
void Generator::gen_block(node_t *block) {
for (node_t *stmt : block->children) {
this->gen_stmt(stmt);
}
}
// 文を生成する
// 文の種別ごとに対応する生成処理へ振り分ける
void Generator::gen_stmt(node_t *stmt) {
switch (stmt->kind) {
// 変数宣言
case ND_VAR_DECL:
this->gen_var_decl(stmt);
break;
// 入れ子のブロック
case ND_BLOCK:
this->gen_block(stmt);
break;
// 代入文・関数呼び出し文・入出力文・増減文 (式文): 副作用のため評価する．結果(r0)は捨てる
case ND_ASSIGN:
case ND_CALL:
case ND_PRINT:
case ND_SCAN:
case ND_UNOP:
case ND_POST_UNOP:
this->gen_expr(stmt, 0);
break;
// if文
case ND_IF:
this->gen_if(stmt);
break;
// while文
case ND_WHILE:
this->gen_while(stmt);
break;
// for文
case ND_FOR:
this->gen_for(stmt);
break;
// do-while文
case ND_DO_WHILE:
this->gen_do_while(stmt);
break;
// switch文
case ND_SWITCH:
this->gen_switch(stmt);
break;
// break文: 最内のループ/switchの脱出先へ飛ぶ (アナライザが内側であることを保証済み)
case ND_BREAK:
this->asm_file_ << " jmp " << this->break_labels_.back() << "\n";
break;
// continue文: 最内ループの継続先へ飛ぶ
case ND_CONTINUE:
this->asm_file_ << " jmp " << this->continue_labels_.back() << "\n";
break;
// return文: 呼び出し元へ復帰する
case ND_RETURN:
this->asm_file_ << " ret\n";
break;
default:
break;
}
}
// 変数宣言を生成する
// 初期化子があれば，初期値を変数の番地へ書き込むコードを生成する
void Generator::gen_var_decl(node_t *decl) {
// 初期化子がなければ何も出力しない (番地は確保済み，未初期化ローカルは不定値)
if (decl->children.empty()) return;
// 初期化式をr0に評価し，変数へ書き込む
this->gen_expr(decl->children[0], 0); // r0 = 初期値
this->gen_store(0, decl->sym); // 変数 = r0
}
// 一意な局所ラベル (.L0, .L1, ...) を生成して返す
std::string Generator::new_label() {
return ".L" + std::to_string(this->label_count_++);
}
// 条件式condが偽のとき，labelへ分岐する命令を出力する
// 評価にはr{reg}・r{reg+1}を使う (式の途中で呼ばれても下位レジスタを壊さないため)
void Generator::gen_branch_if_false(node_t *cond, const std::string &label, int reg) {
// 比較条件: 否定したF系で「偽のとき飛ぶ」を1命令で表現する
if (cond->kind == ND_BINOP && is_comparison(cond->sval)) {
this->gen_expr(cond->children[0], reg); // 左 → r{reg}
this->gen_expr(cond->children[1], reg + 1); // 右 → r{reg+1}
this->asm_file_ << " " << negated_branch(cond->sval)
<< " r" << reg << " r" << (reg + 1) << " " << label << "\n";
}
// 一般条件: 値を評価し，0(偽)なら飛ぶ
else {
this->gen_expr(cond, reg); // cond → r{reg}
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " 0\n"; // r{reg+1} = 0
this->asm_file_ << " eq r" << reg << " r" << (reg + 1) << " " << label << "\n"; // 0なら飛ぶ
}
}
// 条件式condが真のとき，labelへ分岐する命令を出力する
// 評価にはr{reg}・r{reg+1}を使う
void Generator::gen_branch_if_true(node_t *cond, const std::string &label, int reg) {
// 比較条件: そのままのF系で「真のとき飛ぶ」を1命令で表現する
if (cond->kind == ND_BINOP && is_comparison(cond->sval)) {
this->gen_expr(cond->children[0], reg); // 左 → r{reg}
this->gen_expr(cond->children[1], reg + 1); // 右 → r{reg+1}
this->asm_file_ << " " << comparison_branch(cond->sval)
<< " r" << reg << " r" << (reg + 1) << " " << label << "\n";
}
// 一般条件: 値を評価し，0でない(真)なら飛ぶ
else {
this->gen_expr(cond, reg); // cond → r{reg}
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " 0\n"; // r{reg+1} = 0
this->asm_file_ << " ne r" << reg << " r" << (reg + 1) << " " << label << "\n"; // 0以外なら飛ぶ
}
}
// 比較演算を0/1の値としてr{reg}に生成する
// 左をr{reg}・右をr{reg+1}に評価し，比較が真なら1・偽なら0をr{reg}に置く
void Generator::gen_compare(node_t *expr, int reg) {
const std::string t = this->new_label(); // 真の場合の飛び先
const std::string end = this->new_label();
this->gen_expr(expr->children[0], reg); // 左 → r{reg}
this->gen_expr(expr->children[1], reg + 1); // 右 → r{reg+1}
// 比較が真なら .Lt へ
this->asm_file_ << " " << comparison_branch(expr->sval)
<< " r" << reg << " r" << (reg + 1) << " " << t << "\n";
this->asm_file_ << " mov fh r0 r" << reg << " 0\n"; // 偽: r{reg} = 0
this->asm_file_ << " jmp " << end << "\n";
this->asm_file_ << t << ":\n";
this->asm_file_ << " mov fh r0 r" << reg << " 1\n"; // 真: r{reg} = 1
this->asm_file_ << end << ":\n";
}
// 論理 && / || を短絡評価し，結果(0/1)をr{reg}に生成する
// && は0で短絡(両方非0で1)，|| は非0で短絡(両方0で0)
void Generator::gen_logical(node_t *expr, int reg) {
const bool is_and = (expr->sval == "&&");
const std::string shortcut = this->new_label(); // 短絡時の飛び先
const std::string end = this->new_label();
// 短絡判定のF系: && は「0なら短絡(eq)」, || は「0以外なら短絡(ne)」
const std::string br = is_and ? "eq" : "ne";
// 左を評価．短絡条件を満たせば右を評価する命令を飛ばして結果へ行く
this->gen_expr(expr->children[0], reg);
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " 0\n";
this->asm_file_ << " " << br << " r" << reg << " r" << (reg + 1) << " " << shortcut << "\n";
// 右を評価．こちらは飛ばす対象が無いので短絡ではなく，結果(0/1)を確定させるための判定
this->gen_expr(expr->children[1], reg);
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " 0\n";
this->asm_file_ << " " << br << " r" << reg << " r" << (reg + 1) << " " << shortcut << "\n";
// どちらも短絡しなかった場合の結果 (&&なら1, ||なら0)
this->asm_file_ << " mov fh r0 r" << reg << " " << (is_and ? 1 : 0) << "\n";
this->asm_file_ << " jmp " << end << "\n";
// 短絡した場合の結果 (&&なら0, ||なら1)
this->asm_file_ << shortcut << ":\n";
this->asm_file_ << " mov fh r0 r" << reg << " " << (is_and ? 0 : 1) << "\n";
this->asm_file_ << end << ":\n";
}
// 三項演算子 a ? b : c の結果をr{reg}に生成する
void Generator::gen_ternary(node_t *expr, int reg) {
const std::string else_label = this->new_label();
const std::string end = this->new_label();
this->gen_branch_if_false(expr->children[0], else_label, reg); // 条件が偽ならelse値へ
this->gen_expr(expr->children[1], reg); // then値 → r{reg}
this->asm_file_ << " jmp " << end << "\n";
this->asm_file_ << else_label << ":\n";
this->gen_expr(expr->children[2], reg); // else値 → r{reg}
this->asm_file_ << end << ":\n";
}
// インクリメント/デクリメント (++/--) を生成する
// 対象は変数 (アナライザが読み書き可能を保証)．前置は増減後の新値・後置は増減前の旧値を式の値とする
void Generator::gen_incdec(node_t *expr, int reg, bool is_prefix) {
node_t *var = expr->children[0]; // 対象変数 (ND_VAR)
const std::string op = (expr->sval == "++") ? "+" : "-"; // ++→加算, --→減算
// 現在値を読み，1を載せる
this->gen_load(reg, var->sym); // r{reg} = x
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " 1\n"; // r{reg+1} = 1
if (is_prefix) {
// 前置 ++x/--x : r{reg}を増減して書き戻す (新値がそのまま式の値として残る)
this->gen_binop_instr(op, reg, reg, reg + 1); // r{reg} = x ± 1
this->gen_store(reg, var->sym); // x = r{reg}
} else {
// 後置 x++/x-- : 旧値をr{reg}に残したまま，新値をr{reg+1}で計算して書き戻す
this->gen_binop_instr(op, reg + 1, reg, reg + 1); // r{reg+1} = x ± 1
this->gen_store(reg + 1, var->sym); // x = r{reg+1}
}
}
// 単項演算 (-/+/~/!) を生成する
void Generator::gen_unary(node_t *expr, int reg) {
const std::string &op = expr->sval;
this->gen_expr(expr->children[0], reg); // オペランド → r{reg}
if (op == "+") {
// 単項+ : 値はオペランドそのもの (何もしない)
return;
}
else if (op == "-") {
// 単項- : 0 - x で符号反転する
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " 0\n"; // r{reg+1} = 0
this->asm_file_ << " sub r" << (reg + 1) << " r" << reg << " r" << reg << "\n"; // r{reg} = 0 - x
} else if (op == "~") {
// ビット反転 : NOT命令 (not rs1 rd)
this->asm_file_ << " not r" << reg << " r" << reg << "\n"; // r{reg} = ~x
} else if (op == "!") {
// 論理否定 : x==0 なら1，それ以外は0 (比較と同じ0/1生成パターン)
const std::string t = this->new_label(); // 真(x==0)の飛び先
const std::string end = this->new_label();
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " 0\n"; // r{reg+1} = 0
this->asm_file_ << " eq r" << reg << " r" << (reg + 1) << " " << t << "\n"; // x==0 なら .Lt へ
this->asm_file_ << " mov fh r0 r" << reg << " 0\n"; // x!=0: r{reg} = 0
this->asm_file_ << " jmp " << end << "\n";
this->asm_file_ << t << ":\n";
this->asm_file_ << " mov fh r0 r" << reg << " 1\n"; // x==0: r{reg} = 1
this->asm_file_ << end << ":\n";
} else {
throw std::string("compiler error: unsupported unary operator '") + op
+ "' at line " + std::to_string(expr->line);
}
}
// if文を生成する
// children: [0]=条件, [1]=then節, [2]=else節(省略可)
void Generator::gen_if(node_t *stmt) {
node_t *cond = stmt->children[0];
const bool has_else = stmt->children.size() == 3;
if (!has_else) {
// if (cond) then : 偽なら本体を飛ばす
const std::string end = this->new_label();
this->gen_branch_if_false(cond, end);
this->gen_stmt(stmt->children[1]);
this->asm_file_ << end << ":\n";
} else {
// if (cond) then else else節 : 偽ならelseへ，thenの後はelseを飛ばす
const std::string else_label = this->new_label();
const std::string end = this->new_label();
this->gen_branch_if_false(cond, else_label);
this->gen_stmt(stmt->children[1]);
this->asm_file_ << " jmp " << end << "\n";
this->asm_file_ << else_label << ":\n";
this->gen_stmt(stmt->children[2]);
this->asm_file_ << end << ":\n";
}
}
// while文を生成する
// children: [0]=条件, [1]=本体
void Generator::gen_while(node_t *stmt) {
const std::string top = this->new_label(); // 条件判定の先頭 (continueの飛び先)
const std::string end = this->new_label(); // ループ脱出先 (breakの飛び先)
this->break_labels_.push_back(end);
this->continue_labels_.push_back(top);
this->asm_file_ << top << ":\n";
this->gen_branch_if_false(stmt->children[0], end); // 条件が偽なら脱出
this->gen_stmt(stmt->children[1]); // 本体
this->asm_file_ << " jmp " << top << "\n"; // 先頭(条件)へ戻る
this->asm_file_ << end << ":\n";
this->continue_labels_.pop_back();
this->break_labels_.pop_back();
}
// for文を生成する
// children: [0]=初期化, [1]=条件, [2]=更新, [3]=本体 (各部は省略時nullptr)
void Generator::gen_for(node_t *stmt) {
node_t *init = stmt->children[0];
node_t *cond = stmt->children[1];
node_t *update = stmt->children[2];
node_t *body = stmt->children[3];
const std::string top = this->new_label(); // 条件判定の先頭
const std::string cont = this->new_label(); // continueの飛び先 (更新部)
const std::string end = this->new_label(); // ループ脱出先 (break)
// 初期化 (省略時はnullptr)．ループ前に1回だけ実行する
if (init != nullptr) this->gen_stmt(init);
this->break_labels_.push_back(end);
this->continue_labels_.push_back(cont);
this->asm_file_ << top << ":\n";
// 条件 (省略時は判定なし＝常にループ)
if (cond != nullptr) this->gen_branch_if_false(cond, end);
this->gen_stmt(body); // 本体
this->asm_file_ << cont << ":\n"; // continueはここ(更新部)へ来る
if (update != nullptr) this->gen_stmt(update); // 更新 (省略可)
this->asm_file_ << " jmp " << top << "\n"; // 条件へ戻る
this->asm_file_ << end << ":\n";
this->continue_labels_.pop_back();
this->break_labels_.pop_back();
}
// do-while文を生成する
// children: [0]=本体, [1]=条件 (本体を実行してから末尾で条件判定する)
void Generator::gen_do_while(node_t *stmt) {
const std::string top = this->new_label(); // ループ先頭 (本体)
const std::string cont = this->new_label(); // continueの飛び先 (末尾の条件判定)
const std::string end = this->new_label(); // 脱出先 (break)
this->break_labels_.push_back(end);
this->continue_labels_.push_back(cont);
this->asm_file_ << top << ":\n";
this->gen_stmt(stmt->children[0]); // 本体
this->asm_file_ << cont << ":\n"; // continueはここ(条件判定)へ来る
this->gen_branch_if_true(stmt->children[1], top); // 条件が真なら先頭へ戻る
this->asm_file_ << end << ":\n";
this->continue_labels_.pop_back();
this->break_labels_.pop_back();
}
// switch文を生成する
// children: [0]=条件式, [1..]=case/defaultラベルと文を平坦に並べたもの
// 意味解析がcase値をivalに畳み込み済み
void Generator::gen_switch(node_t *stmt) {
// 各case/defaultにラベルを割り当てる
std::map<node_t *, std::string> label_of; // case/defaultノード → 飛び先ラベル
std::string default_label; // default節のラベル (無ければ空)
for (size_t i = 1; i < stmt->children.size(); i++) {
node_t *c = stmt->children[i];
if (c->kind == ND_CASE) {
label_of[c] = this->new_label();
} else if (c->kind == ND_DEFAULT) {
default_label = this->new_label();
label_of[c] = default_label;
}
}
const std::string end = this->new_label(); // switch脱出先 (breakの飛び先)
this->break_labels_.push_back(end);
// ディスパッチ: 条件を一度r0に評価し，各caseと比較して一致したらそのラベルへ飛ぶ
this->gen_expr(stmt->children[0], 0); // r0 = 条件値
for (size_t i = 1; i < stmt->children.size(); i++) {
node_t *c = stmt->children[i];
if (c->kind == ND_CASE) {
this->asm_file_ << " mov fh r0 r1 " << c->ival << "\n"; // r1 = case値
this->asm_file_ << " eq r0 r1 " << label_of[c] << "\n"; // 一致ならそのcaseへ
}
}
// どのcaseにも一致しなければ default へ (無ければ end へ)
this->asm_file_ << " jmp " << (default_label.empty() ? end : default_label) << "\n";
// 本体: case/defaultラベルを所定位置に置き，文を順に生成する (フォールスルーは自然に表現される)
for (size_t i = 1; i < stmt->children.size(); i++) {
node_t *c = stmt->children[i];
if (c->kind == ND_CASE || c->kind == ND_DEFAULT) {
this->asm_file_ << label_of[c] << ":\n";
} else {
this->gen_stmt(c);
}
}
this->asm_file_ << end << ":\n";
this->break_labels_.pop_back();
}
// r{dst} = r{lhs} op r{rhs} となる演算命令を出力する
// 二項演算と複合代入で共用する (剰余だけはdivの4引数形式)
void Generator::gen_binop_instr(const std::string &op, int dst, int lhs, int rhs) {
// 剰余: divは商をrdへ・余りをimmが指すレジスタ番地へ格納する
// 商をr{rhs}に捨て，余りをr{dst}(番地dst)へ得る
if (op == "%") {
this->asm_file_ << " div r" << lhs << " r" << rhs
<< " r" << rhs << " " << dst << "\n";
} else {
// それ以外は単一命令
const std::string mn = binop_mnemonic(op); // 演算子→命令
this->asm_file_ << " " << mn
<< " r" << lhs << " r" << rhs << " r" << dst << "\n";
}
}
// 変数の値をr{reg}へ読み込む
// 置き場所がレジスタ直結(LED等のI/Oレジスタ)ならmovのレジスタ間コピー，メモリ変数ならrm
void Generator::gen_load(int reg, const symbol_t *sym) {
if (sym->location == LOC_REGISTER) {
// mov rs1=番地, rd=r{reg} : r{reg} = register[番地] (即値を付けないとレジスタ間コピーになる)
this->asm_file_ << " mov fh r" << sym->address << " r" << reg << "\n";
} else {
// rm: メモリ絶対番地からr{reg}へ読み込む (即値アドレス指定のためrs1のr0は無視される)
this->asm_file_ << " rm fh r0 r" << reg << " " << sym->address << "\n";
}
}
// r{reg}の値を変数へ書き込む
// 置き場所がレジスタ直結(LED等のI/Oレジスタ)ならmovのレジスタ間コピー，メモリ変数ならwm
void Generator::gen_store(int reg, const symbol_t *sym) {
if (sym->location == LOC_REGISTER) {
// mov rs1=r{reg}, rd=番地 : register[番地] = r{reg}
this->asm_file_ << " mov fh r" << reg << " r" << sym->address << "\n";
} else {
// wm: r{reg}をメモリ絶対番地へ書き込む (即値アドレス指定のためrs1のr0は無視される)
this->asm_file_ << " wm fh r0 r" << reg << " " << sym->address << "\n";
}
}
// 式を評価し，結果をr{reg}に残す
// reg以上のレジスタを作業用に使うレジスタスタック方式 (二項演算は左をr{reg}・右をr{reg+1}に評価して畳む)
void Generator::gen_expr(node_t *expr, int reg) {
// レジスタは16本(r0〜r15)．深い式で枯渇したらエラーにする
if (reg > 15) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(expr->line);
}
switch (expr->kind) {
// リテラル: 即値をr{reg}に載せる
case ND_INT_LIT:
case ND_CHAR_LIT:
this->asm_file_ << " mov fh r0 r" << reg << " " << expr->ival << "\n";
break;
// 変数参照: 変数の値をr{reg}へ読み込む
case ND_VAR:
this->gen_load(reg, expr->sym);
break;
// 二項演算
case ND_BINOP:
// 比較は0/1の値を生成，論理&&/||は短絡評価，それ以外は単一命令(+など)で畳む
if (is_comparison(expr->sval)) {
this->gen_compare(expr, reg);
} else if (expr->sval == "&&" || expr->sval == "||") {
this->gen_logical(expr, reg);
} else {
this->gen_expr(expr->children[0], reg);
this->gen_expr(expr->children[1], reg + 1);
this->gen_binop_instr(expr->sval, reg, reg, reg + 1); // r{reg} = r{reg} op r{reg+1}
}
break;
// 三項演算子 a ? b : c
case ND_TERNARY:
this->gen_ternary(expr, reg);
break;
// 前置単項演算: ++/--は増減，それ以外(-/+/~/!)は単項演算
case ND_UNOP:
if (expr->sval == "++" || expr->sval == "--") {
this->gen_incdec(expr, reg, true); // 前置
} else {
this->gen_unary(expr, reg);
}
break;
// 後置単項演算: ++/--のみ (parserがND_POST_UNOPを作るのはこの2つだけ)
case ND_POST_UNOP:
this->gen_incdec(expr, reg, false); // 後置
break;
// 関数呼び出し: 引数・戻り値なし(void func(void))なので call のみ
// callでレジスタは揮発するが，呼び出し前後で生きた値はメモリにあるため問題ない
case ND_CALL:
this->asm_file_ << " call " << expr->sval << "\n";
break;
// 組み込み関数print: 出力式をr{reg}に評価し，標準出力へ
// printは即値を省略するとrs1(レジスタ)の値を出力する (即値ありはイミディエイト出力になる)
case ND_PRINT:
this->gen_expr(expr->children[0], reg); // 出力値 → r{reg}
this->asm_file_ << " print r" << reg << "\n";
break;
// 組み込み関数scan: 標準入力をr{reg}へ読み込み，格納先変数の番地へ書き込む
case ND_SCAN: {
node_t *target = expr->children[0]; // 格納先変数 (ND_VAR)
this->asm_file_ << " scan r" << reg << "\n"; // 標準入力 → r{reg}
this->gen_store(reg, target->sym); // 格納先変数 = r{reg}
break;
}
// 代入: 右辺(複合代入は左辺の現在値と右辺の演算結果)をr{reg}に求め，変数へ書き込む
case ND_ASSIGN: {
node_t *lhs = expr->children[0]; // 代入先の変数 (ND_VAR)
if (expr->sval == "=") {
// 単純代入: 右辺をr{reg}に評価する
this->gen_expr(expr->children[1], reg);
} else {
// 複合代入 x op= e : 左辺の現在値をr{reg}・右辺をr{reg+1}に評価し，opで畳む
this->gen_load(reg, lhs->sym);
this->gen_expr(expr->children[1], reg + 1);
const std::string op = expr->sval.substr(0, expr->sval.size() - 1); // "+=" → "+"
this->gen_binop_instr(op, reg, reg, reg + 1);
}
// 変数へ書き込む (代入式の値もr{reg}に残る)
this->gen_store(reg, lhs->sym);
break;
}
// TODO: 単項演算・代入式・三項・関数呼び出し等は今後の段階で実装する
default:
throw std::string("compiler error: unsupported expression in code generation at line ")
+ std::to_string(expr->line);
}
}
メイン関数
以上の関数やクラスを使いまして，メイン関数がこちらです．
c2asm
c2asm.cpp
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include "lexer.hpp"
#include "parser.hpp"
#include "analyzer.hpp"
#include "generator.hpp"
// コマンドライン引数情報
typedef struct {
std::string c_file_name; // 入力Cソースファイル名
std::string asm_file_name; // 出力アセンブリファイル名
} args_t;
// 前宣言
void get_args(int argc, char **argv, args_t &args); // コマンドライン引数を取得する
// メイン関数
// 処理に成功したら0，失敗したら1を返す
int main(int argc, char **argv) {
args_t args; // コマンドライン引数
std::vector<token_t> tokens; // トークン列 (字句解析結果)
node_t *ast = nullptr; // AST (構文解析結果)
std::map<std::string, const symbol_t *> symbols; // シンボルテーブル (意味解析結果)
// コマンドライン引数を取得する
get_args(argc, argv, args);
if (args.c_file_name.empty() || args.asm_file_name.empty()) {
return 1;
}
// Cソースファイルをまとめて読み込む
std::ifstream c_file(args.c_file_name);
if (!c_file) {
std::cout << "cannot open c file: " << args.c_file_name << std::endl;
return 1;
}
std::ostringstream ss;
ss << c_file.rdbuf();
const std::string src = ss.str();
c_file.close();
// 出力アセンブリファイルを開く
std::ofstream asm_file(args.asm_file_name);
if (!asm_file) {
std::cout << "cannot open asm file: " << args.asm_file_name << std::endl;
return 1;
}
try {
// 字句解析を行い，トークン列を生成する (Lexer)
lex(src, tokens);
// 構文解析を行い，ASTを生成する (Parser)
Parser parser(tokens);
ast = parser();
// 意味解析を行い，シンボルテーブルを構築する (Semantic Analyzer)
Analyzer analyzer(ast);
symbols = analyzer();
// アセンブリコードを生成する (Code Generator)
Generator generator(ast, symbols, asm_file);
generator();
// 正常終了を報告する
std::cout << "compiled: " << args.asm_file_name << std::endl;
asm_file.flush();
asm_file.close();
}
catch (std::string msg) {
std::cout << msg << std::endl;
asm_file.close();
return 1;
}
return 0;
}
// コマンドライン引数を取得する
// -c: 必須引数．入力Cソースファイル名．
// -o: 出力アセンブリファイル名．省略した場合，Cファイル名の拡張子を .asm に変更して使用．
// 何も指定せずに引数を置いた場合，入力Cソースファイル名と解釈される．
void get_args(int argc, char **argv, args_t &args) {
// 全ての引数でループ (コマンド名は飛ばす)
for (int i = 1; i < argc; i++) {
const char *arg = argv[i]; // 引数一つ
// 指定子なら
if (arg[0] == '-') {
std::string kind = arg; // 指定を保存
// インクリメントして次のパラメータを取得する
i++;
if (i >= argc) break;
// 指定されたパラメータを保存する
if (kind == "-c") args.c_file_name = argv[i];
else if (kind == "-o") args.asm_file_name = argv[i];
}
// 指定子なしの引数は入力ファイル名と解釈する
else {
args.c_file_name = argv[i];
}
}
// 入力ファイル名が .c で終わっているか確認する (短い名前での範囲外アクセスを防ぐ)
const bool c_name_ok =
args.c_file_name.length() >= 2
&& args.c_file_name.substr(args.c_file_name.length() - 2) == ".c";
// 出力ファイル名が省略されていたら，入力ファイル名の末尾の ".c" を ".asm" に変えて使う
if (c_name_ok && args.asm_file_name.empty()) {
args.asm_file_name =
args.c_file_name.substr(0, args.c_file_name.length() - 2) + ".asm";
}
// 出力ファイル名が .asm で終わっているか確認する
const bool asm_name_ok =
args.asm_file_name.length() >= 4
&& args.asm_file_name.substr(args.asm_file_name.length() - 4) == ".asm";
// コマンドライン引数が不正ではないことをチェックする
if (!c_name_ok || !asm_name_ok) {
// メッセージを出力する
std::cout << "args fail" << std::endl
<< "-c: c source file name. e.g. ~~.c" << std::endl
<< " actual: " << args.c_file_name << std::endl
<< "-o: output asm file name. e.g. ~~.asm" << std::endl
<< " actual: " << args.asm_file_name << std::endl;
// 後の処理でエラーになるよう，コマンドライン引数をクリアする
args.c_file_name.clear();
args.asm_file_name.clear();
}
}
今後の展望
これでやっと，念願のコンパイラが完成しました．
C言語(みたいな言語)で作ったプログラムを自作CPU上で実行できるようになりました．
次なる目標としては，ファイルシステムの構築ですね！
これができるようになると，やっとパソコンっぽくなってきます．
もちろんROMじゃなくて今の段階ではスモールスタートとしてRAM上にファイルを作成してみる形になります．