•2025年09月
compilers

实现 Titania 核心：递归下降解析器、类型推断引擎与 LLVM 后端

基于 Oberon-07 的 Titania 语言核心实现指南，聚焦递归下降解析、类型推断及 LLVM 代码生成的无运行时开销设计。

Titania 是一种受 Niklaus Wirth 设计的 Oberon-07 语言启发的编程语言，旨在作为编译器开发的教学工具。它强调简洁的语法和高效的系统代码生成，没有运行时开销。本文将深入探讨 Titania 核心实现的三个关键组件：递归下降解析器、类型推断引擎以及 LLVM 后端。通过这些组件的构建，我们可以生成高效的机器码，适用于系统编程场景。

递归下降解析器的实现

递归下降解析器是一种自顶向下的解析方法，非常适合 Titania 的简单语法。Titania 的语法定义清晰，包括模块、声明序列、表达式和语句等模块化结构，这使得解析器易于实现。

首先，定义词法分析器（lexer），它将源代码分解为 token 流。Titania 的关键字如 "module"、"proc"、"if" 等，以及操作符如 "+"、":=" 需要被识别。使用有限状态机或正则表达式库（如 Go 的 regexp）来匹配 token。例如，整数常量、标识符和字符串都需要处理。lexer 应返回一个 token 类型、值和位置信息，便于错误报告。

接下来，构建解析器。递归下降的核心是每个非终结符对应一个函数。例如，解析 "module" 声明时，期望看到 "module" 关键字，后跟标识符和分号。然后可选的 import_list 和 decl_sequence。decl_sequence 包括 const_decl、type_decl、var_decl 和 proc_decl。

对于表达式，Titania 支持算术、关系和逻辑操作。实现时，先处理 simple_expr（加减乘除），然后是 relation（如 "="、"<"）。factor 可以是常量、设计符或括号表达式。需要注意运算符优先级，通过递归调用确保 mul_operator 先于 add_operator 执行。

在 proc_decl 中，formal_parameters 需要解析参数列表，包括 fp_section 如 ident_list ":" type。proc_body 递归包含 decl_sequence 和 stmt_sequence。语句如 if_stmt、while_stmt 等，也通过递归函数处理嵌套结构。

为了处理错误，使用 panic 或错误恢复机制。在教学实现中，添加位置信息以输出如 "expected ';' at line 10" 的消息。整个解析器应生成抽象语法树（AST），节点如 ModuleNode、ProcDeclNode、ExprNode 等，便于后续阶段使用。

这种方法的优势在于直观性和易调试性。对于 Titania 的简单语法，解析器代码量不超过 1000 行，且易于扩展如添加 case_stmt 的分支。

类型推断引擎的构建

Titania 作为系统语言，强调类型安全，但为了简洁，支持类型推断。这意味着开发者无需显式指定所有类型，编译器能从上下文推断。

类型推断引擎在语义分析阶段运行，遍历 AST 并为每个节点分配类型。核心是统一查找表（unification），类似于 Hindley-Milner 算法，但简化版适合 Titania 的静态类型系统。

首先，定义类型表示：基本类型如 Integer、Real、Boolean、String；复合类型如 ArrayType(len, elemType)、RecordType(fields)、PointerType(base)、ProcType(params, return)。

在 var_decl 中，如果未指定类型，从初始化 expr 推断：如 "var x := 42" 则 x 为 Integer。使用一个类型变量（type var）表示未知类型，然后通过约束求解。

对于 proc_decl，参数类型从 formal_parameters 显式获取，返回类型从 "return" 语句推断或默认为 Void。调用 proc_call 时，检查参数类型匹配，并推断设计符的类型。

表达式推断是关键。简单_expr 如 "a + b"，需确保 a 和 b 同为 Numeric 类型（Integer 或 Real），结果类型为公共超类型。relation 如 "a = b" 要求 a 和 b 类型兼容，结果为 Boolean。

record_type 支持字段访问 ".field"，推断时检查 qual_ident 的类型是否匹配 RecordType，并返回 field 的类型。pointer_type "^T" 的解引用需类型检查。

实现时，使用一个 TypeChecker 类，维护符号表（scope），每个 scope 有变量映射到类型。进入 proc_body 时推入新 scope，退出时弹出。遇到赋值 "designator := expr"，确保 designator 类型与 expr 兼容，否则报告错误。

对于多态，如泛型数组，Titania 语法中 array_type 有固定长度，但推断 elemType 时可从初始化列表推断。built-in 如 len(x) 返回 Integer，x 须为 array。

潜在挑战是循环依赖，如相互递归 proc 的返回类型。通过多遍遍历或延迟求解解决。Titania 的简单性避免了复杂如 OCaml 的高级推断。

LLVM 后端的集成

为了生成高效系统代码，Titania 使用 LLVM 作为后端。这允许优化到接近 C 的性能，无需运行时库。

首先，安装 LLVM（如通过 llvmlite 或直接 C++ API；在 Go 实现中，可用 llvm-go 绑定）。代码生成阶段遍历 AST，构建 LLVM IR。

Module 顶层对应 LLVM Module。const_decl 生成全局常量，如 "i32 42"。var_decl 生成 alloca（栈分配）或 global（全局变量），初始化用 store。

proc_decl 转换为 Function，参数类型映射到 LLVM 类型（如 i32 为 Integer）。proc_body 中，decl_sequence 先处理本地变量 alloca。stmt_sequence 生成基本块（BasicBlock）。

表达式生成：简单_expr 如加法，用 gep（getelementptr）或 binop 指令。factor 如 integer 直接 const_int。designator 如 qual_ident，用 load 加载值；selector 如 ".field" 用 gep 偏移；"[expr]" 为数组访问，用 gep 计算索引。

控制流：if_stmt 生成 cond br 指令，then/else 分支为新 BasicBlock。while_stmt 用 phi 节点处理循环变量，br 到条件块。for_stmt 类似，"to" 和 "by" 控制步进。

return expr 用 ret 指令，返回类型匹配 FunctionType。built-in 如 new(ptr) 用 malloc 调用，delete 用 free；print 用 printf 等外部链接。

优化阶段，调用 LLVM 的 PassManager，如 -O2 等价，启用内联、死码消除。验证 IR 后，生成对象文件或可执行：target machine 为 x86-64，链接 libc 如果需要 I/O。

无运行时开销的关键：所有内存管理手动（new/delete），无 GC；类型静态，无动态分发。LLVM 确保高效代码，如数组访问用 SIMD 如果适用。

工程化参数与落地清单

实现 Titania 时，建议参数：

  • 解析器：token 缓冲区大小 4096，递归深度限 256 防栈溢出。

  • 类型推断：符号表用 hashmap，类型变量上限 1024；超时 5s 防无限循环。

  • LLVM：IR 验证开启，优化级 -O3 for release；监控 IR 大小 < 1MB。

落地清单：

  1. 克隆 GitHub repo，搭建 lexer/parser 骨架。

  2. 实现 AST 遍历的 type checker。

  3. 集成 LLVM，测试简单 "proc main; begin end" 生成 hello world。

  4. 基准测试：斐波那契递归，比较 LLVM 输出与 GCC C。

  5. 错误处理：位置追踪，友好消息。

通过这些，Titania 不仅是教学工具，还能生成高效系统代码，如嵌入式或内核模块。

（字数约 1050）