简介面向编译原理课程中 LL(1) 语法分析实验的完整资源包围绕给定文法构造预测分析表、再由键盘读入输入串判断其是否为该文法句子这一核心任务展开非常适合计算机专业本科生完成课程设计或复习备考时对照学习、直接复用。压缩包内含 13 个文件类型涵盖 C 源代码、可执行程序、实验报告、工程文件以及讲解视频等整包约 24.81MB其中 3 个 exe 可直接运行验证2 份 cpp 便于按需修改docx/doc 实验报告完整呈现设计思路与结论dev/layout 工程文件则帮助打开即恢复开发环境。配套材料包含程序设计思想说明与两版代码实现其中“法二.cpp”可作为另一种解题思路参考配合实验报告能快速形成课程作业方案视频讲解逐步演示预测分析表的构造过程与输入串出错时的报错逻辑可有效降低理解门槛帮助读者掌握 LL(1) 分析的完整流程。目前已有 3101 人学习下载适合需要完成 LL(1) 分析器实验、理解预测分析流程或准备相关考试的读者。1. 编译原理实验二LL(1)语法分析器的本质是先做文法预处理编译原理实验二目标是写一个 LL(1) 语法分析器几乎每所工科院校的编译原理课都会把它当成标准作业。第一次拿到这道题的人通常以为难点在写代码实际做下来才会发现最花时间的步骤发生在写代码之前把文法改造成 LL(1) 能判定的形式把 FIRST 集、FOLLOW 集算准最后才是那张预测分析表和驱动分析的表结构。它解决的是一个很具体的问题——让语法分析器在不回溯、只向前看一个终结符的前提下完成最左推导。适合正在赶实验报告的学生、要给学生验收的实验课助教以及想用最小代码量把编译原理理论落地的工程师。下面按我理解这道题的顺序从文法讲到排错。2. 从文法变成可判定分析表LL(1) 的条件与三类让表失效的文法硬伤2.1 LL(1) 里的三个字母分别约束什么LL(1) 不是一种程序结构而是一条约束。第一个 L 表示从左到右扫描输入串第二个 L 表示构造最左推导括号里的 1 表示每一步只偷看当前输入的那个终结符。这条约束成立的隐含前提是文法必须足够确定不能用“先猜一个产生式猜错了再回头试”的方式工作。一旦某一步有两种可选产生式都能匹配当前输入程序就不知道往哪走这是所有 LL(1) 报错的根源。常见的实现有两种一种是递归下降把每个非终结符写成一个函数函数之间互相调用另一种是表驱动先构造一张预测分析表 M[A, a]行是非终结符列是终结符和结束符表里存的是此时该选用哪条产生式。实验二里大多数老师要求表驱动因为表格可以人工检查验收时可以直接拿一张手写表和程序输出对拍。递归下降虽然写起来更顺手但本质上和你手工推导的步骤一一对应表驱动分析器反而更容易讲清楚每一步。真正决定这道题成败的判断条件只有一条对每个非终结符 A 的任意两条候选产生式 A→α 和 A→βFIRST(α) 与 FIRST(β) 不能有交集如果 α 或 β 能推导出 ε还得保证 FIRST(α) 与 FOLLOW(A) 也不相交。我在检查同学代码时发现大部分分析器跑出错不是因为栈操作写错而是文法本身不满足这个条件程序硬跑自然出怪结果。2.2 左递归、公共前缀、ε 冲突三个必须提前处理的硬伤第一个硬伤是左递归。比如常见的算术表达式文法写成 E→ET|T这就是直接左递归。放到表驱动里M[E,] 和 M[E,id] 都会被填成“使用 E→ET”栈顶的 E 被弹出后压入 E、、TE 又回到栈顶永远消不下去递归下降更惨E() 函数第一行就调用自己输入还没读就爆栈。间接左递归也一样比如 S→AaA→Sb|b走 S→A→S 这条弯也能绕回自己必须先识别出来。第二个硬伤是公共前缀也叫回溯因子。比如 S→aAd|aBe两条产生式都以 a 开头当前输入正好是 a 时必须再多看一个字符才能决定走哪条路这就违反了只向前看 1 个终结符的前提。解决办法是提取公因子把文法改成 S→aSS→Ad|Be让选择往后推迟到 S 这一层。第三个硬伤和 ε 产生式有关。假设某非终结符 A 有一条能推导出 ε 的路径同时它的 FOLLOW 集合又和另一条产生式的 FIRST 集合撞了那么预测分析表里同一个格子会被两条规则占用。最典型的就是“悬空 else”问题C 语言里 if-else 的二义性在这类文法里就是无解的硬改成 LL(1) 反而会把语义搞坏。碰到这种情况正确的方向是承认这个文法不适合 LL(1)而不是继续调表。2.3 改造文法的顺序先消左递归再提公因子最后验证我处理文法固定按三步走顺序不能反。先做左递归消除再做公因子提取最后验证 LL(1) 条件。如果先提取公因子再消左递归很可能白做一遍因为左递归消除之后又会制造出新的公共前缀。直接左递归的标准改法是有模板的对 A→Aα1|Aα2|...|Aαm|β1|...|βn其中 β 开头不是 A改成 A→β1A|...|βnAA→α1A|...|αmA|ε。教材里常用这个模板但很多人忽略了一点改造引入的 A 必须用新的非终结符名字不能和已有符号冲突而且所有引用 A 的地方都要检查一遍是否还指代正确。做完语法改造在写任何代码之前先手动把 FIRST 和 FOLLOW 算一遍再填一张预测分析表的草稿。这一步能挡住绝大多数问题因为程序的输出可以帮你验证手算但手算错的话程序只会越跑越远。多数实验指导书里的文法其实都已经预处理过真正要你做的只是把表算对、把分析流程写对但如果拿到的是原始文法这个预处理步骤跑不掉。3. 手工算 FIRST、FOLLOW 与预测分析表一个能看懂每一步的算例3.1 选定演示文法算术表达式去掉左递归之后后面代码和验证都用同一套文法这里先定下来方便你抄作业的时候对着查。E → T EE → T E | εT → F TT → * F T | εF → ( E ) | id这套文法就是去掉左递归之后的经典算术表达式文法。id 代表任意标识符或者数字实验里通常会把变量名和数字统一成 id 这个终结符。注意 E 和 T 是两个新引入的非终结符名字后面的撇号只是符号的一部分代码里用字符串 E 表示。很多同学在手工推导时容易把 E 和 E 混在一起计算机程序不会混人反而会写推导过程时最好每个符号都写全。3.2 不动点求 FIRST从 F 往上推求 FIRST 可以当成一个不断迭代直到结果不再变化的过程。先看直接就能确定的规则F → ( E ) | id所以 FIRST(F) { (, id }。T → * F T | ε所以 FIRST(T) { *, ε }。E → T E | ε所以 FIRST(E) { , ε }。再看 T → F T。T 的右部第一个符号是 FF 的 FIRST 是 { (, id }F 本身不能推导出 ε所以直接搬运FIRST(T) FIRST(F) { (, id }。千万别把 F 后面的 T 牵扯进来只有当 F 能推导出空串时才有必要继续往后看这里 F 做不到。最后看 E → T E。T 的 FIRST 是 { (, id }T 不能产生 ε所以 FIRST(E) { (, id }和 FIRST(T) 一样。到这里第二轮再去遍历所有产生式发现没有任何集合再增加符号迭代终止。如果一个文法更复杂可能要迭代三到四轮才算稳。判断终止的办法很简单每一轮结束时对比上一轮结果完全没有变化就是收敛了。写代码时也建议用这种不动点思路不要用递归后面排错章节会讲原因。3.3 从开始符号和 $ 出发推 FOLLOWFOLLOW 集合比 FIRST 容易出错因为它的起点是特殊符号 $。规则有两条一如果某个非终结符后面紧跟着一串符号那么这串符号的 FIRST 集合去掉 ε要加入该非终结符的 FOLLOW二如果后面这串符号能推导出 ε或者该非终结符干脆就是产生式的末尾那么产生式左部的 FOLLOW 要加入该非终结符的 FOLLOW。结合例子看更清楚。第一步FOLLOW(E) 初始包含 $。由 F → ( E ) 可知 E 后面跟着一个右括号所以 ) 加入 FOLLOW(E)。此时 FOLLOW(E) { $, ) }。第二步E → T E。这里从右往左看E 后面不再有符号而整个产生式的左部是 E所以 FOLLOW(E) 照搬 FOLLOW(E)也是 { $, ) }。再看 T它后面跟着 EFIRST(E) { , ε }去掉 ε 得到 { }又因为 E 可空所以 FOLLOW(E) 也要并入最终给 T 贡献 $、) 和 。FOLLOW(T) { $, ), }。第三步看 T。T → F T 里T 后面没东西FOLLOW(T) 就是 FOLLOW(T)又由 T → * F T 可知 T 后面的终结符还是 FOLLOW(T)。所以 FOLLOW(T) 和 FOLLOW(T) 相同这是极常见的情况不是算错了是因为 T 可空导致两边的传递关系一样。第四步处理 F。T → F T 中F 后面有 TFIRST(T) { *, ε }去掉 ε 得到 { * }同时 T 可空又把 FOLLOW(T) 并入。所以 FOLLOW(F) { $, ), , * }。到这里所有集合都填完了。结果汇总成一张表对比着检查非终结符FOLLOW 集合E{ $, ) }E{ $, ) }T{ $, ), }T{ $, ), }F{ $, ), , * }我发现初学者最容易漏的是第二步里“E 可空”导致的 FOLLOW(E) 继续传递。你可以把 ε 的传递理解为T 后面跟着一个“可能不存在”的 E所以 FOLLOW(E) 能直接当作 T 后面会出现的符号。3.4 手动填预测分析表并检查冲突预测分析表的行是五个非终结符列是终结符加 $共六列。每个格子的内容是产生式没有产生式就写 err 或留空。填充逻辑就两条对产生式 A→α把 FIRST(α) 去掉 ε 后得到的终结符对应的格子填上它如果 α 能推导出 ε再把 FOLLOW(A) 里的终结符对应格子也填上它。按这个规则填出来的表达式文法表格如下非终结符id*()$EE→TEerrerrE→TEerrerrEerrE→TEerrerrE→εE→εTT→FTerrerrT→FTerrerrTerrerrT→*FTerrT→εT→εFF→iderrerrF→(E)errerr重点检查 E 行。E 有两条产生式E→TE 只填在 列E→ε 出现在 FOLLOW(E) 里的 ) 和 $ 两列。T 行同理。如果一个格子里需要填两条不同产生式说明文法不满足 LL(1) 条件程序可以继续写但分析结果没有任何意义。手工填充最大的价值就是提前暴露这种问题避免浪费时间去调试一个注定失败的表格。4. 把算法跑起来Python 全实现与表驱动分析过程4.1 文法表示与终结符判定代码里最忌讳把终结符的判断逻辑写成“如果首字母是小写”。因为左括号、右括号、加号都不是字母而撇号在字符串里也避不开大小写判断。最稳妥的做法是显式维护一个终结符集合。# LL1.py —— 实验二 LL(1) 语法分析器的最小实现 # 文法沿用第三章的算术表达式文法非终结符用大写字母和 表示 productions { E: [[T, E]], E: [[, T, E], [ε]], T: [[F, T]], T: [[*, F, T], [ε]], F: [[(, E, )], [id]], } terminals {id, , *, (, )} start Eproductions 这个字典的键是非终结符值是产生式右部的列表的列表。比如 E 对应的值里有两条右部第一条是 [, T, E]第二条是 [ε]。用列表而不是字符串存产生式后面做逆序压栈时可以直接遍历省去字符串切割的麻烦。terminals 集合必须写全尤其是括号和加号这种看起来很像符号的终结符它们也要出现在建表的列名里。4.2 FIRST 与 FOLLOW 的不动点求解求解 FIRST 集采用不动点迭代不递归。递归版本在遇到间接左递归时会直接触发 RecursionError不动点迭代天然免疫这类问题。def compute_first(productions, terminals): first {nt: set() for nt in productions} changed True while changed: changed False for lhs, rhs_list in productions.items(): for rhs in rhs_list: before set(first[lhs]) nullable True for symbol in rhs: if symbol ε: break if symbol in terminals: first[lhs].add(symbol) nullable False break first[lhs].update(first[symbol] - {ε}) if ε not in first[symbol]: nullable False break if nullable: first[lhs].add(ε) if before ! first[lhs]: changed True return first这段代码的核心是 nullable 标志它表示“当前这条右部从开头到当前位置为止整体仍然有可能推导出 ε”。初始为 True遇到终结符就置 False 并中断因为终结符不可能推导出空串遇到非终结符就把它的 FIRST 集合里除 ε 以外的符号并进来再看它本身是否可空不可空就中断。如果整个右部扫完 nullable 还是 True说明这条产生式整体可空给左部补一个 ε。外层 while 负责反复迭代直到所有集合不再变化。FOLLOW 集同样用迭代但取一种从右往左扫描的经典写法def compute_follow(productions, first, terminals, start): follow {nt: set() for nt in productions} follow[start].add($) changed True while changed: changed False for lhs, rhs_list in productions.items(): for rhs in rhs_list: trailer set(follow[lhs]) for i in range(len(rhs) - 1, -1, -1): symbol rhs[i] if symbol in terminals: trailer {symbol} else: before len(follow[symbol]) follow[symbol] | trailer if ε not in first[symbol]: trailer set(first[symbol]) else: trailer trailer | (first[symbol] - {ε}) if len(follow[symbol]) ! before: changed True return follow变量 trailer 装的是“当前扫描位置右侧可能出现的终结符集合”。从右往左扫时如果遇到终结符trailer 直接重置成这个终结符遇到非终结符就先把 trailer 并入它的 FOLLOW 集然后再根据该非终结符自身能否推导出 ε 来更新 trailer。这个技巧在编译原理教材里叫“反向扫描法”比按定义一项项套更不容易漏。4.3 预测分析表的构建与冲突标记建表时不要用单个产生式来覆盖格子否则冲突发生时会被静默掩盖。用列表收集同一个格子里的所有产生式冲突一目了然。def build_table(productions, first, follow, terminals): table {lhs: {t: [] for t in sorted(terminals | {$})} for lhs in productions} for lhs, rhs_list in productions.items(): for rhs in rhs_list: rhs_first set() nullable True for symbol in rhs: if symbol ε: break if symbol in terminals: rhs_first.add(symbol) nullable False break rhs_first.update(first[symbol] - {ε}) if ε not in first[symbol]: nullable False break for term in rhs_first: table[lhs][term].append(rhs) if nullable: for term in follow[lhs]: table[lhs][term].append(rhs) return table构建逻辑就是把第三章手工填表的过程机械化。先扫描一条产生式的右部算出它推导出的第一个终结符集合 rhs_first如果右部可空再把左部 FOLLOW 集合里的终结符也作为该产生式的落点。同一个格子循环里被 append 两次就说明文法有冲突。主入口建议单独写一个检查函数把所有冲突格子打印出来def check_conflicts(table): has_conflict False for lhs, col in table.items(): for term, rules in col.items(): if len(rules) 1: has_conflict True print(f冲突格: M[{lhs}, {term}] - {rules}) return has_conflict4.4 表驱动分析器与分析过程输出表驱动分析器维护一个栈初始化为 $ 和开始符号栈顶放在 list 尾部。每次看栈顶符号和当前输入符号分三种情况处理。def parse(tokens, table, start): stack [$, start] pos 0 steps [] while stack: top stack[-1] current tokens[pos] if pos len(tokens) else $ if top current and top $: print(栈:, stack, 输入:, tokens[pos:], 动作: 接受) return True, steps if top current: stack.pop() pos 1 continue if top in terminals or top ε: print(栈:, stack, 输入:, tokens[pos:], 动作: 报错栈顶终结符不匹配) return False, steps rules table[top].get(current, []) if not rules: print(栈:, stack, 输入:, tokens[pos:], 动作: 报错查表无产生式) return False, steps rule rules[0] stack.pop() for sym in reversed(rule): if sym ! ε: stack.append(sym) print(栈:, stack, 输入:, tokens[pos:], 动作:, f{top}-{ .join(rule)}) steps.append((top, rule)) return False, steps这里有一个关键细节压栈时把 rule 反转后逐个 append因为 list 末尾是栈顶我们希望右部第一个符号最先被弹出。比如 E→TE 的右部是 [T, E]反转后先压 E再压 T于是 T 成为新栈顶下一轮先处理 T。分析过程中打印的每一步都可以直接抄进实验报告的“分析过程”章节这是这道题最容易拿分的地方。配套一个最简分词函数方便直接测试字符串输入。实际实验如果已经有词法分析器的输出直接传给 parse 就行def tokenize(source: str): import re tokens re.findall(r[A-Za-z_]\w*|[0-9]|[\-*/()], source) return [id if re.match(r[A-Za-z_]\w*|[0-9], t) else t for t in tokens] tokens tokenize(id id * id) print(输入 token:, tokens) ok, steps parse(tokens, build_table(productions, compute_first(productions, terminals), compute_follow(productions, compute_first(productions, terminals), terminals, start), terminals), start)对 idid*id 的分析过程打印出来大致是下面这个形态栈栈顶在右输入余留动作$ Eid id * id $E→T E$ E Tid id * id $T→F T$ E T Fid id * id $F→id$ E T id * id $T→ε$ E id * id $E→ T E$ E Tid * id $T→F T$ E T Fid * id $F→id$ E T* id $T→* F T$ E T Fid $F→id$ E T$T→ε$ E$E→ε$$接受注意第二次 T→ε 的使用位置。输入里第二个 id 之后已经没有符号可匹配T 必须靠 ε 产生式退出这正是 FOLLOW(T) 里包含 $ 的原因。把这个位置输错的人我见过很多追到底全是 FOLLOW 漏算了 $。5. 避坑记录LL(1) 实验最常见的五类翻车现场5.1 现象分析器一运行就爆栈或无限循环现象很直接程序跑起来后栈越来越大最后卡死或者抛出 RecursionError。原因几乎都是左递归没有消除干净包括间接左递归。有人遇到过明明改了文法还是爆栈后来发现改的是原始文法的副本主程序引用的还是老版本。解决方式是把消除左递归的模板做成一个通用函数自动处理 A→Aα|β 这种结构# 直接左递归消除模板把 A - Aα | β 改成 A - β A | ...A - α A | ε def remove_direct_left_recursion(nonterm, rules): alpha [r[1:] for r in rules if r[0] nonterm] beta [r for r in rules if r[0] ! nonterm] new_nonterm nonterm new_rules {original: [], new: beta, new_nonterm: new_nonterm} # 这里只返回结构实际使用时需要把 beta 右部加上 new_nonterm 再写回 return new_rules消除左递归后建议立刻用程序打印一遍所有产生式人工扫一眼是否还有 A 开头的右部。这种检查 10 秒钟就能做完能省掉半小时调试。5.2 现象FIRST 集用递归函数求解时抛 RecursionError有的学生会选择定义函数 first_of(nt) 递归地去查所有右部碰到 E→T E 再查 TT→F T 再查 F看似没有问题。但文法一旦存在一条循环路径比如 S→A 且 A→S递归就没有出口。即使当前文法没有左递归间接引用链也可能在调试中间版本时出现。解决方法是放弃递归统一改用本章代码里的 while changed 不动点迭代。迭代方式不需要调用栈状态全部存在字典里文法再乱也只是多迭代两轮不会崩。5.3 现象ε 产生式在输入结束时总选不上报错位置在最后一个符号想象输入是 idE 最终需要走 E→ε 把 E 消掉。如果 FOLLOW(E) 里没有 $预测分析表 M[E, $] 就是空的分析器走到最后一步看到栈顶 E、输入终止符 $ 时查不到规则直接报错。这种现象在调试时极其迷惑因为前面所有符号都匹配成功了看起来就差最后一步。原因就是计算 FOLLOW 时的初始化漏了。解决方式只一条记住任何 LL(1) 分析都必须在初始化阶段加一行follow[start].add($)。少了这一行所有可空非终结符在输入末尾时都找不到撤退路线。检查方法也简单打印 FOLLOW 集合看一眼有没有 $没有就是初始化漏了不是迭代算法的问题。5.4 现象输入被拆成了单个字符id 变成 i 和 d很多实验指导书里给的输入样例是 idid但学生图省事直接对字符串做遍历每次只取一个字符。结果栈顶终结符 id 永远无法和输入里的 i 匹配分析器从头错到尾。这个坑之所以普遍是因为教材里写推导过程时确实是一个符号一个符号推的让人误以为程序也应该逐字符处理。处理方式是在进分析器之前必须做一次分词把 id id * id 转成 token 列表 [id, , id, *, id]。分词的粒度必须和文法里终结符的定义一致文法里 id 是一个终结符输入里就不能把 i 和 d 分开。如果实验要求接入前面的词法分析器直接复用它的输出即可不要自己为了省事重新切字符串。5.5 现象程序发现表冲突却继续跑报出让人看不懂的错误预测分析表构建时如果某个格子被填了多条产生式程序继续运行就会随机选一条 rules[0]最终推导出的结果可能在某一步栈顶和输入完全对不上。这类报错表面上看是分析器问题实际上文法从一开始就不满足 LL(1) 条件。实战中经常是一个悬空 else 或某个公共前缀没提干净。解决方式是在主程序里把 check_conflicts 放在构建表之后、parse 之前一旦发现冲突就直接终止让使用者回到文法上找原因。千万不要让程序在冲突状态下继续跑一张有冲突的表在任何输入上产生的分析步骤都是不可信的调试它只会浪费时间。6. 验证与进阶从分析成功到给语法树加语义动作6.1 用一组正反输入验证表和分析器一组合格的测试输入至少应该覆盖四类情况最短合法输入 id嵌套括号的 (idid)id结合律相关的 ididid以及明显非法的 idid。前三个必须全部接受最后一个要在第二个加号处报错。接错时重点观察输出里的“查表无产生式”出现在哪个输入位置位置信息能反过来验证 FOLLOW 和 FIRST 是否算对。idid 的报错位置必须在第二个 如果它错误地接受了基本可以断定 E 行对应 ε 的产生式被填进了不该去的列。6.2 利用分析步骤输出回放最左推导parse 函数里保存的 steps 列表是按执行顺序记录的产生式序列把它原样打印出来就是一次最左推导的完整过程。这意味着你不需要专门写一个语法树类也能在实验报告里展示推导树每一步展开栈顶的非终结符画成树形就是一棵语法树。def print_leftmost(steps): for lhs, rhs in steps: print(f{lhs} - { .join(rhs)})这招在验收时很好用。老师如果问“你的 syntax tree 是怎么构建的”你至少可以解释为分析过程的产生式序列等价于最左推导语法树可以从中恢复而不是交一个黑匣子程序。6.3 进阶在分析动作上做表达式求值如果学有余力可以在 parse 循环的动作输出位置挂一个语义动作回调比如 E→ T E 触发 ADDT→* F T 触发 MUL。这样最终结果不只是一张接受/拒绝的判定表还能输出一个后缀表达式或求值结果。常见的做法是把 stack 里除语法符号外再附带一个值栈分析时同步压入和弹出。这一步能让实验真正连到语义分析也已经能解释“为什么 LL(1) 分析器在按产生式归约时可以顺便计算表达式”。我做这道实验保留的习惯是先在纸上手算一遍 FIRST 和 FOLLOW再让程序输出对比只要有一个符号对不上就回头查文法而不是去改分析器的栈操作。文法错了后面全部白做。这个顺序帮我避开了绝大多数无效调试。希望帮到你。本文还有配套的精品资源点击获取