Ruiさんの書かれた素晴らしいテキスト、「低レイヤを知りたい人のためのCコンパイラ作成入門」 を参考にしながら、Cコンパイラを作っていきます。
ただし、上記テキストと違う点として、
- Rustで記述する
- Mac上で動くようにする
という条件でやっていきたいと思います。
Rustの文法にある程度慣れている読者を想定しています。
毎日少しずつ進めていきます。
この記事では、 電卓レベルの言語の作成 の章を扱います。
ステップ1：整数1個をコンパイルする言語の作成
このステップでの違いは、エントリーポイントのシンボルです。
Linuxでは main がエントリーポイントとなりますが、MacOS 10.7 以前だと start、10.8 以降だと _main がエントリーポイントとなります。
僕の環境は10.15だったので、 _main をエントリーポイントとしました。
つまり、以下のようなアセンブリを出力することになります。
.intel_syntax noprefix
.global _main
_main:
mov rax, 42
ret
コンパイラ本体の作成
コンパイラ自作用のcrateを作成し、そのmainファイルを以下のようにしました。
そんなに複雑なことはやっていないのでコードの解説は割愛します。
あと面倒なのでエラーハンドリングとかちゃんとやってません、、
fn main() {
let i = {
let s = std::env::args().nth(1).unwrap();
usize::from_str_radix(s.as_str(), 10).unwrap()
};
println!(".intel_syntax noprefix");
println!(".global _main");
println!("_main:");
println!(" mov rax, {}", i);
println!(" ret");
}
このcrate内で、以下のようにプログラムを実行すると、目標としていたアセンブリファイルが出力されるはずです。
$ cargo run -- 42 > tmp.s
動作を確認します。
$ cc -o tmp tmp.s
$ ./tmp
$ echo $?
42
動いた。いえい。
自動テストの作成
テストスクリプトは以下のようになりました。
変更箇所は1行だけです。
#!/bin/bash
assert() {
expected="$1"
input="$2"
cargo run -- "$input" > tmp.s ## ここだけ変更
cc -o tmp tmp.s
./tmp
actual="$?"
if [ "$actual" = "$expected" ]; then
echo "$input => $actual"
else
echo "$input => $expected expected, but got $actual"
exit 1
fi
}
assert 0 0
assert 42 42
echo OK
makeによるビルド
完全にスキップします。
ありがとう、cargo。
gitによるバージョン管理
特に差分はないです。
target ディレクトリを .gitignore に追加するのを忘れないようにしてください。
ステップ2：加減算のできるコンパイラの作成
エントリーポイントが異なる以外は、出力するアセンブリはオリジナルのものと一緒です。
では、そのようなコンパイラをRustで書き直していきます。
ですがここで一つ問題があり、オリジナル実装で使用している strtol 関数に相当するものがRustには存在しません。
いや、あるのかな、ちゃんと調べてないのでわかりません。
2020/5/6 追記
strtol関数っぽいやり方を発見したので追記しておきます。fn split_digit(s: &str) -> (&str, &str) { let first_non_num = s.find(|c| !char::is_numeric(c)).unwrap_or(s.len()); s.split_at(first_non_num) } assert_eq!(split_digit("42hoge"), ("42", "hoge"));この関数は文字列を、数値の文字列と残りの文字列に分割したものを返します。
strtol 関数は
- 渡されたポインタに格納してある文字列を10進数の数値としてパースする
- 読み込んだ最後の文字の次の文字へのポインタを、渡されたポインタに格納する
というなかなかに複雑なことをやっています。
Rustでこのようにポインタをゴリゴリいじるのは大変なので、やり方を変えます。
というか、前提条件を変えることでかなり楽をします。
オリジナル記事では、引数で与えられる式には空白が含まれていませんが、今回はトークンの間に空白を含むことにします。
つまり、
1+2+42 => 1 + 2 + 42
のように変更します。
かなりずるいですが、この変更によって、トークンのパースは String::split(" ")で終わります。
この方法で実装したものが以下になります。
fn main() {
let arg = std::env::args().nth(1).unwrap();
let mut expr = arg.split(" ");
let n = {
let s = expr.next().unwrap();
usize::from_str_radix(s, 10).unwrap()
};
println!(".intel_syntax noprefix");
println!(".global _main");
println!("_main:");
println!(" mov rax, {}", n);
while let Some(op) = expr.next() {
let n = {
let s = expr.next().unwrap();
usize::from_str_radix(s, 10).unwrap()
};
match op {
"+" => println!(" add rax, {}", n),
"-" => println!(" sub rax, {}", n),
_ => panic!("Unexpected Operator"),
}
}
println!(" ret");
}
リファレンス実装
ステップ3：トークナイザを導入
この章から本格的にRustの実装に入ります。
もはやオリジナルのコードとの共通部分は1~2割くらいしかないです。
さて、トークナイザのの実装ですが、トークナイザの役割を一言で言うならば、
文字列を受け取り、トークンのイテレータを返す関数
なのではないでしょうか。
そんな感じですよね。そんな感じだと思うので、そんな感じで実装したものが以下になります。
/// １つのトークンを表す列挙体。
/// オリジナルの実装とは違い、PlusとMinusをそれぞれ個別のトークンとして実装しています。
#[derive(Debug)]
pub enum Token {
Plus,
Minus,
Num(usize),
}
/// トークンのイテレータを表す構造体
pub struct TokenIter<'a> {
s: &'a str,
}
/// 文字列を受け取って、トークンのイテレータを返す関数。つまりトークナイザー。
/// Rustのイテレータは遅延評価なのでここでは何もしていない。
pub fn tokenize<'a>(s: &'a str) -> TokenIter<'a> {
TokenIter { s }
}
impl Token {
/// あとで使う便利関数。
pub fn expect_num(&self) -> usize {
match self {
Token::Num(n) => *n,
t => panic!("Expect number but found {:?}", t),
}
}
}
/// トークナイザーの中身。
/// やっていることは、次のトークンの判定を行い、内部の文字列を更新するだけ。
impl<'a> Iterator for TokenIter<'a> {
type Item = Token;
fn next(&mut self) -> Option<Self::Item> {
self.s = self.s.trim_start();
if self.s.is_empty() {
return None;
}
if self.s.as_bytes()[0] == b'+' {
self.s = self.s.split_at(1).1;
return Some(Token::Plus);
}
if self.s.as_bytes()[0] == b'-' {
self.s = self.s.split_at(1).1;
return Some(Token::Minus);
}
let (digit_s, remain_s) = split_digit(self.s);
if !digit_s.is_empty() {
self.s = remain_s;
return Some(Token::Num(usize::from_str_radix(digit_s, 10).unwrap()));
}
panic!("Invalid token stream")
}
}
/// Rustにstrtol関数がないので同じような挙動をする関数を定義する。
fn split_digit(s: &str) -> (&str, &str) {
let first_non_num_idx = s.find(|c| !char::is_numeric(c)).unwrap_or(s.len());
s.split_at(first_non_num_idx)
}
実装だけで50行くらいですね。
わりと素直に実装できました。
C言語の実装と比較すると、列挙体やイテレータなどのあたりで、Rustの恩恵を感じることができます。
このトークナイザーを使用すると、mainモジュールは以下のようになります。
pub mod tokenizer;
use tokenizer::{tokenize, Token};
fn main() {
let arg = std::env::args().nth(1).unwrap();
let mut token_iter = tokenize(arg.as_str());
println!(".intel_syntax noprefix");
println!(".global _main");
println!("_main:");
println!(" mov rax, {}", token_iter.next().unwrap().expect_num());
while let Some(token) = token_iter.next() {
let n = token_iter.next().unwrap().expect_num();
match token {
Token::Plus => println!(" add rax, {}", n),
Token::Minus => println!(" sub rax, {}", n),
_ => panic!("Unexpected Operator"),
}
}
println!(" ret");
}
完成。いえい。
オリジナル記事と同様に、空白をちゃんとパースしているかどうかのテストを追加すると、きちんと動作していることが分かります。
また、このバージョンから、空白で区切られていない式でもパースできるようになっています。
いえい。
あまりコードの詳細な解説はしませんが、もし不明瞭な点などあればコメントいただければ回答します。
リファレンス実装