Compiler/Code Generator
タスク概要
構文解析で得られた Abstract Syntax Tree(AST) から次のタスクで作成する Virtual Machine 用アセンブリを出力する。
入力は Compiler/Syntax Analyzer での出力形式に基づいたテキスト。
実装
意味解析や最適化等は行わないため、基本的には Compiler/AST Interpreter でやったことと変わらない。違いはその場で計算を実行する代わりにアセンブリを出力するくらい。
なので、以降は Code Generation において注意すべき点を挙げるにとどめる。
while, if の扱い
while 文の制御は大まかに以下の図のようになる。
まず cond を評価し、それが True(0 以外) の間は body を実行し続ける。よって、出力すべき code は
- cond の code
- jz body の次
- body の code
- jmp cond へ戻る
という順に code が並ぶ。ここには 2 種類の分岐命令があり、青で示したものは backward 、赤は forward 方向へ飛ぶ。ここで問題になるのは赤の forward 方向の jz 命令で、jz の出力時点では body のサイズが不明なために jump 先アドレスがわからない。
なので、一時的な code を出力しておき、bodyの code 出力後、つまり飛び先のアドレスが確定してから置き換える。
if 文も同様。ただしこちらの方が少し複雑になる。
cond が偽であれば if 節をジャンプする。真であれば、if 節実行後に else 節があればそれをジャンプする。よって置き換え対象が最大 2 つ存在する。
変数、文字列の扱い
定数に関してはスタックマシンということもあって push するだけなので楽。一方で変数と文字列はもう少し考えることがある。
今回、変数はグローバル変数しか存在しない。また、その値は常に i32 になる。よって何種類の変数が使われているかだけで必要なメモリを算出できる。実現には code generation 時に出現した変数を数えておくだけで良い。
CodeGenerator の data_addr が現れた変数をおぼえておくためのもので、変数名 -> アドレス の HashMap になっている。
pub struct CodeGenerator<'a> { data_addr: HashMap<&'a str, u32>, string_pool: Vec<&'a str>, pc: u32, instructions: Vec<Instruction>, }
アドレスは変数の出現順に 0, 1, 2, ... としているため、新しい変数に出会う度にその時点での data_addr のサイズを用いる。処理内容は以下の通りで、None の Arm 部分が新規の変数に出会った時の処理になる。
fn intern(&mut self, name: &'a str) -> u32 { match self.data_addr.get(name) { Some(addr) => *addr, None => { let addr = self.data_addr.len() as u32; self.data_addr.insert(name, addr); addr } } }
文字列は出現順に string_pool へ push する。今回は Vec として実装したが、こちらも HashMap にして同一文字列が現れた場合には以前のアドレスを参照するようにした方が良かったかもしれない。実装対象の言語では String は必ず immutable になるから、それで問題が生じることもない。
その他
特に注意すべき点もないのでソースを見ればわかるはず。
余談
出力するアセンブリの仕様がちゃんと書かれていなくて、主に分岐(ジャンプ)命令で少し難儀した。アセンブリだから当然ターゲットとなる virtual machine の仕様と密接な関連があるのだけれど、virtual machine の仕様がソース以外に見当たらない。
問題になったのは分岐命令で、
- 命令フェッチ
- pc <- pc + 1
- (jz の場合条件判定)
- jump 先アドレス計算
- (ジャンプ しなかった場合)pc <- pc + 4
という順序で処理を行う。よって PC 相対で jump 先アドレスを表現する際には pc が 1 増えた状態での相対アドレスになる。オペランドに含まれるアドレス部の 4 bytes はこの時点ではまだ pc に加えられていないことに注意。
