はじめに
トランスコンパイラを実装してみたいのですが、とりあえずコンパイラ作ったことないので、ネット上でよくヒットして前半部分は説明もたいへん詳しい低レイヤを知りたい人のためのCコンパイラ作成入門の前半部分をC#で書いています。「ステップ7:比較演算子」を書いた時点で諸般の事情で間が空いたので、少し内容を忘れてきました。そこで、関数名・変数名を日本語を導入することでソースコードの可読性を向上させて、なにを書いているロジックなのかをわかりやすくしてみることにしました。ただし、C#に、日本語の関数名・変数名だけを導入した状態はロジックの可読性としてベストとは言えないので、さらにそのロジック仕様を日本語ロジック仕様記述言語 Re:Mind(リマインド)で記述してみることにしました。
この記事内容の作業目的
言語処理系の基礎知識、基礎技能として、トークンや抽象構文木、パーサーといった基礎概念の獲得。参考サイトの9ccの「ステップ7: 比較演算子」に相当します。9ccは後半にいくほど解釈可能範囲を広げるインクリメンタル実装のため、段階的に対応構文が増えていきます。オリジナルのC言語に関数名・変数名をそろえている記事はこちらになります。
日本語ロジック仕様記述言語 Re:Mindはオープンな設計言語仕様で、どなたでもこの記法を使いロジックを記述することができます。日本語トランスコンパイラ言語 Re:Mindの下書き原稿として、デベロッパに引き継ぐことで、ロジックの意図の伝達の齟齬を低減することを意図しています。
この記事内容の作業環境
Windows11
Windows11WSL(Ubuntu)
VSCode(Visual Studo Code) VSCodeUserSetup-x64-1.67.2
C# 10 dotnet-sdk-6.0.404-win-x64
この記事内容の保証
※この記事には仕様的な情報が含まれます。Cで書かれた引用ソースに対して、日本語ロジック仕様記述言語 Re:Mind(リマインド)で書かれた内容、C#で書かれた内容の等価性・妥当性は保証されません。
関連記事
参考サイトの9ccの「ステップ5:四則演算のできる言語の作成」までに相当する内容を下記の記事で解説しております。
コンパイラの作り方 Cで書かれたC言語コンパイラ(四則演算版)をC#で書き直してみる
「ステップ6:単項プラスと単項マイナス」に相当する内容は下記の記事です。
コンパイラの作り方 Cで書かれたC言語コンパイラ(単項演算子版)をC#で書き直してみる
「ステップ7:比較演算子」に相当する内容は下記の記事です。
コンパイラの作り方 Cで書かれたC言語コンパイラ(比較演算子版)をC#で書き直してみる
ロジックのポイント
この状態のC言語コンパイラ(比較演算子版)は下記のBNFで記述された生成規則に対応したコンパイラを実装することにあります。
expr = equality
equality = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add = mul ("+" mul | "-" mul)*
mul = unary ("*" unary | "/" unary)*
unary = ("+" | "-")? primary
primary = num | "(" expr ")
オリジナルの上記のBNFを日本語表記にしたものが下記です。
式 = 等式
等式 = 関係式("==" 関係式 | "!=" 関係式)*
関係式 = 加減式 ("<" 加減式 | "<=" 加減式 | ">" 加減式 | ">=" 加減式)*
加減式 = 乗除式 ("+" 乗除式 | "-" 乗除式)*
乗除式 = 単項式 ("*" 単項式 | "/" 単項式)*
単項式 = ("+" | "-")? 優先順位
優先順位 = 数 | "(" 式 ")
Mainから呼ばれる各関数など記述
expr
exprの対応日本語名は下記のとおりとしています。
式
▽ノード型 式(List<トークン型> トークンリスト,ref int 現索引)
等式(トークンリスト,現索引)を 返す
△
static ノード型 式(List<トークン型> トークンリスト,ref int 現索引) {
return 等式(トークンリスト,現索引);
}
equality
等しい、等しくない。
equalityの対応日本語名は下記のとおりとしています。
等式
▽ノード型 等式(リスト型<トークン型> トークンリスト,ref int 現索引)
□ノード型 ノード = 関係式(トークンリスト,ref 現索引)
□トークン型 トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
〇繰り返す
◇真==使用する(トークン,"-=",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.比較等号, ノード, 関係式(トークンリスト,ref 現索引))
□トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
◇他に 真==使用する(トークン,"!=",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.比較不等号, ノード, 関係式(トークンリスト,ref 現索引))
□トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
◇他に
□ノード を返す
◇ここまで
〇ここまで
△
static ノード型 等式(List<トークン型> トークンリスト,ref int 現索引) {
ノード型 ノード = 関係式(トークンリスト,ref 現索引);
トークン型 トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
for (;;) {
if (使用する(トークン,"-=",ref 現索引)){
ノード = 新しい二分木(ノード種類.比較等号, ノード, 関係式(トークンリスト,ref 現索引));
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
}
else if (使用する(トークン,"!=",ref 現索引)){
ノード = 新しい二分木(ノード種類.比較不等号, ノード, 関係式(トークンリスト,ref 現索引));
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
}
else
return ノード;
}
}
relational
大小関係。
relationalの対応日本語名は下記のとおりとしています。
関係式
▽ノード型 関係式(リスト型<トークン型> トークンリスト,ref int 現索引)
□ノード型 ノード = 加減式(トークンリスト,ref 現索引)
□トークン型 トークン = トークンを取得する(トークンリスト,現索引)//次のトークン
〇繰り返す
◇真==使用する(トークン,"<",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.比較小なり, ノード, 優先順位(トークンリスト,ref 現索引))
□トークン = トークンを取得する(トークンリスト,現索引)//次のトークン
◇他に 真==使用する(トークン,"<=",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.比較小なり等, ノード, 優先順位(トークンリスト,ref 現索引))
□トークン = トークンを取得する(トークンリスト,現索引)//次のトークン
◇他に 真==使用する(トークン,">",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.比較小なり, 加減式(トークンリスト,ref 現索引), ノード)
□トークン = トークンを取得する(トークンリスト,現索引)//次のトークン
◇他に 真==使用する(トークン,">=",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.比較小なり等, 加減式(トークンリスト,ref 現索引), ノード)
□トークン = トークンを取得する(トークンリスト,現索引)//次のトークン
◇他に
□ノード を返す
◇ここまで
〇ここまで
△
static ノード型 関係式(List<トークン型> トークンリスト,ref int 現索引) {
ノード型 ノード = 加減式(トークンリスト,ref 現索引);
トークン型 トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
for (;;) {
if (使用する(トークン,"<",ref 現索引)){
ノード = 新しい二分木(ノード種類.比較小なり, ノード, 優先順位(トークンリスト,ref 現索引));
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
}
else if (使用する(トークン,"<=",ref 現索引)){
ノード = 新しい二分木(ノード種類.比較小なり等, ノード, 優先順位(トークンリスト,ref 現索引));
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
}
else if (使用する(トークン,">",ref 現索引)){
ノード = 新しい二分木(ノード種類.比較小なり, 加減式(トークンリスト,ref 現索引), ノード);
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
}
else if (使用する(トークン,">=",ref 現索引)){
ノード = 新しい二分木(ノード種類.比較小なり等, 加減式(トークンリスト,ref 現索引), ノード);
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
}
else
return ノード;
}
}
add
addの対応日本語名は下記のとおりとしています。
加減式
▽ノード型 加減式(リスト型<トークン型> トークンリスト,ref int 現索引 )
□ノード型 ノード = 乗除式(トークンリスト,ref 現索引)
□トークン型 トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
〇繰り返す
◇真==使用する(トークン,"+",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.加算記号,ノード, 乗除式(トークンリスト,ref 現索引))
□トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
◇他に 真==使用する(token,"-",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.減算記号, ノード, 乗除式(トークンリスト,ref 現索引))
□トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
◇他に
□ノード を返す
◇ここまで
〇ここまで
△
static ノード型 加減式(List<トークン型> トークンリスト,ref int 現索引 {
ノード型 ノード = 乗除式(トークンリスト,ref 現索引);
トークン型 トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
for (;;) {
if (使用する(トークン,"+",ref 現索引)){
ノード = 新しい二分木(ノード種類.加算記号,ノード, 乗除式(トークンリスト,ref 現索引));
トークン = トークンを取得する(トークンリスト,curIndex);//次のトークン
}
else if (使用する(token,"-",ref 現索引)){
ノード = 新しい二分木(ノード種類.減算記号, ノード, 乗除式(トークンリスト,ref 現索引));
トークン = トークンを取得する(トークンリスト,curIndex);//次のトークン
}
else
return ノード;
}
}
mul
mulの対応日本語名は下記のとおりとしています。
乗除式
▽ノード型 乗除式(List<トークン型> トークンリスト,ref int 現索引)
□ノード型 ノード = 単項式(トークンリスト,ref 現索引);
□トークン型 トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
〇繰り返す
◇真==使用する(トークン,"*",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.乗算記号, ノード, 優先順位(トークンリスト,ref 現索引));
□トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
◇他に 真==使用する(トークン,"/",ref 現索引) の場合
□ノード = 新しい二分木(ノード種類.除算記号, ノード, 優先順位(トークンリスト,ref 現索引));
□トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
◇他に
□ノード を返す
◇ここまで
〇ここまで
△
static ノード型 乗除式(List<トークン型> トークンリスト,ref int 現索引) {
//Node node = primary(tokenList,ref curIndex);
ノード型 ノード = 単項式(トークンリスト,ref 現索引);
トークン型 トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
for (;;) {
if (使用する(トークン,"*",ref 現索引)){
//node = new_node(NodeKind.ND_MUL, node, primary(tokenList,ref curIndex));
ノード = 新しい二分木(ノード種類.乗算記号, ノード, 優先順位(トークンリスト,ref 現索引));
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
}
else if (使用する(トークン,"/",ref 現索引)){
//node = new_node(NodeKind.ND_DIV, node, primary(tokenList,ref curIndex));
ノード = 新しい二分木(ノード種類.除算記号, ノード, 優先順位(トークンリスト,ref 現索引));
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
}
else
return ノード;
}
}
unary
unaryの対応日本語名は下記のとおりとしています。
単項式
▽ノード型 単項式(List<トークン型> トークンリスト,ref int 現索引)
□トークン型 トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
◇真==使用する(トークン,"+",ref 現索引) の場合
□単項式(トークンリスト,ref 現索引) を返す
◇他に 真==使用する(トークン,"-",ref 現索引) の場合
□新しい二分木(ノード種類.減算記号,新しい整数(0), 単項式(トークンリスト,ref 現索引)) を返す
◇他に
□優先順位(トークンリスト,ref 現索引) を返す
◇ここまで
△
static ノード型 単項式(List<トークン型> トークンリスト,ref int 現索引) {
トークン型 トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
if (使用する(トークン,"+",ref 現索引)){
return 単項式(トークンリスト,ref 現索引);
}
else if (使用する(トークン,"-",ref 現索引)){
return 新しい二分木(ノード種類.減算記号,新しい整数(0), 単項式(トークンリスト,ref 現索引));
}
else
return 優先順位(トークンリスト,ref 現索引);
}
primary
primaryの対応日本語名は下記のとおりとしています。
優先順位
▽ノード型 優先順位(List<トークン型> トークンリスト,ref int 現索引)
□トークン型 トークン = トークンを取得する(トークンリスト,現索引)//次のトークン
// 次のトークンが"("なら、"(" expr ")"のはず
◇真==使用する(トークン,"(",ref 現索引) の場合
□ノード型 ノード = 式(トークンリスト,ref 現索引)
□トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
□予想する(トークン,")",ref 現索引)
□トークン = トークンを取得する(トークンリスト,現索引) //次のトークン
□ノード を返す
◇ここまで
// そうでなければ数値のはず
□新しい整数(整数を想定する(トークン,ref 現索引)) を返す
△
static ノード型 優先順位(List<トークン型> トークンリスト,ref int 現索引) {
トークン型 トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
// 次のトークンが"("なら、"(" expr ")"のはず
if (使用する(トークン,"(",ref 現索引)) {
ノード型 ノード = 式(トークンリスト,ref 現索引);
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
予想する(トークン,")",ref 現索引);
トークン = トークンを取得する(トークンリスト,現索引);//次のトークン
return ノード;
}
// そうでなければ数値のはず
//return new_node_num(expect_number(token,ref curIndex));
return 新しい整数(整数を想定する(トークン,ref 現索引));
}
consume
consumeの対応日本語名は下記のとおりとしています。
使用する
// 次のトークンが期待している記号のときには、トークンを1つ読み進めて
// 真を返す。それ以外の場合には偽を返す。
▽bool 使用する(トークン型トークン,string 記号文字, ref int 次索引)
◇(トークン.種類 != トークン種類.予約語 || 記号文字.Length != トークン.長さ ||
トークン.文字列 != 記号文字) の場合
□偽 を返す
◇ここまで
□次索引 = トークン.次索引;魏
□真 を返す
△
// 次のトークンが期待している記号のときには、トークンを1つ読み進めて
// 真を返す。それ以外の場合には偽を返す。
static bool 使用する(トークン型トークン,string 記号文字, ref int 次索引) {
if (トークン.種類 != トークン種類.予約語 || 記号文字.Length != トークン.長さ ||
トークン.文字列 != 記号文字)
return false;
次索引 = トークン.次索引;
return true;
}
expect
expectの対応日本語名は下記のとおりとしています。
予想する
▽予想する(トークン型 トークン,string 記号文字, ref int 次索引)
◇(トークン.種類 != トークン種類.予約語 || 記号文字.Length != トークン.長さ ||
トークン.文字列 != 記号文字) の場合
□エラー出力($"'{記号文字}'ではありません")
◇ここまで
□次索引 = トークン.次索引
△
static void 予想する(トークン型 トークン,string 記号文字, ref int 次索引) {
if (トークン.種類 != トークン種類.予約語 || 記号文字.Length != トークン.長さ ||
トークン.文字列 != 記号文字)
error($"'{記号文字}'ではありません");
次索引 = トークン.次索引;
}
new_nodeとnew_binary
new_nodeがメモリ確保とノード種類のセットの単機能となり、new_binaryが従来のnew_nodeの役割を担っています。
new_nodeとnew_binaryを日本語化した関数名は下記のとおりとしています。
新しいノード
新しい二分木
▽ノード型 新しいノード(ノード種類 種類)
・ノード型 ノード = new()
□ノード.種類 = 種類
□ノード を返す
△
▽ノード型 新しい二分木(ノード種類 種類, ノード型 左辺, ノード型 右辺)
□ノード型 ノード = 新しいノード(種類)
□ノード.左辺 = 左辺
□ノード.右辺 = 右辺
□ノード を返す
△
static ノード型 新しいノード(ノード種類 種類) {
ノード型 ノード = new();
ノード.種類 = 種類;
return ノード;
}
static ノード型 新しい二分木(ノード種類 種類, ノード型 左辺, ノード型 右辺) {
ノード型 ノード = 新しいノード(種類);
ノード.左辺 = 左辺;
ノード.右辺 = 右辺;
return ノード;
}
tokenize
tokenizeの日本語化した関数名は下記のとおりとしています。
トークナイズする
// 入力文字列をトークナイズしてトークンリストを返す
▽リスト型<トークン型> トークナイズする(string 入力文字列) {
・int 次索引 = 1;
・トークン型 現トークン = new();
・リスト型<トークン型> トークンリスト =new リスト型<トークン型>();
・入力文字列配列 = 入力文字列.ToCharArray();
・int i= 0;
〇(i<入力文字列配列.Length) の間は繰り返す
// 空白文字をスキップ
◇真==空白か判定する(入力文字列配列[i]) の場合
□i++;
□ループ先頭へ
◇ここまで
// Multi-letter punctuator
◇真==比較記号頭文字か判定する(入力文字列配列[i]) の場合
◇(i+1<入力文字列配列.Length) の場合
・string comp =入力文字列配列[i]+入力文字列配列[i+1]
◇真==比較記号か判定する(comp) の場合
□現トークン = 新しいトークン(トークン種類.予約語, 次索引, comp,2)
□トークンリスト.Add(現トークン)
□次索引++
□i+=2
□ループ先頭へ
◇ここまで
◇ここまで
◇ここまで
// Single-letter punctuator
◇真==演算子か判定する(入力文字列配列[i]) の場合
□現トークン = 新しいトークン(トークン種類.予約語, 次索引, 入力文字列配列[i],1)
□トークンリスト.Add(現トークン)
□次索引++
□i++
□ループ先頭へ
◇ここまで
◇真==数字か判定する(入力文字列配列[i]) の場合
・string 数字文字列 = 入力文字列配列[i]
□i++
◇(i<入力文字列配列.Length) の場合
〇(数字か判定する(入力文字列配列[i])) の間は繰り返す
□数字文字列+= 入力文字列配列[i]
□i++
◇(i>=入力文字列配列.Length) の場合 やめる
〇ここまで
◇ここまで
□現トークン = 新しいトークン(トークン種類.整数,次索引, 数字文字列,i)
□現トークン.値 = strtol(数字文字列)
□トークンリスト.追加(現トークン)
□次索引++
□ループ先頭へ
◇ここまで
//ここに進んだら例外
□エラー出力("トークナイズできません")
□i++
〇ここまで
□現トークン = 新しいトークン(トークン種類.終端,次索引, "",0)
□トークンリスト.追加(現トークン)
□トークンリスト を返す
△
// 入力文字列をトークナイズしてトークンリストを返す
static List<トークン型> トークナイズする(string 入力文字列) {
int 次索引 = 1;
トークン型 現トークン = new();
List<トークン型> トークンリスト =new List<トークン型>();
var 入力文字列配列 = 入力文字列.ToCharArray();
int i= 0;
while(i<入力文字列配列.Length) {
// 空白文字をスキップ
if (空白か判定する(入力文字列配列[i].ToString())) {
i++;
continue;
}
// Multi-letter punctuator
if (比較記号頭文字か判定する(入力文字列配列[i].ToString())) {
if(i+1<入力文字列配列.Length){
var comp =入力文字列配列[i].ToString()+入力文字列配列[i+1].ToString();
if (比較記号か判定する(comp)) {
現トークン = 新しいトークン(トークン種類.予約語, 次索引, comp,2);
トークンリスト.Add(現トークン);
次索引++;
i+=2;
continue;
}
}
}
// Single-letter punctuator
if (演算子か判定する(入力文字列配列[i].ToString())) {
現トークン = 新しいトークン(トークン種類.予約語, 次索引, 入力文字列配列[i].ToString(),1);
トークンリスト.Add(現トークン);
次索引++;
i++;
continue;
}
if (数字か判定する(入力文字列配列[i].ToString())) {
string 数字文字列 = 入力文字列配列[i].ToString();
i++;
if(i<入力文字列配列.Length){
while(数字か判定する(入力文字列配列[i].ToString())) {
数字文字列+= 入力文字列配列[i].ToString();
i++;
if(i>=入力文字列配列.Length)break;
}
}
現トークン = 新しいトークン(トークン種類.整数,次索引, 数字文字列,i);
現トークン.値 = strtol(数字文字列);
トークンリスト.Add(現トークン);
次索引++;
continue;
}
//ここに進んだら例外
error("トークナイズできません");
i++;
}
現トークン = 新しいトークン(トークン種類.終端,次索引, "",0);
トークンリスト.Add(現トークン);
return トークンリスト;
}
下記のサポート関数の関数名を
isspace iscomparison iscomparisonhead isdigit isarithmetic new_token
日本語化した関数名は下記のとおりとしています。
空白か判定する 比較記号か判定する 比較記号頭文字か判定する 数字か判定する 演算子か判定する 新しいトークン
列挙体・内部クラスなど記述
列挙体、クラス(変数のみ)の宣言
▽列挙体 トークン種類
予約語, // 記号
整数, // 整数トークン
終端 // 入力の終わりを表すトークン
△
▽クラス トークン型
・public トークン種類 種類 // Token kind
・public int 次索引 // Next token
・public int 値 // kindがTK_NUMの場合、その数値
・public string? 文字列 // Token string
・public int 長さ // Token length
△
enum トークン種類{
予約語, // 記号
整数, // 整数トークン
終端 // 入力の終わりを表すトークン
}
class トークン型 {
public トークン種類 種類; // Token kind
public int 次索引; // Next token
public int 値; // kindがTK_NUMの場合、その数値
public string? 文字列; // Token string
public int 長さ; // Token length
}
// 抽象構文木のノードの種類
▽列挙体 ノード種類{
加算記号, // +
減算記号, // -
乗算記号, // *
除算記号, // /
比較等号, // ==
比較不等号, // !=
比較小なり, // <
比較小なり等, // <=
整数 // 整数
△
// 抽象構文木のノードの型
▽クラス ノード型 {
・public ノード種類 種類 // Node kind
・public ノード型? 左辺 // Left-hand side
・public ノード型? 右辺 // Right-hand side
・public int 値 // kindがND_NUMの場合のみ使う
△
// 抽象構文木のノードの種類
enum ノード種類{
加算記号, // +
減算記号, // -
乗算記号, // *
除算記号, // /
比較等号, // ==
比較不等号, // !=
比較小なり, // <
比較小なり等, // <=
整数, // 整数
}
// 抽象構文木のノードの型
class ノード型 {
public ノード種類 種類; // Node kind
public ノード型? 左辺; // Left-hand side
public ノード型? 右辺; // Right-hand side
public int 値; // kindがND_NUMの場合のみ使う
}
gen
genの日本語化した関数名は下記のとおりとしています。
コード生成
▽コード生成(ノード型 ノード) {
◇(ノード.種類 == ノード種類.整数) の場合
□コンソール出力($" push {ノード.値}\n")
□返る
◇ここまで
□コード生成(ノード.左辺)
□コード生成(ノード.右辺)
□コンソール出力(" pop rdi\n")
□コンソール出力(" pop rax\n")
◇(ノード.種類) で分岐する
◇ノード種類.加算記号
□コンソール出力(" add rax, rdi\n")
□脱する
◇ノード種類.減算記号
□コンソール出力(" sub rax, rdi\n")
□脱する
◇ノード種類.乗算記号
□コンソール出力(" imul rax, rdi\n")
□脱する
◇ノード種類.除算記号
□コンソール出力(" cqo\n")
□コンソール出力(" idiv rdi\n")
□脱する
◇ノード種類.比較等号
□コンソール出力(" cmp rax, rdi\n")
□コンソール出力(" sete al\n")
□コンソール出力(" movzb rax, al\n")
□脱する
◇ノード種類.比較不等号:
□コンソール出力(" cmp rax, rdi\n")
□コンソール出力(" setne al\n")
□コンソール出力(" movzb rax, al\n")
□脱する
◇ノード種類.比較小なり
□コンソール出力(" cmp rax, rdi\n")
□コンソール出力(" setl al\n")
□コンソール出力(" movzb rax, al\n")
□脱する
◇ノード種類.比較小なり等
□コンソール出力(" cmp rax, rdi\n")
□コンソール出力(" setle al\n")
□コンソール出力(" movzb rax, al\n")
□脱する
◇ここまで
□脱コンソール出力(" push rax\n")
△
static void コード生成(ノード型 ノード) {
if (ノード.種類 == ノード種類.整数) {
Console.Write($" push {ノード.値}\n");
return;
}
コード生成(ノード.左辺);
コード生成(ノード.右辺);
Console.Write(" pop rdi\n");
Console.Write(" pop rax\n");
switch (ノード.種類) {
case ノード種類.加算記号:
Console.Write(" add rax, rdi\n");
break;
case ノード種類.減算記号:
Console.Write(" sub rax, rdi\n");
break;
case ノード種類.乗算記号:
Console.Write(" imul rax, rdi\n");
break;
case ノード種類.除算記号:
Console.Write(" cqo\n");
Console.Write(" idiv rdi\n");
break;
case ノード種類.比較等号:
Console.Write(" cmp rax, rdi\n");
Console.Write(" sete al\n");
Console.Write(" movzb rax, al\n");
break;
case ノード種類.比較不等号:
Console.Write(" cmp rax, rdi\n");
Console.Write(" setne al\n");
Console.Write(" movzb rax, al\n");
break;
case ノード種類.比較小なり:
Console.Write(" cmp rax, rdi\n");
Console.Write(" setl al\n");
Console.Write(" movzb rax, al\n");
break;
case ノード種類.比較小なり等:
Console.Write(" cmp rax, rdi\n");
Console.Write(" setle al\n");
Console.Write(" movzb rax, al\n");
break;
}
Console.Write(" push rax\n");
}
Mainなど記述
Main
▽int メイン(string[] 引数)
◇(引数.Length != 2) の場合
□コンソール出力( "引数の個数が正しくありません\n");
□1 を返す
◇ここまで
// トークナイズする
□リスト型<トークン型> トークンリスト = トークナイズする(引数[1]);
// 現在着目しているトークン
・int 現索引=0
// パースする
□ノード型 ノード = 式(トークンリスト,ref 現索引)
// アセンブリの前半部分を出力
□コンソール出力(".intel_syntax noprefix\n")
□コンソール出力(".globl main\n")
□コンソール出力("main:\n")
// 抽象構文木を下りながらコード生成
□コード生成(ノード);
// スタックトップに式全体の値が残っているはずなので
// それをRAXにロードして関数からの返り値とする
□コンソール出力(" pop rax\n")
□コンソール出力(" ret\n")
□0 を返す
△
static int Main(string[] args)
{
if (args.Length != 2) {
Console.Write( "引数の個数が正しくありません\n");
return 1;
}
// トークナイズする
List<トークン型> トークンリスト = トークナイズする(args[1]);
// 現在着目しているトークン
int 現索引=0;
// パースする
ノード型 ノード = 式(トークンリスト,ref 現索引);
// アセンブリの前半部分を出力
Console.Write(".intel_syntax noprefix\n");
Console.Write(".globl main\n");
Console.Write("main:\n");
// 抽象構文木を下りながらコード生成
コード生成(ノード);
// スタックトップに式全体の値が残っているはずなので
// それをRAXにロードして関数からの返り値とする
Console.Write(" pop rax\n");
Console.Write(" ret\n");
return 0;
}
入出力コード サンプルイメージ
この記事が対象としているchibicc(9cc)の対象構文は優先順位対応の四則演算に単項演算と比較演算子を加えただけで、変数も導入前のものですから、解釈できるのは下記のような四則演算と比較演算だけです。
5 + 6 * 7
5 * ( 9 - 6 )
( 3 + 5 ) / 2
- 10 + 20
2 != 1
1 == 1
1 >= 1
2 <= 1
2 > 1
2 < 1
今回は2 != 1を対象にchibicc(9cc)と同じアセンブラを出力します。
chibicc(9cc)単項演算子版の実行結果
C#との比較用の期待結果として9ccを実行してみます。
実行環境はWindows11上のVSCode統合のUbuntuターミナル(bash)です。
$ ./a.out "2 != 1"
.intel_syntax noprefix
.global main
main:
push 2
push 1
pop rdi
pop rax
cmp rax, rdi
setne al
movzb rax, al
push rax
pop rax
ret
実行結果
コンパイラの出力コード
続いてC#をコンパイルします。ビルド(コンパイル)はVSCodeのタスクで実行しました。
9ccと同じ四則演算文字列を与えて実行すると、下図のようになりました。
実行環境はWindows11上のVSCodeのターミナルです。
>9cc s "2 !=1 "
.intel_syntax noprefix
.globl main
main:
push 2
push 1
pop rdi
pop rax
cmp rax, rdi
setne al
movzb rax, al
push rax
pop rax
ret
もう少しテストケースを増やした結果をあとで追記します。
ソースコード
GitHub準備中
おわりに
日本語ロジック仕様記述言語 Re:Mindは、制御構文の開始シンボルとして、◇、〇、□、・などの全角記号を用い、箇条書きされた日本文としての体裁を日本語トランスコンパイラ言語 Re:Mindの構文と共有しています。
今回は日本語ロジック仕様記述言語による記述のため、直接C#のソースコードには変換されませんが、日本語トランスコンパイラ言語 Re:Mindの下書きとしては十分使える状態となります。
日本語トランスコンパイラ言語 Re:Mindではjavadocのコメントに英字関数名、英字変数名を指定すると、英字だけからなるソースコードを出力できるよう設計されていますが(実装は現時点で未実現)、今回の記事のC#ソースコードはその英字名指定機能を使わなかった場合に生成されるイメージとなります。
参考リンク