張大胖很幸運(yùn)，剛畢業(yè)就進(jìn)入了一家芯片設(shè)計公司。

不過，工作了一個月以后，他就覺得不對勁了。

原因很簡單，對于公司開發(fā)的最新芯片，主流的編程語言還不支持呢！

無論是驗證特性，還是編寫測試，都不得不用最最古老的形式：匯編!

張大胖決心改變這種狀況，他找到了梁經(jīng)理，說出了自己的想法。

確實是這樣，操作系統(tǒng)、圖形學(xué)，編譯器號稱程序員的三大浪漫，但每一項真做起來都讓人頭大。

張大胖當(dāng)年的畢業(yè)設(shè)計，一個極其簡單的編譯器，就讓他做了8個月！

不過，梁經(jīng)理似乎發(fā)現(xiàn)了一個“秘密武器”。

MoonBit是一門國產(chǎn)開源編程語言，由 Rescript 作者張宏波（現(xiàn)居深圳）及其團(tuán)隊打造，它的一些優(yōu)秀特性，非常適合用來開發(fā)編譯器和新編程語言。

張大胖非常高興，決定利用之前畢業(yè)設(shè)計的經(jīng)驗，用MoonBit做個實驗，設(shè)計并實現(xiàn)一個新的編程語言！

為了記錄自己的工作，他用日記的形式記錄下了每天的進(jìn)展：

———日記開始———

第一天：語言設(shè)計與詞法分析

晚上下班，照常來說，我會打開原神欣賞一下提瓦特的風(fēng)景。不過今天要用MoonBit實現(xiàn)新編程語言了，游戲就先放到一邊吧。

1、語言設(shè)計

我打算設(shè)計的這門語言叫 TinyMoonBit。它得有常見的數(shù)值類型、分支循環(huán)、函數(shù)、內(nèi)存管理和 CFFI。語法上，我決定讓它看起來像 MoonBit，但內(nèi)核更像 C。

同時，為了體現(xiàn)“現(xiàn)代”語言的優(yōu)越性，我給它設(shè)計了更嚴(yán)格的類型系統(tǒng)，比如 1 + 1.0 這種在 C 語言里司空見慣的隱式類型轉(zhuǎn)換，在 TinyMoonBit 里是不允許的。

我隨手寫下了一個 TinyMoonBit 的示例程序，用來計算斐波那契數(shù)列：

extern fn print_int(x : Int) -> Unit;
// 遞歸實現(xiàn)斐波那契數(shù)列
fn fib(n : Int) -> Int {
  if n <= 1 { return n; }
  return fib(n - 1) + fib(n - 2);
}
fn main() -> Unit {
  print_int(fib(10));
}

2、詞法分析

第一步是詞法分析。通俗地說，就是把一長串代碼文本，切分成一個個有意義的“單詞”，我們稱之為 Token。比如 let x = 5;，處理后應(yīng)該變成一個 Token 序列：Keyword("let") -> Identifier("x") -> Operator("=") -> IntLiteral(5) -> Symbol(";")。

在 MoonBit 里，這件事出奇的簡單。首先，用一個代數(shù)數(shù)據(jù)類型（ADT）來定義所有可能的 Token：

pub enum Token {
  Bool(Bool)       // 布爾值：true, false
  Int(Int)         // 整數(shù)
  Keyword(String)  // 關(guān)鍵字：let, if, fn
  Upper(String)    // 類型標(biāo)識符：Int, Bool
  Lower(String)    // 變量標(biāo)識符：x, n
  Symbol(String)   // 運(yùn)算符：+, -, ->
  Bracket(Char)    // 括號：(, ), {, }
  EOF              // 文件結(jié)束標(biāo)記
} derive(Show, Eq)

然后，借助 MoonBit 的一大殺器——字符串模式匹配，我們可以像寫詩一樣實現(xiàn)詞法分析器：

pub fn lex(code: String) -> Array[Token] {
  let tokens = Array::new()
  loop code[:] {
    // 跳過空白字符
    [' ' | '\n' | '\r' | '\t', ..rest] => 
      continue rest
    // 處理單行注釋
    [.."http://", ..rest] =>
      continue loop rest {
        ['\n', ..rest] => break rest
        [_, ..rest] => continue rest
        [] => break ""
      }
    
    // 識別多字符運(yùn)算符 (順序很重要！)
    [.."->", ..rest] => { tokens.push(Symbol("->")); continue rest }
    [.."<=", ..rest] => { tokens.push(Symbol("<=")); continue rest }
    
    // 識別單字符運(yùn)算符
    [':' |1 ';' | '+' | '-' | '*' | '/' | '<' | '=' as c, ..rest] => {
      tokens.push(Symbol("\{c}")); continue rest
    }
    
    // 識別標(biāo)識符和關(guān)鍵字
    ['a'..='z', ..] as code => {
      let (tok, rest) = lex_ident(code) // lex_ident 會區(qū)分關(guān)鍵字和普通變量
      tokens.push(tok)
      continue rest
    }
    // ... 其他匹配，如數(shù)字、大寫字母開頭的類型等 ...
    
    [] => { tokens.push(EOF); break tokens }
  }
}

MoonBit 特性解讀

函數(shù)式循環(huán) (loop)：它不是簡單的重復(fù)，而是一個不斷用新狀態(tài)（rest）迭代自身的遞歸過程，非常適合處理“吃掉”一部分字符串，然后處理剩余部分的場景。

強(qiáng)大的模式匹配：[.."->", ..rest] 這樣的語法，可以直觀地匹配字符串前綴，比晦澀的正則表達(dá)式清晰百倍。

只花了大半個小時，詞法分析器就寫完并測試通過了。我暗自竊喜，這要是用別的語言，光是處理各種邊界情況就得焦頭爛額。MoonBit 的 ADT 和模式匹配，寫起來真是既優(yōu)雅又高效。

第二天：語法分析與類型檢查

有了昨晚的順利開局，我信心更足了。我趁著午休和晚上的時間，開始攻克編譯器的第二個難關(guān)。

1、語法分析：從扁平到立體

詞法分析產(chǎn)生的是一維的 Token 序列，而程序本身是有層次結(jié)構(gòu)的。語法分析的任務(wù)，就是將這個扁平的序列，組織成一棵能夠反映代碼結(jié)構(gòu)的抽象語法樹（AST）。

首先，我定義了 AST 的節(jié)點。這就像為程序搭建骨架，每一塊骨骼都代表一種語法結(jié)構(gòu)：

// 表達(dá)式的定義
pub enum Expr {
  AtomExpr(AtomExpr, mut ty~ : Type?)          // 原子表達(dá)式 (變量、字面量等)
  Unary(String, Expr, mut ty~ : Type?)         // 一元運(yùn)算：-, !
  Binary(String, Expr, Expr, mut ty~ : Type?)  // 二元運(yùn)算：+, -, *, /
} derive(Show, Eq, ToJson)
// 語句的定義
pub enum Stmt {
  Let(String, Type, Expr)      // 變量聲明：let x : Int = 5;
  If(Expr, Array[Stmt], Array[Stmt])           // 條件分支
  While(Expr, Array[Stmt])     // 循環(huán)
  Return(Expr?)                // 返回
  // ... 其他語句 ...
} derive(Show, Eq, ToJson)
// 函數(shù)和程序的頂層結(jié)構(gòu)
pub struct Function {
  name : String
  params : Array[(String, Type)]
  ret_ty : Type
  body : Array[Stmt]
} derive(Show, Eq, ToJson)
pub type Program Map[String, Function]

設(shè)計巧思：注意到每個表達(dá)式節(jié)點都有一個 mut ty~ : Type? 字段嗎？這是一個可變的可選類型字段。這樣，我就可以在后續(xù)的類型檢查階段，直接把推斷出的類型信息“填”進(jìn)去，而無需重新構(gòu)建一棵新樹，非常巧妙。

有了骨架，接下來就是用 遞歸下降 的方法來填充它。簡單來說，就是為每一種語法結(jié)構(gòu)（如函數(shù)、語句、表達(dá)式）編寫一個解析函數(shù)。在 MoonBit 中，這又成了模式匹配的絕佳舞臺：

pub fn parse_function(tokens : ArrayView[Token]) -> (Function, ArrayView[Token]) raise {
  // Function一定由fn關(guān)鍵字，Lower，左括號開頭
  guard tokens is [Keyword("fn"), Lower(fname), Bracket('('), .. rest_tokens]
  let params : Array[(String, Type)] = Array::new()
  let (tokens, ret_ty) = loop rest_tokens {
    // 參數(shù)格式：param_name : Type
    [Lower(param_name), Symbol(":"), Upper(type_name), .. rest] => {
      params.push((param_name, parse_type(type_name)))
      continue rest
    }
    [Symbol(","), .. rest] => continue rest
    [Bracket(')'), Symbol("->"), Upper(ret_ty), .. rest] => 
      break (rest, parse_type(ret_ty))
  }
  // ... 解析函數(shù)體
}

整個過程就像剝洋蔥，parse_program 調(diào)用 parse_function，parse_function 調(diào)用 parse_stmt，parse_stmt 調(diào)用 parse_expr，層層遞進(jìn)，直到把所有 Token 都消耗完畢。

MoonBit 高級特性應(yīng)用

derive(Show, Eq, ToJson)：這個小小的注解威力巨大。Show 讓我能輕松打印 AST 用于調(diào)試，Eq 用于測試，而 ToJson 能一鍵將 AST 序列化為 JSON，方便檢查其結(jié)構(gòu)。

raise 錯誤處理：通過在函數(shù)簽名中標(biāo)記 raise，我可以優(yōu)雅地向上拋出解析錯誤，而不用到處傳遞錯誤碼。

2、類型檢查：確保語義正確

在代碼生成之前，通常需要實現(xiàn)一個類型檢查階段。一些語句雖然符合語法，但可能不符合語義，例如我有一個foo函數(shù)，然后又有了1+foo這樣的代碼，但這是語義不正確的，因為一個整數(shù)無法與一個函數(shù)相加。

我設(shè)計了一個環(huán)境鏈來處理作用域：

pub struct TypeEnv[K, V] {
  parent : TypeEnv[K, V]?
  data : Map[K, V]
}
pub fn TypeEnv::get[K : Eq + Hash, V](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
    }
  }
}

類型檢查器會自頂向下掃描每個表達(dá)式，填充類型信息并驗證類型一致性：

pub fn Expr::check_type(self : Self, env : TypeEnv[String, Type]) -> Type raise {
  match self {
    Binary("+", lhs, rhs, ..) as node => {
      let lhs_type = lhs.check_type(env)
      let rhs_type = rhs.check_type(env)
      guard lhs_type == rhs_type else {
        raise TypeCheckError("類型不匹配")
      }
      node.ty = Some(lhs_type)
      lhs_type
    }
    // ... 其他表達(dá)式類型
  }
}

語法分析消耗的時間比預(yù)想的多一些，尤其是在處理運(yùn)算符優(yōu)先級時頗費(fèi)腦筋。但在 MoonBit 強(qiáng)大的模式匹配和 AI 助手的幫助下，我還是在深夜前完成了這項工作。萬里長征，只剩下最后一步——代碼生成了。

第三天：代碼生成，最后的難關(guān)

MoonBit本身語言特性適合編譯器實現(xiàn)之外，也有一個超級好用的LLVM綁定，叫做llvm.mbt。

1、LLVM：現(xiàn)代編譯器的基石

LLVM作為現(xiàn)代編譯器基礎(chǔ)設(shè)施的集大成者，為我們提供了一個強(qiáng)大而靈活的解決方案。通過將程序轉(zhuǎn)換為LLVM中間表示（IR），我們可以利用LLVM成熟的工具鏈將代碼編譯到多種目標(biāo)架構(gòu)。

我們先來試用LLVM的經(jīng)典起手三段式：

pub fn initialize_llvm() -> (Context, Module, Builder) {
  let ctx = @IR.Context::new()          // LLVM上下文
  let mod = ctx.addModule("demo")       // 模塊容器
  let builder = ctx.createBuilder()     // IR構(gòu)建器
  (context, module, builder)
}

有了這三樣法寶，我們就能像搭積木一樣，一條條地構(gòu)建出程序的 LLVM IR。比如生成一個計算 a*b+c 的函數(shù)：

pub fn generate_muladd_function() -> String {
  let (ctx, mod, builder) = initialize_llvm()
  // 定義函數(shù)簽名：i32 muladd(i32, i32, i32)
  let i32_ty = ctx.getInt32Ty()
  let func_type = ctx.getFunctionType(i32_ty, [i32_ty, i32_ty, i32_ty])
  let func_value = mod.addFunction(func_type, "muladd")
  // 創(chuàng)建函數(shù)入口基本塊
  let entry_block = func_value.addBasicBlock(name="entry")
  builder.setInsertPoint(entry_block)
  // 獲取函數(shù)參數(shù)并生成計算指令
  let arg_a = func_value.getArg(0).unwrap()
  let arg_b = func_value.getArg(1).unwrap()
  let arg_c = func_value.getArg(2).unwrap()
  let mul_result = builder.createMul(arg_a, arg_b)
  let add_result = builder.createAdd(mul_result, arg_c)
  let _ = builder.createRet(add_result)
  mod.dump()
}

這會生成非常清晰的 LLVM IR：

define i32 @muladd(i32 %a, i32 %b, i32 %c) {
entry:
  %mul_res = mul i32 %a, %b
  %add_res = add i32 %mul_res, %c
  ret i32 %add_res
}

看起來很簡單，對吧？但真正的挑戰(zhàn)在于，如何將我們前一天生成的、復(fù)雜的 AST，系統(tǒng)性地翻譯成這一條條的 LLVM 指令。

2、類型系統(tǒng)的映射

在LLVM中，類型系統(tǒng)相當(dāng)復(fù)雜。llvm.mbt使用Trait Object的概念，&Type可以表示任意LLVM類型。我需要建立TinyMoonBit類型與LLVM類型的映射：

pub fn CodeGen::convert_type(self : Self, parser_type : Type) -> &@llvm.Type {
  match parser_type {
    Type::Unit => self.ctx.getVoidTy() as &@llvm.Type
    Type::Bool => self.ctx.getInt1Ty()
    Type::Int => self.ctx.getInt32Ty()  
    Type::Double => self.ctx.getDoubleTy()
  }
}

然后就是真正的代碼生成。我需要為 AST 中的每一種節(jié)點編寫一個 emit 方法。其中最有趣也最關(guān)鍵的，是如何處理變量和分支：

3、變量處理：SSA與可變性的橋梁

TinyMoonBit支持變量的重新賦值，但LLVM IR采用SSA（Static Single Assignment）形式，每個變量只能賦值一次。我需要采用alloca + load/store模式來處理可變變量：

// 變量聲明：let x : Int = 5;
Let(var_name, var_type, init_expr) => {
  let llvm_type = self.convert_type(var_type)
  let alloca = self.builder.createAlloca(llvm_type, name=var_name)
  env.symbols.set(var_name, alloca)
  let init_value = init_expr.emit(env)
  let _ = self.builder.createStore(alloca, init_value)
}
// 變量賦值：x = 10;
Assign(var_name, rhs_expr) => {
  let var_ptr = env.get_symbol(var_name).unwrap()
  let rhs_value = rhs_expr.emit(env)
  let _ = self.builder.createStore(var_ptr, rhs_value)
}

4、控制流：基本塊的藝術(shù)

控制流是程序邏輯的骨架。在LLVM IR中，控制流通過基本塊和分支指令來實現(xiàn)。每個基本塊代表一個沒有內(nèi)部跳轉(zhuǎn)的指令序列：

// if-else語句的實現(xiàn)
If(cond, then_stmts, else_stmts) => {
  let cond_val = cond.emit(env)
  // 創(chuàng)建三個基本塊
  let then_block = func.addBasicBlock(name="if.then")
  let else_block = func.addBasicBlock(name="if.else") 
  let merge_block = func.addBasicBlock(name="if.end")
  // 條件分支
  let _ = builder.createCondBr(cond_val, then_block, else_block)
  // 生成then分支
  builder.setInsertPoint(then_block)
  then_stmts.each(s => s.emit(env))
  let _ = builder.createBr(merge_block)
  // 生成else分支  
  builder.setInsertPoint(else_block)
  else_stmts.each(s => s.emit(env))
  let _ = builder.createBr(merge_block)
  // 繼續(xù)在merge塊生成后續(xù)代碼
  builder.setInsertPoint(merge_block)
}

5、完整的代碼生成

經(jīng)過詞法分析、語法分析、類型檢查和代碼生成四個階段，我們的編譯器已經(jīng)能夠?qū)inyMoonBit源代碼轉(zhuǎn)換為完整的LLVM IR。

對于我們的斐波那契例子：

fn fib(n : Int) -> Int {
  if n <= 1 { return n; }
  return fib(n - 1) + fib(n - 2);
}

最終生成的LLVM IR：

define i32 @fib(i32 %0) {
entry:
  %1 = alloca i32, align 4
  store i32 %0, ptr %1, align 4
  %2 = load i32, ptr %1, align 4
  %3 = icmp sle i32 %2, 1
  br i1 %3, label %4, label %6
4:                                                
  %5 = load i32, ptr %1, align 4
  ret i32 %5
6:                                                
  %7 = load i32, ptr %1, align 4
  %8 = sub i32 %7, 1
  %9 = call i32 @fib(i32 %8)
  %10 = load i32, ptr %1, align 4
  %11 = sub i32 %10, 2
  %12 = call i32 @fib(i32 %11)
  %13 = add i32 %9, %12
  ret i32 %13
}

使用LLC工具鏈，我們可以進(jìn)一步將LLVM IR編譯成RISC-V匯編代碼，完成整個編譯過程。

攻克了這些核心難點后，剩下的工作就是水到渠成了。周三深夜，當(dāng)我看到 fib(10) 的代碼成功生成了復(fù)雜的 LLVM IR ，并順利通過llc鏈接編譯成可執(zhí)行程序并且運(yùn)行通過時，我知道，我成功了！

———日記結(jié)束———

總結(jié)

周四的午休時刻，張大胖向同事們展示了自己三天時間編寫的TinyMoonBit編譯器。

確實，MoonBit的模式匹配讓詞法分析變得異常簡單，遞歸下降語法分析也很直觀。

最關(guān)鍵的是llvm.mbt這個綁定庫，讓代碼生成變得容易很多。

有了MoonBit以后，開發(fā)新語言就不那么難了，也許你也可以再把編譯原理撿起來，用MoonBit完成自己的年輕時的夢想：實現(xiàn)一個自己的編程語言！

資源推薦

對這個項目感興趣的讀者，可以從以下鏈接獲取更多信息：

TinyMoonBit 完整項目 :

https://github.com/Kaida-Amethyst/TinyMoonbitLLVM

MoonBit 官方文檔 :

https://www.moonbitlang.com/docs/

llvm.mbt 文檔 :

https://mooncakes.io/docs/Kaida-Amethyst/llvm

LLVM 官方教程 :

https://www.llvm.org/docs/tutorial/