RustでMacで動くCコンパイラを作成する

Ruiさんの書かれた素晴らしいテキスト、[「低レイヤを知りたい人のためのCコンパイラ作成入門」](https://www.sigbus.info/compilerbook) を参考にしながら、Cコンパイラを作っていきます。

ただし、上記テキストと違う点として、

- Rustで記述する
- Mac上で動くようにする

という条件でやっていきたいと思います。

Rustの文法にある程度慣れている読者を想定しています。

毎日少しずつ進めていきます。

---

この記事では、 [電卓レベルの言語の作成](https://www.sigbus.info/compilerbook#%E9%9B%BB%E5%8D%93%E3%83%AC%E3%83%99%E3%83%AB%E3%81%AE%E8%A8%80%E8%AA%9E%E3%81%AE%E4%BD%9C%E6%88%90) の章を扱います。


## [ステップ1：整数1個をコンパイルする言語の作成](https://www.sigbus.info/compilerbook#%E3%82%B9%E3%83%86%E3%83%83%E3%83%971%E6%95%B4%E6%95%B01%E5%80%8B%E3%82%92%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%AB%E3%81%99%E3%82%8B%E8%A8%80%E8%AA%9E%E3%81%AE%E4%BD%9C%E6%88%90)

このステップでの違いは、エントリーポイントのシンボルです。
Linuxでは `main` がエントリーポイントとなりますが、MacOS 10.7 以前だと `start`、10.8 以降だと `_main` がエントリーポイントとなります。

僕の環境は10.15だったので、 `_main` をエントリーポイントとしました。

つまり、以下のようなアセンブリを出力することになります。

```tmp.s
.intel_syntax noprefix
.global _main

_main:
        mov rax, 42
        ret
```

### [コンパイラ本体の作成](https://www.sigbus.info/compilerbook#%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E6%9C%AC%E4%BD%93%E3%81%AE%E4%BD%9C%E6%88%90)

コンパイラ自作用のcrateを作成し、そのmainファイルを以下のようにしました。
そんなに複雑なことはやっていないのでコードの解説は割愛します。
あと面倒なのでエラーハンドリングとかちゃんとやってません、、

```rust:main.rs
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内で、以下のようにプログラムを実行すると、目標としていたアセンブリファイルが出力されるはずです。

```shell:shell
$ cargo run -- 42 > tmp.s
```

動作を確認します。

```shell:shell
$ cc -o tmp tmp.s
$ ./tmp
$ echo $?
42
```

動いた。いえい。

### [自動テストの作成](https://www.sigbus.info/compilerbook#%E8%87%AA%E5%8B%95%E3%83%86%E3%82%B9%E3%83%88%E3%81%AE%E4%BD%9C%E6%88%90)

テストスクリプトは以下のようになりました。
変更箇所は1行だけです。

```shell:test.sh
#!/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によるビルド](https://www.sigbus.info/compilerbook#make%E3%81%AB%E3%82%88%E3%82%8B%E3%83%93%E3%83%AB%E3%83%89)

完全にスキップします。
ありがとう、cargo。

### [gitによるバージョン管理](https://www.sigbus.info/compilerbook#git%E3%81%AB%E3%82%88%E3%82%8B%E3%83%90%E3%83%BC%E3%82%B8%E3%83%A7%E3%83%B3%E7%AE%A1%E7%90%86)

特に差分はないです。
`target` ディレクトリを `.gitignore` に追加するのを忘れないようにしてください。


## [ステップ2：加減算のできるコンパイラの作成](https://www.sigbus.info/compilerbook#%E3%82%B9%E3%83%86%E3%83%83%E3%83%972%E5%8A%A0%E6%B8%9B%E7%AE%97%E3%81%AE%E3%81%A7%E3%81%8D%E3%82%8B%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%81%AE%E4%BD%9C%E6%88%90)

エントリーポイントが異なる以外は、出力するアセンブリはオリジナルのものと一緒です。
では、そのようなコンパイラをRustで書き直していきます。

ですがここで一つ問題があり、オリジナル実装で使用している `strtol` 関数に相当するものがRustには存在しません。
いや、あるのかな、ちゃんと調べてないのでわかりません。

> 2020/5/6 追記
> strtol関数っぽいやり方を発見したので追記しておきます。
> 
> ```rust
> 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(" ")`で終わります。

この方法で実装したものが以下になります。

```rust:main.rs
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");
}
```

#### リファレンス実装

https://github.com/AtsukiTak/atomcc/tree/04ba099f34ddb32059343a2c84d7240998e85577

## [ステップ3：トークナイザを導入](https://www.sigbus.info/compilerbook#%E3%82%B9%E3%83%86%E3%83%83%E3%83%973%E3%83%88%E3%83%BC%E3%82%AF%E3%83%8A%E3%82%A4%E3%82%B6%E3%82%92%E5%B0%8E%E5%85%A5)

この章から本格的にRustの実装に入ります。
もはやオリジナルのコードとの共通部分は1~2割くらいしかないです。

さて、トークナイザのの実装ですが、トークナイザの役割を一言で言うならば、

**文字列を受け取り、トークンのイテレータを返す関数**

なのではないでしょうか。

そんな感じですよね。そんな感じだと思うので、そんな感じで実装したものが以下になります。

```rust:tokenizer.rs
/// １つのトークンを表す列挙体。
/// オリジナルの実装とは違い、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モジュールは以下のようになります。

```rust:main.rs
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");
}
```

完成。いえい。

オリジナル記事と同様に、空白をちゃんとパースしているかどうかのテストを追加すると、きちんと動作していることが分かります。

また、このバージョンから、空白で区切られていない式でもパースできるようになっています。

いえい。

あまりコードの詳細な解説はしませんが、もし不明瞭な点などあればコメントいただければ回答します。

#### リファレンス実装

https://github.com/AtsukiTak/atomcc/tree/79e5dfd5e4e7cec333079015c535ec37a77e5582