トイ言語のコンパイラとかLSPを作りたかった

友人と通話しながらペアプロでLSP実装したいってなってその前にコンパイラ作ろうってなった.

日時

• [[2021-12-27]]
• [[2021-12-28]]
• [[2021-12-29]]

目標

• トイ言語のパーザを書く
• トイ言語のLLVM IRコード生成をする
• 最小限の型を導入する
• LSPを実装する

技術スタック, 実装の流れ

目的としては「言語処理系周辺の技術を試す」なのでコンパイラといってもフロントエンド(LLVM IRへの変換)のみでごく基本的な事しかしません.

• Rust
  • parser combinatorの nom を使う(v7)
  • inkwell でLLVM IR生成
  • (clang で実行ファイルにコンパイル)

Day1 プログラム -> ASTまで

文法

<program> := [ <function_decl> ]
<function_decl> := 'fn (' [<variable_val> ':' <type>,] ') {' <stmts> '}'
<stmts> := <stmt> [ <stmts> ]
<stmt> :
    = <or-expr> ';'
    | <var_decl>
    | <assign>
    | <return>
    | <if_else>
    | <for>

<return> := 'return' <or-expr> ';'
<assign> := <variable_val> '=' <or-expr> ';'
<var_decl>   := 'var' ID ':' <type> (= <or-expr>)? ';'
<if_else> := if '(' <or-expr> ')' '{' <stmts> '}' [ else '{' <stmts> '}' ]
<for> := 'for' '(' <var_decl> <or-expr> ';' <assign> ')' '{' <stmts> '}'

https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm
<or-expr>             := <and-expr> | <or-expr> '||' <and-expr>
<and-expr>            := <equality-expr> | <and-expr> '&&' <equality-expr>
<equality-expr>       := <relational-expr> | <equality-expr> ('==' | '!=') <relational-expr>
<relational-expr>     := <additive-expr> | <relational-expr> ('>' | '<' | '<=' | '>=') <additive-expr>
<additive-expr>       := <multiplicative-expr> | <additive-expr> ('+'|'-') <multiplicative-expr>
<multiplicative-expr> := <factor> | <multiplicative-expr> ('*' | '/' | '%') <factor>

<factor> :
    = <const_num_val> 
    | <paren_expr> 
    | <call>
    | <variable_val> 
<paren_expr> := '(' <or-expr> ')'
<const_num_val> := 0 | [1-9][0-9]*
<const_bool_val> := 'true' | 'false'
<call> = ID '(' <expr>* ')'
<variable_val> := ID
<type> := unit | int32 | int64 | uint32 | uint64 | bool | String

ID := [a-zA-Z][a-zA-Z0-9]* 

AST(型なし)

パーズされたプログラムはASTになって欲しいです. なのでまずはASTを表す構造体を作ります. 以下にASTノードの一覧を書きます. 構造体メンバの意味は察してください.

• 定数 Const= I32Const(i32) | I64Const(i64) | BoolConst(bool)
• 二項演算 BinOp { left: Expr, op: Op, right: Expr }
• 変数 Variable { id: String }
• 関数呼び出し Call { id: String, args: Vec<Expr> }
• 式 Expr = Const | Variable | BinOp | Call
• 変数宣言 VariableDecl { id: String, init: Option<Expr> }
• for文 For { var_decl: VariableDecl, cond: Expr, assign: Assign, stmts: Stmts }
• 代入 Assign { left: String, right: Expr }
• if文 IfElse { cond: Expr, success: Stmts, failure: Option<Stmts> }
• 文 Stmt = Expr | Return(Expr) | VariableDecl | IfElse | For
• 文の集まり Stmts(Vec<Stmt>)
• 関数宣言 FunctionDecl { id: String, args: Vec<Variable>, stmts: Stmts }
• プログラム全体 Program(Vec<FunctionDecl>)

ipulang/nodes.rs at a49d28bdd9d4fcdaaf95a23f3300991acf721e5f · i-pu/ipulang · GitHub に載ってます.

nom でパーズする

色々な先人の方がとてもわかりやすい記事 ¹ を書いてくださっているので, 詳細は別記事に譲りますが, nom はRust製のパーサコンビネータの一つで, 小さなパーサを組み合わせて対象をパーズする関数を作ります.
パーザ関数は fn parser(input: I) -> nom::IResult<I, O> のようになっていて, 返り値の Result::Ok は (I, O) は (残り, パース結果) を意味しています. 今回の場合は入力がプログラム文字列なので I = &str, 出力がASTノードなので O = <何かのASTノード> となります.

nom が用意しているパーザの中でよく使うのが

• 予約語にマッチ: bytes::complete::tag(value)
• 括弧の中を取り出す時: sequence::delimited(first, sep, second) -> <sepの結果>
  • ex. delimited(tag("("), tag("abc"), tag(")"))("(abc)def") == ("def", "abc")
• パーズ結果をタプルで受け取る: sequence::tuple((parsers...))
• multi::many1: 1回以上の繰り返し
• branch::alt: どれか
• combinator::opt: あってもなくても良い

等です. 詳細は nom - Rust で見れます.

二項演算のパーズ

注意点として, パーザはマッチした瞬間に消費されるので演算子の優先順位を考慮したパーズを行う場合は演算優先度が低いものからパーズをするように作る必要があります. 今回の例では式のパーザは

1. or_expr_parser は <and-expr> (|| <or-expr>)? にマッチ
2. and_expr_parserは <eq-expr> (&& <and-expr>)? にマッチ
3. eq_expr_parser は <rel-expr> ([==, !=] <eq-expr>)? にマッチ
4. relational_expr_parser は <add-expr> ([>=, <=, >, <] <rel-expr>)? にマッチ
5. additive_expr_parser は <mult-expr> ([+, -] <add-expr>)? にマッチ(乗算の方が優先度が高い)
6. multiplicative_expr_parser は <factor> ([*, /, %] <mult-expr>)? にマッチ

のようにパーザを分ける必要があります.

if文のパーザ

実用例として, if文のパーザを示します. 途中にスペースが含まれるのを許すとパーザが多少大変になる.

pub fn if_else_parser(s: &str) -> IResult<&str, IfElse> {
    map(
        tuple((
            tag("if"),
            multispace0,
            // cond
            delimited(
                char('('),
                delimited(multispace0, or_expr_parser, multispace0),
                char(')'),
            ),
            // success
            delimited(
                multispace0,
                delimited(char('{'), stmts_parser, char('}')),
                multispace0,
            ),
            opt(tag("else")),
            // failure
            opt(delimited(
                multispace0,
                delimited(char('{'), stmts_parser, char('}')),
                multispace0,
            )),
        )),
        |(_, _, cond, sucess, _, failure)| IfElse::new(cond, sucess, failure),
    )(s)
}

各ASTノードに対応するパーザを作り, 最後にそれらを組み合わせればプログラム全体のパーザの完成です.
プログラム全体のパーザが入力文字列を全て消費することが出来れば, 妥当なプログラム文字列であると言えます.

pub fn program_parser(s: &str) -> Program {
    let (ss, ast) = many1(delimited(multispace0, function_decl_parser, multispace0))(s).unwrap();
    assert_eq!(ss, "", "program parser must consume all string");
    Program::new(ast)
}

¹ 例えば, Rust製のパーサコンビネータnom v6.0.0を解剖する · drumato.com](https://www.drumato.com/ja/posts/dive-into-nom-internals/)

参考文献

• Rust製のパーサコンビネータnom v6.0.0を解剖する · drumato.com
• nom::bytes::complete - Rust

AST -> LLVM IR, 型チェック

inkwell クレート

Cargo.toml

[dependencies]
inkwell = { git = "https://github.com/TheDan64/inkwell", branch = "master", features = ["llvm12-0"] }

LLVM IR

LLVM IR は Module > Function > Block > Instruction の構造になっていて, inkwell では Builder のメソッドを呼ぶことで手続き的にLLVM IRを生成していきます.

以下に

i32 main() {
    var a: i32 = 3;
    var b: i32 = 5;
    return a + b;
}

のコード生成のコードイメージは

let context = Context::create();
 
// module
let module = context.create_module("main");
// builder
let builder = context.create_builder();

// i32
let i32_type = context.i32_type();

// main: () -> i32
let main_fn_type = i32_type.fn_type(&[i32_type.into()], false);
let main_fn = module.add_function("main", main_fn_type, None);

// block
let basic_block = context.append_basic_block(main_fn, "entry");
builder.position_at_end(basic_block);

// a = 3, b = 5
let a = builder.build_alloca(context.i32_type(), "a");
let b = builder.build_alloca(context.i32_type(), "b");
let three = i32_type.const_int(3, false);
let five = i32_type.const_int(5, false);
builder.build_store(a, three);
builder.build_store(b, five);

// load a, b
let bload = builder.build_load(b, "bload");
let aload = builder.build_load(a, "aload");

// add a, b
let c = builder.build_int_add(aload.into_int_value(), bload.into_int_value(), "c");

builder.build_return(Some(&c));

のようになります(参照: ipulang/inkwell-alloca.rs at a49d28bdd9d4fcdaaf95a23f3300991acf721e5f · i-pu/ipulang · GitHub).

朝起きた時点で, LLVM IR何も知りませんでしたが, 簡単な Cコードから clang を使ってLLVMが見られるので参考にしながら進めましょう.

clang -S -emit-llvm test.c
cat test.ll

ASTを走査する

環境

ipulang/codegen.rs at 2aa0cf801213b4be194e0ef10a2e5a67579adb0d · i-pu/ipulang · GitHub ASTを走査してコード生成をしている途中で関数や変数等を記録しておくための構造体です.

/// コード生成時のための情報
struct Env<'ctx> {
    module: Module<'ctx>,
    ctx: &'ctx Context,
    /// function id -> variable id -> PointerValue
    /// 宣言されている変数一覧
    variables: HashMap<String, HashMap<String, PointerValue<'ctx>>>,
    /// compilerが作った一時変数の個数
    var_count: Rc<Cell<usize>>,
    /// 宣言されている関数一覧
    functions: HashMap<String, FunctionValue<'ctx>>,
    /// 現在の builder
    builder: Builder<'ctx>,
    /// 現在のfunction id
    function: String,
    /// 現在の FunctionValue
    function_value: Option<FunctionValue<'ctx>>,
}

組み込み関数

LLVM IR内では putchar, getchar などの関数は宣言さえされていれば使うことが出来ます( #todo なぜ?).
ので環境生成時に組み込み関数として関数テーブルに追加しておきます. ipulang/codegen.rs at 2aa0cf801213b4be194e0ef10a2e5a67579adb0d · i-pu/ipulang · GitHub

let mut functions = HashMap::new();

// decrare putchar(i32): i32
let i32_type = ctx.i32_type();
let putchar_type = i32_type.fn_type(&[i32_type.into()], false);
let putchar_val = module.add_function("putchar", putchar_type, None);
functions.insert("putchar".to_owned(), putchar_val);

// decrate getchar(): i32
let getchar_type = i32_type.fn_type(&[], false);
let getchar_val = module.add_function("getchar", getchar_type, None);
functions.insert("getchar".to_owned(), getchar_val);

コード生成エントリ関数

ASTのrootである Program の gen_code(&mut env) を呼ぶと子ノードの gen_code(&mut env) が次々と呼ばれ, 最後に module.print_to_string() することでLLVM IRが生成されます.

pub fn code_gen(ast: Program) -> Result<String, Box<Error>> {
    let context = Context::create();
    let mut env = Env::new(&context);
    // 再帰的にコード生成が行われる
    ast.gen_code(&mut env);
    Ok(env.module.print_to_string().to_string())
}

各ASTノードに gen_code() を実装していきます.

impl Const {
    fn gen_code<'ctx>(self, env: &Env<'ctx>) -> IntValue<'ctx>
}

impl BinOp {
    fn gen_code<'ctx>(self, env: &mut Env<'ctx>) -> PointerValue<'ctx>
}

impl VariableDecl {
    fn gen_code<'ctx>(self, env: &mut Env<'ctx>)
}

impl Variable {
    fn gen_code<'a>(self, env: &Env<'a>) -> PointerValue<'a>
}

impl Expr {
    fn gen_code<'ctx>(self, env: &mut Env<'ctx>) -> Option<PointerValue<'ctx>>
}

impl Call {
    fn gen_code<'a>(self, env: &mut Env<'a>) -> CallSiteValue<'a>
}

impl IfElse {
    fn gen_code<'a>(self, env: &mut Env<'a>)
}

impl Assign {
    fn gen_code<'ctx>(self, env: &mut Env<'ctx>)
}

impl For {
    fn gen_code<'ctx>(self, env: &mut Env<'ctx>)
}

impl Stmt {
    fn gen_code<'a>(self, env: &mut Env<'a>)
}

impl FunctionDecl {
    fn gen_code(self, env: &mut Env)
}

impl Program {
    fn gen_code<'a>(self, env: &mut Env<'a>)
}

上位のノードが生成されたコードの情報を使うかによって返り値が異なっています, ここらへんは時間がない中考えたJust Ideaなのでより良い方法があると思います.

後日談

trait にしました ipulang/mod.rs at 03ce758bf398d9ea8ad1fac319a377f7e5477d2f · i-pu/ipulang · GitHub.

trait CodeGen<'ll, T: 'll + AnyValue<'ll>> {
    fn code_gen(self, env: &mut Env<'ll>) -> Option<T>;
}

コード生成

やっていることは大体 元コード を見て頂ければわかると思うので, いくつか掻い摘んで紹介します.

関数宣言

1. 関数の型を宣言

   • <返り値の型>.fn_type(<引数の型...>, <可変長引数か>)
     • IntType in inkwell::types - Rust

   let i32_type = env.ctx.i32_type();
   let fn_type = i32_type.fn_type(&vec![i32_type.into(); self.args.len()], false);
   let fn_value = env.module.add_function(&self.id, fn_type, None);
   

2. 環境に関数の情報を追加, module に関数を追加

   // 現在の関数の情報を設定
   env.function_value = Some(fn_value.clone());
   if !env.functions.insert(self.id.clone()) {
       panic!("function {} is already decleared", &self.id);
   }
   // 変数マップを作る
   env.variables.entry(self.id.clone()).or_default();
   env.function = self.id.clone();
   

3. entry ラベルを作成, 引数をload

   // block
   let basic_block = env.ctx.append_basic_block(fn_value, "entry");
   env.builder.position_at_end(basic_block);
   
   // 引数を使う時
   for (i, arg) in self.args.iter().enumerate() {
       let param = fn_value.get_nth_param(i as u32).unwrap().into_int_value();
       // 引数名に対応するptrを作成
       let ptr_param = env.int_to_point(param, Some(arg));
       env.set_variable(arg.clone(), ptr_param);
   }
   

4. 中身のコード生成, 返り値のコード生成(値を返さなくても 0 を返す)

   #todo void 値を扱う方法はあるのか

   // returnがないときも0をかえすようにしている
   let zero = i32_type.const_int(0, false);
   env.builder.build_return(Some(&zero));
   

for文

以下のようなコードが生成されて欲しいです.

//   <decl>
//   jmp cond
// cond:
//   <cond>
//   jmp <do> or <dest>
// do:
//   <stmts>
//   jmp update
// update:
//   <update>
//   jmp <cond>
// dest:

あとはそれをそのまま Inkwell のコードで行うだけです, ブロックのコード生成をする前に builder::position_at_end(block) し忘れに注意しましょう.

let cond_label = env.get_tmp_label_id();
let fn_value = env.function_value.clone().unwrap();
let cond_block = env.ctx.append_basic_block(fn_value, &cond_label);

let do_label = env.get_tmp_label_id();
let do_block = env.ctx.append_basic_block(fn_value, &do_label);
let update_id = env.get_tmp_label_id();
let update_block = env.ctx.append_basic_block(fn_value, &update_id);
let dest_id = env.get_tmp_label_id();
let dest_block = env.ctx.append_basic_block(fn_value, &dest_id);

self.var_decl.gen_code(env);
env.builder.build_unconditional_branch(cond_block);

// generate cond
env.builder.position_at_end(cond_block);
let ptr = self.cond.gen_code(env);
let var_id = env.get_tmp_var_id();
let res = env.builder.build_load(ptr, &var_id).into_int_value();
// cond != 0
let zero = res.get_type().const_int(0, false);
let var_id = env.get_tmp_var_id();
let cond = env
		.builder
		.build_int_compare(inkwell::IntPredicate::NE, res, zero, &var_id);

// jmp do: if cond else dest:
env.builder
		.build_conditional_branch(cond, do_block, dest_block);

// generate do
env.builder.position_at_end(do_block);
self.stmts.gen_code(env);

// jmp update:
env.builder.build_unconditional_branch(update_block);

// generate update
env.builder.position_at_end(update_block);
self.assign.gen_code(env);
env.builder.build_unconditional_branch(cond_block);

// jmp dest:
env.builder.position_at_end(dest_block);

fizzbuzz

ここまででfizzbuzzを動かすのに最低限のコード生成が出来るようになります.

fn fizz() {
    putchar(102);
    putchar(105);
    putchar(122);
    putchar(122);
}

fn buzz() {
    putchar(98);
    putchar(117);
    putchar(122);
    putchar(122);
}

fn judge(i) {
    if (i % 3 == 0) {
        fizz();
        putchar(10);
    }
    else {
        if (i % 5 == 0) {
            buzz();
            putchar(10);
        } else {
            if (i % 15 == 0) {
                fizz();
                buzz();
                putchar(10);
            } else {
                putchar(i + 48);
                putchar(10);
            }
        }
    }
}

fn main() {
    for (var i: i32; i < 30; i = i + 1;) {
        judge(i); 
    }
}

参考文献

• inkwell - Rust

Day3: 型チェック

最小限の型を導入する

自作プログラミング言語処理系といえば型推論などが大きなマイルストーンとしてあるかと思われますが, その布石としてごく簡単なプリミティブ型を導入して, ASTを生成した後に簡単な型チェッカーを作ります. 例えば2項演算子の右辺と左辺の型が違っていたらエラーを出すといった程度のものです.

• TODO

Day4: LSP実装

• TODO

• tower-lsp

• nom_locate

• Semantic Tokens