低レイヤを知りたい人のためのCコンパイラ作成入門 ステップ11-15を参考にしています。
識別子を、[a-z] から [a-zA-Z_][a-zA-Z0-9_]* に拡張
- 参考: ステップ11
- コード差分
- ローカル変数をスタックフレーム内にどう割り当てるか、パース時に保存し、コード生成時に読み出すように変更した。
/* 字句解析器の identifier 部分 */ if(std::isalpha(*p) || *p == '_'){ // 最初の文字は [a-zA-Z_] auto p_lookahead = p+1; while(is_alnum(*p_lookahead)){ // それ以降は [a-zA-Z0-9_] (is_alnum に実装されてる) じゃなくなるまで読む ++p_lookahead; } /* トークン構造体生成 (省略) */ continue; }
ひとつの文をたずさえた if 文, for 文, while 文を導入
# 構文の一部
stmt := "return" expression ";"
| "if" "(" expression ")" stmt
| "for" "(" expression ";" expression ";" expression ")" stmt
| "while" "(" expression ")" stmt
| expression ";"
/* for 文のコード生成 */ if(node->type == ASTNodeType::FOR){ size_t static new_for_stmt_sequence = 0; auto const for_stmt_sequence = new_for_stmt_sequence; new_for_stmt_sequence++; // 雑に通し番号をつくってユニークなラベルをつくる std::string const loop_label = ".FOR_STMT_" + std::to_string(for_stmt_sequence) + "_LOOP"; std::string const break_label = ".FOR_STMT_" + std::to_string(for_stmt_sequence) + "_BREAK"; // 初期化式を生成 gen(node->initialization); // ループ用ラベルを配置 std::cout << loop_label << ":\n"; // 条件式を生成 gen(node->condition); std::cout << // 条件式の評価結果をポップして " ld a0, (sp)\n" " addi sp, sp, " << sizeof_variable << "\n" // 0 なら body を抜けるラベルに飛ぶ " beqz a0, " << break_label << "\n"; // body と afterthought を生成 gen(node->body); gen(node->afterthought); std::cout << // 条件式の評価に戻る " j " << loop_label << "\n" // 抜けるラベルを配置 << break_label << ":\n"; return; }
複文（ブロック）
# 構文の一部
stmt := "return" expression ";"
| "if" "(" expression ")" stmt
| "for" "(" expression ";" expression ";" expression ")" stmt
| "while" "(" expression ")" stmt
(NEW) | "{" block_items "}"
| expression ";"
block_items := none
| stmt
| stmt block_items
block_items は stmt の 0回以上の 繰り返しっていうのがミソで、1回以上にしちゃうと後で void f(){} がコンパイルできなくなる。
ここで発覚したヤバめのバグは脚注*1で…。
次のコードをコンパイルできるようになった。
{a = 0; b = 0;}
if(1){ a = 1; b = 2; }
if(0){ a = 3; b = 4; }
while(1){{return a*a*b*b;}}
関数呼び出し
まず構文を変更して
unary := "+" funccall
| "-" funccall
| funccall
funccall := term
| term "(" ")"
term := "(" expression ")"
| number
| identifier
構文解析器を変更
/* 構文解析の funccall (= 関数呼び出しか term) 解析部分 */ ASTNode* funccall(std::vector<Token>::const_iterator& token_itr){ ASTNode* node = term(token_itr); if(consume(TokenType::BEGIN_PAREN, token_itr)){ // term 直後の開きカッコ ( をみつけたら ASTNode* callnode = new ASTNode(); callnode->type = ASTNodeType::FUNCTION_CALL; callnode->lhs = node; if(consume(TokenType::END_PAREN, token_itr)){ // term () の場合 callnode->inner_nodes = {}; }else{ // term ( argument_list ) の場合 callnode->inner_nodes = argument_list(token_itr); require_token(TokenType::END_PAREN, token_itr); } return callnode; } return node; } std::vector<ASTNode const*> argument_list(std::vector<Token>::const_iterator& token_itr){ std::vector<ASTNode const*> arguments; // 式を解析・コンマを消費 を繰り返す （コンマがなくなったら終わり） do{ arguments.push_back(expression(token_itr)); }while (consume(TokenType::COMMA, token_itr)); return arguments; }
コード生成は… 各実引数を評価してレジスタに積む。
/* グローバル定数においてあるレジスタ一覧 */ std::array<std::string, 8> const static argument_registers{ "a0", "a1", "a2", "a3", "a4", "a5", "a6", "a7" }; /* コード生成の FUNCTION_CALL 部分 */ size_t const num_of_args = std::min(argument_registers.size(), node->inner_nodes.size()); for(size_t i=0; i<num_of_args; ++i){ // 実引数を左から順番に評価（スタックに積まれる） gen(node->inner_nodes.at(i)); } for(size_t i=0; i<num_of_args; ++i){ // sp からのオフセットを考えて、評価した実引数をスタックから取り出し、レジスタにロード ptrdiff_t const offset = sizeof_variable * (num_of_args-i-1); std::cout << " ld " << argument_registers.at(i) << ", " << offset << "(sp)\n"; } std::cout << // 使った分は sp を始末しておきましょう " addi sp, sp, " << sizeof_variable * num_of_args << "\n" // 自分の戻り先アドレスが失くなってしまわないように保存しておきましょう " addi sp, sp, -" << sizeof_variable << "\n" " sd ra, (sp)\n" // 識別子名をそのまま call に発行します（アセンブラありがとう） " call ra, " << callee->id_name << "\n" // 戻り先アドレスを復元 " ld ra, (sp)\n"; return;
このとき、スタックポインタ sp は 16 バイト境界に align しないといけないみたい で、面倒なので各 push, pop を16バイトにした。
関数定義
ここが一番バグった（&バグを顕在化させた）…。
ソースコード全体は 関数定義の0回以上の繰り返し になるように文法を変更。
program := funcdef program
| none
funcdef := identifier "(" ")" "{" block_items "}"
| identifier "(" parameter_list ")" "{" block_items "}"
parameter_list := identifier "," parameter_list
構文解析器も変更して、各関数定義に通し番号を振って、ローカル変数のオフセットなどが相互に影響しないようにした。（コード省略）
コード生成。関数の突入時には ベースポインタの退避・新規設定 と スタックフレームの取得をして
size_t const stackframe_size = variables_info.num_of_variables(generating_funcdef_function_id) * sizeof_variable; std::cout << "# prologue\n" // ベースポインタをスタックに退避 " addi sp, sp, -" << sizeof_variable << "\n" " sd s0, (sp)\n" // 現在のスタックポインタをベースポインタにコピー " mv s0, sp\n" // スタックフレームを確保 " addi sp, sp, -" << stackframe_size << "\n";
レジスタに入っている（実引数の）値を、スタックに割り当てた仮引数にコピーする。これで関数内でローカル変数と同列に扱える。
size_t const num_of_parameters = node->call_list.size(); for(size_t i=0; i<num_of_parameters; ++i){ ASTNode const* const param = node->call_list.at(i); ptrdiff_t const offset = variables_info.offset_of(generating_funcdef_function_id, param->id_name); std::cout << " # copy " << param->id_name << "\n" " sd " << argument_registers.at(i) << ", -" << offset << "(s0)\n"; }
absprod(x, y, z){
return labs(x * y * z); // libc の関数を呼ぶ
}
main(){
return absprod(2, 3, 4); // -> 24
}
FizzBuzz できました。
自作処理系でコンパイル:
fizz(){
putchar(70); // F
putchar(105); // i （以下略）
putchar(122);
putchar(122);
}
buzz(){
putchar(66);
putchar(117);
putchar(122);
putchar(122);
}
judge(x){
f = x % 3 == 0;
b = x % 5 == 0;
if(f) fizz();
if(b) buzz();
if(f + b == 0) print_ld(x);
putchar(10); // 改行コード 0x0a
return 0;
}
main(){
for(i = 1; i <= 30; i = i + 1){
judge(i);
}
return 0;
}
#include <stdio.h> #include <stdlib.h> void print_ld(int64_t x){ printf("%ld", x); }
実行結果:
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz （後略）
本記事に対応するコード差分 ← ここ
総括
知れたこと
- 「文脈自由文法」
- 再帰下降構文解析、LL(1) 解析
- 再帰下降は構文規則と実際の解析コードの見た目が近く、編集しやすい。他はこうもいかないだろう。
- 遷移表とか全然書いてない。
- 文法のネストが関数呼び出しのスタックと各関数の仕事によってキレイに表現されてるの美しいなぁ…。
- First Set、FollowSet、Director Set とかの理論的な部分？と結びつけるのはまだだけど、そういう本も読みやすくなる素地を作れた気がする。
- 字句解析 → 構文解析 → コード生成 の流れの肌感
- 「フロントエンド」「バックエンド」と言いたくなる理由もわかってきた。
- 抽象構文木のトラバースたのしい。
- 今後拡張していった場合、たとえば
break;のコード生成をするときに、「自分がどの while 文に所属するのか」という 文脈 が必要になるのでは？ - Token にソースからの情報を保存して、 ASTNode はそれを覚えたり、ASTNode から Token を指したりしないと、「何行目でエラー」といったメッセージすら出せない！
知れなかったこと
- LL(1) 再帰下降以外の解析法
- 型
- LL(1) の限界
- C の実装をやっていくうちに、どこかで無理が来て解析法を変更しましょうねっていう流れになると思っていた。
- C のツライ部分
- 「宣言文」「型」に手を出していないので。
typedef怖そう。- ポインタ・関数型系の構文も。
- パーサジェネレータ、パーサコンビネータ
- 一回なにか触ってみてもいいのかもしれない。
- LLVM
- 同上。
参考文献
*1: expression ; という文はスタックに1つ結果を残すので、ここまでは、 stmt の評価後はスタックを1段棄てることにしていた。if や for が入り、その expression ; が評価されるか不確定になったり、空の複文 {} があったりして、スタックを余計に棄てたりするバグが起こった。スタックマシン風をやっている限り、「そこで確実に評価する文」＝「expression ;」は他の文と別に扱う必要があるのかも…？ 今は stmt のコード生成で「IFじゃなくてFORじゃなくてWHILEじゃなくて…」という対症療法をしたけど、それはそれで「expression ;」をbodyにもつ制御構文 stmt の評価後に1段余計にスタックを残す。治ってないぞ！
*2:ここで、UNIX に渡される返り値が uchar 幅相当なのを忘れて、でかい数を返して「テスト合わない！！」っていうヘマをしました…
