编译原理这门课，实验三通常就是LL(1)语法分析。这是很多人第一次真正体会到“一段程序去分析另一段程序”的关卡，也是从词法分析那种偏机械的活儿，转向带有决策逻辑的语法分析的过渡。我当时做这个实验的时候，最大的感受是：书上的FIRST集、FOLLOW集定义看了三遍觉得懂了，一动手写代码就处处是坑。这篇博客就把我踩过的坑、走过的弯路、以及最后稳定跑通的实现思路完整拆开讲一遍，代码用Python写，逻辑可以无缝移植到C++或者Java。

这个实验能解决什么？简单说，给出一份文法，我们自己写程序求FIRST集和FOLLOW集，构造预测分析表，然后用表驱动的算法去判断一个输入串是否符合文法。适合正在做编译原理实验的学生、想补语法分析基础的自学者，以及想找一个可复现的LL(1)分析器参考实现的人。内容不会只讲结论，每一步的“为什么这样设计”我都会说明白。

1. LL(1)实验的整体设计与思路拆解

1.1 为什么实验一定要落在LL(1)上

语法分析有两大流派：自顶向下和自底向上。LL(1)属于自顶向下分析中最经典、最适合教学的一个子集。所谓的LL(1)，第一个L表示从左到右扫描输入串，第二个L表示推导时始终选择最左非终结符进行展开，括号里的1表示每次做决策时只需要向前看一个终结符就能确定下一步动作。

正因为这个“向前看一个符号”的特性，LL(1)分析器的核心就变成了一张表的查询问题：当前栈顶是非终结符A，输入缓冲区的当前符号是a，那么查预测分析表M[A][a]，表格里已经写好了该用哪条产生式去展开A。整个过程没有回溯，没有猜测，线性时间内就能完成一次分析。

实验最有价值的地方在于：它必须建立在一整套严格的文法变换之上。第一步是消除左递归，因为左递归文法直接会让自顶向下分析陷入无限循环；第二步是提取左公因子，否则预测表里会出现同一个格子对应多条产生式的冲突；第三步才是求FIRST集和FOLLOW集，最后填表。这四个环节任何一个出错，最终的分析器都会在某个输入串上翻车。所以这个实验表面上是写一个分析器，实际是在逼你把文法理论完整走一遍。

1.2 完整流程拆解：从文法到分析器的五条主线

整个实验可以拆成五条主线，这也是我认为比较合理的工程组织方式：

1. 文法输入与内部表示：把用户输入的文法字符串解析成产生式列表。
2. 求FIRST集：对所有非终结符计算其所有可能推导出的第一个终结符集合。
3. 求FOLLOW集：对所有非终结符计算在某些句型中可能紧跟在其后面的终结符集合。
4. 构造LL(1)预测分析表：依据FIRST集和FOLLOW集填充二维表，并检测冲突。
5. 表驱动语法分析：用一个栈、一张表和输入串完成匹配过程，输出分析轨迹。

实验报告里最容易被忽略的是第2步和第3步的迭代算法。很多同学只扫一遍产生式就结束了，实际上FIRST集和FOLLOW集的求解是不断迭代直到集合不再变大的过程，需要用while循环反复更新，直到两次循环之间所有集合都没有变化才能停止。这一点在后面的代码里我会特意体现。

1.3 语言选型和数据结构设计

我实现的版本用Python。原因有两个：一是Python的dict和set用起来非常顺手，二是求集合的运算天然适合set的并集差集操作。如果学校要求用C++，核心算法几乎一样，只不过需要自己用unordered_map和set来替换。数据结构的选型逻辑是这样的：

• 终结符和非终结符都用字符串表示，终结符统一标记为不含尖括号，非终结符统一用<...>包裹，避免混淆。
• FIRST集、FOLLOW集用字典存储，key是被分析符号，value是set。
• 预测分析表用二维字典，key是(non_terminal, terminal)，value是产生式下标或者产生式本身。
• 分析用的栈直接用list实现，栈底固定压入特殊的结束符号（我用#表示输入结束，对应课本上的$符号）。

设计上的一个关键选择是：我把产生式的右部存成字符串列表，而不是整个字符串，这样在做“逆序入栈”的时候不需要再把字符串切片，直接用列表[::-1]就可以。实验做多了你会明白，这种细节决定你在调试时是十分钟搞定还是折腾一晚上。

2. 核心环节一：FIRST集和FOLLOW集的迭代求法

2.1 FIRST集的算法逻辑与收敛条件

FIRST集的定义不重复了，重点说实现思路。对每个非终结符，我们初始让它的FIRST集为空，然后反复扫描所有产生式。对形如A -> X1 X2 ... Xn的产生式，要按顺序处理X1到Xn：

• 若X1是终结符，将X1并入FIRST(A)，本条产生式处理结束。
• 若X1是非终结符，将FIRST(X1)去掉ε后并入FIRST(A)。如果ε不在FIRST(X1)中，处理结束；否则继续看X2。
• 如果一直处理到Xn，并且每个Xi的FIRST都包含ε，那么把ε也并入FIRST(A)。

这里有两处非常容易写错的地方。第一，当某个中间符号Xi的FIRST不包含ε时，必须立刻停止，后面的Xj即使有终结符也不能再加进去，因为推导到Xi这里就断掉了。第二，整个算法必须放在while循环里，直到某次循环没有任何集合发生变化才终止。如果不做收敛判断，第一次扫描时前面的非终结符可能还没算完，后面的产生式引用了它还没更新的FIRST集，就会得到不完整的结果。

2.2 从开始符号出发的FOLLOW集迭代

FOLLOW集在实验里比FIRST集更容易出错。关键点在于三条规则：

1. 对文法的开始符号S，把#加入FOLLOW(S)。
2. 对形如A -> αBβ的产生式，把FIRST(β)去掉ε后加入FOLLOW(B)。
3. 对形如A -> αB的产生式（或者β可以推导出ε时），把FOLLOW(A)加入FOLLOW(B)。

第三条规则是重灾区。很多同学只处理了β为空的情况，忘了当β能推导出ε时，FOLLOW(A)同样要传给FOLLOW(B)。判断“β是否可推导出ε”的实现是：β中每个符号的FIRST都包含ε，或者β本身就是空串。

FOLLOW集的循环依赖也比FIRST集更隐蔽。比如文法中有S -> A B，B -> ε，那么FOLLOW(A)依赖于FOLLOW(S)，同时FOLLOW(S)又可能依赖文法中其他位置的规则。这种相互依赖只有通过多轮迭代才能收敛。我这里直接采用同样的处理：while循环扫描所有产生式，直到所有FOLLOW集不再扩大。

代码实现如下：

def compute_follow(grammar, non_terminals, terminals, first_sets, start_symbol): follow_sets = {nt: set() for nt in non_terminals} follow_sets[start_symbol].add('#') changed = True while changed: changed = False for lhs, rhs in grammar: for i, symbol in enumerate(rhs): if symbol in non_terminals: # 计算后面符号串的FIRST rest = rhs[i+1:] rest_first = set() can_derive_epsilon = True for sym in rest: if sym in terminals: rest_first.add(sym) can_derive_epsilon = False break else: rest_first |= (first_sets[sym] - {'ε'}) if 'ε' not in first_sets[sym]: can_derive_epsilon = False break if rest: before_len = len(follow_sets[symbol]) follow_sets[symbol] |= rest_first if can_derive_epsilon: follow_sets[symbol] |= follow_sets[lhs] if len(follow_sets[symbol]) != before_len: changed = True else: before_len = len(follow_sets[symbol]) follow_sets[symbol] |= follow_sets[lhs] if len(follow_sets[symbol]) != before_len: changed = True return follow_sets

这份代码里有个细节我踩过坑：rest_first的计算中，遇到终结符就要立刻break，因为终结符的FIRST就是它本身，而且它后面不可能再推导出别的符号。很多人把终结符也当成集合去求FIRST，结果把后面的符号错误地加进来了。

2.3 手工推导的例子：经典表达式文法

以课本上经典的表达式文法为例：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

这里非终结符是E、E'、T、T'、F，终结符是+、*、(、)、id。手工求一下FIRST集：

• FIRST(F) = {(, id}
• FIRST(T') = {*, ε}
• FIRST(T) = FIRST(F)去掉ε = {(, id}
• FIRST(E') = {+, ε}
• FIRST(E) = {(, id}

FOLLOW集的初始只有FOLLOW(E) = {#}。扫描产生式F -> (E)时，因为E后面是)，所以FOLLOW(E)加入)。扫描E' -> +TE'时，T后面是E'，而FIRST(E')包含ε，所以FOLLOW(T)加入FIRST(E')去掉ε的{+}，还要加入FOLLOW(E')。最终得到：

• FOLLOW(E) = {#, )}
• FOLLOW(E') = FOLLOW(E) = {#, )}
• FOLLOW(T) = {+, ), #}
• FOLLOW(T') = FOLLOW(T) = {+, ), #}
• FOLLOW(F) = FIRST(T')去掉ε + FOLLOW(T) + FOLLOW(T') = {*, +, ), #}

建议实验报告里把这些推导过程完整写出来，有助于理清依赖关系，我在调试时也是先手工算一遍再和程序输出对照。

3. 核心环节二：预测分析表的构造与冲突检测

3.1 表的构造规则

LL(1)预测分析表是一个二维表，行是非终结符，列是终结符加结束符号#。每个格子里存放的是一条产生式。填表规则很清晰：

1. 对产生式A -> α，先计算FIRST(α)。
2. 对FIRST(α)中的每一个终结符a（不包括ε），在表M[A][a]中填入该产生式。
3. 如果ε在FIRST(α)中，则对FOLLOW(A)中的每一个符号b，在表M[A][b]中填入该产生式。
4. 如果某个格子已经被填过且不是同一条产生式，说明文法存在冲突，不是LL(1)文法。

这里需要对“同一个格子填入不同产生式”做区分。如果第2步和第3步都试图填入同一条产生式，那不算冲突，因为它们是同一个动作；但如果填入的是不同的产生式，那就意味着分析器在同一个栈顶符号和同一个输入符号下，有两个可能的扩展方向，LL(1)要求的“确定性”被破坏了。

构造表的代码如下：

def build_parse_table(grammar, non_terminals, terminals, first_sets, follow_sets): parse_table = {} conflict = False for lhs, rhs in grammar: rhs_first = set() can_derive_epsilon = True for sym in rhs: if sym in terminals: rhs_first.add(sym) can_derive_epsilon = False break else: rhs_first |= (first_sets[sym] - {'ε'}) if 'ε' not in first_sets[sym]: can_derive_epsilon = False break # 规则2和规则3 if can_derive_epsilon: fill_set = follow_sets[lhs] for b in fill_set: if (lhs, b) in parse_table and parse_table[(lhs, b)] != (lhs, rhs): conflict = True parse_table[(lhs, b)] = (lhs, rhs) else: for a in rhs_first: if (lhs, a) in parse_table and parse_table[(lhs, a)] != (lhs, rhs): conflict = True parse_table[(lhs, a)] = (lhs, rhs) return parse_table, conflict

3.2 左递归消除与提取左公因子

为什么我要先讲这张表？因为只有在填表时你才会真正理解为什么教材反复强调要先消除左递归、提取左公因子。左递归文法，比如E -> E + T | T，在求FIRST集时会陷入间接递归，在填表时M[E][id]这个格子会同时出现E -> E+T和E -> T两条产生式，直接冲突。而左公因子文法，比如A -> a b | a c，会让M[A][a]格子同时有两条规则。

消除左递归的标准做法是引入新的非终结符。以包含左递归的表达式文法为例：

原始文法：

E -> E + T | T T -> T * F | F F -> ( E ) | id

消除后变成：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

这里面E'和T'是新增的非终结符，它们的作用就是承接原来左递归运算符后面的部分。提取左公因子的思路也类似，把公共前缀提到外面，新增一个非终结符来表达剩余的选择。比如A -> a b | a c改成A -> a A'，A' -> b | c。虽然这个改造有的文法做不了，会引入新的间接左递归，但作为实验，掌握这两种变换的熟练度，比背一百道题都管用。

3.3 一个非LL(1)文法的冲突实例

有些文法无论怎么处理也不是LL(1)。比如：

S -> i E t S | i E t S e S | a E -> b

这是一个简化版的if语句文法。在构造预测分析表时，M[S][i]这个格子会同时填入前两条产生式。消除左递归没有用，提取左公因子后得到：

S -> i E t S S' | a S' -> e S | ε E -> b

看起来没有冲突了，但仔细检查S'的FOLLOW集包含e，而FIRST(S')也包含e，于是在M[S'][e]格子里会同时出现S' -> e S和S' -> ε。这本质上是因为e既属于S'的FIRST，又属于S'的FOLLOW，出现了FIRST/FIRST冲突。这类文法确实是二义的，不是通过简单的变换就能修复。实验报告里如果能写出这个分析，老师会觉得你是真的理解了LL(1)的局限，而不是只会跑例子。

4. 核心环节三：表驱动的预测分析过程

4.1 分析器的工作机制与栈操作细节

有了预测分析表之后，剩下的就是模拟一个下推自动机。整体流程：

1. 初始化：栈里压入#，再压入文法开始符号。输入串后面追加#。
2. 重复以下步骤，直到接受或报错：
   • 栈顶符号是X，当前输入符号是a。
   • 如果X == a == #，接受。
   • 如果X是终结符且X == a，弹出X，读取下一个输入符号。
   • 如果X是非终结符，查表M[X][a]：
     • 表中存在产生式X -> Y1 Y2 ... Yn，弹出X，把Y1...Yn逆序压栈。如果n为0，即产生式为X -> ε，则什么都不压。
     • 表中不存在，报错。

这里最容易出问题的场景有两个。一个是栈顶符号是#但输入还没读完，说明输入串有多余的符号，应该报错而不是继续查表。另一个是非终结符遇到ε产生式时，如果什么都不压，那栈会直接变短，如果输入符号也不匹配，容易造成栈底#提前冒出来。我调试时碰到的死循环基本都是因为ε产生式的压栈逻辑写错了。

4.2 分析过程的代码骨架

def predictive_parse(parse_table, start_symbol, input_tokens): stack = ['#', start_symbol] ip = 0 input_tokens = input_tokens + ['#'] while stack: top = stack[-1] current = input_tokens[ip] if top == current: stack.pop() ip += 1 if top == '#': return True elif top not in parse_table or (top, current) not in parse_table: print(f"error at {top} vs {current}") return False else: lhs, rhs = parse_table[(top, current)] stack.pop() if rhs != ['ε']: for symbol in reversed(rhs): stack.append(symbol) return False

注意一个容易忽略的点：程序里的ε我用一个字符串'ε'表示，但实际存储时它只是一个普通终结符。判断产生式是否为ε产生式时，最好做一个显式的判断，而不是依赖rhs为空列表。因为空列表可能被解释为“没有右侧”，而ε产生式的含义是“空串也可以推导”，在压栈逻辑上它们的结果相同，但语义上显式标记ε会让代码可读性更好。

4.3 分析过程的示例演示：id + id * id

用前面表达式文法分析id + id * id。手工走几轮栈的变化：

初始状态：

栈：["#", "E"] 输入：[id, +, id, *, id, #]

查表M[E][id]得到E -> T E'，弹E，逆序压T和E'，于是栈变成["#", "E'", "T"]，注意这里的顺序：栈顶是T，先处理T。然后查M[T][id]得到T -> F T'，弹T，逆序压F和T'，栈变成["#", "E'", "T'", "F"]。栈顶F配id，F -> id，两个id匹配，弹出，ip后移。这时栈顶是T'，当前输入是+，查表M[T'][+]得到T' -> ε，弹出T'不压任何东西。接着栈顶E'配+，E' -> + T E'，弹出E'压入E'和T，逆序后栈变成["#", "E'", "T"]，同时输入指针移到id。这个过程不断重复，直到最后栈里只剩#，输入也只剩#。

这个手动模拟的过程强烈建议在实验报告里至少画出一个表格，列出步骤序号、栈变化、剩余输入、使用的产生式。一方面是为了给老师看，另一方面它也是调试的利器。我写代码时经常靠这种表格去对照程序输出，定位是栈的问题还是表的问题。

5. 常见问题与排查技巧实录

5.1 终结符和非终结符的区分错误

这是新手最频繁翻车的地方。如果输入文法里终结符和非终结符的表示没有强制区分，比如都用大写字母表示非终结符，但文法中又有id、num这种多字符终结符，问题就来了。我的处理方式是在文法读取时做规范：所有非终结符强制用<名称>包裹，不在尖括号里的符号一律视为终结符。这样FIRST集和FOLLOW集的计算就不需要依赖字母大小写判断，也避免了多字符终结符被拆成单个字符的坑。

5.2 FIRST集扫描一次就终止导致集合不完整

有一种很典型的错误写法：只对每个产生式扫描一遍，把所有能直接看到的终结符加入FIRST集，就认为任务完成了。但遇到间接推导，比如S -> A，A -> a，如果只扫描一遍，扫描S时看到A，而A的FIRST还没算出来，那S的FIRST就漏掉了a。虽然可以调整产生式顺序碰巧算对，但一旦文法规模变大就必然出错。

正确做法就是前面说的，用while循环判断集合是否有变化。我给一个判断集合是否有变化的小技巧：在每次加入新元素之前记录before_len = len(first_sets[symbol])，结束一轮后如果某个集合长度变了，就把changed置True。这个办法稳定可靠，比比较整个set的相等要省事。

5.3 FOLLOW集中的#号时有时无

这是一个非常隐蔽的bug。开始符号的FOLLOW集一定要先初始化加入#，否则最终分析时输入串末尾的#永远无法匹配。我调试一个多行文法的FOLLOW集时，因为没有给开始符号加#，导致栈底#和输入#永远对不上，分析器最后总在错误状态退出。这个#号的添加顺序要放在while循环之前，而不是每轮迭代都加，否则虽然结果一样，但会显得逻辑混乱，不方便给老师讲解。

5.4 表驱动分析的死循环与栈溢出

死循环通常有两种来源。一种是文法含有间接左递归，又没有提前消除，导致查表查到自己，栈上永远压着同一个非终结符；另一种是产生式列表里出现了环，比如A -> B，B -> A，且两者都能推导出ε，分析器会在这两个非终结符之间来回弹跳。

排查方法是给循环加一个最大步数限制。我在实现时设置了一个step_limit = 10000，超过这个步数直接报错退出，至少不会卡死终端。定位问题时，打印每一步的栈顶和当前输入符号，很快就能看出来是不是两个非终结符在来回震荡。如果是这种原因，说明文法本身就不满足LL(1)，需要回去改写文法，而不是在代码层面修补。

5.5 常见问题速查表

5.6 一个提高开发效率的小建议

千万不要一上来就写完整代码再调试。我的习惯是分成五个小模块，每个模块单独测试：先测文法解析，再测FIRST集，对着手工结果比对；然后是FOLLOW集，再是预测表；最后才是分析器。这样每个模块的错误范围都很小，定位起来非常快。尤其是FIRST集和FOLLOW集，可以用几个已知答案的经典文法优先验证算法正确性，再换到自己的文法上。我见到太多同学把五个模块全写完再一起调试，结果报错之后根本不知道是集合求错了还是表填错了还是分析器逻辑错了。

6. 实验扩展与一些后话

做完成基本要求之后，我给这个实验加了两个扩展功能，算是把整个知识面又拉宽了一些。一个是在分析器中输出每一步的推导树信息，简单一点可以用缩进表示树形结构，这样输入串一旦报错，能直观看到是哪个非终结符在哪一步出了问题。另一个是加了一个很小的错误恢复机制：当预测表中查不到条目时，丢弃当前输入符号并继续，统计一次错误的恢复次数。虽然这个恢复策略很粗糙，但能帮助理解编译器在真实情况下遇到语法错误时是怎么尝试继续分析的。

做完这个实验之后，我对递归下降分析的理解也顺了很多。LL(1)表驱动分析和递归下降本质上是同一套决策逻辑，只不过一个显式用栈模拟，一个用函数调用栈实现。后来看那些手写递归下降的解析器，脑子里会自动把每个函数对应到预测表的某一行。这个实验的价值不只是数组、集合和栈的组合练习，而是真正把文法理论、自动机和算法串成了一条线。

如果你用的是C++，注意set遍历时插入元素导致迭代器失效的问题，我的做法是先把待插入的元素收集到临时集合里，最后再统一合并。如果你用的是Java，注意HashSet在遍历时也不能直接修改，同样是先收集再合并的思路。这个小细节可以帮你省下不少崩溃调试时间。

最后再分享一个我个人的操作习惯：文法文件和输入串都做成外部输入，程序启动时读取文件而不是在代码里写死。这样做的好处是换一个文法测试的时候完全不用重新编译，而且可以快速验证多个文法是否是LL(1)。实验报告中附上几组不同文法的运行结果，会让整个实验看起来更有说服力。