Rust+LLVMでコンパイラを作る：#4 電卓づくり

## 本連載のバックナンバー
 * [#1: 環境構築](https://qiita.com/_53a/items/de260505610256a00dbe)
 * [#2: 概要と方針](https://qiita.com/_53a/items/304f1562b3aa0cad616d)
 * [#3: 大枠づくり](https://qiita.com/_53a/items/d7d4e4fc250bfd945d9e)
 * [#4: 電卓づくり](https://qiita.com/_53a/items/843b7fa8328523c115cf)
 * [#5: ファイルの分割と単体テスト](https://qiita.com/_53a/items/bde614986696a9bddd23)
---

お久しぶりです。冬休みの宿題として、久々に本連載でも書いてみようかと思います。
今回は前回作成したコンパイラの土台に、空白の読み飛ばしと演算子（手始めに四則演算のみ）、丸括弧を実装し、シンプルな電卓程度の機能を持たせます。

まずは上記バックナンバーを参考に、 [前回記事](https://qiita.com/_53a/items/d7d4e4fc250bfd945d9e) のコードが実行できる環境を整えておいてください。

## AST

まずは AST が四則演算と丸括弧を扱えるようにします。

`mod ast{...}` の中に、以下の内容を追記していきます。

まずは四則演算の種類を表す `enum` を追加します。ここでは、後で別の二項演算子を追加できるよう、名前を `BiOpKind` にします。 `BiOp` は binary operator （二項演算子）の略です。

```rust
#[derive(Debug, Clone, PartialEq)]
pub enum BiOpKind {
    Add,
    Sub,
    Mul,
    Div,
}
```

`Add` は足し算、`Sub` は引き算、 `Mul` は掛け算、 `Div` は割り算を表します。

また、`NodeKind` の中に、

```rust
Paren(Id),
BiOp(BiOpKind, Id, Id),
```

という項目を追加します。それぞれ、`BiOp` は二項演算子、 `Paren` は丸括弧を表します。

## パーサ

次に、パーサに機能を追加していきます。
`mod parser` 内の `grammar main_parser(context: &Context) for str {...}` の中に以下の内容を追加していきます。

まずはパーサが空白を無視できるようにします。

```rust
#[cache]
rule _() = quiet!{[' '|'\t'|'\r'|'\n']*{}}
```
詳細については peg の[ドキュメント](https://docs.rs/peg/latest/peg/) を参照していただきたいのですが、このコードの要点をかいつまむと、

 - `#[cache]` はパース結果をメモリにキャッシュすることを指示する属性です。これにより、メモリ使用量が増大する代わりに実行速度を向上させることができます。
 - `_` というルール名は peg 側で特別扱いされます。通常のルール名は使用時に `()` を後置する必要があるのですが、 `_` というルール名は `()` を後置せずに使用できます。
 - `quiet!` は、パースエラー時のエラーメッセージにこのルールが表れてこないように指定する記法です。

といった形となっています。

また、上記で実装した空白の無視を、前回実装した整数パーサに導入します。

```rust
rule int_lit() -> ast::NodeKind = _ n:$(['0' ..= '9']+) {
    ast::NodeKind::Lit(ast::LitKind::IntLit(n.parse().unwrap()))
}
```

少しわかりにくいですが、 `n:$(...` の前に `_` が入っています。
このように、空白を入れることが許容される位置に `_` を入れていきます。



次に、パーサが四則演算を含む演算子、および丸括弧をパースできるようにします

ここでは、演算子には優先順位というものがあることに注意しましょう。具体的には、 `*` は `+` に比べて優先順位が高いため、 `+` より後ろに `*` があっても `*` が先に計算されます。

演算子の優先順位を愚直に実装すると、見た目が冗長だったり速度が遅かったりしがちですが、今回使用している peg ライブラリでは優先順位のある演算子専用の構文を用意してくれているので、それをありがたく使用させてもらいます。

```rust
rule expr() -> ast::Id = precedence! {
    _:position!() p:@ _:position!() {
        let mut arena = context.arena.borrow_mut();
        arena.alloc(
            ast::Node {
                kind: p,
            }
        )
    }
    --
    x:(@) (_ "+") y:@ { ast::NodeKind::BiOp(ast::BiOpKind::Add, x, y) }
    x:(@) (_ "-") y:@ { ast::NodeKind::BiOp(ast::BiOpKind::Sub, x, y) }
    --
    x:(@) (_ "*") y:@ { ast::NodeKind::BiOp(ast::BiOpKind::Mul, x, y) }
    x:(@) (_ "/") y:@ { ast::NodeKind::BiOp(ast::BiOpKind::Div, x, y) }
    --
    n: int_lit() { n }
    _ "(" e:expr() _ ")" { ast::NodeKind::Paren(e) }
}
```

`precedence! {` 内が優先順位つきの演算子を定義する専用構文です。詳細は上記と同じく peg のドキュメントを参照していただきたいのですが、

- 演算子の引数の位置に `@` を記述する 
- `(@)` を記述する位置によって左優先か右優先か指定する
- `--` を挟むごとに優先順位が高くなる

といった点が本構文の特徴になっています。

また、最初の `_:position!() p:@ _:position!() {` については、`NodeKind` から `Node` への変換処理をここでやる必要があるのと、そのついでに式の位置情報を取得可能にしておくといった程度の意図があります。

## IR

次に、IR にも演算子への対応を入れていきます。
空白や丸括弧の情報はパーサと IrGen で欠落させているので、これらはIRでは扱う必要がありません。

以下の内容を `mod ir {...}` 内に記述していきます。

まずは演算子の種類を表す `enum` を作成します。

```rust
#[derive(Debug, Clone, PartialEq)]
pub enum OpKind {
    IAdd,
    ISub,
    IMul,
    IDiv,
}
```

また、`pub enum Kind` に演算子を表す項 `Op(OpKind, Vec<Id>)` を追加します。

AST では 演算子のアリティ（引数の数）によって kind の項を分けていましたが、 IR では これを統合しています。
また、演算子の型によってオペコードを分けています[^opcode]

[^opode]: 現在は整数型（`I` から始まるもの）しかありませんが


## IrGen

`mod irgen` の　`impl IrGen {...}` の中に以下のものを追加していきます。

まずは AST の `BiOpKind` から IR の `OpKind` へ単純に変換できる箇所について変換を行う関数を作成します。

```rust
fn map_biop_kind(kind: &ast::BiOpKind) -> Result<ir::OpKind> {
    match kind {
        ast::BiOpKind::Add => Ok(ir::OpKind::IAdd),
        ast::BiOpKind::Sub => Ok(ir::OpKind::ISub),
        ast::BiOpKind::Mul => Ok(ir::OpKind::IMul),
        ast::BiOpKind::Div => Ok(ir::OpKind::IDiv),
    }
}
```

現在は扱う型が整数型しかないため、このようにかなり単純な実装になっていますが、将来的には AST 側の演算子の引数の型によって生成する IR のオペコードを変えるなどの変更を入れることになるかと思います。


次に、 `generate_impl` を以下のように書き換えます。

```rust
fn generate_impl(&mut self, root: ast::Id) -> Result<ir::Id> {
    let kind = &self
        .ast_arena
        .get(root)
        .ok_or(anyhow!("failed to get ast node from arena"))?
        .kind
        .clone();
    match kind {
        ast::NodeKind::Lit(lit) => match lit {
            &ast::LitKind::IntLit(i) => Ok(self.new_node(ir::Kind::IntValue(i))),
        },
        ast::NodeKind::Paren(e) => self.generate_impl(*e),
        ast::NodeKind::BiOp(kind, lhs, rhs) => {
            let op_kind = Self::map_biop_kind(&kind)?;
            let lhs = self.generate_impl(*lhs)?;
            let rhs = self.generate_impl(*rhs)?;
            let args = vec![lhs, rhs];
            Ok(self.new_node(ir::Kind::Op(op_kind, args)))
        }
    }
}
```

変更点として、 `kind` を取得する際に `clone` している他、 `ast::NodeKind::Paren` および `ast::NodeKind::BiOp` に対応する IR 生成部を追加しています。

`Paren` は式の評価順を制御するための丸括弧を表しているため、評価順を木構造で持っている IR では不要な項になっています。そこで、IR に変換する際に `Paren` を捨て去ってしまいます。実装的には、中身の `Node` について再帰的に `generate_impl` したものをそのまま返しています。

`BiOp` は、まず先ほど追加した `map_biop_kind` を使用して現在の `BinOpKind` から対応する `ir::OpKind` を取得します。次に現在の演算子の左辺と右辺に対して `generate_impl` を適用し、 IR に変換します。これらを `Vec` に詰めた後、 `IR` のノードに詰めて返しています。

## CodeGen

`mod codegen` の `impl<'a> CodeGen<'a> {...}` 内の `fn generate_impl(&self, id: ir::Id) -> Result<Value>` を以下のように書き換えます。

具体的には、 `match kind {...}` 内に `ir::Kind::Op` に対応するコード生成部を追加しています。

```rust
fn generate_impl(&self, id: ir::Id) -> Result<Value> {
    let kind = &self
        .ir_arena
        .get(id)
        .ok_or(anyhow!("failed to get ir from arena"))?
        .kind;

    match kind {
        &ir::Kind::IntValue(i) => Ok(Value::from_int_value(
            self.context.i64_type().const_int(i as u64, true),
        )),
        ir::Kind::Op(op, args) => {
            let ret = match op {
                ir::OpKind::IAdd => Value::from_int_value(
                    self.builder.build_int_add(
                        self.generate_impl(args[0])?.into_int_value()?,
                        self.generate_impl(args[1])?.into_int_value()?, 
                        ""
                    )
                ),
                ir::OpKind::ISub => Value::from_int_value(
                    self.builder.build_int_sub(
                        self.generate_impl(args[0])?.into_int_value()?,
                        self.generate_impl(args[1])?.into_int_value()?, 
                        ""
                    )
                ),
                ir::OpKind::IMul => Value::from_int_value(
                    self.builder.build_int_mul(
                        self.generate_impl(args[0])?.into_int_value()?,
                        self.generate_impl(args[1])?.into_int_value()?, 
                        ""
                    )
                ),
                ir::OpKind::IDiv => Value::from_int_value(
                    self.builder.build_int_signed_div(
                        self.generate_impl(args[0])?.into_int_value()?,
                        self.generate_impl(args[1])?.into_int_value()?, 
                        ""
                    )
                ),
            };
            Ok(ret)
        }
    }
}
```

`ir::Kind::Op` に対応するコードを生成する箇所ですが、まずは `op` で分岐させ、それぞれのオペコードに対応する処理 （`builder` への命令の追加）を愚直に行っています。

今回は基本的に、各オペコードが持つオペランドに対して再帰的に `generate_impl`　を適用した後、それぞれを本来の型である `IntValue` に変換した後 `builder` の対応する関数に渡し、帰ってきた `IntValue` を `Value` 型に変換して返しています。

似たような処理がいくつも羅列されていますが、下手に共通化させようとすると lifetime 地獄に陥るため、やむなくべた書きしています。今後リファクタリングするかもしれません。

## 実行

ここまで実装し終えたら、適当なファイル（ここでは `test.bonsai` とします）に適当な数式（`2 + 5 * 8` など）を書き込んだ後、`cargo run --bin bonsaic -- test.bonsai` を実行しましょう。

`successfully compiled to test` 等の一行が出たら（Rustで書いたbonsai言語処理系と、その言語処理系がコンパイルする上記数式の両方の）コンパイル成功です。次に生成された実行ファイルを実行してみて、計算結果が予期したとおりになることを確認しましょう。

なお、今回は整数型しか扱っていないため、割り算の計算結果は小数点以下切り捨てになります。

## 終わりに

今回は処理系が四則演算を扱えるまでに実装を進めることができました。次回以降はエラーメッセージの改善、モジュールの分割等をやっていければと思います。

また、そろそろ Qiita の記事だけでは厳しくなってきたため、GitHub あたりにリポジトリを作ろうかと思っています。

それでは次回をお楽しみに[^next]

*2023-12-31 追記: 次回記事は[こちら](https://qiita.com/_53a/items/bde614986696a9bddd23)です。*

[^next]: あるかなぁ…