编译原理语法分析实验：LL(1)与递归下降的排坑指南

“编译原理实验二 语法分析”是很多人第一次真正感觉到“编译器有智商”的实验。词法分析阶段你只是把字符流切成token，说白了还是一个字符串处理问题，但到了语法分析，你开始判断“这个句子到底符不符合语言的语法规则”，也就是真正用形式化文法去约束输入。这个实验的经典要求是：给定一个上下文无关文法，实现一个语法分析器，能够判定输入的token序列是否符合文法，并在出错时尽量给出有用的提示。

我当年做这个实验时最大的错觉是觉得代码量不大、随便搞搞就行，结果在First集和Follow集上翻车翻得相当难看。写下这篇东西，既是复盘，也是给正在做这个实验的人一份能直接用的排查指南。无论你是用递归下降还是表驱动，下面这些坑你大概率都会遇到。

1. 语法分析实验到底在做什么

1.1 从字符流到句子结构：它在整个编译流程中的位置

编译器前端有很清晰的一条流水线：词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成。词法分析负责把源程序字符流切成一个个token，比如关键字、标识符、运算符、数字、括号。它输出的是一串扁平的东西，像“ID PLUS ID TIMES ID”这样。你拿到这串token之后，下一步就是语法分析。

语法分析要回答的问题很简单：这一串token，按你定义的语言文法来看，成不成立？这里的“成立”指的是结构合法，比如“ID + ID * ID”结构合法，而“ID + * ID”结构不合法。这个阶段完全不关心“ID代表的是什么类型的变量”这种语义问题，那是实验三的活。为了表达结构，我们需要用上下文无关文法（CFG）来描述语言。语法分析器本质上就是文法的执行器：它读入token，按照文法规则尝试推导，能推导成功就接受，失败就报错。

一个容易误会的点在于：语法分析不只是做一个“通过/不通过”的判断。在正规的编译器中，它还会输出一棵语法树，把句子的层次结构显式表达出来。比如“ID + ID * ID”经过分析，会生成一棵体现乘法优先级高于加法的树。很多学校的实验二只要求到“判断合法性”为止，但如果你在实现时顺手把树建出来，后面做语义分析和中间代码生成会轻松非常多。

从教学定位上看，这个实验是很多人第一次接触“形式化方法”的落地。前面学的正规式、DFA还比较像自动机玩具，到了语法分析，你真的要为一个有递归结构的语言写出能跑的程序。这就像学英文时，词法相当于认单词，语法分析则是判断“主谓宾定状补”是否成立。单词都认识不代表句子合法，“我吃苹果”合法，“苹果吃我”在句法上也成立但意思奇怪，“我苹果吃”在常规句法中通常就不成立了。编译器在语法分析阶段只关心句法，不关心语义。

1.2 自顶向下还是自底向上：实验选型背后的道理

语法分析的实现路线分两大类：自顶向下和自底向上。自顶向下是从文法的开始符号出发，不断用产生式推导，尝试最终推导出输入串；自底向上则反过来，从输入串开始不断归约，最终归约成文法的开始符号。对应到主流算法，自顶向下的代表是LL(1)和递归下降分析，自底向上的代表是LR、SLR、LALR。

学校实验课几乎清一色选LL(1)或递归下降，不是没有理由的。LL(1)的分析过程非常直观：从左到右读输入，做最左推导，每一步只向前看一个符号来决定用哪条产生式。这个概念讲起来清楚，算起来也有套路可循，适合出题和考评。递归下降则是LL(1)的手工实现形态，每个非终结符对应一个函数，代码结构和文法结构几乎一一对应，单步调试时你能亲眼看到推导过程，教学价值很高。

自底向上的LR系列能力强很多，能识别的语言范围比LL(1)大得多，几乎覆盖所有上下文无关文法。但代价是构造状态表的过程相当繁琐，需要算项目集规范族、构造ACTION和GOTO表，手工写一个LR分析器对本科生来说工程量不小。一般用到LR的场合，都是借助Yacc/Bison这类语法分析器生成工具，写完文法直接生成分析器，这通常是另一个实验方向的事。

如果你在实验要求里看到“递归下降分析法”和“LL(1)分析法”两个选项，我建议首选递归下降。理由后文会详细讲，简单说就是：递归下降的代码自解释性强，出错时更容易通过函数调用栈定位问题，而且将来要扩展成构建语法树时非常自然。表驱动LL(1)虽然也很经典，但对初学者来说，调试时需要在脑子里反复回放压栈出栈的过程，效率低不少。

这个“1”是LL(1)能力边界的关键。它表示每一步决策最多向前看一个输入符号。正因为有的文法在只看一个符号时无法确定走哪条路，才需要做后面要说的左公因子提取，才需要引入Follow集，所有这些工作，本质上都是为了让“只看一个符号就能决策”这件事成立。

2. 写代码前先把文法收拾干净

很多同学做这个实验的第一件事是打开编辑器写代码，这是一个大坑。语法分析实验真正的第一步，是拿一张纸，把文法写出来，然后回答几个问题：这个文法有没有左递归？有没有公共前缀？有没有会推导出空串的非终结符？这几个问题不解决，写出来的代码要么死循环，要么对一堆输入误判。

我自己带人做这个实验时，见过太多“代码看起来没问题但一跑就崩”的情况，最后定位到文法上全是问题。所以我强烈建议：先花一晚上把文法推干净，再谈实现。下面这三件事，每一个都值得认真做。

2.1 消除左递归：不然你的分析器会停不下来

递归下降的函数调用关系直接映射到产生式。如果存在A → Aα这种直接左递归，那函数A()的第一件事就是调用A()，不用看输入就能无限递归下去，程序瞬间栈溢出。凡是遇到“某个函数一调用就栈溢出”的情况，十有八九是左递归没处理干净。

直接左递归的消除是标准操作。把形如下面的产生式组：

A → Aα1 | Aα2 | ... | Aαm | β1 | β2 | ... | βn

其中β1到βn是不以A开头的候选，改写为：

A → β1 A' | β2 A' | ... | βn A' A' → α1 A' | α2 A' | ... | αm A' | ε

初看公式有点绕，用表达式文法演示一遍就清楚了。假设我们已经有一个带乘除优先级的四则运算文法：

E → E + T | T T → T * F | F F → (E) | id

这里E的第一个候选是E + T，存在直接左递归。按公式消除：

E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → (E) | id

注意消除后的E'和T'都出现了ε，这个空串在后面会带来一系列问题，一定要重视。

直接左递归好认，真正坑人的是间接左递归。比如A → B x，B → A y。表面上看，A的函数调用B，B的函数调用A，如果输入碰巧走到这条路径，照样无限循环。处理方法是要先把某个非终结符的产生式代入另一个，把间接左递归转化成直接左递归，再按上面的公式消除。这个技巧不仅实验要用，考试也常考，值得多练几遍。

2.2 提取左公因子与悬空else：LL(1)的第二个门槛

左公因子是指多个产生式有相同的开头。考虑典型的条件语句：

statement → if (expr) statement statement → if (expr) statement else statement

两个候选都以“if (expr) statement”开头。对LL(1)来说，当前token只看到if时，根本无法确定该匹配第一个还是第二个候选，这就是冲突。解决办法是提取公共因子：

statement → if (expr) statement else_part else_part → else statement | ε

这一步又引入了ε。ε一来，悬空else（dangling else）问题就跟着来了。对于“if (c1) if (c2) s1 else s2”这种嵌套输入，后面的else到底匹配内层if还是外层if？C等主流语言的选择是就近匹配，把else绑定到最近的未匹配if。想要在文法层面表达这个策略，通常要把“带else的语句”和“不带else的语句”分成两层来定义，具体写法因教材而异，但核心思路是一致的：让文法在每一个决策点都能依据当前token唯一决定走向。

做实验时的经验是：如果在构造预测分析表时发现某个格子里有多条产生式，也就是冲突，不要急着在代码里加特殊判断绕过去。先退回文法层面，思考能不能通过提取公因子或者重新分层来消除冲突。硬编码分支虽然有可能骗过几个测试样例，但换一条输入可能就翻车，后面做语法树时还会被自己埋的逻辑雷炸到。

2.3 First集与Follow集：手算一遍胜过调试三小时

如果说消除左递归和提取左公因子是“清理文法”，First集和Follow集就是给清理后的文法做体检。很多同学觉得这一步是纯体力劳动，随手算算就去写代码，结果分析器对合法输入报错、对非法输入放行，回头只能一遍遍调试。我的建议很直接：在纸上完整手算一遍，算完先自己核对，再让程序照着实现，千万别跳。

First集的定义是：一个符号串α的First(α)，表示从α能推导出的所有可能开头的终结符集合。如果α还能推导出空串，那么ε也加入First(α)。Follow集则是站在非终结符A的角度：当A出现在某个推导中时，后面可能紧跟着哪些终结符。注意Follow(A)中不允许有ε，因为“后面跟着空串”对实际输入没有意义。

还是用上面那个表达式文法：

E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → (E) | id

先算First：

• First(F) = { ( , id }
• First(T') = { * , ε }
• First(T) = First(F) = { ( , id }
• First(E') = { + , ε }
• First(E) = First(T) = { ( , id }

再算Follow，这里最容易算错。规则是：把$加入Follow(开始符号)；对形如A → αBβ的产生式，把First(β)中除ε外的符号全部加入Follow(B)；如果β能推导出ε或者β不存在，那么把Follow(A)的所有符号也加入Follow(B)。跟着规则走，结果是：

• Follow(E) = { $ , ) }，因为E是开始符号有$，而F → (E)里E后面跟着右括号
• Follow(E') = Follow(E) = { $ , ) }，因为E → T E'里E'在产生式末尾
• Follow(T) = { + , $ , ) }，因为E' → + T E'里T后面的E'可能推导出空串，于是要借用Follow(E')，而E'不推导空串时，First(E')中的+也要给T
• Follow(T') = Follow(T) = { + , $ , ) }
• Follow(F) = { * , + , $ , ) }，因为T' → * F T'里F后面跟T'，First(T')中的*给F；T'又能推导出空串，所以Follow(T')整体并入Follow(F)

Follow(F)最后有四个符号，经常有人漏掉*或者+。我的经验是：每算完一轮，就检查一下“是不是所有出现该非终结符的位置，我都把后面可能跟随的终结算进去了”，发现问题就继续迭代，直到集合不再变化为止。Follow集之间存在相互依赖，一轮算不完是正常的，需要多跑几轮才能收敛。

3. 两条经典实现路线：递归下降与表驱动

文法处理完之后，实现路线无非两条。递归下降是直接用代码模拟推导，表驱动则是先构造一张预测分析表，再写一个通用的分析驱动器。两条路的底层决策逻辑是一样的，都是“用当前token决定走哪条产生式”，但工程形态差别很大。

3.1 递归下降：让每个函数对应一个非终结符

递归下降的核心思想非常直白：为文法中的每个非终结符写一个函数，函数体就是该非终结符的产生式候选。遇到终结符就调用match去匹配当前token，遇到非终结符就调用对应函数。拿表达式文法来说，代码框架长这样：

void E() { T(); // E -> T E' E_prime(); // E' -> + T E' | ε } void E_prime() { if (lookahead.type == TOKEN_PLUS) { match(TOKEN_PLUS); T(); E_prime(); } // 如果当前不是PLUS，就当作 E' -> ε 处理 }

match函数比较当前token和期望token，一致就推进到下一个token，不一致就报错。lookahead通常是一个全局变量，由词法分析器喂进来。这里有一个极容易被忽略的细节：E_prime里看到当前不是PLUS时就默认走了ε分支，但“默认走ε”并不等于当前token一定合法。严谨的写法是先检查当前token是否在Follow(E')中：在，说明这里确实应该匹配空串，可以返回；不在，说明输入串根本不在这个文法能接受的语言里，必须报错。这个细节放到4.1节详细讲。

递归下降的优点很明显：代码和文法一一对应，调试时单步跟踪一下就能看到整个推导过程，非常直观。要做语法树也很方便，每个函数返回一个节点即可。缺点也不是没有，如果文法里有公共前缀没提取干净，函数内部就要写多个if分支硬判，很容易出逻辑错误。写递归下降时，我建议先把lookahead和match这两个工具函数写好，再写所有非终结符函数。这两个工具是所有函数的地基，地基有bug，比如match失败后没有正确推进token，那后面每个函数都会连锁出错，而且错误位置会非常离谱。

提示：递归下降中每进入一个函数，实际上就是在模拟一次推导。你可以在入口打印当前函数名和lookahead类型，这比断点调试更直观，能帮你快速看到推导路径。

3.2 表驱动LL(1)：一张表代替所有分支

表驱动不写一堆函数，而是把“哪种情况下用哪条产生式”集中成一张二维表。表格的行是非终结符，列是终结符（包括结束符$），每个格子存放一条产生式，空白格表示错误。构造步骤很机械：对每个产生式A → α，把该产生式填入First(α)中每个终结符对应的列；如果α能推导出ε，再把它填入Follow(A)中每个终结符对应的列。

还是用表达式文法，预测分析表长这样：

注意E'行：+, ), $三列都有产生式。+列来自First(+TE')中的+，)列和$列来自Follow(E')。很多同学填表时只记得往First集合对应的列填，忘了ε产生式其实是跑到了Follow集合对应的列，这是考试和实验里最容易错的点。

表驱动的分析驱动器很短：

push(END_MARKER); push(START_SYMBOL); while (stack_is_not_empty()) { X = peek_stack_top(); if (is_terminal(X)) { if (X == current_token.type) { pop(); advance_input(); } else error("unexpected token"); } else { production = table[X][current_token.type]; if (production == NULL) error("no production"); else { pop(); push_right_hand_side_reversed(production); } } }

这里有一个关键点：产生式右部要逆序压栈，栈顶才会是右部第一个符号。表驱动的优点是把分析和文法解耦，改文法只需要重建表，不用动分析器代码。缺点是调试时缺少递归下降那种“函数调用栈上的直觉”，一报错，你只能在脑子里回放整个压栈出栈过程。对初学者，我建议先在纸上模拟两个输入：一个合法的“id + id * id”，一个非法的“id + * id”，亲手写几行栈的变化过程。写过一遍，表驱动就再也忘不掉了。

3.3 错误处理的落地方式：同步符号与报错信息

语法分析器光会“接受”和“拒绝”是不够的，还要在拒绝的时候给出像样的错误信息。最常用的错误处理策略是恐慌模式（panic mode）加同步符号。思路是：发现语法错误时，先打印一条带位置信息的错误消息，然后不断丢弃输入中的token，直到碰到一组“同步符号”才恢复分析。同步符号一般选那些结构边界明显的token，比如分号、右括号、语句关键字、结束符$等。

为什么要等到同步符号再恢复？因为如果你在错误点立即继续，分析器已经处于半崩溃状态，后续几乎每个token都可能触发新的误报，最后报错列表长得没法看。等一个“明确的结构边界”再恢复，分析器就能重新找到节奏，继续分析后续内容。这个策略在表驱动和递归下降里都能实现，差别只在“丢token”的执行位置。

报错信息最少要有三类内容：行列号、期望的token、实际遇到的token。很多同学只打印一个“syntax error!”，调试时连错在哪一行都不知道。我给match函数传参数时，习惯带上上下文说明，比如“in expression”或“at end of statement”，这样报错信息可以写成“line 3, column 7: expected ';' but got ')' in statement”。这段信息在后续实验调试中价值极高，千万别省。

4. 实验的常见问题与排查实录

这一章全部是我自己或带人做实验时真实踩过的坑。很多坑书上看不到，但只要亲手写一个语法分析器，几乎一定会遇到。这里按经验顺序排一下，方便对照。

4.1 空串ε引发的连锁问题

我印象里最阴险的坑就是ε。表面上看，ε产生式就是“什么都不匹配”，好像很好处理，但它牵扯两个非常容易错的问题。

第一个问题是前面说的：ε分支要不要验证当前token在Follow集合里。假设E'能在当前输入不是PLUS时匹配空串，但当前token实际是TOKEN_MUL，按文法这个token根本不应该出现在这里。如果你直接return，等于把一个非法输入“放生”到了上层，最后可能在很靠后的位置才报错，甚至在某些表驱动实现里直接误判为合法。试想输入“id + * id”，E'匹配PLUS后调用T，T又调用F，F发现当前token是MUL而不是ID或(，如果F的ε分支没有校验，就可能跳过错误继续往下走，最后在输入末尾才报错，错误位置完全失真。所以正确做法是：进入ε分支前，必须检查当前token是否属于Follow(A)，不属于就报错。

第二个问题是构造预测分析表时ε产生式容易填错位置。很多同学只记得把产生式A → ε填入First(α)对应的列，但First(ε)就是{ε}，真正决定它填到哪一列的是Follow(A)。这一点前面已经强调过，做实验时务必再检查一遍：A → ε这条产生式，是否出现在Follow(A)中每个终结符对应的列上。

4.2 无限递归和栈溢出

无限递归的元凶大概率还是左递归。直接左递归一眼能看出来，难的是间接左递归。我遇到过印象很深的一个例子：某位同学写出了三个函数互相调用，A调B、B调C、C调A，看起来每个函数都在做“有意义的事”，但输入一到特定分支就栈溢出。排查半天才发现，把这三个产生式展开之后，构成了一条完整的间接左递归链。处理办法还是那套：先代入展开，暴露直接左递归，再消除。

表驱动分析器也有可能出现无限循环。比如某个非终结符X在当前token下被替换成Y Z，而Y又能在同样的当前token下被替换成以X开头的组合，于是分析栈上反复出现同样的非终结符和输入，形成死循环。这类问题同样要从文法层面找原因，不是驱动器代码的问题。

如果你需要快速定位递归深度问题，可以在每个非终结符函数入口维护一个全局深度计数器，超过阈值就打印当前调用栈。这办法很土，但比调试器直观，尤其适合递归下降的代码。

4.3 与词法分析的对接细节

词法分析器接到语法分析器时，最容易出三个问题。

一是token类型映射不一致。词法层和语法层对“什么是一个token类型”的约定必须一致。比如“==”和“=”到底是一个类型还是两个类型，词法层一旦把二者归成一个，语法层就无法区分。做实验前先列一张token类型表，把词法输出和语法输入严格对齐。

二是位置信息丢失。token如果在词法阶段没有记录行列号，语法分析器报错时只能报“第n个token出错”，这在调试时几乎没有意义。解决办法是给token结构加line和column字段，词法分析时顺路记上。这一行代码，能为你后续省下大量时间。

三是空白和注释的处理。这个应该在词法层完成，语法层完全不需要看到空白token。如果你在语法分析器里见到了空格token，那一定是哪里搞串了。另外，关键字和标识符的区分也要在词法层完成。比如if在词法分析时就该输出TOKEN_IF，而不是输出TOKEN_IDENTIFIER之后再靠字符串内容判断。否则语法分析器每次都要去翻字符串值，效率低而且容易出错。

如果没有现成的词法分析器可对接，实验允许直接输入token串，我也建议不要省掉“把源程序文本转成token数组”这一步。手工敲token方式测几次还行，多了真的会疯。

4.4 问题速查表

下面的表格基本涵盖了我见过的大部分语法分析器故障，可以当成排查流程来用：出现问题时，先看现象，再对照原因和方向。

这张表不需要背，调试时对着看就行。我自己每次遇到诡异问题，都会先问一句：“这又是ε或者Follow集的问题吗？”事实确凿，十有七八都是。

5. 从能跑到能用：测试用例与扩展方向

实验交上去的时候，有的同学只测了老师给的一两个样例，觉得“能跑就行”，结果答辩时老师随便换一个输入就露馅。这一章说两件事：怎么设计靠谱的测试用例，以及如果有进阶要求，怎么顺手把语法树构建出来。

5.1 一套靠谱的测试用例怎么设计

设计测试用例的原则是分层递进。先把最小的合法程序测通，再测嵌套结构，最后测各种非法输入和边界情况。以最典型的表达式文法来举例。

第一层，最小合法输入：

• 单个标识符：id
• 单个括号表达式：(id)
• 最简单的运算：id + id、id * id

第二层，优先级与结合性：

• id + id * id，这个必须能过，而且后续如果建语法树，树要体现乘法优先
• (id + id) * id，括号要能改变优先级
• id + (id * id + id)
• id + id + id，同时要体现加法左结合

第三层，非法输入：

• 空输入，什么都没有，必须报错
• id + * id，运算符后面缺操作数
• (id + id，右括号缺失
• id id，两个标识符直接并列，中间缺运算符
• id +，表达式以运算符结尾

如果你实现的不只是表达式，而是带if、while、声明的完整语句文法，还需要补对应结构嵌套和错误用例。不管哪种语言，我都建议写一个自动化测试脚本，把“用例文件、期望结果、实际输出”三列对比跑。手工一个一个敲输入，不仅累，还容易漏掉边界情况。写测试驱动的过程，本身就在倒逼你理解文法。

测试执行顺序也有讲究：先测合法输入，确保分析器能够正确接受；再测非法输入，确保在正确位置报错；最后测那些容易让表驱动“假接受”的输入，比如“id id”。如果第三类都能稳定报错，那你的ε处理和Follow集基本没问题了。

5.2 顺手把AST构建出来：语法分析的进阶

多数实验二的进阶要求是在分析过程中构建抽象语法树（AST）。这件事没有看起来那么难，关键是找准扩展点。递归下降在这方面有天然优势：每个函数对应一个非终结符，只要让每个函数返回一个该非终结符对应的AST节点，在匹配时把子节点拼起来就行。

以表达式文法为例，可以这样写E_prime：

ASTNode *E_prime(ASTNode *left) { if (lookahead.type == TOKEN_PLUS) { match(TOKEN_PLUS); ASTNode *right = T(); ASTNode *node = make_binary_node(TOKEN_PLUS, left, right); return E_prime(node); // 左结合通过参数传递体现 } return left; // E' -> ε，直接返回已有的左操作数 }

这个模式能正确处理左结合，是因为递归调用时把“已经累积的左操作数”作为参数传下去，而不是在返回后做左折叠。很多人第一次写AST时容易在这里翻车，最后构造出来的树会变成右结合的样子，求值结果就错了。

如果是表驱动分析器，构建AST会麻烦一些。你需要给每条产生式挂一个语义动作编号，分析驱动器在匹配完一条产生式后执行对应动作，本质上是在表里额外维护“动作指针”。我个人的建议是：如果实验没强制要求表驱动，又想做AST，直接选递归下降，省心得多。

建好AST之后，实验二和实验三之间的墙基本就打通了。AST本身可以做表达式求值，可以遍历输出，可以挂上符号表做类型分析。这也是很多人说语法分析是编译原理“骨架”的原因——树建好了，后面做中间代码生成、解释器，都顺很多。

最后分享一个我自己的习惯：所有集合计算和文法改写，先在纸上完整推一遍再碰键盘。语法分析这个实验最大的门槛不在代码，而在对文法的理解。你把这个理解了，递归下降也好、表驱动也好，都只是表达方式的问题。做完实验二之后如果还有余力，我建议把LR(1)的分析表构造原理简单看一看，那会让你对“语法分析能力边界”有更深的认识。祝你能在这个实验里真的弄懂那些集合的含义，而不是只交上一份能跑的代码。