从零手搓C++子集编译器：LL(1)文法实战与避坑指南

1. 从零手搓一个C++子集编译器：LL(1)文法到底能走多远

编译原理这门课，很多人学完的感觉就是“听懂了，但让我写一个编译器，我连从哪下手都不知道”。词法分析、语法分析、语义分析、中间代码生成、目标代码生成——每个阶段单拎出来都能讲一章，但真要把它们串起来跑通，中间隔着的不是一层窗户纸，而是一堵墙。我当初做这个实验的时候，前前后后折腾了将近两周，踩过的坑比预想的多得多。这篇文章就把整个实验的完整思路、关键实现细节、以及那些只有真正动手写过才会遇到的问题，全部摊开来讲一遍。

这个项目的核心目标很明确：用LL(1)文法设计并实现一个能编译C++语言子集的简单编译器。所谓“子集”，意味着我们不需要支持C++的全部特性——模板、多继承、异常处理这些统统不要，但基本的变量声明、赋值、算术运算、条件判断、循环、函数定义和调用，这些得能跑通。最终产物是一个能把源代码翻译成某种可执行形式（比如四元式中间代码，或者简单的汇编指令）的完整程序。

适合谁来参考？如果你正在上编译原理课，被实验作业卡住了；或者你自学编译原理，想找一个不太复杂但足够完整的项目练手；又或者你单纯好奇“编译器到底是怎么把一行代码变成机器能跑的东西”——那这篇内容应该能帮到你。我会尽量把每个设计决策背后的“为什么”讲清楚，而不是只丢一堆代码让你自己悟。

2. 整体架构设计与LL(1)的选型逻辑

2.1 为什么选LL(1)而不是LR系列

做编译器实验，第一个要做的决策就是语法分析用什么方法。常见的选择有递归下降、LL(1)、LR(1)、LALR等。LL(1)不是最强的，但它是最适合教学和快速原型开发的。

原因有三。第一，LL(1)的分析逻辑非常直观：从左到右扫描输入，每次只看一个token就能决定用哪条产生式，分析栈的操作就是“弹出栈顶非终结符，压入对应产生式右部”这么简单。第二，LL(1)的预测分析表可以手工构造，也可以程序自动生成，这个过程能让你真正理解FIRST集、FOLLOW集、SELECT集是怎么算出来的。第三，LL(1)对文法的限制虽然严格（不能有左递归、不能有公共左因子），但C++子集的语法经过适当改写后完全可以满足这些条件。

LR系列当然更强，能处理的文法范围更广，但它的分析表构造复杂得多，状态机动辄几百个状态，调试起来非常痛苦。对于一个教学实验来说，LL(1)的复杂度刚刚好——足够让你理解编译器的核心原理，又不至于陷在状态机的泥潭里出不来。

2.2 编译器的整体流水线

整个编译器我分成了五个阶段，每个阶段是一个独立的模块，通过明确定义的数据结构串联起来：

• 词法分析器（Lexer）：读入源代码字符流，输出Token序列。每个Token包含类型（关键字、标识符、常量、运算符等）和值。
• 语法分析器（Parser）：基于LL(1)预测分析表，读入Token序列，构建语法分析树或直接进行语法制导翻译。
• 符号表管理（Symbol Table）：记录变量、函数的名字、类型、作用域等信息，供语义分析和代码生成使用。
• 语义分析（Semantic Analyzer）：检查类型匹配、变量是否声明、函数调用参数是否匹配等。
• 中间代码生成（IR Generator）：将语法树翻译成四元式形式的中间代码。

这五个阶段的数据流向是单向的，每个阶段的输出是下一个阶段的输入。这种模块化设计的好处是，任何一个阶段出问题，你可以单独调试它，而不用把整个编译器跑一遍才能定位错误。

2.3 目标语言子集的界定

“C++子集”这个范围必须提前划定清楚，否则你会陷入“要不要支持指针”“要不要支持类”这种无休止的纠结中。我最终确定的子集包含以下特性：

这个子集虽然小，但已经足够写一些有实际意义的程序了，比如计算斐波那契数列、求最大公约数、简单的数学计算器等。

3. 词法分析器的实现细节与踩坑记录

3.1 Token的定义与分类

词法分析器的核心任务是把字符流切分成有意义的Token。我定义的Token类型包括以下几类：

enum TokenType { KEYWORD, // int, float, if, else, while, return 等 IDENTIFIER, // 变量名、函数名 NUMBER, // 整数和浮点数常量 OPERATOR, // +, -, *, /, %, <, >, ==, !=, = 等 DELIMITER, // ( ) { } ; , END_OF_FILE // 文件结束标记 };

每个Token用一个结构体表示，包含类型、原始字符串值和行号（行号用于报错时定位）：

struct Token { TokenType type; std::string value; int line; };

这里有个细节值得注意：行号信息一定要在词法分析阶段就记录下来。我一开始偷懒没加行号，结果后面语法分析报错的时候只能说“语法错误”，完全不知道错在哪一行，调试效率极低。后来加上行号之后，报错信息变成“第12行：期望 ‘;’ 但遇到 ‘}'”，定位问题快了很多。

3.2 手写词法分析器的状态机逻辑

词法分析器本质上是一个有限状态自动机。我用一个大的while循环逐字符扫描，根据当前字符决定进入哪个分支：

std::vector<Token> tokenize(const std::string& source) { std::vector<Token> tokens; int pos = 0; int line = 1; while (pos < source.size()) { char c = source[pos]; // 跳过空白字符 if (isspace(c)) { if (c == '\n') line++; pos++; continue; } // 跳过注释 if (c == '/' && pos + 1 < source.size() && source[pos+1] == '/') { while (pos < source.size() && source[pos] != '\n') pos++; continue; } // 识别标识符和关键字 if (isalpha(c) || c == '_') { std::string ident; while (pos < source.size() && (isalnum(source[pos]) || source[pos] == '_')) { ident += source[pos++]; } if (keywords.count(ident)) { tokens.push_back({KEYWORD, ident, line}); } else { tokens.push_back({IDENTIFIER, ident, line}); } continue; } // 识别数字 if (isdigit(c)) { std::string num; bool isFloat = false; while (pos < source.size() && (isdigit(source[pos]) || source[pos] == '.')) { if (source[pos] == '.') isFloat = true; num += source[pos++]; } tokens.push_back({NUMBER, num, line}); continue; } // 识别运算符和分隔符 // ... 省略具体分支 pos++; } tokens.push_back({END_OF_FILE, "", line}); return tokens; }

3.3 那些容易忽略的边界情况

第一个坑：多字符运算符的识别。==和=是两个不同的Token，!=和!也是。如果你先匹配单字符运算符，就会把==错误地切成两个=。我的处理方式是优先尝试匹配双字符运算符，匹配失败再回退到单字符。

第二个坑：浮点数的识别。3.14是一个浮点数，但3.和.14呢？我选择只支持标准形式的浮点数（小数点前后都必须有数字），遇到3.这种就报词法错误。这样虽然限制了一些写法，但避免了歧义。

第三个坑：注释的处理。行注释//要一直跳到行尾，块注释/* */要跨行匹配。块注释如果没闭合，要报错提示“未终止的注释”。

实操心得：词法分析器写完之后，一定要单独测试。构造一组包含各种边界情况的测试用例——空文件、只有注释的文件、超长标识符、非法字符等——确保每个分支都能正确处理。不要等到整个编译器跑起来才发现词法分析有问题，那时候定位错误会非常困难。

4. LL(1)文法改造与预测分析表构造

4.1 消除左递归：从表达式文法说起

C++的表达式文法天然是左递归的，比如：

Expr -> Expr + Term | Term

这个文法直接拿来做LL(1)分析是不行的，因为LL(1)要求每次只看一个Token就能决定用哪条产生式，而左递归会导致分析器无限循环。所以第一步是消除左递归，改写成右递归形式：

Expr -> Term Expr' Expr' -> + Term Expr' | - Term Expr' | ε Term -> Factor Term' Term' -> * Factor Term' | / Factor Term' | ε Factor -> ( Expr ) | id | num

改写之后，每个非终结符的产生式右部要么以终结符开头，要么以唯一的非终结符开头，满足了LL(1)的基本要求。

4.2 FIRST集和FOLLOW集的计算

FIRST集和FOLLOW集是构造预测分析表的基础。我写了一个程序来自动计算这两个集合，核心逻辑是不断迭代直到集合不再变化。

FIRST集的计算规则：

• 如果X是终结符，FIRST(X) = {X}
• 如果X -> ε 是产生式，把ε加入FIRST(X)
• 如果X -> Y1Y2...Yk，把FIRST(Y1)中除ε外的元素加入FIRST(X)；如果Y1能推导出ε，继续看Y2，以此类推

FOLLOW集的计算规则：

• 把$（结束符）加入FOLLOW(开始符号)
• 如果A -> αBβ，把FIRST(β)中除ε外的元素加入FOLLOW(B)
• 如果A -> αB 或 A -> αBβ且β能推导出ε，把FOLLOW(A)加入FOLLOW(B)

这两个集合的计算程序大概各50行代码，但一定要仔细验证结果。我当初因为一个产生式写错了，导致FOLLOW集算出来少了一个元素，后面预测分析表就出现了空白项，语法分析器遇到某些输入直接崩溃。

4.3 预测分析表的构造与冲突处理

预测分析表的行是非终结符，列是终结符，单元格填的是产生式编号。构造规则很简单：

• 对每条产生式 A -> α，计算SELECT(A -> α)
• 如果α不能推导出ε，SELECT = FIRST(α)
• 如果α能推导出ε，SELECT = (FIRST(α) - {ε}) ∪ FOLLOW(A)
• 把SELECT集中的每个终结符对应的单元格填入这条产生式

如果某个单元格被填入了多条产生式，说明存在冲突，这个文法不是LL(1)的。我在构造过程中遇到了两处冲突：

冲突一：if-else的悬挂问题。经典的悬空else问题，if (a) if (b) s1; else s2;中的else到底匹配哪个if。解决办法是改写文法，用“匹配的if”和“不匹配的if”来区分：

Stmt -> MatchedStmt | UnmatchedStmt MatchedStmt -> if ( Expr ) MatchedStmt else MatchedStmt | OtherStmt UnmatchedStmt -> if ( Expr ) Stmt | if ( Expr ) MatchedStmt else UnmatchedStmt

冲突二：变量声明和函数定义的区分。int a;是变量声明，int f() {...}是函数定义，两者都以int开头。解决办法是提取公共左因子，把int后面的部分做成一个单独的非终结符，根据下一个Token是标识符还是左括号来决定走哪条路。

注意事项：LL(1)文法的改写是一个反复迭代的过程。你可能会改了好几轮才发现某个冲突无法消除，这时候要么继续改写文法，要么承认这个文法不是LL(1)的，换用其他分析方法。我的经验是，C++子集的语法经过仔细改写后是可以做到LL(1)的，但需要耐心。

5. 语法分析器的核心实现与语法制导翻译

5.1 预测分析器的工作流程

LL(1)预测分析器本质上是一个下推自动机，它维护一个分析栈和一个输入指针。工作流程如下：

1. 初始化：分析栈压入开始符号和结束符$，输入指针指向第一个Token
2. 取栈顶符号X和当前输入Token a
3. 如果X是终结符且X == a，弹出栈顶，输入指针后移
4. 如果X是非终结符，查预测分析表M[X, a]，把对应产生式的右部逆序压入栈
5. 如果X == $且a == $，分析成功
6. 否则报语法错误

这个流程用代码实现大概30行：

void parse(std::vector<Token>& tokens) { std::stack<std::string> stk; stk.push("$"); stk.push("Program"); int pos = 0; while (!stk.empty()) { std::string top = stk.top(); Token cur = tokens[pos]; if (isTerminal(top)) { if (top == cur.value || (top == "id" && cur.type == IDENTIFIER) || (top == "num" && cur.type == NUMBER)) { stk.pop(); pos++; } else { error("第" + std::to_string(cur.line) + "行：期望 '" + top + "' 但遇到 '" + cur.value + "'"); } } else { std::string prod = table[top][cur.value]; if (prod.empty()) { error("第" + std::to_string(cur.line) + "行：无法匹配 '" + cur.value + "'"); } stk.pop(); // 逆序压栈 std::vector<std::string> symbols = split(prod); for (int i = symbols.size() - 1; i >= 0; i--) { if (symbols[i] != "ε") stk.push(symbols[i]); } } } }

5.2 语法制导翻译：从分析到生成中间代码

光做语法分析还不够，我们的目标是生成代码。所以需要在分析过程中嵌入语义动作。LL(1)的语法制导翻译有两种实现方式：

方式一：在递归下降分析器中嵌入语义动作。如果你用递归下降来实现LL(1)分析（本质上和预测分析器等价），可以在每个函数返回的时候执行语义动作，比如生成四元式。

方式二：先构建语法树，再遍历语法树生成代码。这种方式更清晰，但需要额外的树结构。

我选择了方式一，因为递归下降的代码结构更直观，语义动作可以直接写在函数里。比如解析表达式的函数：

std::string parseExpr() { std::string left = parseTerm(); while (currentToken is '+' or '-') { std::string op = currentToken.value; advance(); std::string right = parseTerm(); std::string temp = newTemp(); // 生成新临时变量 emit(temp + " = " + left + " " + op + " " + right); left = temp; } return left; }

这里的emit函数把四元式写入一个全局列表，newTemp生成一个新的临时变量名（如t1, t2, t3...）。

5.3 符号表的设计与管理

符号表是语义分析的核心数据结构。我用一个栈式符号表来管理作用域：

struct Symbol { std::string name; std::string type; // "int", "float", "bool", "char" int scopeLevel; bool isFunction; std::vector<std::string> paramTypes; // 函数参数类型列表 }; std::vector<std::map<std::string, Symbol>> scopeStack;

进入一个新的作用域（比如函数体或if块）时，压入一个新的map；离开时弹出。查找变量时从栈顶往下找，找到第一个匹配的就返回。

这里有个细节：函数名和变量名可以重名，因为它们的命名空间不同。我在符号表中用isFunction标志来区分，查找时根据上下文决定找哪种。

实操心得：符号表的管理一定要在语义分析阶段就做好，不要等到代码生成时才去查变量类型。我一开始偷懒，代码生成时才发现有些变量的类型不确定，又回头补符号表逻辑，浪费了很多时间。

6. 中间代码生成与目标代码输出

6.1 四元式的设计与生成规则

四元式是一种常见的中间代码形式，每条指令包含四个部分：操作符、源操作数1、源操作数2、目标操作数。比如a = b + c对应的四元式是(+, b, c, a)。

我定义的四元式操作包括：

• 算术运算：+,-,*,/,%
• 赋值：=
• 比较：<,>,==,!=
• 控制流：label,goto,if_goto
• 函数：param,call,return

控制流的翻译稍微复杂一些。比如if (a < b) { s1 } else { s2 }翻译成：

(if_goto, a, b, L1) // 如果a < b跳转到L1 (goto, _, _, L2) // 否则跳转到L2 (label, _, _, L1) // L1: s1的代码 ... s1的四元式 ... (goto, _, _, L3) // 跳过else分支 (label, _, _, L2) // L2: s2的代码 ... s2的四元式 ... (label, _, _, L3) // L3: 结束

while循环的翻译类似：

(label, _, _, L1) // L1: 循环开始 (if_goto, a, b, L2) // 如果条件成立跳转到L2 (goto, _, _, L3) // 否则跳出循环 (label, _, _, L2) // L2: 循环体 ... 循环体的四元式 ... (goto, _, _, L1) // 跳回循环开始 (label, _, _, L3) // L3: 循环结束

6.2 从四元式到可执行形式

四元式本身不能直接执行，需要进一步翻译成目标代码。为了简化，我选择把四元式翻译成一种简单的栈式虚拟机指令。这个虚拟机有以下几个指令：

• PUSH value：把值压栈
• LOAD var：把变量的值压栈
• STORE var：弹出栈顶存入变量
• ADD,SUB,MUL,DIV：弹出两个操作数，运算后压回结果
• JMP label：无条件跳转
• JZ label：栈顶为0则跳转
• CALL func：调用函数
• RET：返回

比如(+, b, c, a)翻译成：

LOAD b LOAD c ADD STORE a

这个翻译过程是机械的，写一个循环遍历四元式列表即可。

6.3 一个完整的编译示例

假设源代码是：

int main() { int a = 3; int b = 4; int c = a * a + b * b; print(c); return 0; }

经过词法分析、语法分析、语义分析后，生成的四元式大致是：

(=, 3, _, a) (=, 4, _, b) (*, a, a, t1) (*, b, b, t2) (+, t1, t2, t3) (=, t3, _, c) (param, c, _, _) (call, print, 1, _) (=, 0, _, _) (return, _, _, _)

再翻译成虚拟机指令：

PUSH 3 STORE a PUSH 4 STORE b LOAD a LOAD a MUL STORE t1 LOAD b LOAD b MUL STORE t2 LOAD t1 LOAD t2 ADD STORE t3 LOAD t3 STORE c LOAD c PRINT PUSH 0 RET

这个虚拟机指令序列可以直接用一个简单的解释器执行，输出结果。

7. 常见问题排查与调试技巧实录

7.1 语法分析器报错但不知道错在哪

这是最常见的问题。LL(1)分析器报错时，你只知道“当前Token无法匹配”，但不知道为什么会走到这一步。我的解决办法是在报错时打印完整的分析栈和剩余的输入Token序列。这样你可以看到分析器当前期望什么，实际遇到了什么，从而推断出是哪条产生式选错了。

另外，在预测分析表中记录产生式编号而不是产生式本身，报错时可以打印“在应用产生式23时出错”，然后去查产生式23是什么，定位问题会快很多。

7.2 语义分析阶段的类型检查

类型检查是语义分析的核心。我遇到的一个典型问题是隐式类型转换：int a = 3.14;应该报错还是自动截断？我选择报错，因为自动截断容易掩盖bug。但float b = 3;是允许的，整数自动提升为浮点数。

类型检查的实现方式是在语法树节点上标注类型，然后自底向上检查。比如加法节点，要求左右操作数类型相同，或者一个是int一个是float（此时把int提升为float）。

7.3 常见问题速查表

7.4 调试技巧：从最小用例开始

不要一上来就用复杂的测试程序。先用最简单的用例——比如只有一条变量声明——确保整个流程能跑通。然后逐步增加复杂度：加一个加法、加一个if、加一个while、加一个函数调用。每增加一个特性，就单独测试它，确保没有问题后再加下一个。

我当初犯的错误是，一口气把整个子集都实现了，然后拿一个几十行的程序去测，结果报了一堆错，完全不知道从哪开始修。后来改成增量开发，每次只加一个特性，问题定位就简单多了。

避坑技巧：在编译器的每个阶段输出中间结果。词法分析后打印Token序列，语法分析后打印语法树或四元式，代码生成后打印虚拟机指令。这样一旦最终结果不对，你可以快速定位是哪个阶段出了问题。

8. 项目扩展方向与个人实操体会

这个编译器虽然只支持C++的一个很小的子集，但它的架构是完整的，可以在此基础上继续扩展。比如：

• 增加数组支持：需要在符号表中记录数组的维度信息，在四元式中增加数组下标寻址的操作。
• 增加for循环：for循环可以脱糖成while循环，在语法分析阶段做转换即可。
• 增加简单的结构体：需要扩展类型系统，支持复合类型。
• 优化中间代码：比如常量折叠、公共子表达式消除、死代码删除等。

我个人在实际操作中的体会是，编译原理实验最大的难点不在于理论，而在于工程实现。课本上讲LL(1)分析，几页纸就把FIRST集、FOLLOW集、预测分析表讲完了，但真正写代码的时候，你会发现有无数细节需要处理：Token的行号、符号表的作用域、四元式的临时变量命名、错误信息的友好提示……这些东西课本上不会讲，但缺了任何一个，你的编译器都不好用。

另一个体会是，测试用例的设计比代码本身更重要。我建议你专门花时间构造一组覆盖各种边界情况的测试用例，包括正确的程序和错误的程序。正确的程序用来验证功能，错误的程序用来验证错误处理。一个健壮的编译器，不仅要能编译正确的代码，还要能对错误的代码给出清晰的报错信息。

最后分享一个小技巧：如果你在预测分析表的构造上卡住了，可以先用一个更小的文法（比如只支持加法和乘法的表达式文法）来验证你的FIRST/FOLLOW集计算程序是否正确。确认无误后，再逐步扩大文法范围。这样可以把问题隔离在最小的范围内，避免一次性面对太多变量。