第 2 章 编译器的结构 - 学习笔记

本文为《Learn LLVM 17》第 2 章的学习笔记，主要介绍编译器前端的构建块，并通过 calc 算术表达式语言实现一个完整的编译器前端。

1. 编译器的构建块

编译器通常分为三个部分：

LLVM 的优势：LLVM 核心库提供了中端和后端，我们只需专注于前端开发。

前端的处理流程

1

源代码 → 词法分析器 → 标记流 → 解析器 → AST → 语义分析器 → IR

1. 词法分析器：将源代码分解为标记 (Token)，如数字、标识符、操作符
2. 解析器：分析标记的句法结构，生成抽象语法树 (AST)
3. 语义分析器：检查语言规则（如变量声明、类型兼容性）
4. 代码生成：将 AST 转换为 LLVM IR

2. 算术表达式语言 calc

2.1 示例

1

with a, b: a * (4 + b)

• 变量用 with 声明
• 程序会询问变量值并输出计算结果

2.2 EBNF 语法

1
2
3
4
5
6

calc   : ("with" ident ("," ident)* ":")? expr ;
expr   : term (("+" | "-") term)* ;
term   : factor (("*" | "/") factor)* ;
factor : ident | number | "(" expr ")" ;
ident  : ([a-zA-Z])+ ;
number : ([0-9])+ ;

语法对编译器作者的意义：

• 定义所有标记 → 指导词法分析器实现
• 语法规则 → 可转化为解析器
• 作为正确性的衡量标准

3. 词法分析 (Lexer)

3.1 核心组件

• Token：唯一编号 + 文本内容
• Lexer：将文本输入转换为 Token 序列

3.2 关键实现要点

LLVM 工具类：

• llvm::MemoryBuffer：只读内存块，末尾有 \0
• llvm::StringRef：封装指针+长度，无需 \0 结尾

字符分类：不使用 <cctype>，原因：

1. 受 locale 影响（如德语变音符）
2. char → int 转换有移植性问题

Token 类型：eoi, unknown, ident, number, comma, colon, plus, minus, star, slash, l_paren, r_paren, KW_with

关键字识别：标识符正则也匹配关键字，先收集字符再判断是否为 with

4. 语法分析 (Parser)

4.1 递归下降解析器

• 每个非终结符对应一个解析方法
• 可选组 (…)? → if 判断
• 重复组 (…)* → while 循环
• 选择 | → switch 或 if-else

4.2 错误处理：恐慌模式

• 丢弃标记直到找到可继续的符号
• 对每个非终结符定义后继标记集
• 简单但有效：开发者修复第一条错误后重新编译

4.3 LL(1) 语法

递归下降解析器要求语法满足 LL(1) 条件，大多数网上语法不满足。经典参考：《编译原理》（龙书）。

5. 抽象语法树 (AST)

5.1 设计原则

• 去除对语义无意义的符号（如 with、,、:）
• 只保留：变量列表、表达式结构、操作符

5.2 AST 类层次

1
2
3
4
5

AST (根)
├── Expr (表达式根)
│   ├── Factor (数字/标识符)
│   └── BinaryOp (二元运算)
└── WithDecl (变量声明 + 表达式)

5.3 访问者模式

• ASTVisitor：定义 visit() 接口
• 各 AST 节点实现 accept(Visitor) 调用对应 visit
• 便于语义分析和代码生成时遍历树

6. 语义分析 (Sema)

6.1 检查内容

• 变量在使用前必须声明
• 变量不能重复声明

6.2 实现思路

• 使用 llvm::StringSet<> 存储已声明变量
• WithDecl：将变量加入集合，检查重复
• Factor(Ident)：检查变量是否在集合中
• BinaryOp：递归检查左右子树

7. 代码生成 (CodeGen)

7.1 LLVM IR 文本表示

库函数声明：

1
2

declare i32 @calc_read(ptr)
declare void @calc_write(i32)

字符串常量：

1

@a.str = private constant [2 x i8] c"a\00"

main 函数结构：

1
2
3
4
5
6
7

define i32 @main(i32, ptr) {
entry:
  %2 = call i32 @calc_read(ptr @a.str)
  %3 = mul nsw i32 3, %2
  call void @calc_write(i32 %3)
  ret i32 0
}

注意：LLVM 16+ 默认使用不透明指针 ptr，不再使用 i8* 等类型化指针。

7.2 ToIRVisitor 实现要点

• IRBuilder<>：构建 IR 指令
• StringMap<Value*>：变量名 → calc_read 返回值
• WithDecl：为每个变量创建字符串常量，调用 calc_read，存入 map
• Factor：Ident 查 map，Number 转 ConstantInt
• BinaryOp：CreateNSWAdd/Sub/Mul、CreateSDiv

8. 驱动与运行时

8.1 Calc 驱动程序流程

1
2
3
4
5
6
7

main()
  → InitLLVM, ParseCommandLineOptions
  → Lexer → Parser → AST
  → 语法错误? → 退出
  → Sema.semantic()
  → 语义错误? → 退出
  → CodeGen.compile() → 输出 IR

8.2 运行时库 (rtcalc.c)

• calc_write(int)：printf 输出结果
• calc_read(char*)：fgets + sscanf 读取整数，非法输入则 exit(1)

9. 构建与测试

9.1 CMake 配置

• find_package(LLVM REQUIRED CONFIG)
• llvm_map_components_to_libnames(llvm_libs Core)
• 源文件：Calc.cpp, CodeGen.cpp, Lexer.cpp, Parser.cpp, Sema.cpp

9.2 完整编译流程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# 配置与构建
cmake -GNinja -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++ \
  -DLLVM_DIR=<path> ../
ninja

# 生成目标文件并链接
calc "with a: a*3" | llc -filetype=obj -relocation-model=pic -o=expr.o
clang -o expr expr.o rtcalc.c

# 运行
./expr
# Enter a value for a: 4
# The result is: 12

10. 总结

本章通过 calc 算术表达式语言，完整实现了编译器前端的四个阶段：

1. 词法分析：手写 Lexer，Token 枚举 + StringRef
2. 语法分析：递归下降 Parser，恐慌模式错误恢复
3. 语义分析：访问者模式 + StringSet 作用域检查
4. 代码生成：ToIRVisitor 生成 LLVM IR，配合 llc 生成机器码

关键收获：

• 语法 (EBNF) 直接指导词法/语法分析实现
• 访问者模式统一 AST 遍历逻辑
• LLVM 提供 IR 接口，只需实现前端即可利用其优化与后端