编程语言设计与编译器实现历来被视为计算机科学领域的一个复杂而深奥的主题。传统上，学生需要在学校里学习复杂的自动机理论，类型理论，计算机底层等才能尝试开发一个自己的编程语言和编译器。Moonbit作为一门现代函数式语言，不仅拥有严谨的类型系统和出色的安全保障，更配备了专为AI时代设计的工具链，为开发者提供了丰富的语法特性，各种特性使得Moonbit成为一个特别适合用于开发编译器的语言。
本文将通过构建一个名为TinyMoonbit的小型语言的编译器，深入探讨编译器实现的核心概念。本文将简单设计编译器开发的四个阶段，词法分析，语法分析，语义分析与类型检查，以及代码生成。
关于本文的代码：由于篇幅所限，本文所展示的代码不是很全，读者可以参考
https://github.com/Kaida-Amethyst/TinyMoonbit，这个仓库实现了比本文稍微复杂一点的TinyMoonbit。
在开始构建编译器之前，我们首先要设计一门我们将要实现的语言。我们将其命名为TinyMoonbit，它是Moonbit的一个极简化版本，旨在帮助我们专注于编译器构建的核心概念。
TinyMoonbit语言具有以下特征：
-
类型系统
TinyMoonbit采用静态类型系统，支持三种基本数据类型：
Int、Bool和Double。此外，语言还支持函数的声明和调用。 -
变量声明与初始化
TinyMoonbit使用
let关键字进行变量声明，语法形式为let 变量名 : 类型名 = 表达式 ;let x : Int = 1 ; let y : Double = 1.0; let b : Bool = true;
ℹ️ 设计简化: 为了简化解析器的实现，TinyMoonbit要求在变量声明时显式指定类型，这与原版Moonbit的类型推导机制有所不同。
-
赋值操作
与原版Moonbit需要
mut关键字不同，TinyMoonbit中所有通过let声明的变量都具有可变性，可以进行重新赋值，前提是类型保持一致。let x : Int = 1; x = 3;
-
表达式计算
TinyMoonbit支持常见的算术和逻辑运算符，包括加减乘除、比较运算等。
let x : Int = 1 + 2; let y : Double = 1.0 * 3.0; let b : Bool = 1 > 2;
⚠️ 注意: 二元运算符要求左右操作数类型严格一致，即1 + 1.0这样的混合类型表达式是不被允许的。 -
控制流结构
TinyMoonbit支持条件分支和循环结构。与原版Moonbit不同的是，这里的
if和while被设计为语句而非表达式。let x : Int = 0; while x < 5 { print_int(x); print_endln(); x = x + 1; }
-
函数定义
函数定义采用
fn关键字，支持参数和返回值的类型标注。特别地，main函数遵循与Moonbit相同的约定（无参数，无返回值）。fn fib(n: Int) -> Int { if n <= 2 { return 1; } return fib(n-1) + fib(n-2); } fn main { let n : Int = 5; let res : Int = fib(n); print_int(res); print_endln(); }
词法分析（Lexical Analysis）是编译过程的第一个阶段。这个阶段的核心任务是将输入的字符序列转换为一个有意义的符号序列，这些符号被称为词法单元（Tokens）。
例如，对于代码片段 let x : Int = 5;，经过词法分析后，将产生以下Token序列：
(Keyword "let") (Identifier "x") (Symbol ":") (Type "Int") (Symbol "=") (IntLiteral 5) (Symbol ";")
这种转换看似简单，但实际上需要处理诸如空白符过滤、关键字识别、数值解析等多种情况。传统的编译器教学往往从有限状态自动机的理论开始，但Moonbit的强大模式匹配能力为我们提供了一种更直观的实现方法。
根据TinyMoonbit的语法规范，我们首先将所有可能出现的符号分类为以下几种Token类型：
pub enum Token {
Bool(Bool) // 布尔字面量：true, false
Int(Int) // 整数字面量：1, 2, 3, ...
Double(Double) // 浮点数字面量：1.0, 2.5, 3.14, ...
Keyword(String) // 关键字：let, if, while, fn, return
Upper(String) // 类型标识符：以大写字母开头的字符串，如 Int, Double, Bool
Lower(String) // 变量标识符：以小写字母开头的字符串，如 x, y, result
Symbol(String) // 运算符和标点符号：+, -, *, :, ;, ->
Bracket(Char) // 括号类符号：(, ), [, ], {, }
EOF // 文件结束标记
} derive(Show, Eq)有了Token的定义，我们就可以利用Moonbit的字符串模式匹配功能来编写词法分析器了。这是一种优雅而直观的实现方法，我们可以利用函数式编程中的loop结构，结合模式匹配来处理字符串：
pub fn lex(code: String) -> Array[Token] {
let tokens = Array::new()
loop code[:] {
// 跳过空白字符
[' ' | '\n' | '\r' | '\t', .. rest] => continue rest
// 识别关键字
[.."let", ..rest] => { tokens.push(Keyword("let")); continue rest }
[.."if", ..rest] => { tokens.push(Keyword("if")); continue rest }
// ... 其他关键字和符号 ...
[.."return", ..rest] => { tokens.push(Keyword("return")); continue rest }
// 识别多字符运算符
[.."->", ..rest] => { tokens.push(Symbol("->")); continue rest }
[.."==", ..rest] => { tokens.push(Symbol("==")); continue rest }
// ... 其他多字符运算符 ...
// 识别单字符运算符和标点符号
[':' | '.' | ',' | ';' | '+' | '-' | '*' |
'/' | '%' | '>' | '<' | '=' as c, .. rest] => {
tokens.push(Symbol("\{c}"));
continue rest
}
// 识别括号
['(' | ')' | '[' | ']' | '{' | '}' as c, .. rest] => {
tokens.push(Bracket(c));
continue rest
}
// 识别标识符和数值
['a'..='z' as c, ..] as code => { /* ... */ }
['A'..='Z' as c, ..] as code => { /* ... */ }
['0'..='9', ..] as code => { /* ... */ }
// ...
}
tokens.push(EOF)
tokens
}上述 lex 函数完美地展示了Moonbit在编译器开发中的几个优秀语法：
-
函数式循环 (****
loop) :loop不是传统意义上的循环结构，而是一种函数式的递归抽象。它接受一个初始参数（这里是code[:]），在循环体内进行模式匹配，continue后跟的表达式会成为下一次迭代的参数。这种设计使得状态的传递变得明确而安全。 -
字符串模式匹配: Moonbit的字符串模式匹配功能极大简化了词法分析的实现。模式
['a', ..]匹配以字符'a'开头的字符串，而[.."hello", ..rest]则是一个语法糖，等价于['h', 'e', 'l', 'l', 'o', ..rest]。 -
匹配优先级的重要性:
⚠️ 重要提示: 模式匹配的顺序 在编写模式匹配规则时，顺序至关重要。例如，多字符运算符（如->）必须在单字符运算符（如-和>）之前匹配，否则->将被错误地解析为两个独立的符号。// 错误的顺序示例："->"将永远无法被匹配 loop code[:] { ['-' | '>' as c, ..rest] => { ... } [.."->", ..rest] => { ... } // 永远不会执行 // ... }
语法分析（Syntactic Analysis）是编译器的第二个主要阶段，其任务是将词法分析产生的Token序列组织成具有层次结构的抽象语法树（Abstract Syntax Tree, AST）。这个过程不仅要验证程序是否符合语言的语法规则，更要为后续的语义分析和代码生成提供结构化的数据表示。
在解析Token流之前，我们需要定义好AST的结构。这包括语言的类型以及各种表达式和语句的节点。
首先，我们定义TinyMoonbit的类型系统在AST中的表示。
pub enum Type {
Unit // 单位类型，用于无返回值的函数
Bool // 布尔类型
Int // 整数类型
Double // 双精度浮点数类型
} derive(Show, Eq)
pub fn Type::parse(master : String) -> Type {
// ...
}我们将AST节点分为多个层次，以清晰地表示程序的结构。
-
原子表达式 (AtomExpr) : 代表不可再分解的基本表达式单元。
pub enum AtomExpr { Bool(Bool) // 布尔字面量 Int(Int) // 整数字面量 Double(Double) // 浮点数字面量 Var(String, mut ty~ : Type?) // 变量引用 Paren(Expr, mut ty~ : Type?) // 括号表达式 Call(String, Array[Expr], mut ty~ : Type?) // 函数调用 } derive(Show, Eq)
-
复合表达式 (Expr) : 可以包含运算符和多个子表达式。
pub enum Expr { Atom(AtomExpr, mut ty~ : Type?) // 原子表达式 Unary(String, Expr, mut ty~ : Type?) // 一元表达式 Binary(String, Expr, Expr, mut ty~ : Type?) // 二元表达式 } derive(Show, Eq)
-
语句 (Stmt) : 代表程序中的可执行单元。
pub enum Stmt { Let(String, Type, Expr) // 变量声明 Assign(String, Expr) // 赋值语句 If(Expr, Array[Stmt], Array[Stmt]) // 条件分支 While(Expr, Array[Stmt]) // 循环语句 Return(Expr?) // 返回语句 } derive(Show, Eq)
-
顶层结构: 函数和整个程序。
pub struct Function { name : String // 函数名 params : Array[(String, Type)] // 参数列表 ret_ty : Type // 返回类型 body : Array[Stmt] // 函数体 } derive(Show, Eq) pub type Program = Map[String, Function] // 程序是函数的集合
递归下降（Recursive Descent）是一种自顶向下的语法分析方法。在Moonbit中，我们可以利用模式匹配来优雅地实现这种算法。
pub fn AtomExpr::parse(
tokens : ArrayView[Token]
) -> (AtomExpr, ArrayView[Token]) {
match tokens {
// 解析布尔、整数、浮点数字面量
[Bool(b), .. rest] => (Bool(b), rest)
[Int(i), .. rest] => (Int(i), rest)
[Double(d), .. rest] => (Double(d), rest)
// 解析函数调用
[Lower(func_name), Bracket('('), .. rest] => { /* ... */ }
// 解析变量引用
[Lower(var_name), .. rest] => (Var(var_name, ty=None), rest)
// 解析括号表达式
[Bracket('('), .. rest] => { /* ... */ }
_ => { /* 错误处理 */ }
}
}语句解析需要处理多种不同的语句类型：
pub fn Stmt::parse(tokens : ArrayView[Token]) -> (Stmt, ArrayView[Token]) {
match tokens {
// 解析let语句
[Keyword("let"), Lower(var_name), Symbol(":"), ..] => { /* ... */ }
// 解析if/while/return语句
[Keyword("if"), .. rest] => Stmt::parse_if(rest)
[Keyword("while"), .. rest] => Stmt::parse_while(rest)
[Keyword("return"), .. rest] => { /* ... */ }
// 解析赋值语句
[Lower(_), .. rest] => Stmt::parse_assign(tokens)
_ => { /* 错误处理 */ }
}
}难点：处理运算符优先级：
表达式解析中最复杂的部分是处理运算符优先级，我们需要确保
1 + 2 * 3被正确解析为1 + (2 * 3)而不是(1 + 2) * 3。
语义分析是编译器设计中承上启下的关键阶段。在语法分析完成后，我们得到了结构正确的抽象语法树，但这并不意味着程序在语义上是正确的。类型检查作为语义分析的核心组成部分，负责验证程序中所有操作的类型一致性。
类型检查的一个核心挑战是处理变量的作用域（Scope）。我们可以采用环境链的（Environment Chain）设计：
pub struct Env[K, V] {
parent : Env[K, V]? // 指向父环境的引用
data : Map[K, V] // 当前环境的绑定
}我们将环境变量设定为符号和类型的映射，当我们遇到一个变量时，我们首先从当前环境中查找这个变量的类型，如果找不到，就递归的从环境的上一级环境（parent）中继续查找。如果都没有找到，就返回None，否则就返回找到的类型。
pub fn[K : Eq + Hash, V] Env::get(self : Self[K, V], key : K) -> V? {
match self.data.get(key) {
Some(value) => Some(value)
None =>
match self.parent {
Some(parent_env) => parent_env.get(key)
None => None
}
}
}仅仅有一个环境还不够，有些指令需要知道整个程序的信息，譬如Call指令，它必须要从程序中获取函数的信息，因此我们需要一个类型检查器。
类型检查器需要维护当前的环境状态，并遍历AST来检查每个节点的类型。
pub struct TypeChecker {
local_env : Env[String, Type] // 本地变量环境
current_func : Function // 当前正在检查的函数
program : Program // 完整的程序信息
}
pub fn TypeChecker::check_program(program : Program) -> Unit {
// 对程序中的每个函数进行类型检查
for func_entry in program {
// ...
}
}类型检查器会递归地遍历AST，对每种语句和表达式应用其特定的检查规则。
- 变量声明 (
Let) : 检查初始化表达式的类型是否与声明的类型匹配。 - 赋值 (
Assign) : 检查赋值表达式的类型是否与变量的原有类型匹配。 - 条件 (
If/While) : 检查条件表达式的类型是否为Bool。 - 返回 (
Return) : 检查返回表达式的类型是否与函数的返回类型匹配。 - 二元运算 (
Binary) : 检查左右操作数类型是否一致，并根据运算符推导结果类型。 - 函数调用 (
Call) : 检查实参的数量和类型是否与函数定义匹配。
下面是 check_statement 的一个片段，展示了其工作原理：
pub fn TypeChecker::check_statement(self : Self, stmt : Stmt) -> Unit {
match stmt {
// 变量声明语句
Let(var_name, declared_type, expr) => {
let expr_type = self.check_expression(expr)
if expr_type != declared_type {
// 抛出类型错误
}
self.local_env.set(var_name, declared_type)
}
// 赋值语句
Assign(var_name, expr) => {
// ...
}
// 条件分支语句
If(condition, then_block, else_block) => {
// ...
}
// ... 其他语句
}
}代码生成实际上是一个复杂的问题，为了简便起见，我们选择生成llvm代码，并借助llvm的工具链将代码进一步转化为原生机器码。这里moonbitlang官方实现了一个llvm的moonbit binding：https://github.com/moonbitlang/llvm.mbt，我们可以利用这个工具。
基本的原理与我们做类型检查时非常类似，使用一个环境来保存变量和对应的Value，然后遍历语法树，最终生成代码。
priv struct Env {
gen: CodeGen
parser_func: @parser.Function
llvm_func: @llvm.FunctionValue
parent: Env?
symbols: Map[String, &@llvm.Value]
}
pub struct CodeGen {
parser_prog: @parser.Program
llvm_ctx: @llvm.Context
llvm_prog: @llvm.Module
builder: @llvm.Builder
}篇幅所限，这里展示一部分代码：
fn Env::runOnStmt(self: Self, stmt: @parser.Stmt) -> Unit raise Error {
match stmt {
Let(name, ty, expr) => {
let data_ty = self.gen.convert_parser_type_to_llvm_type(ty);
let alloca = self.gen.builder.build_alloca(data_ty); // create an alloca inst
self.symbols.set(name, alloca); // set a varibale in Env
let value = self.runOnExpr(expr); // emit IRs for expr
let _ = self.gen.builder.build_store(value, alloca); // store value to the allocated address.
}
Assign(var_name, expr) => {
let ptr = self.get_symbol(var_name).or_else(() => {...});
let value = self.runOnExpr(expr);
let _ = self.gen.builder.build_store(value, ptr);
}
// ... other cases
}
}
fn Env::runOnExpr(self: Self, expr: @parser.Expr) -> &Value raise {
match expr {
AtomExpr(a, ..) => self.runOnAtomExpr(a)
Binary("+", lhs, rhs, ty=Some(Int)) => {
let lhs_val = self.runOnExpr(lhs);
let rhs_val = self.runOnExpr(rhs);
self.gen.builder.build_int_add(lhs_val, rhs_val)
}
Binary("-", lhs, rhs, ty=Some(Int)) => {
let lhs_val = self.runOnExpr(lhs);
let rhs_val = self.runOnExpr(rhs);
self.gen.builder.build_int_sub(lhs_val, rhs_val)
}
// ... other cases
}
}
完整代码请参考：TinyMoonbit
通过TinyMoonbit的实现过程，我们可以深刻体会到Moonbit在编译器开发中的独特优势：
- 模式匹配的表达力：无论是字符串的词法分析还是AST的语法分析，模式匹配都提供了简洁而强大的表达方式
- 类型系统的安全性：强类型系统在编译时就能捕获许多潜在错误，提高了编译器本身的可靠性
- 函数式编程范式：不可变数据结构和纯函数设计使得代码更易于理解和维护
- 现代语言特性：泛型、特质、派生等特性减少了样板代码，提高了开发效率
通过TinyMoonbit的实现过程，我们可以深刻体会到Moonbit语言在解决复杂系统设计问题时的优雅与强大。这只是编译器世界的第一步，前方还有广阔的探索空间。希望本文对读者在学习Moonbit或者编译器构建等问题上有所启发。
