编译原理这门课实验三通常就是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 完整流程拆解从文法到分析器的五条主线整个实验可以拆成五条主线这也是我认为比较合理的工程组织方式文法输入与内部表示把用户输入的文法字符串解析成产生式列表。求FIRST集对所有非终结符计算其所有可能推导出的第一个终结符集合。求FOLLOW集对所有非终结符计算在某些句型中可能紧跟在其后面的终结符集合。构造LL(1)预测分析表依据FIRST集和FOLLOW集填充二维表并检测冲突。表驱动语法分析用一个栈、一张表和输入串完成匹配过程输出分析轨迹。实验报告里最容易被忽略的是第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集更容易出错。关键点在于三条规则对文法的开始符号S把#加入FOLLOW(S)。对形如A - αBβ的产生式把FIRST(β)去掉ε后加入FOLLOW(B)。对形如A - αB的产生式或者β可以推导出ε时把FOLLOW(A)加入FOLLOW(B)。第三条规则是重灾区。很多同学只处理了β为空的情况忘了当β能推导出ε时FOLLOW(A)同样要传给FOLLOW(B)。判断“β是否可推导出ε”的实现是β中每个符号的FIRST都包含ε或者β本身就是空串。FOLLOW集的循环依赖也比FIRST集更隐蔽。比如文法中有S - A BB - ε那么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[i1:] 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)预测分析表是一个二维表行是非终结符列是终结符加结束符号#。每个格子里存放的是一条产生式。填表规则很清晰对产生式A - α先计算FIRST(α)。对FIRST(α)中的每一个终结符a不包括ε在表M[A][a]中填入该产生式。如果ε在FIRST(α)中则对FOLLOW(A)中的每一个符号b在表M[A][b]中填入该产生式。如果某个格子已经被填过且不是同一条产生式说明文法存在冲突不是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, conflict3.2 左递归消除与提取左公因子为什么我要先讲这张表因为只有在填表时你才会真正理解为什么教材反复强调要先消除左递归、提取左公因子。左递归文法比如E - E T | T在求FIRST集时会陷入间接递归在填表时M[E][id]这个格子会同时出现E - ET和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 AA - 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 分析器的工作机制与栈操作细节有了预测分析表之后剩下的就是模拟一个下推自动机。整体流程初始化栈里压入#再压入文法开始符号。输入串后面追加#。重复以下步骤直到接受或报错栈顶符号是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(ferror 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配idF - 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 - AA - 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 - BB - A且两者都能推导出ε分析器会在这两个非终结符之间来回弹跳。排查方法是给循环加一个最大步数限制。我在实现时设置了一个step_limit 10000超过这个步数直接报错退出至少不会卡死终端。定位问题时打印每一步的栈顶和当前输入符号很快就能看出来是不是两个非终结符在来回震荡。如果是这种原因说明文法本身就不满足LL(1)需要回去改写文法而不是在代码层面修补。5.5 常见问题速查表现象可能原因解决思路FIRST集缺元素扫描不收敛只做了一轮改为while循环直到集合无变化FOLLOW集缺#忘记给开始符号初始化#在迭代前对FOLLOW[start]加入#FOLLOW集多出符号处理规则3时条件写宽了只在β可推导ε时才加FOLLOW[A]预测表冲突文法有左递归或左公因子先消除左递归再提取公因子分析时栈顶空白报错预测表缺少对应条目检查输入的终结符是否与文法一致分析无限循环文法间接左递归打印调试信息限制最大步数5.6 一个提高开发效率的小建议千万不要一上来就写完整代码再调试。我的习惯是分成五个小模块每个模块单独测试先测文法解析再测FIRST集对着手工结果比对然后是FOLLOW集再是预测表最后才是分析器。这样每个模块的错误范围都很小定位起来非常快。尤其是FIRST集和FOLLOW集可以用几个已知答案的经典文法优先验证算法正确性再换到自己的文法上。我见到太多同学把五个模块全写完再一起调试结果报错之后根本不知道是集合求错了还是表填错了还是分析器逻辑错了。6. 实验扩展与一些后话做完成基本要求之后我给这个实验加了两个扩展功能算是把整个知识面又拉宽了一些。一个是在分析器中输出每一步的推导树信息简单一点可以用缩进表示树形结构这样输入串一旦报错能直观看到是哪个非终结符在哪一步出了问题。另一个是加了一个很小的错误恢复机制当预测表中查不到条目时丢弃当前输入符号并继续统计一次错误的恢复次数。虽然这个恢复策略很粗糙但能帮助理解编译器在真实情况下遇到语法错误时是怎么尝试继续分析的。做完这个实验之后我对递归下降分析的理解也顺了很多。LL(1)表驱动分析和递归下降本质上是同一套决策逻辑只不过一个显式用栈模拟一个用函数调用栈实现。后来看那些手写递归下降的解析器脑子里会自动把每个函数对应到预测表的某一行。这个实验的价值不只是数组、集合和栈的组合练习而是真正把文法理论、自动机和算法串成了一条线。如果你用的是C注意set遍历时插入元素导致迭代器失效的问题我的做法是先把待插入的元素收集到临时集合里最后再统一合并。如果你用的是Java注意HashSet在遍历时也不能直接修改同样是先收集再合并的思路。这个小细节可以帮你省下不少崩溃调试时间。最后再分享一个我个人的操作习惯文法文件和输入串都做成外部输入程序启动时读取文件而不是在代码里写死。这样做的好处是换一个文法测试的时候完全不用重新编译而且可以快速验证多个文法是否是LL(1)。实验报告中附上几组不同文法的运行结果会让整个实验看起来更有说服力。