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

本連載のバックナンバー

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

まずは上記バックナンバーを参考に、前回記事のコードが実行できる環境を整えておいてください。

AST

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

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

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

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

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

また、NodeKind の中に、

Paren(Id),
BiOp(BiOpKind, Id, Id),

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

パーサ

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

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

#[cache]
rule _() = quiet!{[' '|'\t'|'\r'|'\n']*{}}

詳細については peg のドキュメントを参照していただきたいのですが、このコードの要点をかいつまむと、

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

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

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

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

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

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

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

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

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 を作成します。

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

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

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

IrGen

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

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

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 を以下のように書き換えます。

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 に対応するコード生成部を追加しています。

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 あたりにリポジトリを作ろうかと思っています。

それでは次回をお楽しみに¹

2023-12-31 追記: 次回記事はこちらです。

あるかなぁ… ↩