手写递归下降语法分析器：从LL(1)文法改写到Python实现

简介本资源是一份面向计算机专业本科生及编译原理初学者的语法分析实验教学文档聚焦算术表达式子集的语法检查与结构分析实践帮助学习者掌握LL(1)预测分析等核心语法分析方法。文档完整覆盖实验目的、BNF文法定义含E→T|ET|E−T等简化规则、LL(1)文法改写过程、预测分析表构建逻辑及C实现源码含分析栈、符号栈操作、错误提示机制等关键细节并提供测试用例设计规范与典型错例反馈示例。资源为单个Word文档.doc大小127KB内容精炼、结构清晰适合作为课程实验报告模板或自主调试参考。目前已有143人学习下载可直接用于编译原理课程实验二的方案设计、代码实现与结果验证全过程。1. 为什么手写一个语法分析器比直接调yacc更能救你的编译原理期末设计“实验二——语法分析程序设计与实现.doc” 这个标题对计算机专业本科生来说不是文档名是学期中期的血压计。它背后藏着的不是 Word 文件而是一段必须亲手敲出来的、能真正读入字符串、输出语法树或错误提示、经得起老师现场输入测试用例的灵魂代码。你查到的热搜词——LL(1)、递归下降、算符优先、LR(1)——不是选择题选项而是四条不同难度的逃生通道LL(1)适合教学闭环递归下降最易调试算符优先专治表达式LR(1)强大但容易在状态机里迷路。本篇不讲理论推导不贴教科书定义只还原我带三届学生做这个实验的真实路径从文法设计开始踩坑到用 Python 写出可单步调试的递归下降分析器再到用ply验证 LR(1) 的边界行为。所有代码可在 Windows/macOS/Linux 下零依赖运行所有错误信息都来自真实翻车现场——比如next_token()返回 None 却没判空导致 SegFaultPython 里是AttributeError比如FIRST/FOLLOW集算错一个终结符让整个预测表失效。如果你正对着.doc文件发呆不确定该选哪种方法、怎么验证自己没写错、或者被“预测分析表为空”卡住三天这篇就是为你写的血泪复现笔记。2. 从文法出发为什么先改写文法比急着写代码重要十倍语法分析器不是万能翻译器它是严格按文法规则工作的机械裁判。而实验二给的文法通常是类 C 或简化 Pascal 的子集往往自带“陷阱”左递归、公共左因子、二义性。不提前处理后面所有代码都在给错误买单。我带学生做的第一件事永远是打开纸笔把原始文法抄下来逐条过筛。2.1 识别并消除左递归别让E → E T | T毁掉你的递归下降左递归是递归下降分析器的死穴。看这个经典表达式文法E → E T | T T → T * F | F F → ( E ) | id如果直接按此写parse_E()函数会无休止调用自身直到栈溢出。必须改写。标准消除法是引入新非终结符和右递归E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id提示ε 表示空产生式代码中对应“什么也不做直接 return”。不要试图用if token 判断那是逻辑错误——空产生式触发条件是预测成功但无需消耗输入由FIRST/E集决定。2.2 提取公共左因子解决if和if-else的歧义冲突常见控制流文法S → if ( B ) S | if ( B ) S else S | other这会产生公共左因子if ( B ) S导致FIRST集重叠无法构造 LL(1) 分析表。正确改写为S → if ( B ) S S | other S → else S | ε注意S的FIRST是{else}FOLLOW(S)是{else, $}$ 表示输入结束所以else对应S → else S而$对应S → ε。这个细节决定你后续预测表是否填得满。2.3 验证改写后文法是否满足 LL(1) 条件三步手工检查法改写完别急着编码用三步法快速验证无左递归检查每个非终结符的产生式左部没有形如A → Aα的规则无公共左因子对每个A → α₁ | α₂ | ... | αₙ确保FIRST(αᵢ) ∩ FIRST(αⱼ) ∅i ≠ j对含 ε 的产生式满足FIRST(α) ∩ FOLLOW(A) ∅例如A → α | ε则FIRST(α)和FOLLOW(A)不能有交集。我让学生用 Excel 表格列FIRST/FOLLOW集每行一个非终结符每列一个终结符手动打勾。这不是形式主义——90% 的预测表为空错误根源都在这里没过第三关。3. 递归下降实现用 Python 写出可单步调试的分析器主干递归下降是实验二最推荐的起点逻辑直白、调试友好、无需生成预测表。核心思想是——每个非终结符对应一个函数函数体就是该产生式的“执行版”。我们以改写后的表达式文法为例构建最小可行骨架。3.1 词法分析器接口约定next_token()和match()是基石语法分析器不负责切词但必须和词法器无缝协作。我们约定两个函数next_token()返回下一个Token对象含.type如,id,(.value如a,123调用一次消耗一个 tokenmatch(expected_type)检查当前 token 类型是否为expected_type是则调用next_token()推进否则报错。# token.py class Token: def __init__(self, type_, valueNone): self.type type_ self.value value # lexer.py简化版实际需完整实现 tokens [id, , *, (, ), $] # 终结符集合 def next_token(): # 实际从输入流读取此处用全局变量模拟 global token_stream, pos if pos len(token_stream): t token_stream[pos] pos 1 return t return Token($) # 输入结束标记 def match(expected_type): global lookahead if lookahead.type expected_type: lookahead next_token() else: raise SyntaxError(fExpected {expected_type}, got {lookahead.type})逻辑说明lookahead是当前待处理 tokennext_token()推进指针。match()不仅校验还自动推进——这是递归下降的契约漏掉next_token()就会导致无限循环。3.2 非终结符函数编写parse_E()到parse_F()的逐层展开按文法E → T EE → T E | εT → F TT → * F T | εF → ( E ) | id编写# parser.py def parse_E(): parse_T() parse_Eprime() def parse_Eprime(): if lookahead.type : match() parse_T() parse_Eprime() # 右递归对应 E → T E # else: ε 产生式什么也不做 def parse_T(): parse_F() parse_Tprime() def parse_Tprime(): if lookahead.type *: match(*) parse_F() parse_Tprime() # ε 分支隐含 def parse_F(): if lookahead.type id: match(id) elif lookahead.type (: match(() parse_E() match()) else: raise SyntaxError(fExpected id or (, got {lookahead.type})参数说明所有函数无参数依赖全局lookahead。这是教学实现的权衡——避免传递 token 流增加复杂度。生产环境建议用类封装状态。3.3 主程序与错误恢复如何让SyntaxError不直接崩掉整个流程主程序需初始化lookahead并捕获异常# main.py from lexer import next_token, match, Token from parser import parse_E token_stream [Token(id, a), Token(), Token(id, b), Token($)] pos 0 lookahead next_token() # 预读第一个 token try: parse_E() print(Parsing successful!) except SyntaxError as e: print(fSyntax error at position {pos}: {e})关键点lookahead必须在parse_*调用前初始化且所有match()都基于它。错误信息包含pos当前 token 索引方便定位——这是比line:col更底层、更可控的调试粒度。4. 预测分析表构造与驱动当递归下降不够用时LL(1) 表驱动才是正解递归下降适合小文法但实验二若要求“支持完整 if-while 语句”手动写parse_IfStmt()容易遗漏嵌套分支。此时必须上预测分析表Predictive Parsing Table用二维表驱动分析过程这才是“语法分析程序设计”的题眼。4.1 手工计算 FIRST 和 FOLLOW 集三个必须掌握的规则FIRST(X)从 X 出发能推出的所有可能首终结符集合含 εFOLLOW(A)在某句型中紧跟在 A 后面的所有可能终结符集合含 $规则描述示例FIRST 规则 1若 X 是终结符则FIRST(X) {X}FIRST() {}FIRST 规则 2若 X → ε 是产生式则 ε ∈FIRST(X)E → ε ⇒ ε ∈ FIRST(E)FIRST 规则 3若 X → Y₁Y₂...YₖY₁⇒ε, Y₂⇒ε, ..., Yᵢ₋₁⇒ε则FIRST(Yᵢ) ⊆ FIRST(X)若所有 Yⱼ ⇒ε则 ε ∈FIRST(X)E → T E ⇒ ∈ FIRST(E)E → ε ⇒ ε ∈ FIRST(E)FOLLOW计算更易错牢记三点FOLLOW(S)总含$S 是开始符号若A → αBβ则FIRST(β) \ {ε} ⊆ FOLLOW(B)若A → αB或A → αBβ且β ⇒* ε则FOLLOW(A) ⊆ FOLLOW(B)。我让学生用颜色笔标出每条产生式对FOLLOW的贡献比纯文字推导快 3 倍。4.2 构造预测分析表填表不是暴力枚举而是精准映射对每个产生式A → α对每个a ∈ FIRST(α)将A → α填入M[A, a]若ε ∈ FIRST(α)则对每个b ∈ FOLLOW(A)将A → α填入M[A, b]。以E → T E | ε为例FIRST( T E) {}→M[E, ] E → T Eε ∈ FIRST(ε)→FOLLOW(E) {$, )}→M[E, $] E → ε,M[E, )] E → ε注意M[A, a]必须唯一。若同一格填入多个产生式说明文法非 LL(1)必须回退修改文法。4.3 表驱动分析器实现用栈模拟推导过程核心是维护一个符号栈自顶向下和输入缓冲区自左向右# predictive_parser.py def parse_with_table(): stack [$, E] # 栈底 $栈顶 E input_tokens [Token(id), Token(), Token(id), Token($)] pos 0 while stack: top stack.pop() current_token input_tokens[pos] if top current_token.type: pos 1 # 匹配成功消耗 token elif top in non_terminals and (top, current_token.type) in parse_table: # 查表得到产生式右部逆序压栈 rhs parse_table[(top, current_token.type)] if rhs ! [ε]: # ε 产生式不压栈 for symbol in reversed(rhs): stack.append(symbol) else: raise SyntaxError(fNo entry for ({top}, {current_token.type}))逻辑说明stack模拟推导的最左推导序列reversed(rhs)是因为栈是 LIFO而产生式右部从左到右应用。[ε]不压栈直接跳过——这是 ε 处理的关键。5. 避坑指南LL(1) 实现中最常踩的 5 个深坑及血泪解法这章不讲道理只列真实翻车现场。每一条都来自学生提交的第 3~7 版代码。5.1 现象predictive_parser.py运行时KeyError: (E, id)原因parse_table字典未覆盖所有(non_terminal, terminal)组合尤其忽略了FOLLOW集中的$和)。例如E的FOLLOW是{$, )}但表只填了()导致遇到)时查不到。解决初始化parse_table时对每个非终结符 A 和每个终结符 a含$先设为None填表后遍历所有(A, a)打印None的位置人工补全或确认文法缺陷。5.2 现象分析器对a b * c输出正确但对a * b c报错原因FIRST/T/FOLLOW(T)计算错误。T → * F T | εFOLLOW(T) FOLLOW(T) {, ), $}但误算成{*, , ), $}导致M[T, *]被错误填入T → ε而非T → * F T。解决用print(FIRST, FOLLOW)调试对比标准答案。特别注意FOLLOW传递链——T的FOLLOW来自T → F T中的FOLLOW(T)而FOLLOW(T)来自E → T E中的FIRST(E)\{ε}即和FOLLOW(E)即{$, )}。5.3 现象parse_F()中match(()成功但parse_E()后match())失败报Expected ), got $原因parse_E()执行后lookahead已指向)后的 token如$因为parse_E()内部消耗了)后的 token。根本错误是match()函数设计缺陷——它无条件推进但)应由parse_F()的外层match())消耗。解决match()必须严格只匹配当前lookahead匹配成功才调next_token()。检查所有match()调用点确保没有重复next_token()。5.4 现象递归下降版本能跑通但预测表版本在id处卡死栈不断压入F原因F → id的FIRST(id) {id}正确但F → ( E )的FIRST(( E )) {(}也正确问题出在parse_table[(F, id)]被错误填为F → ( E )因FIRST计算时混淆了括号和 id。解决FIRST计算必须区分终结符字面量。id是终结符类型(是另一终结符二者绝不相等。用字符串精确比较禁用模糊匹配。5.5 现象程序输出Parsing successful!但输入a b )多一个右括号也通过原因错误恢复缺失。分析器在)处匹配失败后未跳过非法 token而是直接退出循环pos未走到$却误判为成功。解决主循环结束后必须检查pos len(input_tokens)-1 and input_tokens[pos].type $。若不满足说明输入未完全消耗属于语法错误。6. 进阶验证用 PLY 验证 LR(1) 行为看清 LL(1) 的能力边界实验二要求“设计与实现”但没说只能用一种方法。当你用递归下降/预测表跑通后下一步是用工业级工具反向验证——PLYPython Lex-Yacc能自动生成 LR(1) 分析器它比 LL(1) 更强大能处理更多文法。用它不是为了替代作业而是为了看清自己手写的 LL(1) 在哪卡住。6.1 用 PLY 实现同一文法三步写出可运行的 LR(1) 分析器PLY 要求定义tokens终结符列表、precedence运算符优先级、p_*函数产生式动作# calc.py import ply.yacc as yacc import ply.lex as lex tokens (ID, PLUS, TIMES, LPAREN, RPAREN) def p_expression_plus(p): expression : expression PLUS term p[0] (, p[1], p[3]) def p_expression_term(p): expression : term p[0] p[1] def p_term_times(p): term : term TIMES factor p[0] (*, p[1], p[3]) def p_term_factor(p): term : factor p[0] p[1] def p_factor_id(p): factor : ID p[0] (id, p[1]) def p_factor_expr(p): factor : LPAREN expression RPAREN p[0] (paren, p[2]) # 优先级声明解决 和 * 的结合性 precedence ( (left, PLUS), (left, TIMES), ) parser yacc.yacc() result parser.parse(a b * c) print(result) # (, (id, a), (*, (id, b), (id, c)))关键点PLY 默认生成 LALR(1)LR(1) 的优化版precedence声明让其自动解决移进-归约冲突。这正是 LL(1) 无法处理的——它要求文法无二义性而a b * c的二义性由优先级规则化解。6.2 对比 LL(1) 与 LR(1) 的文法支持能力一张表看清本质差异场景LL(1) 是否支持LR(1) 是否支持原因E → E TT左递归❌ 必须改写✅ 原生支持if E then S else S/if E then S悬空 else⚠️ 需改写为S → if E then S S✅ 用优先级或状态转移自然处理LL(1) 依赖FIRST集分离LR(1) 依赖上下文运算符优先级vs*❌ 需拆成E/T/F多层非终结符✅ 用precedence声明一行解决LL(1) 无“上下文感知”LR(1) 有 Lookahead token文法含公共左因子❌ 必须提取✅ 无影响LL(1) 预测表要求FIRST不交LR(1) 用状态区分6.3 用 PLY 暴露手写 LL(1) 的盲区一个实操技巧把你的手写 LL(1) 文法直接喂给 PLY观察其报错# test_grammar.py # 将你的 LL(1) 文法改写后复制为 PLY 产生式 def p_E(p): E : T Eprime pass def p_Eprime(p): Eprime : PLUS T Eprime | empty # empty 对应 ε pass运行yacc.yacc(debugTrue)PLY 会输出shift/reduce或reduce/reduce冲突。这些冲突点就是你手写 LL(1) 时靠FIRST/FOLLOW计算规避掉的雷区——它告诉你哪些看似安全的改写在更严格的 LR(1) 视角下仍有隐患。我带学生做这一步时常发现他们FOLLOW(E)漏掉了)PLY 直接报reduce/reduce conflict in state 5比手动推导快 10 倍。这不再是作业验收而是真正理解“语法分析”作为编译前端核心环节的工程重量。最后说一句实在话这个实验的价值不在交一份.doc而在你亲手让一段字符串经过next_token()、match()、parse_E()、FIRST集、预测表、栈操作最终变成一棵树。过程中摔的每一跤都在重塑你对“程序如何被理解”的直觉。我至今保留着第一届学生交的parser.py里面# TODO: handle error recovery的注释还没删——但那行注释比任何完美代码都真实。希望帮到你。本文还有配套的精品资源点击获取