简介这份资源是南京邮电大学编译原理实验二的语法分析实验报告面向计算机科学与技术等专业正在学习编译原理、需要完成LL(1)语法分析器实验的学生。内容围绕设计、编制并调试一个LL(1)语法分析器展开涵盖检测并消除左递归、求解FIRST集与FOLLOW集、构建LL(1)分析表以及编写分析程序对用户输入句子进行识别并显示分析过程完整呈现了从文法改写、集合推导到分析表构造与核心算法实现的思路。压缩包内共1个doc文档约937KB以实验报告形式记录了实验目的、原理、步骤与C源代码及注释并附有时间复杂度分析便于对照理解与复现。目前已有296人学习适合需要参考实验流程、核对集合求解过程或借鉴分析程序实现的读者使用。1. 南京邮电大学编译原理实验二语法分析到底在考什么如果你正在做南京邮电大学编译原理实验二大概率已经写完了词法分析手里攥着一串 Token却卡在“怎么让程序看懂a b c * d;这种句子的结构”上。语法分析要解决的就是这件事把线性的 Token 序列变成一棵能体现运算优先级和嵌套关系的语法树。实验二通常要求你实现一个自顶向下或自底向上的分析器能判断输入串是否合法并在合法时输出推导过程或语法树。它适合已经掌握正规式、有限自动机但还没真正写过递归下降或 LR 分析表的同学。很多人以为语法分析就是套个模板真动手才发现左递归、FIRST 集冲突、错误恢复这些坑一个比一个硬。这篇笔记就按南邮实验二的常见要求把选型、代码、参数和排错一次讲透让你能直接复现并跑通。2. 先定文法再写代码南邮实验二常见的两类实现路线2.1 递归下降 vs LR 分析实验二到底该选哪条路南邮编译原理实验二通常给出一段类 C 或类 Pascal 的文法要求实现语法分析。你面前有两条路递归下降和 LRSLR/LLR。递归下降写起来快适合文法没有左递归、没有公共左因子的情况LR 分析器更通用但需要构造分析表实验里往往要求你手写或程序生成 ACTION/GOTO 表。我一般会先看实验指导书里的文法形式。如果产生式里出现E → E T这种直接左递归递归下降必须改写成E → T E、E → T E | ε否则程序会无限递归。如果实验要求输出“最右推导的逆过程”或“规范归约”那基本就是 LR 路线。南邮实验二多数年份偏向递归下降因为代码量可控调试直观。但如果你选 LR实验报告里能写的东西更多得分上限也高。选型时还要看错误处理要求。递归下降可以在每个函数入口检查 Token 是否匹配出错时直接报“第 X 行缺少右括号”LR 分析器则依赖分析表里的 error 项错误恢复更复杂。实验二通常只要求“发现错误并给出位置”递归下降足够。提示先翻实验指导书最后两页的测试用例。如果用例里有大量嵌套括号和混合运算递归下降的调用栈会变深但一般不会爆栈如果用例里有if-else悬挂问题LR 的移进-归约冲突处理会更稳。2.2 把文法改写成 LL(1) 的四个固定动作假设实验二给的是经典表达式文法E → E T | T T → T * F | F F → ( E ) | id要改成递归下降能用的 LL(1) 文法按下面四步走。第一步消除直接左递归。对E → E T | T引入新非终结符E写成E → T E E → T E | ε第二步对T做同样处理T → F T T → * F T | ε第三步检查是否有公共左因子。上面F → ( E ) | id没有公共前缀不用提取。第四步求 FIRST 和 FOLLOW 集验证 LL(1) 条件。E的 FIRST 是{, ε}FOLLOW 是{), #}T的 FIRST 是{*, ε}FOLLOW 是{, ), #}。只要同一非终结符的多个产生式 FIRST 集不相交或者其中一个能推出 ε 且 FIRST 与 FOLLOW 不相交就是 LL(1)。改写后的文法直接对应递归下降代码结构每个非终结符一个函数函数体里按 FIRST 集选分支遇到 ε 产生式就返回。2.3 用 Python 写一个可跑的递归下降分析器下面这段代码可以直接作为实验二的核心实现。它读取词法分析输出的 Token 列表每个 Token 是(类型, 值)元组类型包括id、num、、*、(、)、#。# 递归下降语法分析器对应改写后的 LL(1) 文法 # Token 格式: (type, value)输入末尾必须带 (#, #) tokens [] # 全局 Token 列表 pos 0 # 当前 Token 下标 def peek(): 返回当前 Token不移动指针 return tokens[pos] def match(expected_type): 匹配并消费一个 Token失败则报错 global pos if tokens[pos][0] expected_type: pos 1 else: raise SyntaxError( f第 {tokens[pos][1]} 处期望 {expected_type}实际 {tokens[pos][0]} ) def parse_E(): E - T E parse_T() parse_E_prime() def parse_E_prime(): E - T E | ε if peek()[0] : match() parse_T() parse_E_prime() # 否则按 ε 处理直接返回 def parse_T(): T - F T parse_F() parse_T_prime() def parse_T_prime(): T - * F T | ε if peek()[0] *: match(*) parse_F() parse_T_prime() def parse_F(): F - ( E ) | id | num if peek()[0] (: match(() parse_E() match()) elif peek()[0] id: match(id) elif peek()[0] num: match(num) else: raise SyntaxError(f第 {peek()[1]} 处期望表达式实际 {peek()[0]}) def parse(token_list): 入口函数返回 True 表示语法正确 global tokens, pos tokens token_list pos 0 try: parse_E() match(#) # 必须消费到结束符 return True except SyntaxError as e: print(语法错误:, e) return False逻辑说明peek()只看不消费match()消费并校验。parse_E_prime和parse_T_prime里的if就是按 FIRST 集选分支没有或*时自动走 ε。parse_F处理括号和原子。最后match(#)保证整个输入被完整消费防止a b后面多出)这种错误被漏掉。参数说明tokens必须由词法分析器生成末尾加(#,#)作为结束标记。pos是全局下标递归调用时共享。如果你实验里 Token 类型名不同比如用ID而不是id把match里的字符串改掉即可。2.4 测试用例与输出验证跑通下面三组用例基本能覆盖实验二的评分点# 用例 1合法表达式 print(parse([(id,a), (,), (id,b), (*,*), (id,c), (#,#)])) # 输出 True # 用例 2括号嵌套 print(parse([((,(), (id,a), (,), (id,b), (),)), (*,*), (id,c), (#,#)])) # 输出 True # 用例 3缺少右括号 print(parse([((,(), (id,a), (,), (id,b), (#,#)])) # 输出 语法错误: 第 # 处期望 )实际 #如果实验要求输出语法树可以在每个parse_X函数里返回节点对象比如parse_E返回Node(E, left, right)最后打印树形结构。南邮实验二多数只要求判断合法性并输出错误位置上面代码已经够用。3. 实验二避坑与排查左递归、FIRST 集冲突和错误恢复3.1 左递归没消除导致栈溢出现象程序运行后报RecursionError: maximum recursion depth exceeded或者直接卡死。原因文法里还有E → E T这种直接左递归递归下降函数parse_E第一件事就是调用parse_E永远不消费 Token。解决按 2.2 节的方法改写成右递归引入E。检查所有非终结符包括间接左递归比如A → B、B → A这种环也要先代入消除。3.2 FIRST 集算错导致选错分支现象输入a * b时parse_E_prime看到*却走了 ε 分支结果match(#)失败。原因E的 FIRST 集只算了忘了ε也在 FIRST 里但*属于 FOLLOW 集不应该由E处理。解决重新求 FIRST 和 FOLLOW。E的 FIRST 是{, ε}FOLLOW 是{), #}。*在T的 FIRST 里所以parse_T_prime会消费它。用一张表把每个非终结符的 FIRST/FOLLOW 列出来对照代码里的if条件。3.3 错误位置报不准现象输入a b程序报“第 b 处期望 id”但实际错误在第二个。原因parse_E_prime消费了第一个后调用parse_Tparse_T调用parse_Fparse_F看到才报错此时pos已经指向b。解决在match失败时用当前 Token 的位置而不是下一个 Token。更稳的做法是在parse_F的else分支里直接报peek()[1]不要等match。另外词法分析阶段记录每个 Token 的行号和列号报错时输出行列实验报告里更专业。3.4 忘记处理结束符现象输入a b )程序返回 True。原因parse_E只消费到b后面的)没检查match(#)也没加。解决入口函数最后必须match(#)确保所有 Token 被消费。如果实验要求允许尾随空白或注释在词法阶段过滤掉语法阶段只认#。3.5 用 LR 时移进-归约冲突没处理现象构造 SLR 分析表时某个状态同时有移进和归约动作程序不知道选哪个。原因文法不是 SLR(1)或者 FOLLOW 集算错。解决先检查文法是否有二义性比如if-else悬挂。如果是实验二通常不会给二义性文法如果给了按“移进优先”解决并在报告里说明。另外确认 ACTION 表和 GOTO 表的列对应正确的非终结符。4. 从能跑到能交实验二报告里该写清楚的三个细节4.1 把 FIRST/FOLLOW 集表格化实验报告里不要只贴代码评审老师会看你对 LL(1) 的理解。用一张表列出每个非终结符的 FIRST 和 FOLLOW非终结符FIRSTFOLLOWE{ (, id, num }{ ), # }E{ , ε }{ ), # }T{ (, id, num }{ , ), # }T{ *, ε }{ , ), # }F{ (, id, num }{ *, , ), # }这张表直接对应代码里的分支条件。如果实验要求输出预测分析表把每个产生式填到M[非终结符, 终结符]格子里空项就是 error。4.2 错误恢复至少做一种南邮实验二通常要求“发现错误后能继续分析”或“至少报出第一个错误”。我一般会在match失败时抛异常入口捕获后打印错误并返回 False。如果要求继续可以在parse_F的else分支里跳过当前 Token然后返回一个占位节点让上层继续。但这样容易产生连锁错误报告里要说明你只保证报出第一个错误。4.3 用脚本批量跑测试用例手动输入 Token 列表太慢写个脚本把实验指导书里的用例转成 Token 序列# 批量测试用例来自实验指导书 cases [ a b * c, ( a b ) * c, a b, a b ), ] for expr in cases: toks lex(expr) [(#,#)] # lex 是你词法分析函数 print(expr, , parse(toks))这样能快速回归改文法后不用一个个手敲。lex函数返回的 Token 类型要和语法分析器约定一致否则会误报。5. 进阶技巧用预测分析表自动生成递归下降代码如果你已经跑通了手写递归下降可以再往前一步用预测分析表自动生成分析器。这样做的好处是文法改了不用改代码只改表。具体做法是先构造 LL(1) 预测分析表然后写一个通用驱动器# 通用 LL(1) 驱动器table 是预测分析表 # table[非终结符][终结符] 产生式右部列表 def ll1_parse(token_list, table, start_symbol): stack [#, start_symbol] tokens token_list [(#,#)] pos 0 while stack: top stack.pop() cur tokens[pos][0] if top cur: # 匹配终结符 pos 1 elif top in table: # 非终结符查表 prod table[top].get(cur) if prod is None: print(f错误{cur} 无法由 {top} 推导) return False # 逆序压栈保证左部先处理 for sym in reversed(prod): if sym ! ε: stack.append(sym) else: print(f错误期望 {top}实际 {cur}) return False return True逻辑说明栈里放的是待匹配符号#是底。每次看栈顶和当前 Token如果相同就消费如果栈顶是非终结符就查表把产生式右部逆序压栈。table可以用字典嵌套字典表示比如table[E][id] [T, E]。参数说明start_symbol是文法开始符token_list末尾不用加#函数内部会加。这个驱动器只有 20 行但能处理任何 LL(1) 文法。实验报告里可以对比手写递归下降和表驱动说明表驱动的可维护性更好。我自己的习惯是先用递归下降快速验证文法再用表驱动做最终提交因为表驱动不容易漏掉 ε 分支。最后说个血泪教训实验二最耗时的不是写代码而是调文法。我一般会先把 FIRST/FOLLOW 集手算一遍再写代码否则改一个产生式就要重新推一遍。另外词法分析器输出的 Token 类型一定要和语法分析器约定死别一边用id一边用ID这种低级错误能让你查一晚上。希望帮到你。本文还有配套的精品资源点击获取