Rust + PEG + LLVM で電卓を作る

Last updated at 2020-08-09Posted at 2020-08-09

言語書いてる人すごいな〜かっけな〜って思ったので、ちょっとした処理系を書いてみたくてやってみた。

主にWebやアプリを開発している人がやってみたので、処理系をやったことなくても、読みやすいと思う。

※　ちょっと前に書いたRustのコードなので書き方がふるくなってるかも？？

ソースコード
https://github.com/anharu2394/rust-llvm-calculator

使ったライブラリ

rust-PEG

知識がなくても、とりあえず簡単に構文が作れる。

inkwell

LLVMのラッパー。安全にラップしたらしい。
詳しくないので勧められたから使った。

計算機の処理の流れ

のちに詳しく説明する。

パース(文字列→AST)
↓
ASTをたどってLLVM IRに変換(AST->LLVM IR)
↓
(LLVM IRの関数を)実行する

パース

上の通り、PEGというライブラリに任せている。
下の図のように、文字列からAST（構文木）に変換してくれる。
ASTで、入力されたソースコードの処理の構造を表現している。（なるほどぉ！この木を順番に辿れば計算できるね）

このように構文を宣言し、Node(ASTの列挙体)に変換されるようにする。

calculator.rustpeg

use crate::ast::Node;
use std::str::FromStr;

pub expr -> Node = op / value

pars -> Node = ws<"("> n:expr ws<")"> { n }

whitespace = #quiet<[ \n\t\r]+>

ws<R> = whitespace* R whitespace*

op -> Node = #infix<value> {
#L x "+" y { Node::Add(Box::new(x),Box::new(y)) }
  x "-" y { Node::Sub(Box::new(x),Box::new(y)) }
#L x "*" y { Node::Mul(Box::new(x),Box::new(y)) }
  x "/" y { Node::Div(Box::new(x),Box::new(y))}
}

value -> Node = pars / node_number

integer -> i32 = whitespace* n:$([0-9]+) whitespace* {? i32::from_str(n).map_err(|_| "failed to parse i32") }

node_number -> Node = n:integer { Node::Number(n) }

ast.rs

#[derive(Debug, PartialEq)]
pub enum Node {
    Number(i32),
    Add(Box<Node>, Box<Node>),
    Sub(Box<Node>, Box<Node>),
    Mul(Box<Node>, Box<Node>),
    Div(Box<Node>, Box<Node>),
}

ASTをたどってLLVM IRに変換

LLVM IRはLLVMの中間表現である。LLVMのなかで使われている言語と思っておけばOK。LLVMの恩恵を得られる。（最適化とか？？）
RustもLLVMが使われているのでLLVM IRを経由している！(cargo rustc -- --emit=llvm-irで見れるらしい)

jit_compileでLLVM IRをつくって、compile_astでASTを辿って処理をLLVM IRに追加してる。（なるほどぉ！モジュールやら関数やらを作って、どんどんASTを読んで処理を追加すればいいのか）

compile.rs

use crate::ast::Node;
use crate::error::CreateExecutionEngineError;
use crate::parser;
use failure;
use failure::Error;

use inkwell;
use inkwell::builder::Builder;
use inkwell::context::Context;
use inkwell::execution_engine::JitFunction;
use inkwell::OptimizationLevel;

type SumFunc = unsafe extern "C" fn() -> i32;

pub fn compile_string(source: &str) -> Result<i32, Error> {
    let ast = parser::parse(&source)?;
    jit_compile(ast)
}

pub fn jit_compile(ast: Node) -> Result<i32, Error> {
    let context = Context::create();
    let module = context.create_module("calculator");
    let builder = context.create_builder();
    let execution_engine = module
        .create_jit_execution_engine(OptimizationLevel::None)
        .map_err(|e| CreateExecutionEngineError {
            llvm_message: e.to_string(),
        })?;
    let i32_type = context.i32_type();
    let fn_type = i32_type.fn_type(&[], false);
    let calc = module.add_function("calc", fn_type, None);
    let basic_block = context.append_basic_block(&calc, "entry");
    builder.position_at_end(&basic_block);

    let return_val = compile_ast(ast, &context, &builder);
    builder.build_return(Some(&return_val));
    let calc_fn: JitFunction<SumFunc> = unsafe { execution_engine.get_function("calc") }?;
    Ok(unsafe { calc_fn.call() })
}

pub fn compile_ast(ast: Node, context: &Context, builder: &Builder) -> inkwell::values::IntValue {
    match ast {
        Node::Number(n) => {
            let i32_type = context.i32_type();
            i32_type.const_int(n as u64, false)
        }
        Node::Add(x, y) => {
            let i32_type_x = compile_ast(*x, context, builder);
            let i32_type_y = compile_ast(*y, context, builder);

            let sum = builder.build_int_add(i32_type_x, i32_type_y, "sum");
            sum
        }
        Node::Sub(x, y) => {
            let i32_type_x = compile_ast(*x, context, builder);
            let i32_type_y = compile_ast(*y, context, builder);
            let sum = builder.build_int_sub(i32_type_x, i32_type_y, "sub");
            sum
        }
        Node::Mul(x, y) => {
            let i32_type_x = compile_ast(*x, context, builder);
            let i32_type_y = compile_ast(*y, context, builder);
            let sum = builder.build_int_mul(i32_type_x, i32_type_y, "mul");
            sum
        }
        Node::Div(x, y) => {
            let i32_type_x = compile_ast(*x, context, builder);
            let i32_type_y = compile_ast(*y, context, builder);
            let sum = builder.build_int_unsigned_div(i32_type_x, i32_type_y, "div");
            sum
        }
    }
}

(LLVM IRの関数を)実行する

上のソースコードのcalc_fn.call()でやってる。

#　まとめ
ASTっていうので処理が木になるんだ〜とか、有名な処理系のライブラリなどいろいろ発見があった。

ライブラリがやっているところに目をつぶれば簡単、ライブラリがどうやって動いてるんだろうとかんがえると難しい。

ライブラリが豊富で感謝。