前回までのあらすじ
- 自作PCを作ろう！
- まずメモリを作ったよ！
- ISAを作ったよ！
- アセンブリ言語を作ったよ！
- CPUを作ったよ！
- 任意のプログラムを実行できるようになったよ！
- キーボード入力を受け付けられるようになったよ！(ただし独力ではない)
- 複数桁+複数桁の足し算が行えるようになったよ！
-
CALL命令とRET命令を実装して，関数呼び出しが可能になったよ！ - 自作CPU上で動作する自作プログラミング言語をコンパイルするコンパイラを作ったよ！
今回の目標
前回の記事で，コンパイラが(やっと)完成しました．
自作PCを作る8の記事でも書いたように，次なる目標はファイルシステムの構築です．
といっても，ROM上にファイルシステムを作るわけではありません．
まずはRAM上でファイルシステムを作ることを考えます．電源を切ったら揮発してしまいますが，RAM上に作る方が簡単だと思うので，まずはこれを実装してからROM上に配置することを考えます．
…の予定だったのですが，それをするには障害があります．
と言うのも，前回の記事で作ったコンパイラの内容がシンプルすぎる．
流石にこれでOSシステムを作るってのは大変だよね，ということでコンパイラの機能拡張をすることになりました．
具体的に，追加する内容は以下の二つです．
- 配列に対応する
- 関数の引数と返り値に対応する
まず配列については，そもそもこれがないと文字列が扱えません．
そのため標準入出力が非常に面倒です．
それだけでなく，lsなどのコマンドが入力されてきても一文字ずつ比較するソースを愚直に書かなければならず，非常に面倒ですそれはもう大変に面倒です．
関数の引数と返り値については，自作PCの経験がなくてもプログラミングの経験がある人ならわかってくれると思います．
これがないと，
- いったんグローバル変数に格納して関数呼び出し
- 計算結果を別のグローバル変数に格納
- 関数の処理終了
という事になり，非常に面倒です．
また，再帰関数にも対応できませんね．
まあ現状再帰関数に対応する予定はないのですが．
という事で今回の記事では，配列と，関数の引数戻り値，この二つに対応していきます．
前回の補足
書き忘れていましたが，このコンパイラでは以下にも対応しません．
-
const変数 (面倒くさいため．必要になったら対応する) - カンマ演算子 (どうせ使わないため)
- キャスト演算子 (普通に忘れていたため)
ここから本題
CPUの変更点
コンパイラの変更の前に，CPUの実装を変更します．
char配列を実装する場合に不都合な点があったためです．
これまでこのCPUはビッグエンディアン実装でしたが，リトルエンディアンに変更します．
つまりメモリから読み込んだ後のレジスタは以下のような感じになります．
31 23 15 7 0
|address + 3|address + 2|address + 1|address|
という事で実際のソースを変更するぞ，と思ったのですがソースをよく見てみるともうリトルエンディアンになっていました．
今まで4バイト単位でしかアクセスしていなかったので気づかなかったのですが既にこうなっていたみたいです．
あとついでに，今までのメモリ書き込みには重大なバグがあったので修正しました．
これまで，maskで書き込まないよう指定されたバイトには，0を書き込んでいました．
しかしこれっておかしいですよね．指定されていないなら変更もしないはずで，0で上書きして値リセットしてしまうのは普通にマズい．
という事でこれは修正しました．
なので修正後のソースとしてはこれだけです．
ram_sv.sv
ram_sv.sv
`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Company:
// Engineer:
//
// Create Date: 2024/07/02 20:50:34
// Design Name:
// Module Name: ram_sv
// Project Name:
// Target Devices:
// Tool Versions:
// Description:
//
// Dependencies:
//
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
//
//////////////////////////////////////////////////////////////////////////////////
`include "ram.svh"
`include "util.svh"
module ram_sv import ram_p::*, util_p::*; (
input logic clk,
input logic resetn,
// メモリデータ読み出し
ram_read_if.slave ram_read,
// メモリデータ書き込み
ram_write_if.slave ram_write
);
// メモリに保存されるデータ
memory_t memory_data = 0;
// メモリ読み出し・書き込み状態
state_enum ram_read_state = IDLE;
state_enum ram_write_state = IDLE;
always_ff @(posedge clk) begin
// リセット
if (!resetn) begin
// IO
ram_read.data <= 32'b0;
ram_read.ready <= 1'b0;
ram_read.code <= NONE;
ram_write.ready <= 1'b0;
ram_write.code <= NONE;
// 内部変数
memory_data <= 0;
ram_read_state <= IDLE;
ram_write_state <= IDLE;
end
// メモリ実行
else begin
// メモリデータ読み出し
unique case (ram_read_state)
// 待機
IDLE: begin
ram_read.code <= NONE;
// 読み出し命令を検知
if (ram_read.valid) begin
ram_read_state <= EXECUTE;
end
end
// メモリ読み込み実行
EXECUTE: begin
if (ram_read.valid) begin
ram_read.ready <= 1'b1;
// マスクに応じて読み込み
foreach (ram_read.mask[i]) begin
if (ram_read.mask[i])
// 32ビットのうち，8ビット分を出力
ram_read.data[i*8 + 7:i*8] <= memory_data[ram_read.address + i];
else
ram_read.data[i*8 + 7:i*8] <= 8'h00;
end
// 読み込みラスト？
if (ram_read.last) begin
ram_read_state <= RESPONSE;
end
end else begin
ram_read.ready <= 1'b0;
end
end
// メモリ読み込みの実行結果を返す
RESPONSE: begin
ram_read.ready <= 1'b0;
ram_read.code <= SUCCESS;
ram_read_state <= IDLE;
end
endcase
// メモリデータ書き込み
unique case (ram_write_state)
// 待機
IDLE: begin
ram_write.code <= NONE;
// 書き込み命令を検知
if (ram_write.valid) begin
ram_write_state <= EXECUTE;
end
end
// メモリ書き込み実行
EXECUTE: begin
if (ram_write.valid) begin
ram_write.ready <= 1'b1;
// マスクに応じて書き込み(マスクが立っていない番地は元の値を保持する)
foreach (ram_write.mask[i]) begin
if (ram_write.mask[i])
// 32ビットのうち，8ビット分を入力
memory_data[ram_write.address + i] <= ram_write.data[i*8 + 7:i*8];
end
// 書き込みラスト？
if (ram_write.last) begin
ram_write_state <= RESPONSE;
end
end else begin
ram_write.ready <= 1'b0;
end
end
// メモリ書き込みの実行結果を返す
RESPONSE: begin
ram_write.ready <= 1'b0;
ram_write.code <= SUCCESS;
ram_write_state <= IDLE;
end
endcase
end
end
endmodule
配列に対応する
これは実質的には文字列に対応するためです．
なので文字列リテラルにも対応します．"hello, world!"みたいなやつのことです．
基本的にはC言語仕様と同じなので特にコメントすることはないです．
char c[32]みたいに宣言して，要素へのアクセスはc[10]みたいに行います．
ちなみに，以下の制限事項があります
- 配列サイズを指定したうえで文字列リテラルで初期化することは出来ない (配列サイズと文字列リテラルのサイズをチェックするのが面倒なため．また，一度リテラルで初期化した文字列を変更する使用用途が現状ないため)
関数の引数と返り値に対応する
仕様について
引数について
引数はローカル変数と同じ扱いにします．
現状この言語では，ローカル変数はメモリ上の固定位置に配置されます．
引数も同様にメモリ上に固定配置して，関数呼び出し前にそのメモリに値を書き込む形になります．
逆に言えば，可変長引数には対応していません．また，再帰関数にも対応できませんが，これは現状別の理由により対応していないので問題ないです．
ちなみに，引数をローカル変数みたいに扱ってメモリ上に値を置くのはFortranも同じ仕組みらしいです．
あと，引数がない場合の関数宣言は()としてもいいし(void)としてもいいです．後者はC++的な書き方ですね．
配列を引数に取る場合
このコンパイラでは，ポインタに対応していません．
関数呼び出し側では，配列はC言語のように変数名を書くだけ．受け取る側では，データ型をchar []のように記述して受け取ります．ただし，受け取る実体は配列全体ではなくポインタです．プログラム上には登場しませんが，アセンブリ言語内ではポインタを扱います．関数引数のデータ型をchar []と記述しても実際にはポインタで受け取る仕様に関してはC言語と一致しますね．
返り値について
これは簡単です．レジスタ上に，戻り値用のRAXが用意されているのでそこに格納するだけです．
制限事項
以下は制限事項となります．実装しようとすると面倒くさいなどの理由で．
- オーバーロード
- デフォルト引数
- 関数呼び出し時に，同じ関数の返り値を引数に取る (例:
add(add(1, 2), 3))) - main関数の引数と返り値 (指定しても別にエラーにはならないが，特に意味もない．将来的に
lsなどのコマンドを作るときのために必要となるが，今の時点では指定しても意味はない状態) - 宣言した引数の型と違う型の値を渡すことが出来てしまう．配列の場合に特に致命的 (要素の型によって確保するメモリサイズが違うため，確保していないメモリにアクセスする危険がある．また，
charをintに渡した場合に，それが負の数だと値が崩れる．-1が255になる．スカラの場合はあたいは壊れない．スカラの場合は内部的には全てintで保存される)
printとscanの引数を変更する
これまで，printとscanの引数はchar一文字だけでした．
しかしさすがに不便すぎるので，両方ともchar配列引数に対応することにします．
仕様は以下．
printについて
配列にある文字を一つずつ出力する．終端文字に達するまで，または配列サイズの上限に達するまで．
なお，関数引数の配列の場合は配列サイズを確認する方法がないので，関数引数として受け取った配列の中身をprintすることは出来ません．
scanについて
標準入力に溜まっている文字のうち，改行文字が来るまで，または配列サイズの上限に達するまで読み込む．
文字列の末尾には終端文字を入れる．
なお，標準入力の先頭が改行文字だった場合はスキップする．
こちらもprintと同様，関数引数の場合に配列サイズが分からないのでその場合はscanできません．
なお，scanの引数に渡された配列のサイズが1だった場合は終端文字しか入れることが出来ず，意味がないのでその場合はコンパイル時点でエラーになります．
ソース
実際のプログラムがこちらです．
ちなみに，別エージェントにソースレビューしてもらって色々不具合修正も入っています．
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_PRINT, TK_SCAN,
// リテラル
TK_INT_LIT, // 整数リテラル
TK_CHAR_LIT, // 文字リテラル
TK_STRING_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_LBRACKET, // [
TK_RBRACKET, // ]
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},
{"print", TK_PRINT}, {"scan", TK_SCAN},
};
// 演算子・区切り文字文字列からトークン種別への変換表
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_LBRACKET}, {"]", TK_RBRACKET},
{";", 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;
}
// 文字列リテラル: " で始まる
if (c == '"') {
int start = i;
i++; // 開き " をスキップする
// 閉じ " が来るまで読み進める (エスケープシーケンスを考慮する)
while (i < src_size && src[i] != '"') {
if (src[i] == '\n') {
throw std::string("compiler error: newline in string literal at line ")
+ std::to_string(line);
}
if (src[i] == '\\') i++; // エスケープ文字の次をスキップする
i++;
}
if (i >= src_size) {
throw std::string("compiler error: unterminated string literal at line ")
+ std::to_string(line);
}
i++; // 閉じ " をスキップする
// 引用符を除いた中身を取得する (エスケープシーケンスはパーサーで解釈する)
const std::string content = src.substr(start + 1, i - start - 2);
// 隣接する文字列リテラルを連結する ("hello" " world" → hello world)
if (!tokens.empty() && tokens.back().kind == TK_STRING_LIT) {
tokens.back().value += content;
} else {
tokens.push_back({TK_STRING_LIT, content, 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;
}
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 = BASE_INT; // 基本型
bool is_signed = true; // signed/unsigned (unsignedは未対応のため常にtrue)
bool is_array = false; // 配列かどうか
int array_size = 0; // 配列の要素数 (is_array==trueのとき有効)
} 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_STRING_LIT, // 文字列リテラル (svalに引用符なしの文字列内容を格納)
ND_VAR, // 変数参照
ND_ARRAY_ACCESS, // 配列要素アクセス a[i] (children: [インデックス式])
} 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; // 現在のトークンを覗き見る (消費しない)
token_kind_t peek_kind_ahead(int offset) const; // pos_+offset先のトークン種別を返す (範囲外ならTK_EOF扱い)
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); // 文字リテラル文字列を文字コードに変換する
static std::string parse_string_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_param(); // 関数パラメータ (型 名前)
node_t *parse_print(); // 組み込み関数print(char配列)
node_t *parse_scan(); // 組み込み関数scan(char配列)
node_t *parse_sizeof(); // sizeof(型名 または 変数名)
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 <stdexcept>
#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_];
}
// pos_からoffset先のトークン種別を返す (範囲外ならTK_EOF扱いにして安全に返す)
token_kind_t Parser::peek_kind_ahead(int offset) const {
const size_t idx = this->pos_ + offset;
if (idx >= this->tokens_.size()) {
return TK_EOF;
}
return this->tokens_[idx].kind;
}
// 現在のトークンの種別が一致するか調べる (消費しない)
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());
}
// 型キーワード(int/char/short等)で始まるなら関数定義またはグローバル変数宣言
else if (Parser::is_type_start(this->peek_token().kind)) {
// signed/unsignedがあれば，本体の型キーワードは1つ後ろにずれる
const token_kind_t first_kind = this->peek_token().kind;
const int offset = (first_kind == TK_SIGNED || first_kind == TK_UNSIGNED) ? 1 : 0;
// 型の次が識別子でなければエラー (範囲外アクセスを避けてEOF扱いで判定する)
if (this->peek_kind_ahead(offset + 1) != TK_IDENT) {
throw std::string("compiler error: expected identifier after type at line ")
+ std::to_string(this->peek_token().line);
}
// 識別子の次が '(' なら関数定義，それ以外は変数宣言
if (this->peek_kind_ahead(offset + 2) == TK_LPAREN) {
node->children.push_back(this->parse_func_def());
} else {
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) ブロック
node_t *Parser::parse_func_def() {
node_t *node = this->new_node(ND_FUNC_DEF); // 関数ノード
// signed/unsigned修飾子 (unsignedは未対応のためここで専用エラーにする)
if (this->token_kind_is(TK_SIGNED)) {
this->get_token();
} else if (this->token_kind_is(TK_UNSIGNED)) {
throw std::string("compiler error: 'unsigned' is not supported yet at line ")
+ std::to_string(this->peek_token().line);
}
// 戻り値型を読む
base_type_t ret_base;
const token_kind_t ret_kind = this->peek_token().kind;
if (ret_kind == TK_VOID) { ret_base = BASE_VOID; this->get_token(); }
else if (ret_kind == TK_INT) { ret_base = BASE_INT; this->get_token(); }
else if (ret_kind == TK_CHAR) { ret_base = BASE_CHAR; this->get_token(); }
else if (ret_kind == TK_SHORT) { ret_base = BASE_SHORT; this->get_token(); }
else {
throw std::string("compiler error: expected return type at line ")
+ std::to_string(this->peek_token().line);
}
node->type = {ret_base, true};
// 関数名
node->sval = this->get_token(TK_IDENT).value; // 関数名
this->get_token(TK_LPAREN); // 開きカッコ
// パラメータリスト: (void) / () は引数なし，それ以外は型+名前のカンマ区切り
if (this->token_kind_is(TK_VOID) && this->peek_kind_ahead(1) == TK_RPAREN) {
// (void) : 引数なし
this->get_token();
} else if (!this->token_kind_is(TK_RPAREN)) {
// パラメータを1つ以上パースする
node->children.push_back(this->parse_param());
while (!this->token_kind_is(TK_RPAREN)) {
this->get_token(TK_COMMA); // , を消費
node->children.push_back(this->parse_param());
}
}
// () : 引数なしの場合はそのまま閉じ括弧へ
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);
// セミコロンでなければ戻り値の式をパースする
if (!this->token_kind_is(TK_SEMICOLON)) {
node->children.push_back(this->parse_expr());
}
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 ( char配列 ) ※ ヌル終端までを標準出力へ出力する
node_t *Parser::parse_print() {
node_t *node = this->new_node(ND_PRINT);
this->get_token(TK_PRINT); // print
this->get_token(TK_LPAREN); // (
node->children.push_back(this->parse_expr()); // 出力する配列
this->get_token(TK_RPAREN); // )
return node;
}
// 組み込み関数scanを解析してND_SCANを返す
// 構文: scan ( char配列 ) ※ 改行までの1行をヌル終端付きで配列へ格納する
node_t *Parser::parse_scan() {
node_t *node = this->new_node(ND_SCAN);
this->get_token(TK_SCAN); // scan
this->get_token(TK_LPAREN); // (
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;
}
// sizeof式を解析してND_SIZEOFを返す
// 構文: sizeof ( 型名 ) または sizeof ( 変数名 ) TODO: 任意の式には非対応
// 型名の場合はnode->typeに型を格納し(children空)，変数名の場合はchildren[0]にND_VARを格納する(意味解析で解決)
node_t *Parser::parse_sizeof() {
node_t *node = this->new_node(ND_SIZEOF);
this->get_token(TK_SIZEOF); // sizeof
this->get_token(TK_LPAREN); // (
const token_kind_t kind = this->peek_token().kind;
if (kind == TK_INT) { node->type = {BASE_INT, true}; this->get_token(); }
else if (kind == TK_CHAR) { node->type = {BASE_CHAR, true}; this->get_token(); }
else if (kind == TK_SHORT) { node->type = {BASE_SHORT, true}; this->get_token(); }
else {
// 型名でなければ変数名として解析する (意味解析で型を確定する)
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を返す
// 構文: 型 変数名 (初期化子・セミコロンなし)
node_t *Parser::parse_param() {
node_t *node = this->new_node(ND_VAR_DECL);
// signed/unsigned修飾子 (unsignedは未対応のためここで専用エラーにする)
if (this->token_kind_is(TK_SIGNED)) {
this->get_token();
} else if (this->token_kind_is(TK_UNSIGNED)) {
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 kind = this->peek_token().kind;
if (kind == TK_INT) { base = BASE_INT; this->get_token(); }
else if (kind == TK_CHAR) { base = BASE_CHAR; this->get_token(); }
else if (kind == TK_SHORT) { base = BASE_SHORT; this->get_token(); }
else {
throw std::string("compiler error: expected parameter type at line ")
+ std::to_string(this->peek_token().line);
}
node->type = {base, true};
// パラメータ名
node->sval = this->get_token(TK_IDENT).value;
// 配列パラメータ: 名前の後に [] があれば配列引数 (サイズ指定なし)
if (this->token_kind_is(TK_LBRACKET)) {
this->get_token(TK_LBRACKET);
this->get_token(TK_RBRACKET);
node->type.is_array = true;
}
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_LBRACKET)) {
this->get_token(TK_LBRACKET); // [
node->type.is_array = true;
if (this->token_kind_is(TK_RBRACKET)) {
// サイズ省略: char msg[] = "hello"; の形式 (サイズは意味解析で文字列長から決定する)
this->get_token(TK_RBRACKET); // ]
this->get_token(TK_ASSIGN); // =
node->children.push_back(this->parse_expr()); // 文字列リテラル (ND_STRING_LIT)
} else {
// サイズ明示: int table[10]; の形式
node->children.push_back(this->parse_expr());
this->get_token(TK_RBRACKET); // ]
}
}
// スカラー変数の初期化式があれば読む
else 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_LBRACKET)) {
// []の前は変数名でなければならない (例: (a+b)[0]は非対応)
if (node->kind != ND_VAR) {
throw std::string("compiler error: expected variable name before '[' at line ")
+ std::to_string(this->peek_token().line);
}
this->get_token(TK_LBRACKET); // [
node_t *access = this->new_node(ND_ARRAY_ACCESS);
access->line = node->line;
access->sval = node->sval; // 配列名
access->children.push_back(this->parse_expr()); // インデックス式
this->get_token(TK_RBRACKET); // ]
// 配列要素への後置++/--は非対応 (仕様上の制限)
if (this->token_kind_is(TK_PLUSPLUS) || this->token_kind_is(TK_MINUSMINUS)) {
throw std::string("compiler error: '++'/'--' on array element is not supported at line ")
+ std::to_string(this->peek_token().line);
}
return access;
}
// 後置インクリメント・デクリメント
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;
}
// 関数呼び出し: 引数の式をカンマ区切りでchildrenに格納する
if (this->token_kind_is(TK_LPAREN)) {
// (の前は関数名でなければならない (例: (a+b)(1)は非対応)
if (node->kind != ND_VAR) {
throw std::string("compiler error: expected function name before '(' at line ")
+ std::to_string(this->peek_token().line);
}
this->get_token(); // (
node_t *call = this->new_node(ND_CALL);
call->line = node->line;
call->sval = node->sval; // 関数名
// 引数がある場合はカンマ区切りでパースする
if (!this->token_kind_is(TK_RPAREN)) {
call->children.push_back(this->parse_expr());
while (!this->token_kind_is(TK_RPAREN)) {
this->get_token(TK_COMMA); // , を消費
call->children.push_back(this->parse_expr());
}
}
this->get_token(TK_RPAREN); // )
return call;
}
return node;
}
// 基本式を解析してASTノードを返す
// 対応するもの: 整数リテラル・文字リテラル・文字列リテラル・sizeof・変数参照・括弧式
node_t *Parser::parse_primary() {
// sizeof(型名 または 変数名)
if (this->token_kind_is(TK_SIZEOF)) {
return this->parse_sizeof();
}
// 組み込み関数print/scan (予約語のため専用トークンで判定する)
if (this->token_kind_is(TK_PRINT)) return this->parse_print();
if (this->token_kind_is(TK_SCAN)) return this->parse_scan();
// 整数リテラル
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_STRING_LIT)) {
node_t *node = this->new_node(ND_STRING_LIT);
node->sval = Parser::parse_string_literal(this->get_token().value);
return node;
}
// 変数参照・関数呼び出し (print/scanは予約語のため専用トークンで上で処理済み)
if (this->token_kind_is(TK_IDENT)) {
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(64bit)の範囲を超えるリテラルはstd::stollがstd::out_of_rangeを投げるため，ここで捕捉してコンパイルエラーに変換する
long long Parser::parse_int_literal(const std::string &text) {
long long value;
try {
if (text.size() >= 2 && text[0] == '0' && (text[1] == 'x' || text[1] == 'X')) {
value = std::stoll(text.substr(2), nullptr, 16);
} else {
value = std::stoll(text, nullptr, 10);
}
} catch (const std::out_of_range &) {
throw std::string("compiler error: integer literal out of range: ") + text;
} catch (const std::invalid_argument &) {
throw std::string("compiler error: invalid integer literal: ") + text;
}
// intは32ビットなので，リテラル自体はint型の範囲(0〜2147483647)に収まっているか検査する
// (単項マイナスは別トークンとして扱われここでは付与されていないため，C言語同様リテラル自体の絶対値だけで判定する．
// そのため-2147483648(intの最小値)はこの言語では表現できない)
if (value < 0 || value > 2147483647LL) {
throw std::string("compiler error: integer literal out of range: ") + text;
}
return value;
}
// 文字リテラル文字列 ('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]);
}
}
// 文字列リテラル(引用符除去済み)のエスケープシーケンスを解釈する
std::string Parser::parse_string_literal(const std::string &text) {
std::string result;
for (size_t i = 0; i < text.size(); i++) {
if (text[i] == '\\' && i + 1 < text.size()) {
// エスケープシーケンスを変換する
i++;
switch (text[i]) {
case 'n': result += '\n'; break;
case 't': result += '\t'; break;
case 'r': result += '\r'; break;
case '0': result += '\0'; break;
case '\\': result += '\\'; break;
case '\'': result += '\''; break;
case '"': result += '"'; break;
default: result += text[i]; break;
}
} else {
result += text[i];
}
}
return result;
}
analyzer
analyzer.hpp
#pragma once
#include <map>
#include <set>
#include <string>
#include <vector>
#include "parser.hpp"
// ハードウェア制約: 関数呼び出しネストの最大段数 (戻り先レジスタ6'h11〜6'h1aの10本による)
const int MAX_CALL_DEPTH = 10;
// ハードウェア制約: プログラムの最大命令数 (ROMの容量による．c2asm.cppで生成後に検査する)
const int MAX_INSTRUCTION_COUNT = 255;
// ハードウェア制約: 汎用レジスタの本数 (r0〜r15の16本)
const int MAX_REG = 16;
// 変数の置き場所の種別
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()(); // 意味解析を実行してシンボルテーブルを返す
// パラメータシンボル表 (関数名→パラメータのシンボル列．コード生成で引数の書き込み先アドレスに使う)
const std::map<std::string, std::vector<const symbol_t *>> &func_params() const;
// 呼び出しをまたいで生かしたいレジスタ値の退避領域の先頭番地
// (呼び出された関数はr0から使い直すため，レジスタは呼び出しをまたいで保持されない．
// 全変数のアドレス割り当てが終わった直後の空き番地から，MAX_REG個分の退避枠を確保している)
int scratch_base() const;
private:
node_t *root_; // AST
std::map<std::string, const symbol_t *> symbols_; // シンボルテーブル (変数名→保存先番地等の対応表)
std::map<std::string, type_t> func_names_; // 定義済み関数名→戻り値型の対応表
std::map<std::string, std::vector<const symbol_t *>> func_params_; // 関数名→パラメータのシンボル列
int next_addr_; // 次に割り当てるメモリ番地 (グローバル→ローカルで連番)
int scratch_base_; // レジスタ退避領域の先頭番地 (全変数のアドレス割り当て後に確保)
std::vector<std::map<std::string, const symbol_t *>> scopes_; // ローカル変数のスコープスタック (内側ほど後ろ)
int loop_depth_ = 0; // ループの入れ子の深さ (break/continueの検査用)
int switch_depth_ = 0; // switchの入れ子の深さ (breakの検査用)
std::string current_function_; // 現在解析中の関数名 (呼び出しグラフ構築用)
type_t current_return_type_; // 現在解析中の関数の戻り値型 (return文の整合性検査用)
std::map<std::string, std::set<std::string>> call_graph_; // 関数名→直接呼び出す関数名の集合 (ネスト段数検査用)
// 解析メソッド
void collect_globals(); // 1パス目: グローバル変数の登録と関数名の収集
// 定数式をコンパイル時に計算する (初期化子・配列サイズ・case値)
// sizeof(変数名)の解決にシンボルテーブル参照が必要なため非static
long long eval_const_expr(const node_t *expr);
static int calc_array_words(const type_t &type); // 配列が占有するワード数を計算する
static int type_size_bytes(const type_t &type); // 型のバイト数を返す (sizeof用．配列は要素数×要素サイズ)
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; // 名前からシンボルを探す (スコープ→グローバル)
// 呼び出しグラフを検査する (再帰の検出，最大ネスト段数MAX_CALL_DEPTHの超過検出)
void check_call_depth();
// mainから呼び出しグラフを深さ優先探索し，再帰(既に経路上にある関数への到達)とネスト段数を検査する
// path: 現在の呼び出し経路(再帰検出用)．depthは戻り値(mainからのネスト段数の最大値)
int check_call_depth_dfs(const std::string &func, std::set<std::string> &path);
};
analyzer.cpp
#include <set>
#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パス目: 各関数本体を検査する
// (analyze_expr内のND_CALLケースが，通りがけに全関数の呼び出し先をcall_graph_へ記録する．
// ここまで完了した時点で，どの関数がどの関数を呼ぶかの記録がすべて出揃っている)
this->analyze_functions();
// 呼び出しグラフを検査する (再帰の検出，最大ネスト段数の超過検出)
this->check_call_depth();
// レジスタ退避領域を，全変数のアドレス割り当て後の空き番地に確保する
this->scratch_base_ = this->next_addr_;
this->next_addr_ += MAX_REG * 4;
// 全変数の合計アドレスがアドレス空間(28ビット)を超えていないか確認する
if (this->next_addr_ > 0x10000000) {
throw std::string("compiler error: total variable memory exceeds address space (28-bit)");
}
return this->symbols_;
}
// パラメータシンボル表を返す
const std::map<std::string, std::vector<const symbol_t *>> &Analyzer::func_params() const {
return this->func_params_;
}
// レジスタ退避領域の先頭番地を返す
int Analyzer::scratch_base() const {
return this->scratch_base_;
}
// 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->type.is_array) {
if (!child->children.empty() && child->children[0]->kind == ND_STRING_LIT) {
// 文字列リテラルによる初期化: char msg[] = "hello";
if (child->type.base != BASE_CHAR) {
throw std::string("compiler error: string literal can only initialize char array at line ")
+ std::to_string(child->children[0]->line);
}
// サイズは文字列長 + 1(ヌル終端)
const int size = static_cast<int>(child->children[0]->sval.size()) + 1;
child->type.array_size = size;
} else {
// サイズ明示の配列宣言: int table[10];
const long long size = Analyzer::eval_const_expr(child->children[0]);
if (size <= 0) {
throw std::string("compiler error: array size must be positive at line ")
+ std::to_string(child->children[0]->line);
}
child->type.array_size = static_cast<int>(size);
// サイズ式を畳み込み済みリテラルに置き換える
node_t *folded = new node_t;
folded->kind = ND_INT_LIT;
folded->ival = size;
folded->line = child->children[0]->line;
child->children[0] = folded;
}
// アドレスを割り当てて登録する (確保ワード数は型に応じて計算)
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_ += Analyzer::calc_array_words(child->type) * 4;
} else {
// スカラー変数: 初期化子があればコンパイル時に計算し，リテラルに置き換える(定数畳み込み)
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バイト)使う
}
}
// 関数定義: 関数名・戻り値型・パラメータのシンボルを登録する
// 呼び出し側の引数検査(analyze_expr の ND_CALL)は2パス目より前に全関数のパラメータが必要なため，
// パラメータの番地割り当てもここ(1パス目)で行う．2パス目(analyze_functions)はここで作った
// シンボルをスコープに積んで本体を検査するだけになる
else if (child->kind == ND_FUNC_DEF) {
this->func_names_[child->sval] = child->type;
std::vector<const symbol_t *> params;
for (size_t i = 0; i + 1 < child->children.size(); i++) {
node_t *param = child->children[i];
// 同一関数内でのパラメータ名重複はエラー
for (const symbol_t *p : params) {
if (p->name == param->sval) {
throw std::string("compiler error: duplicate parameter name '") + param->sval
+ "' at line " + std::to_string(param->line);
}
}
// ハードウェア変数と同名のパラメータは禁止する (I/Oレジスタを上書きしないように)
const auto hw_it = this->symbols_.find(param->sval);
if (hw_it != this->symbols_.end() && hw_it->second->location == LOC_REGISTER) {
throw std::string("compiler error: cannot shadow hardware register '") + param->sval
+ "' at line " + std::to_string(param->line);
}
symbol_t *sym = new symbol_t{param->sval, param->type, LOC_LOCAL, this->next_addr_, true, true};
this->next_addr_ += 4;
param->sym = sym;
params.push_back(sym);
}
this->func_params_[child->sval] = params;
}
}
}
// コンパイル時に値が確定する定数式を計算して値を返す (定数畳み込み)
// 呼び出し元 (=定数式が要求される文脈): グローバル配列のサイズ指定・グローバルスカラー変数の初期化子・
// ローカル配列のサイズ指定・switch文のcase値
// 変数参照や関数呼び出しなど，コンパイル時に値が確定しない式を含む場合はエラーにする．
// ただし sizeof(変数名) だけは例外で許可する．sizeofが必要とするのは変数の「値」ではなく「型のサイズ」であり，
// 型は変数の値と無関係にシンボルテーブルから分かるため，変数参照であってもコンパイル時に確定できるため
long long Analyzer::eval_const_expr(const node_t *expr) {
// リテラルはそのまま値を返す
if (expr->kind == ND_INT_LIT || expr->kind == ND_CHAR_LIT) {
return expr->ival;
}
// sizeof: 型名，または変数名の型サイズをコンパイル時に返す (式自体は評価しない)
if (expr->kind == ND_SIZEOF) {
if (expr->children.empty()) {
// sizeof(型名)
return Analyzer::type_size_bytes(expr->type);
}
// sizeof(変数名): 値ではなく型だけが必要なのでND_VARのみ許可する
const node_t *inner = expr->children[0];
if (inner->kind != ND_VAR) {
throw std::string("compiler error: sizeof argument in a constant expression "
"must be a type name or variable name at line ")
+ std::to_string(inner->line);
}
const symbol_t *sym = this->lookup_symbol(inner->sval);
if (sym == nullptr) {
throw std::string("compiler error: use of undeclared identifier '") + inner->sval
+ "' at line " + std::to_string(inner->line);
}
// 関数引数の配列が使用される可能性もあるのでそれをチェック
if (sym->type.is_array && sym->type.array_size == 0) {
throw std::string("compiler error: sizeof of an array parameter (size unknown) at line ")
+ std::to_string(inner->line);
}
return Analyzer::type_size_bytes(sym->type);
}
// 前置単項演算
if (expr->kind == ND_UNOP) {
const long long v = this->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 = this->eval_const_expr(expr->children[0]);
const long long r = this->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);
}
// 配列が占有するワード数を計算する (int=1要素1ワード, short=2要素1ワード, char=4要素1ワード)
int Analyzer::calc_array_words(const type_t &type) {
const int n = type.array_size;
switch (type.base) {
case BASE_INT: return n; // 32ビット: 1要素=1ワード
case BASE_SHORT: return (n + 1) / 2; // 16ビット: 2要素=1ワード
case BASE_CHAR: return (n + 3) / 4; // 8ビット: 4要素=1ワード
default:
throw std::string("compiler error: unsupported array element type");
}
}
// 型の論理バイト数を返す (sizeof用．C言語準拠で実メモリのワード境界は考慮しない)
// 配列は「要素数 × 要素型のバイト数」を返す
int Analyzer::type_size_bytes(const type_t &type) {
int elem_bytes;
switch (type.base) {
case BASE_CHAR: elem_bytes = 1; break;
case BASE_SHORT: elem_bytes = 2; break;
case BASE_INT: elem_bytes = 4; break;
default:
throw std::string("compiler error: sizeof of unsupported type");
}
return type.is_array ? elem_bytes * type.array_size : elem_bytes;
}
// 2パス目: 各関数本体を検査する
// ND_FUNC_DEFのchildren = [param0, param1, ..., block] (パラメータがなければchildren[0]がブロック)
void Analyzer::analyze_functions() {
for (node_t *child : this->root_->children) {
if (child->kind != ND_FUNC_DEF) continue;
// 現在解析中の関数名・戻り値型を記録する (呼び出しグラフ構築・return文の整合性検査用)
this->current_function_ = child->sval;
this->current_return_type_ = child->type;
this->call_graph_[child->sval]; // 呼び出し先が無い関数もグラフに登録しておく(空集合)
// 関数スコープを開く (パラメータと本体のローカル変数が同じスコープに入る)
this->scopes_.push_back({});
// パラメータをスコープに登録する (シンボル自体は1パス目のcollect_globalsで作成済み)
for (const symbol_t *sym : this->func_params_[child->sval]) {
this->scopes_.back()[sym->name] = sym;
}
// 関数本体ブロック(最後の子)を検査する
this->analyze_block(child->children.back());
// 関数スコープを閉じる
this->scopes_.pop_back();
}
}
// 呼び出しグラフを検査する (再帰の検出，最大ネスト段数MAX_CALL_DEPTHの超過検出)
// mainを起点に深さ優先探索する(mainはCALLされないため，ネスト段数の起点として数えない)
void Analyzer::check_call_depth() {
std::set<std::string> path; // 現在の呼び出し経路(再帰検出用)
this->check_call_depth_dfs("main", path);
}
// funcから辿れる呼び出し経路を深さ優先探索し，再帰とネスト段数超過を検査する
// pathには現在の探索経路上にある関数名が入っている(再帰=pathに既にある関数への到達で検出する)
// 戻り値: funcを起点とした場合の最大ネスト段数(func自身は含まず，呼び出し先の段数のみ)
int Analyzer::check_call_depth_dfs(const std::string &func, std::set<std::string> &path) {
// 現在の経路に既にfuncがあれば，直接・間接を問わず再帰(循環)
if (path.count(func)) {
throw std::string("compiler error: recursive function call detected involving '") + func + "'";
}
path.insert(func); // 経路にfuncを追加してから子を探索する
int max_depth = 0; // funcの呼び出し先の中で最も深いネスト段数
for (const std::string &callee : this->call_graph_[func]) {
const int callee_depth = this->check_call_depth_dfs(callee, path);
if (callee_depth + 1 > max_depth) {
max_depth = callee_depth + 1;
}
}
path.erase(func); // 探索し終えたので経路から外す(他の兄弟経路と共有しないため)
if (max_depth > MAX_CALL_DEPTH) {
throw std::string("compiler error: function call nesting exceeds maximum depth (")
+ std::to_string(MAX_CALL_DEPTH) + ") at '" + func + "'";
}
return max_depth;
}
// ブロックを検査する (新しいローカルスコープを積み，抜けるときに捨てる)
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文: 関数の戻り値型とreturn文の有無・値が一致するか検査する
else if (stmt->kind == ND_RETURN) {
if (stmt->children.empty()) {
// void関数はreturn文自体が任意なので，値なしのreturn;はvoid以外のときのみエラー
if (this->current_return_type_.base != BASE_VOID) {
throw std::string("compiler error: non-void function '") + this->current_function_
+ "' must return a value at line " + std::to_string(stmt->line);
}
} else {
if (this->current_return_type_.base == BASE_VOID) {
throw std::string("compiler error: void function '") + this->current_function_
+ "' cannot return a value at line " + std::to_string(stmt->line);
}
this->analyze_expr(stmt->children[0]);
}
}
// 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);
}
if (decl->type.is_array) {
if (!decl->children.empty() && decl->children[0]->kind == ND_STRING_LIT) {
// 文字列リテラルによる初期化: char msg[] = "hello";
if (decl->type.base != BASE_CHAR) {
throw std::string("compiler error: string literal can only initialize char array at line ")
+ std::to_string(decl->children[0]->line);
}
// サイズは文字列長 + 1(ヌル終端)
const int size = static_cast<int>(decl->children[0]->sval.size()) + 1;
decl->type.array_size = size;
} else {
// サイズ明示の配列宣言: int table[10];
const long long size = Analyzer::eval_const_expr(decl->children[0]);
if (size <= 0) {
throw std::string("compiler error: array size must be positive at line ")
+ std::to_string(decl->children[0]->line);
}
decl->type.array_size = static_cast<int>(size);
// サイズ式を畳み込み済みリテラルに置き換える
node_t *folded = new node_t;
folded->kind = ND_INT_LIT;
folded->ival = size;
folded->line = decl->children[0]->line;
decl->children[0] = folded;
}
// アドレスを割り当てて登録する
symbol_t *sym = new symbol_t{decl->sval, decl->type, LOC_LOCAL, this->next_addr_, true, true};
this->next_addr_ += Analyzer::calc_array_words(decl->type) * 4;
this->scopes_.back()[decl->sval] = sym;
decl->sym = sym;
} else {
// スカラー変数: 初期化式があれば先に検査する (登録より前に行い，自己参照 int x = x; では外側のxを参照させる)
if (!decl->children.empty()) {
this->analyze_expr(decl->children[0]);
// void関数の戻り値(値を持たない)で初期化することはできない
if (decl->children[0]->type.base == BASE_VOID) {
throw std::string("compiler error: cannot initialize with void value at line ")
+ std::to_string(decl->line);
}
}
// メモリ番地を割り当てて登録する (ローカルも静的割り当てで固定番地)
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;
// 文字列リテラル: 匿名のグローバルchar配列としてメモリを確保する
case ND_STRING_LIT: {
// サイズは文字列長 + 1(ヌル終端)
type_t str_type = {BASE_CHAR, true, true, static_cast<int>(expr->sval.size()) + 1};
symbol_t *sym = new symbol_t{"", str_type, LOC_GLOBAL, this->next_addr_, true, false};
this->next_addr_ += Analyzer::calc_array_words(str_type) * 4;
expr->sym = sym;
expr->type = str_type;
return;
}
// sizeof: 型のバイト数をコンパイル時に確定するintリテラルとして扱う (実行時命令は生成しない)
case ND_SIZEOF: {
int size;
if (expr->children.empty()) {
// sizeof(型名): パーサがexpr->typeに型を格納済み
size = Analyzer::type_size_bytes(expr->type);
} else {
// sizeof(変数名): 値ではなく型だけが必要なのでND_VARのみ許可する
// (analyze_exprではなくlookup_symbolで直接型を取得する．readable=falseの
// 書き込み専用ハードウェア変数(LED等)もsizeofの対象になり得るため)
node_t *inner = expr->children[0];
if (inner->kind != ND_VAR) {
throw std::string("compiler error: sizeof argument must be a type name or "
"variable name at line ") + std::to_string(inner->line);
}
const symbol_t *sym = this->lookup_symbol(inner->sval);
if (sym == nullptr) {
throw std::string("compiler error: use of undeclared identifier '")
+ inner->sval + "' at line " + std::to_string(inner->line);
}
inner->sym = sym;
inner->type = sym->type;
size = Analyzer::type_size_bytes(sym->type);
}
expr->ival = size;
expr->type = type_t{BASE_INT, true}; // sizeofの結果はint
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_ARRAY_ACCESS) {
this->analyze_expr(lhs); // 左辺(配列要素)の名前解決
this->analyze_expr(expr->children[1]); // 右辺の式を検査する
// void関数の戻り値(値を持たない)を代入することはできない
if (expr->children[1]->type.base == BASE_VOID) {
throw std::string("compiler error: cannot assign void value at line ")
+ std::to_string(expr->line);
}
expr->type = lhs->type;
return;
}
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]); // 右辺を検査する
// void関数の戻り値(値を持たない)を代入することはできない
if (expr->children[1]->type.base == BASE_VOID) {
throw std::string("compiler error: cannot assign void value at line ")
+ std::to_string(expr->line);
}
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;
}
// その他の前置単項演算子(-, +, !, ~): 子を検査し，void値の使用を禁止する
this->analyze_expr(expr->children[0]);
if (expr->children[0]->type.base == BASE_VOID) {
throw std::string("compiler error: cannot use void value in expression at line ")
+ std::to_string(expr->line);
}
expr->type = expr->children[0]->type;
return;
// 関数呼び出し: 関数の定義確認・引数数の検証・各引数式の検査・戻り値型の設定
case ND_CALL: {
auto it = this->func_names_.find(expr->sval);
if (it == this->func_names_.end()) {
throw std::string("compiler error: call to undefined function '")
+ expr->sval + "' at line " + std::to_string(expr->line);
}
// 呼び出しグラフに記録する (再帰・ネスト段数の検査用)
this->call_graph_[this->current_function_].insert(expr->sval);
// 引数の数がパラメータの数と一致するか検証する
const auto ¶ms = this->func_params_[expr->sval];
if (expr->children.size() != params.size()) {
throw std::string("compiler error: function '") + expr->sval + "' expects "
+ std::to_string(params.size()) + " argument(s) but got "
+ std::to_string(expr->children.size())
+ " at line " + std::to_string(expr->line);
}
// 各引数式を検査する
for (size_t i = 0; i < expr->children.size(); i++) {
this->analyze_expr(expr->children[i]);
// void値(戻り値のない関数呼び出し)は引数に使えない
if (expr->children[i]->type.base == BASE_VOID) {
throw std::string("compiler error: cannot use void value in expression at line ")
+ std::to_string(expr->children[i]->line);
}
// 配列パラメータには配列変数または文字列リテラルを，スカラーパラメータにはスカラー式を渡す
node_t *arg = expr->children[i];
if (params[i]->type.is_array) {
if ((arg->kind != ND_VAR && arg->kind != ND_STRING_LIT) || !arg->sym->type.is_array) {
throw std::string("compiler error: argument for array parameter '")
+ params[i]->name + "' must be an array variable or string literal at line "
+ std::to_string(arg->line);
}
// TODO: スカラ変数の対応後にコメントアウトを外す
// // 要素型の不一致チェック (char配列をint配列パラメータに渡す等を防ぐ)
// if (arg->sym->type.base != params[i]->type.base) {
// throw std::string("compiler error: array element type mismatch for parameter '")
// + params[i]->name + "' at line " + std::to_string(arg->line);
// }
} else {
if (arg->kind == ND_VAR && arg->sym->type.is_array) {
throw std::string("compiler error: cannot pass array '")
+ arg->sval + "' to scalar parameter '"
+ params[i]->name + "' at line " + std::to_string(arg->line);
}
// TODO: func(1 + 2) など計算式を引数に与えた場合に型を正確に推論する仕組みが出来たらコメントアウトを外す
// // スカラー引数の型不一致チェック (charをintパラメータに渡す等を防ぐ)
// if (arg->type.base != params[i]->type.base) {
// throw std::string("compiler error: argument type mismatch for parameter '")
// + params[i]->name + "' at line " + std::to_string(arg->line);
// }
}
}
expr->type = it->second;
return;
}
// 組み込み関数print: char配列(直接配列)のみ対応．ヌル終端まで出力する
case ND_PRINT: {
node_t *target = expr->children[0];
this->analyze_expr(target);
if (!target->type.is_array || target->type.base != BASE_CHAR) {
throw std::string("compiler error: print requires a char array at line ")
+ std::to_string(target->line);
}
if (target->type.array_size == 0) {
throw std::string("compiler error: print does not support array parameters (size unknown) at line ")
+ std::to_string(target->line);
}
// printは値を返さない(void)．戻り値を式として使うコードを既存のvoidチェック経路で検出させる
expr->type = type_t{BASE_VOID, true};
return;
}
// 組み込み関数scan: char配列(直接配列，2要素以上)のみ対応．改行までの1行をヌル終端付きで格納する
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;
if (!sym->type.is_array || sym->type.base != BASE_CHAR) {
throw std::string("compiler error: scan requires a char array at line ")
+ std::to_string(target->line);
}
if (sym->type.array_size == 0) {
throw std::string("compiler error: scan does not support array parameters (size unknown) at line ")
+ std::to_string(target->line);
}
if (sym->type.array_size < 2) {
throw std::string("compiler error: scan target array must have at least 2 elements "
"(1 for content plus 1 for null terminator) at line ")
+ std::to_string(target->line);
}
// scanは値を返さない(void)．戻り値を式として使うコードを既存のvoidチェック経路で検出させる
expr->type = type_t{BASE_VOID, true};
return;
}
// 配列要素アクセス: 配列変数の名前解決とインデックス式の検査を行う
case ND_ARRAY_ACCESS: {
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->type.is_array) {
throw std::string("compiler error: '") + expr->sval
+ "' is not an array at line " + std::to_string(expr->line);
}
expr->sym = sym;
// 要素の型は配列のbase型(スカラー)
expr->type = {sym->type.base, sym->type.is_signed};
// インデックス式を検査する
this->analyze_expr(expr->children[0]);
// void値(戻り値のない関数呼び出し)は配列インデックスに使えない
if (expr->children[0]->type.base == BASE_VOID) {
throw std::string("compiler error: cannot use void value in expression at line ")
+ std::to_string(expr->children[0]->line);
}
return;
}
// 二項演算: 両辺を検査し，どちらかがvoid値(戻り値のない関数呼び出し)なら使用を禁止する
case ND_BINOP:
this->analyze_expr(expr->children[0]);
this->analyze_expr(expr->children[1]);
if (expr->children[0]->type.base == BASE_VOID || expr->children[1]->type.base == BASE_VOID) {
throw std::string("compiler error: cannot use void value in expression at line ")
+ std::to_string(expr->line);
}
expr->type = expr->children[0]->type;
return;
// 三項演算 a ? b : c: 条件・両分岐を検査し，いずれかがvoid値なら使用を禁止する
case ND_TERNARY:
this->analyze_expr(expr->children[0]);
this->analyze_expr(expr->children[1]);
this->analyze_expr(expr->children[2]);
if (expr->children[0]->type.base == BASE_VOID ||
expr->children[1]->type.base == BASE_VOID ||
expr->children[2]->type.base == BASE_VOID) {
throw std::string("compiler error: cannot use void value in expression at line ")
+ std::to_string(expr->line);
}
expr->type = expr->children[1]->type;
return;
// 到達しない (式ノードの全種類は上記いずれかのcaseで処理される)．
// 将来式ノードを追加した際に検査漏れとなるのを防ぐため，未対応として即エラーにする
default:
throw std::string("compiler error: unsupported expression node kind at line ")
+ std::to_string(expr->line);
}
}
// 名前からシンボルを探す (内側のローカルスコープから順に，最後にグローバル・ハードウェア変数)
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;
}
generator
generator.hpp
#pragma once
#include <fstream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "analyzer.hpp"
// ハードウェア制約: 演算結果を格納するRAXレジスタのアセンブリ表記 (6'h1e)
const std::string RAX_REGISTER = "r30";
// 注釈付きASTとシンボルテーブルを受け取り，アセンブリコードを生成するジェネレータ
class Generator {
public:
Generator(node_t *root, const std::map<std::string, const symbol_t *> &symbols,
const std::map<std::string, std::vector<const symbol_t *>> &func_params,
int scratch_base, std::ofstream &asm_file);
void operator()(); // コード生成を実行して .asm に書き出す
private:
node_t *root_; // 注釈付きAST
const std::map<std::string, const symbol_t *> &symbols_; // シンボルテーブル (変数名→番地)
const std::map<std::string, std::vector<const symbol_t *>> &func_params_; // 関数名→パラメータのシンボル列
// レジスタ退避領域の先頭番地．r{reg}を呼び出しをまたいで保持したいとき，scratch_base_ + reg*4番地へ退避する
const int scratch_base_;
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_expr_protecting(node_t *expr, int reg, int protect_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_sign_extend(int reg, int bits); // r{reg}の下位bitsビットを符号として32ビットに符号拡張する (char/shortロード後に使用)
void gen_array_load(node_t *expr, int reg); // 配列要素をr{reg}へ読み込む
void gen_array_store(node_t *expr, int val_reg, int work_reg); // r{val_reg}を配列要素へ書き込む
void gen_array_base_addr(int reg, const symbol_t *sym); // 配列の先頭アドレスをr{reg}に載せる (直接配列は即値，配列パラメータは間接読み出し)
void gen_string_init(int base_addr, const std::string &str); // 文字列をchar配列に書き込む初期化コードを生成する
void gen_print_string(const symbol_t *sym, int reg); // char配列をヌル終端まで1文字ずつ出力するループを生成する
void gen_scan_line(const symbol_t *sym, int reg); // 標準入力を改行まで読み込みchar配列へヌル終端付きで格納するループを生成する
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) を生成する
// 補助メソッド (gen_ 本体からは独立した，AST走査などの下請け処理)
// AST全体(全関数の本体)を再帰的に走査し，式中に現れる文字列リテラル(匿名グローバル配列)を集める
// 変数宣言の初期化子として使われた文字列リテラルはsymを持たないため対象外
void collect_string_literals(node_t *node, std::vector<node_t *> &out);
};
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 に条件値を入れて実際に使う)
// 式の中に関数呼び出しが含まれるかどうかを再帰的に調べる
static bool contains_call(const node_t *expr) {
if (expr->kind == ND_CALL) return true;
for (const node_t *child : expr->children) {
if (contains_call(child)) return true;
}
return false;
}
// コンストラクタ: AST・シンボルテーブル・パラメータシンボル表・レジスタ退避領域の先頭番地・出力先を受け取る
Generator::Generator(node_t *root, const std::map<std::string, const symbol_t *> &symbols,
const std::map<std::string, std::vector<const symbol_t *>> &func_params,
int scratch_base, std::ofstream &asm_file)
: root_(root), symbols_(symbols), func_params_(func_params),
scratch_base_(scratch_base), 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);
}
}
// 式中に現れる文字列リテラル(匿名グローバル配列)も，ここで1回だけ初期化する
// (呼び出し回数に関わらず値が変わらない定数データのため，通常のグローバル変数と同じ扱い)
std::vector<node_t *> string_lits;
for (node_t *child : this->root_->children) {
if (child->kind == ND_FUNC_DEF) {
this->collect_string_literals(child, string_lits);
}
}
for (node_t *lit : string_lits) {
this->gen_string_init(lit->sym->address, lit->sval);
}
}
// AST全体(全関数の本体)を再帰的に走査し，式中に現れる文字列リテラル(匿名グローバル配列)を集める
// 変数宣言の初期化子として使われた文字列リテラルはsymを持たないため対象外
void Generator::collect_string_literals(node_t *node, std::vector<node_t *> &out) {
if (node == nullptr) return;
if (node->kind == ND_STRING_LIT && node->sym != nullptr) {
out.push_back(node);
}
for (node_t *child : node->children) {
this->collect_string_literals(child, out);
}
}
// 関数定義を生成する
// 関数ラベルを出力し，本体ブロックの文を生成して，末尾に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.back()); // 本体ブロック(最後の子)の文を生成する
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文: 戻り値があればRAX(r30)に書き込んでから復帰する
case ND_RETURN:
if (!stmt->children.empty()) {
this->gen_expr(stmt->children[0], 0); // 戻り値の式 → r0
this->asm_file_ << " mov fh r0 " << RAX_REGISTER << "\n"; // r0 → RAX
}
this->asm_file_ << " ret\n";
break;
default:
break;
}
}
// 変数宣言を生成する
// 初期化子があれば，初期値を変数の番地へ書き込むコードを生成する
void Generator::gen_var_decl(node_t *decl) {
// 配列宣言: 文字列リテラルによる初期化のみ対応 (サイズ指定のみの宣言はスキップ)
if (decl->type.is_array) {
if (!decl->children.empty() && decl->children[0]->kind == ND_STRING_LIT) {
this->gen_string_init(decl->sym->address, decl->children[0]->sval);
}
return;
}
// 初期化子がなければ何も出力しない (番地は確保済み，未初期化ローカルは不定値)
if (decl->children.empty()) return;
// 初期化式をr0に評価し，変数へ書き込む
this->gen_expr(decl->children[0], 0); // r0 = 初期値
this->gen_store(0, decl->sym); // 変数 = r0
}
// 文字列をchar配列のメモリに書き込む初期化コードを生成する
// 4文字ずつ1ワードにパックしてwmで書き込む (末尾にヌル終端を含む)
void Generator::gen_string_init(int base_addr, const std::string &str) {
// ヌル終端を含めた全バイト列を構築する
std::string data = str;
data += '\0';
// 4バイトずつワードにパックして書き込む
const int word_count = (static_cast<int>(data.size()) + 3) / 4;
for (int w = 0; w < word_count; w++) {
// 1ワード = 4バイトをリトルエンディアン的にパックする (byte0が最下位)
unsigned int word = 0;
for (int b = 0; b < 4; b++) {
const int idx = w * 4 + b;
if (idx < static_cast<int>(data.size())) {
word |= (static_cast<unsigned char>(data[idx]) << (b * 8));
}
}
// ワードをメモリに書き込む (wワード目は base_addr + w*4 番地から4バイト)
this->asm_file_ << " mov fh r0 r0 " << word << "\n";
this->asm_file_ << " wm fh r0 r0 " << (base_addr + w * 4) << "\n";
}
}
// char配列をヌル終端(0)まで1文字ずつ標準出力へ出力するループを生成する
// ヌル終端が見つからない不正な配列でも，配列の宣言サイズで安全に打ち切る
// レジスタ使用: r{reg}=インデックス, r{reg+1}=ベースアドレス(不変), r{reg+2}=アドレス→文字値(作業用),
// r{reg+3}=配列サイズ(打ち切り境界，不変), r{reg+4}=0(ヌル終端比較用，不変), r{reg+5}=1(インデックス加算用，不変)
void Generator::gen_print_string(const symbol_t *sym, int reg) {
if (reg + 5 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers)");
}
const std::string loop = this->new_label();
const std::string end = this->new_label();
// 必要な変数をレジスタに格納する
this->gen_array_base_addr(reg + 1, sym); // r{reg+1} = ベースアドレス
this->asm_file_ << " mov fh r0 r" << reg << " 0\n"; // r{reg} = インデックス(0)
this->asm_file_ << " mov fh r0 r" << (reg + 3) << " " << sym->type.array_size << "\n"; // r{reg+3} = 配列サイズ(打ち切り境界)
this->asm_file_ << " mov fh r0 r" << (reg + 4) << " 0\n"; // r{reg+4} = 0 (ヌル終端比較用)
this->asm_file_ << " mov fh r0 r" << (reg + 5) << " 1\n"; // r{reg+5} = 1 (インデックス加算用)
this->asm_file_ << loop << ":\n";
// 配列サイズに達したら打ち切る (ヌル終端がなくても無限ループ・範囲外読み出しを防ぐ)
this->asm_file_ << " egt r" << reg << " r" << (reg + 3) << " " << end << "\n";
// r{reg+2} = mem[base + index] (1バイト)
this->asm_file_ << " add r" << (reg + 1) << " r" << reg << " r" << (reg + 2) << "\n";
this->asm_file_ << " rm 1h r" << (reg + 2) << " r" << (reg + 2) << "\n";
// ヌル終端なら終了
this->asm_file_ << " eq r" << (reg + 2) << " r" << (reg + 4) << " " << end << "\n";
this->asm_file_ << " print r" << (reg + 2) << "\n";
this->asm_file_ << " add r" << reg << " r" << (reg + 5) << " r" << reg << "\n";
this->asm_file_ << " jmp " << loop << "\n";
this->asm_file_ << end << ":\n";
}
// 標準入力を改行(\n=10)まで読み込み，char配列へヌル終端付きで格納するループを生成する
// 先頭の改行はすべて読み飛ばす．配列サイズ-1文字を超えたら追加のscanを行わず打ち切る
// (超過分は次にscanを実行したときに読み込まれる．そのためのscanが1回多く消費されることはない)
// レジスタ使用: r{reg}=読み込んだ文字, r{reg+1}=インデックス, r{reg+2}=ベースアドレス(不変), r{reg+3}=アドレス(作業用),
// r{reg+4}='\n'(不変), r{reg+5}=配列サイズ-1(格納できる最大文字数，不変), r{reg+6}=1(インデックス加算用，不変),
// r{reg+7}=0(ヌル終端書き込み用，不変)
void Generator::gen_scan_line(const symbol_t *sym, int reg) {
if (reg + 7 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers)");
}
const std::string skip_loop = this->new_label();
const std::string skip_end = this->new_label();
const std::string read_loop = this->new_label();
const std::string read_end = this->new_label();
// 必要な変数をレジスタに格納する
this->gen_array_base_addr(reg + 2, sym); // r{reg+2} = ベースアドレス
this->asm_file_ << " mov fh r0 r" << (reg + 4) << " 10\n"; // r{reg+4} = '\n'
this->asm_file_ << " mov fh r0 r" << (reg + 5) << " " << (sym->type.array_size - 1) << "\n"; // r{reg+5} = 配列サイズ-1
this->asm_file_ << " mov fh r0 r" << (reg + 6) << " 1\n"; // r{reg+6} = 1
this->asm_file_ << " mov fh r0 r" << (reg + 7) << " 0\n"; // r{reg+7} = 0
// 先頭の改行はすべて読み飛ばす
this->asm_file_ << " scan r" << reg << "\n";
this->asm_file_ << skip_loop << ":\n";
this->asm_file_ << " ne r" << reg << " r" << (reg + 4) << " " << skip_end << "\n"; // 改行以外ならスキップ終了
this->asm_file_ << " scan r" << reg << "\n";
this->asm_file_ << " jmp " << skip_loop << "\n";
this->asm_file_ << skip_end << ":\n";
// 改行が来るまで1文字ずつ配列へ格納する
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " 0\n"; // r{reg+1} = インデックス(0)
this->asm_file_ << read_loop << ":\n";
this->asm_file_ << " eq r" << reg << " r" << (reg + 4) << " " << read_end << "\n"; // 改行なら終了
this->asm_file_ << " add r" << (reg + 2) << " r" << (reg + 1) << " r" << (reg + 3) << "\n"; // アドレス = base+index
this->asm_file_ << " wm 1h r" << (reg + 3) << " r" << reg << "\n"; // buf[index] = 文字
this->asm_file_ << " add r" << (reg + 1) << " r" << (reg + 6) << " r" << (reg + 1) << "\n"; // index += 1
// 配列サイズ上限に達したら，これ以上scanせずに打ち切る (残りは次回のscanで読む)
this->asm_file_ << " egt r" << (reg + 1) << " r" << (reg + 5) << " " << read_end << "\n";
this->asm_file_ << " scan r" << reg << "\n";
this->asm_file_ << " jmp " << read_loop << "\n";
this->asm_file_ << read_end << ":\n";
// ヌル終端を書き込む
this->asm_file_ << " add r" << (reg + 2) << " r" << (reg + 1) << " r" << (reg + 3) << "\n"; // アドレス = base+index
this->asm_file_ << " wm 1h r" << (reg + 3) << " r" << (reg + 7) << "\n"; // buf[index] = 0
}
// 一意な局所ラベル (.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) {
// r{reg+1}を使うため，上限(r15)を超えないことを確認する
if (reg + 1 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(cond->line);
}
// 比較条件: 否定したF系で「偽のとき飛ぶ」を1命令で表現する
if (cond->kind == ND_BINOP && is_comparison(cond->sval)) {
this->gen_expr(cond->children[0], reg); // 左 → r{reg}
this->gen_expr_protecting(cond->children[1], reg + 1, reg); // 右 → 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) {
// r{reg+1}を使うため，上限(r15)を超えないことを確認する
if (reg + 1 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(cond->line);
}
// 比較条件: そのままのF系で「真のとき飛ぶ」を1命令で表現する
if (cond->kind == ND_BINOP && is_comparison(cond->sval)) {
this->gen_expr(cond->children[0], reg); // 左 → r{reg}
this->gen_expr_protecting(cond->children[1], reg + 1, reg); // 右 → 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_protecting(expr->children[1], reg + 1, reg); // 右 → 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) {
// r{reg+1}を使うため，上限(r15)を超えないことを確認する
if (reg + 1 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(expr->line);
}
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) {
// r{reg+1}を使うため，上限(r15)を超えないことを確認する
if (reg + 1 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(expr->line);
}
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 で符号反転する (r{reg+1}を使うため上限(r15)を超えないことを確認する)
if (reg + 1 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(expr->line);
}
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生成パターン，r{reg+1}を使うため上限(r15)を超えないことを確認する)
if (reg + 1 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(expr->line);
}
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
// メモリ変数はchar/shortの型幅でmaskし(他バイトのゴミを混入させない)，符号付きなので読み込み後に符号拡張する
// (レジスタ上の演算は型に関係なく常に32ビットで行うため，char/shortはintに昇格した状態で保持する)
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";
return;
}
// 配列(配列パラメータ含む)はここでは要素の値ではなく「先頭アドレス」を保持しているだけなので，
// 要素型に関わらず常にfh(全32ビット)で読み込む (char配列のアドレスを1バイトに切り詰めてはいけない)
if (sym->type.is_array) {
this->asm_file_ << " rm fh r0 r" << reg << " " << sym->address << "\n";
return;
}
switch (sym->type.base) {
case BASE_CHAR:
this->asm_file_ << " rm 1h r0 r" << reg << " " << sym->address << "\n";
this->gen_sign_extend(reg, 8);
break;
case BASE_SHORT:
this->asm_file_ << " rm 3h r0 r" << reg << " " << sym->address << "\n";
this->gen_sign_extend(reg, 16);
break;
case BASE_INT:
// rm: メモリ絶対番地からr{reg}へ読み込む (即値アドレス指定のためrs1のr0は無視される)
this->asm_file_ << " rm fh r0 r" << reg << " " << sym->address << "\n";
break;
default:
throw std::string("compiler error: unsupported scalar type in gen_load");
}
}
// r{reg}の値を変数へ書き込む
// 置き場所がレジスタ直結(LED等のI/Oレジスタ)ならmovのレジスタ間コピー，メモリ変数ならwm
// メモリ変数はchar/shortの型幅でmaskし，該当バイトのみ書き込む(桁あふれした上位ビットを書き込まない)
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";
return;
}
// 配列(配列パラメータ含む)はここでは要素の値ではなく「先頭アドレス」を保持しているだけなので，
// 要素型に関わらず常にfh(全32ビット)で書き込む (char配列のアドレスを1バイトに切り詰めてはいけない)
if (sym->type.is_array) {
this->asm_file_ << " wm fh r0 r" << reg << " " << sym->address << "\n";
return;
}
const char *mask;
switch (sym->type.base) {
case BASE_CHAR: mask = "1h"; break;
case BASE_SHORT: mask = "3h"; break;
case BASE_INT: mask = "fh"; break;
default:
throw std::string("compiler error: unsupported scalar type in gen_store");
}
// wm: r{reg}をメモリ絶対番地へ書き込む (即値アドレス指定のためrs1のr0は無視される)
this->asm_file_ << " wm " << mask << " r0 r" << reg << " " << sym->address << "\n";
}
// r{reg}の下位bitsビットを符号として32ビットへ符号拡張する
void Generator::gen_sign_extend(int reg, int bits) {
const int shift = 32 - bits;
// シフト量を保存しておく
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " " << shift << "\n";
// 最上位ビットをMSBにシフトする
this->asm_file_ << " sll r" << reg << " r" << (reg + 1) << " r" << reg << "\n";
// 算術シフトして，実際の値が入っているよりも上位のビットを符号ビットで埋める
this->asm_file_ << " sra r" << reg << " r" << (reg + 1) << " r" << reg << "\n";
}
// 式を評価し結果を指定レジスタに残す．評価対象の式が関数呼び出しを含む場合，
// 呼び出し先はr0から使い直すため，別に指定したレジスタの値を一時メモリへ退避してから評価し，評価後に復元する
void Generator::gen_expr_protecting(node_t *expr, int reg, int protect_reg) {
if (!contains_call(expr)) {
this->gen_expr(expr, reg);
return;
}
const int addr = this->scratch_base_ + protect_reg * 4;
this->asm_file_ << " wm fh r0 r" << protect_reg << " " << addr << "\n"; // 退避
this->gen_expr(expr, reg);
this->asm_file_ << " rm fh r0 r" << protect_reg << " " << addr << "\n"; // 復元
}
// 式を評価し，結果をr{reg}に残す
// reg以上のレジスタを作業用に使うレジスタスタック方式 (二項演算は左をr{reg}・右をr{reg+1}に評価して畳む)
void Generator::gen_expr(node_t *expr, int reg) {
// レジスタは16本(r0〜r15)．深い式で枯渇したらエラーにする
if (reg >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(expr->line);
}
switch (expr->kind) {
// リテラル: 即値をr{reg}に載せる
// sizeofは意味解析でコンパイル時に値(ival)が確定済みのため，リテラルと同じ即値ロードで済む
case ND_INT_LIT:
case ND_CHAR_LIT:
case ND_SIZEOF:
this->asm_file_ << " mov fh r0 r" << reg << " " << expr->ival << "\n";
break;
// 文字列リテラル: 配列名と同様，先頭の番地(コンパイル時確定の即値)をr{reg}に載せる
// データ自体はgen_global_initsで1回だけ書き込み済み
// 現状は関数の引数としてしか使用されないので，先頭アドレスだけ保存すればいい
case ND_STRING_LIT:
this->asm_file_ << " mov fh r0 r" << reg << " " << expr->sym->address << "\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_protecting(expr->children[1], reg + 1, reg);
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;
// 関数呼び出し: 各引数をr{reg}で評価しパラメータのアドレスへ書き込んでからCALLする
// callでレジスタは揮発するが，呼び出し前後で生きた値はメモリにあるため問題ない
// r{reg}を使うのは，呼び出し元がr{reg}未満のレジスタに置いている生存値(二項演算の左辺等)を
// 破壊しないため．各引数はメモリへの書き込みが完了してから次の引数評価に移るので使い回して良い
case ND_CALL: {
// 各引数をr{reg}に評価し，対応するパラメータのメモリアドレスにWMで書き込む
const auto ¶ms = this->func_params_.at(expr->sval);
for (size_t i = 0; i < expr->children.size(); i++) {
node_t *arg = expr->children[i];
if (params[i]->type.is_array) {
// 配列引数: ベースアドレスをr{reg}にロードする
this->gen_array_base_addr(reg, arg->sym);
} else {
// スカラー引数: 式を評価する
this->gen_expr(arg, reg);
}
this->gen_store(reg, params[i]);
}
this->asm_file_ << " call " << expr->sval << "\n";
// 非void関数はRAX(r30)から戻り値を取り出す
if (expr->type.base != BASE_VOID) {
this->asm_file_ << " mov fh " << RAX_REGISTER << " r" << reg << "\n";
}
break;
}
// 組み込み関数print: char配列をヌル終端まで1文字ずつ出力するループを生成する
case ND_PRINT:
this->gen_print_string(expr->children[0]->sym, reg);
break;
// 組み込み関数scan: 標準入力を改行まで読み込み，char配列へヌル終端付きで格納するループを生成する
case ND_SCAN:
this->gen_scan_line(expr->children[0]->sym, reg);
break;
// 代入: 右辺(複合代入は左辺の現在値と右辺の演算結果)をr{reg}に求め，変数へ書き込む
case ND_ASSIGN: {
node_t *lhs = expr->children[0];
if (lhs->kind == ND_ARRAY_ACCESS) {
// 配列要素への代入
this->gen_expr(expr->children[1], reg); // 右辺 → r{reg}
this->gen_array_store(lhs, reg, reg + 1); // 配列要素へ書き込む
} else {
// スカラー変数への代入
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_protecting(expr->children[1], reg + 1, reg);
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;
}
// 配列要素アクセス(読み出し): インデックスからメモリアドレスを計算して読み込む
case ND_ARRAY_ACCESS:
this->gen_array_load(expr, reg);
break;
default:
throw std::string("compiler error: unsupported expression in code generation at line ")
+ std::to_string(expr->line);
}
}
// 配列の先頭アドレスをr{reg}に載せる
// 直接配列(array_size>0)はコンパイル時にアドレス確定済みなので即値ロード，
// 配列パラメータ(array_size==0)は呼び出し元が書き込んだ先頭アドレスをメモリから間接読み出しする
void Generator::gen_array_base_addr(int reg, const symbol_t *sym) {
if (sym->type.array_size == 0) {
this->asm_file_ << " rm fh r0 r" << reg << " " << sym->address << "\n";
} else {
this->asm_file_ << " mov fh r0 r" << reg << " " << sym->address << "\n";
}
}
// 配列要素をr{reg}へ読み込む
// アドレス = base + index * サイズ(バイト単位)をr{reg}に作り，型に応じたmaskで1回のrmで読み込む
// (maskの最下位ビットに合わせて自動的にレジスタLSB側へゼロ拡張格納されるため，シフトは不要)
// レジスタ使用: r{reg}=index→アドレス→結果, r{reg+1}=定数・base (2本, reg<=14)
void Generator::gen_array_load(node_t *expr, int reg) {
const symbol_t *sym = expr->sym;
if (reg + 1 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(expr->line);
}
// r{reg} = index (r{reg+1}はまだ未使用)
this->gen_expr(expr->children[0], reg);
// 型ごとの要素サイズ(2^shift バイト)とmask(バイト位置)を決定する
const char *mask;
int shift;
switch (sym->type.base) {
case BASE_CHAR: mask = "1h"; shift = 0; break;
case BASE_SHORT: mask = "3h"; shift = 1; break;
case BASE_INT: mask = "fh"; shift = 2; break;
default:
throw std::string("compiler error: unsupported array element type at line ")
+ std::to_string(expr->line);
}
// オフセット = index * サイズ (サイズ1のcharはシフト不要)
// 実行後: r{reg} = index * サイズ(バイトオフセット), r{reg+1} = シフト量(破棄可)
if (shift > 0) {
this->asm_file_ << " mov fh r0 r" << (reg + 1) << " " << shift << "\n";
this->asm_file_ << " sll r" << reg << " r" << (reg + 1) << " r" << reg << "\n";
}
// アドレス = base + オフセット
// 実行後: r{reg+1} = base番地
this->gen_array_base_addr(reg + 1, sym);
// 実行後: r{reg} = base + オフセット = 読み込み先の実アドレス
this->asm_file_ << " add r" << reg << " r" << (reg + 1) << " r" << reg << "\n";
// maskに従って読み込む (該当バイトのみ自動抽出・ゼロ拡張)
// 実行後: r{reg} = 配列要素の値 (式全体の結果)
this->asm_file_ << " rm " << mask << " r" << reg << " r" << reg << "\n";
// char/shortはゼロ拡張されたままなので，スカラー変数の読み込み(gen_load)と同様に符号拡張する
if (sym->type.base == BASE_CHAR) {
this->gen_sign_extend(reg, 8);
} else if (sym->type.base == BASE_SHORT) {
this->gen_sign_extend(reg, 16);
}
}
// r{val_reg}の値を配列要素へ書き込む (work_reg以降を作業用に使う)
// アドレス = base + index * サイズ(バイト単位)をr{work_reg}に作り，型に応じたmaskで1回のwmで書き込む
// (該当バイト以外はハードウェアが元の値を保持するread-modify-writeを内部で行うため，ソフト側での読み出しは不要)
// レジスタ使用: r{val_reg}=値, r{work_reg}=index→アドレス, r{work_reg+1}=定数・base (2本, work_reg+1<=15)
void Generator::gen_array_store(node_t *expr, int val_reg, int work_reg) {
const symbol_t *sym = expr->sym;
if (work_reg + 1 >= MAX_REG) {
throw std::string("compiler error: expression too complex (out of registers) at line ")
+ std::to_string(expr->line);
}
// r{work_reg} = index (r{work_reg+1}はまだ未使用)
this->gen_expr_protecting(expr->children[0], work_reg, val_reg);
// 型ごとの要素サイズ(2^shift バイト)とmask(バイト位置)を決定する
const char *mask;
int shift;
switch (sym->type.base) {
case BASE_CHAR: mask = "1h"; shift = 0; break;
case BASE_SHORT: mask = "3h"; shift = 1; break;
case BASE_INT: mask = "fh"; shift = 2; break;
default:
throw std::string("compiler error: unsupported array element type at line ")
+ std::to_string(expr->line);
}
// オフセット = index * サイズ (サイズ1のcharはシフト不要)
// 実行後: r{work_reg} = index * サイズ(バイトオフセット), r{work_reg+1} = シフト量(破棄可)
if (shift > 0) {
this->asm_file_ << " mov fh r0 r" << (work_reg + 1) << " " << shift << "\n";
this->asm_file_ << " sll r" << work_reg << " r" << (work_reg + 1) << " r" << work_reg << "\n";
}
// アドレス = base + オフセット
// 実行後: r{work_reg+1} = base番地
this->gen_array_base_addr(work_reg + 1, sym);
// 実行後: r{work_reg} = base + オフセット = 書き込み先の実アドレス
this->asm_file_ << " add r" << work_reg << " r" << (work_reg + 1) << " r" << work_reg << "\n";
// maskに従って書き込む (該当バイトのみ更新，他バイトはハードウェアが保持)
this->asm_file_ << " wm " << mask << " r" << work_reg << " r" << val_reg << "\n";
}
c2asm
c2asm.hpp
#pragma once
// Cソースをアセンブリに変換する本処理．mainと同じ引数(argc, argv)を受け取る
// 処理に成功したら0，失敗したら1を返す
int compile_c_to_asm(int argc, char **argv);
c2asm.cpp
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include "c2asm.hpp"
#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;
// 前宣言
static void get_args(int argc, char **argv, args_t &args); // コマンドライン引数を取得する
// メイン関数: compile_c_to_asmをそのまま呼ぶだけ
// c2bin.cppに直接組み込むビルド(C2ASM_NO_MAIN定義時)ではmain多重定義を避けるため除外する
#ifndef C2ASM_NO_MAIN
int main(int argc, char **argv) {
return compile_c_to_asm(argc, argv);
}
#endif
// Cソースをアセンブリに変換する本処理
// 処理に成功したら0，失敗したら1を返す
int compile_c_to_asm(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, analyzer.func_params(), analyzer.scratch_base(), asm_file);
generator();
asm_file.flush();
asm_file.close();
// 出力命令数がROMの上限(MAX_INSTRUCTION_COUNT)を超えていないか確認する
// (命令行は先頭が半角スペース．ラベル行・.global行は先頭にスペースを付けない規約で判定する．
// ただしコメント行(先頭の空白を除いた最初の文字が';')は命令行に含めない)
std::ifstream check_file(args.asm_file_name);
int instruction_count = 0;
std::string line;
while (std::getline(check_file, line)) {
const size_t pos = line.find_first_not_of(' ');
if (pos != std::string::npos && line[0] == ' ' && line[pos] != ';') {
instruction_count++;
}
}
check_file.close();
if (instruction_count > MAX_INSTRUCTION_COUNT) {
throw std::string("compiler error: instruction count (")
+ std::to_string(instruction_count) + ") exceeds maximum ("
+ std::to_string(MAX_INSTRUCTION_COUNT) + ")";
}
// 正常終了を報告する
std::cout << "compiled: " << args.asm_file_name << std::endl;
}
catch (std::string msg) {
std::cout << msg << std::endl;
asm_file.close();
return 1;
}
return 0;
}
// コマンドライン引数を取得する
// -c: 必須引数．入力Cソースファイル名．
// -a: 出力アセンブリファイル名．省略した場合，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 == "-a") 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
<< "-a: 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();
}
}
あとついでに，アセンブラもちょっと変更しました．
なぜかというと，プログラムから機械語へ一発で変換するプログラムが欲しかったからですね．
今までのmain関数をほかの関数に移植して，その関数を順番に呼ぶことで，プログラミング言語→アセンブリ言語→機械語に変換するようにしました．
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 "asm2bin_main.hpp"
#include "util.hpp"
// コマンドライン引数情報
typedef struct {
std::string asm_file_name; // アセンブリファイル名
std::string sv_file_name; // 出力ファイル名
} args_t;
// 関数
// (assemble_asm_to_sv以外はこのファイル内でしか使わないため，c2bin.exeへのリンク時に
// コンパイラ側の同名シンボルと衝突しないようすべてstaticにする)
static void get_args(int argc, char **argv, args_t &args); // コマンドライン引数を取得
static void asm2bin(std::ifstream &asm_file, std::ofstream &sv_file); // アセンブリをバイナリに変換する
static void output_header(std::ofstream &sv_file); // svファイルのヘッダーを出力する
static void output_bin(std::ifstream &asm_file, std::ofstream &sv_file); // バイナリ部分を出力する
static std::string read_global_line(std::ifstream &asm_file); // .global行まで読み飛ばして返す
static void get_function_names( // プログラムに存在する関数の名前を取得する
std::map<std::string, std::size_t> &functions, std::string line
);
static 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
);
static void output_bin_line( // アセンブリ一行を機械語化しinstructionsへ追加
std::vector<std::string> &instructions,
const std::map<std::string, std::size_t> &functions, std::string line
);
static 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
);
static void validate_arg_count( // 引数の個数が命令の仕様に合うか検証する
const command_arg_t &command_arg, const int arg_num, const std::string &command
);
static std::string get_machine_function_name(const std::string &command); // machine.svh側の関数名へ変換する
static void throw_if_tab(const std::string &line); // タブ文字があればエラーにする
static void resolve_labels( // 局所ラベル参照を絶対index/相対オフセットに解決する
std::vector<std::string> &instructions,
const std::map<std::string, std::size_t> &local_labels
);
static std::string offset2imm(const long offset); // 相対オフセットをイミディエイト表記にする（負は32bit2の補数）
static void apply_main_self_loop( // mainが到達する最初のretを自己ループに置換する
std::vector<std::string> &instructions
);
static std::string join_instructions( // 命令を結合する（末尾カンマ無し）
const std::vector<std::string> &instructions
);
static std::string function_name2line_num( // 関数参照を行番号に置換する
const std::map<std::string, std::size_t> &functions, const std::string &bin
);
static 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 = ">>"; // ラベル参照の終端
// メイン関数: assemble_asm_to_svをそのまま呼ぶだけ
// c2bin.cppに直接組み込むビルド(ASM2BIN_NO_MAIN定義時)ではmain多重定義を避けるため除外する
#ifndef ASM2BIN_NO_MAIN
int main(int argc, char **argv) {
return assemble_asm_to_sv(argc, argv);
}
#endif
// アセンブリをSystemVerilog ROMに変換する本処理
// 処理に成功したら0，失敗したら1を返り値にする
int assemble_asm_to_sv(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: 必須引数．アセンブリファイル名．
// -b: 出力ファイル名．省略した場合，アセンブリファイル名の拡張子を変更して同階層に出力される．
// 何も指定せずに引数を置いた場合，アセンブリファイル名と解釈される．
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 == "-b") 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
<< "-b: 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) {
// 負の10進数はそのまま足すと符号拡張により33bit目の即値使用フラグが消えるため，
// 32bit2の補数のhexにしてから足す
if (!converted_arg.empty() && converted_arg[0] == '-') {
converted_arg = offset2imm(std::stol(converted_arg));
}
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";
}
c2bin
c2bin.cpp
#include "c2asm.hpp"
#include "../assembler/asm2bin_main.hpp"
// メイン関数
// compile_c_to_asm(Cソース→アセンブリ)とassemble_asm_to_sv(アセンブリ→SystemVerilog ROM)を順に呼び出す入口．
// これが今後のコンパイラの入口となる(このプロジェクトのテスト対象はc2asm.cppのままとする)．
//
// CLI: -c(入力Cファイル) -a(中間アセンブリファイル) -b(出力SystemVerilog ROMファイル) の3つ全てを指定する．
// compile_c_to_asmは-c/-aを，assemble_asm_to_svは-a/-bを見て，互いに関係ないフラグは無視するため，
// 同じargv一式をそのまま両方へ渡すだけでよい．
// スモールスタートのため，省略時に内部でエラーになる形で構わないこととし，明示的な検証は行わない
// (-aを省略すると，compile_c_to_asmは.cから自動導出して成功するが，assemble_asm_to_svは-aを持たず失敗する)．
// 処理に成功したら0，失敗したら1を返す
int main(int argc, char **argv) {
if (compile_c_to_asm(argc, argv) != 0) {
return 1;
}
if (assemble_asm_to_sv(argc, argv) != 0) {
return 1;
}
return 0;
}
ちなみに，コンパイラ(といいつつプログラミング言語をアセンブリ言語に翻訳するだけ)とアセンブラを連結する過程でそれぞれの仕様を変更しています．
コンパイラ(と言いつつプログラミング言語をアセンブリ言語に翻訳するプログラム)の仕様
入力プログラミング言語ファイルを-cで指定，出力アセンブリ言語ファイルを-oで指定
↓
入力プログラミング言語ファイルを-cで指定，出力アセンブリ言語ファイルを-aで指定
アセンブラの仕様
入力アセンブリ言語ファイルを-aで指定，出力機械語ファイルを-oで指定
↓
入力アセンブリ言語ファイルを-aで指定，出力機械語ファイルを-bで指定
つまり，全部ファイル種別になったって感じです．
これによって，上記二つを連結するだけでコンパイラ完成版になりました．
今後の展望
今回AIにソースレビューしてもらうと，延々と指摘事項が続いてそれの修正に追われていたので結構時間がかかってしまいました．
ただかなりの数の不具合を修正したので，コンパイラプログラムは今かなり不具合が少ない状態だと思います．
さて，これで自作プログラミング言語から自作機械語への一気通貫が可能になりましたので，やっとOS作成に…
と思っていたのですが，プロジェクトの数が増えてきたのと，変更履歴や変更理由を残したいという動機により，リポジトリとか作ってちゃんとソースをgit管理しようと思います．次回はそれですね．