手写编译器：从词法到代码生成的技术深度解析

手写编译器（Handwritten Compiler）指不依赖 Lex/Yacc、ANTLR 等生成工具，完全由程序员使用通用编程语言（如 C++、Rust、Go）实现编译器前端（Frontend）乃至后端（Backend）的全过程。其核心价值在于细粒度控制、极致优化、教学研究、DSL 高度定制化。

1. 词法分析（Lexical Analysis）

目标

将字符流（char* 或 std::string_view）转换为标记流（Token Stream），每个 Token 包含：

• 类型（TokenType，如 TK_IDENTIFIER, TK_PLUS, KW_IF）
• 原始文本（std::string_view，避免拷贝）
• 位置信息（Location：行、列、文件 ID）

实现技术：确定性有限自动机（DFA）驱动

enum TokenType {
TK_EOF,
TK_IDENTIFIER,
TK_NUMBER,
TK_PLUS, TK_MINUS, /* … */
KW_IF, KW_WHILE, /* … */
};

struct Token {
TokenType type;
std::string_view text;
Location loc;
};

class Lexer {
const char* input; // 输入指针
const char* ptr; // 当前扫描位置
int line, column;
Token next_token; // 预读 Token（用于 lookahead）
bool has_next;

public:
Lexer(const char* input) : input(input), ptr(input), line(1), column(1), has_next(false) {}

Token next(); // 主接口
Token scan(); // 核心扫描逻辑
void skip_whitespace(); // 跳过空白与注释
};

扫描核心：状态机 + 查表优化

Token Lexer::scan() {
skip_whitespace();
const char* start = ptr;

switch (*ptr) {
case '\\0': return {TK_EOF, "", {line, column}};
case '+': advance(); return {TK_PLUS, "+", loc(start)};
case '-': advance(); return {TK_MINUS, "-", loc(start)};
case '0'...'9': return scan_number(start);
case 'a'...'z':
case 'A'...'Z':
case '_': return scan_identifier(start);
// … 其他字符
default:
error("Unexpected character: ", *ptr);
}
}

关键优化点：

• 零拷贝：使用 std::string_view 指向源码子串，避免频繁 std::string 构造。
• 关键字哈希表：标识符识别后，查静态哈希表判断是否为关键字。static const std::unordered_map<std::string_view, TokenType> keyword_map = {
  {"if", KW_IF}, {"while", KW_WHILE}, /* … */
  };

• DFA 表驱动（高级）：将状态转移编码为二维表，用 state = table[state][char_class] 加速。

2. 语法分析（Syntax Analysis）

主流选择：递归下降解析（Recursive Descent Parsing, RDP）

适用于 LL(k) 文法，手写首选，因其：

• 控制流清晰
• 易于插入语义动作（如 AST 构造）
• 错误恢复灵活

消除左递归（Left Recursion Elimination）

原始表达式文法（左递归）：

Expr → Expr '+' Term | Term

转换为右递归：

Expr → Term Expr'
Expr' → '+' Term Expr' | ε

对应 C++ 实现：

std::unique_ptr<ExprAST> parse_expr() {
auto LHS = parse_term();
return parse_expr_rhs(0, std::move(LHS));
}

std::unique_ptr<ExprAST> parse_expr_rhs(int min_precedence, std::unique_ptr<ExprAST> LHS) {
while (true) {
int tok_prec = get precedence(peek().type);
if (tok_prec < min_precedence) break;

Token op = consume(); // consume '+'/'-'
auto RHS = parse_term();

int next_prec = get_precedence(peek().type);
if (tok_prec < next_prec) {
RHS = parse_expr_rhs(tok_prec + 1, std::move(RHS));
}

LHS = std::make_unique<BinaryExprAST>(std::move(LHS), op, std::move(RHS));
}
return LHS;
}

技巧：使用“优先级驱动解析”（Pratt Parsing）高效处理表达式，时间复杂度 O(n)。

3. 抽象语法树（AST）设计

设计原则

• 不可变性（Immutable）：AST 节点构造后不应修改。
• 多态性：使用虚函数或标签联合（Tagged Union）。
• 位置信息嵌入：每个节点携带 Location 用于错误报告。

struct Location { int line, col; };

class ASTNode {
public:
virtual ~ASTNode() = default;
virtual void accept(ASTVisitor* v) = 0;
Location loc;
};

class ExprAST : public ASTNode { /* … */ };
class BinaryExprAST : public ExprAST {
std::unique_ptr<ExprAST> lhs, rhs;
Token op;
public:
void accept(ASTVisitor* v) override { v->visit(*this); }
};

4. 语义分析（Semantic Analysis）

核心：符号表（Symbol Table）与类型系统

符号表结构：作用域栈（Scope Stack）

struct Symbol {
std::string name;
Type* type;
StorageKind storage; // local, global, param
int offset; // frame offset
};

class Scope {
std::unordered_map<std::string, std::unique_ptr<Symbol>> symbols;
Scope* parent;
public:
void insert(const std::string& name, std::unique_ptr<Symbol> sym);
Symbol* lookup(const std::string& name); // 向上查找
};

class SemanticAnalyzer : public ASTVisitor {
std::stack<std::unique_ptr<Scope>> scope_stack;
Type* current_function_return_type;

public:
void visit(BinaryExprAST& expr) override;
void visit(VarDeclAST& decl) override;
void visit(IdentifierExprAST& id) override;
// …
};

类型检查算法（以 BinaryExpr 为例）

void SemanticAnalyzer::visit(BinaryExprAST& expr) {
expr.lhs->accept(*this);
expr.rhs->accept(*this);

Type* lhs_type = expr.lhs->type;
Type* rhs_type = expr.rhs->type;

if (expr.op.type == TK_PLUS) {
if (lhs_type->is_numeric() && rhs_type->is_numeric()) {
expr.type = unify_numeric(lhs_type, rhs_type); // 类型提升
} else if (lhs_type->is_pointer() && rhs_type->is_integral()) {
expr.type = lhs_type; // 指针算术
} else {
error("Invalid operand types for +", expr.loc);
}
}
// … 其他操作符
}

5. 中间表示（Intermediate Representation, IR）

选择：三地址码（Three-Address Code, TAC）或 SSA 形式

TAC 示例：

// a = b + c * d
t1 = c * d
t2 = b + t1
a = t2

实现 IR 指令：

enum Opcode {
OP_ADD, OP_SUB, OP_MUL, OP_DIV,
OP_LOAD, OP_STORE, OP_CALL,
OP_JMP, OP_JZ, OP_RET
};

struct IRInstruction {
Opcode op;
Operand dest, src1, src2;
std::optional<Label> label;
};

从 AST 生成 TAC（使用 Visitor 模式）

class IRGenerator : public ASTVisitor {
std::vector<std::unique_ptr<IRInstruction>> instructions;
int temp_counter = 0;

Temp new_temp() { return Temp{temp_counter++}; }

Temp visit(BinaryExprAST& expr) override {
Temp lhs = expr.lhs->accept(*this);
Temp rhs = expr.rhs->accept(*this);
Temp result = new_temp();

Opcode op = get_opcode(expr.op.type);
instructions.push_back(std::make_unique<IRInst>(op, result, lhs, rhs));

return result;
}
};

6. 代码生成（Code Generation）

目标：x86-64 汇编（AT&T 语法）

寄存器分配：线性扫描（Linear Scan）或图着色（Graph Coloring）

以线性扫描为例：

指令选择：模式匹配 + 模板

void CodeGenerator::visit(BinaryExprAST& expr) {
Reg lhs = expr.lhs->accept(*this);
Reg rhs = expr.rhs->accept(*this);
Reg result = alloc_reg(); // 分配寄存器

switch (expr.op.type) {
case TK_PLUS:
emit("addq %s, %s", reg_name(rhs), reg_name(result));
break;
case TK_MUL:
emit("imulq %s, %s", reg_name(rhs), reg_name(result));
break;
}
}

调用约定（x86-64 System V ABI）

• 前 6 个整数参数：%rdi, %rsi, %rdx, %rcx, %r8, %r9
• 返回值：%rax
• 被调用者保存：%rbx, %rbp, %r12-%r15

7. 优化技术（手写实现）

常见优化 Pass（遍历 IR 或 AST）

8. 错误处理与诊断

精准错误报告

• 使用 Location 定位源码行。
• 提供上下文（如打印出错行）。
• 支持多错误收集（不因一个错误终止）。

class Diagnostics {
std::vector<Diagnostic> errors;
public:
void error(const std::string& msg, Location loc) {
errors.push_back({ERROR, msg, loc});
print_source_context(loc);
}
};

9. 性能考量

• 内存管理：使用对象池（Object Pool）或 Arena Allocator 减少 new/delete 开销。
• 字符串处理：string_view + 字符串驻留（String Interning）避免重复。
• 缓存友好：IR 指令连续存储，符号表使用哈希表。
• 并行编译：现代编译器支持多文件并行编译（需独立上下文）。

10. 工业级实践参考

• Clang：C++ 前端，手写递归下降解析器 + AST。
• Rustc：使用 librustc_parse 手写 LL(1) 解析器。
• V8 Ignition：JavaScript 字节码生成器手写。
• LuaJIT：高度优化的手写汇编生成。

总结：手写 vs 工具生成

结论：手写编译器是系统编程的“黑带”技能。它要求对形式语言、自动机、数据流分析、目标架构有深刻理解。

建议路径：从实现一个支持 int、+ – * /、if、while、函数调用的子集语言编译器开始，目标输出 x86-64 汇编，逐步加入类型系统、优化与错误恢复。