简介这份资源是南京邮电大学编译原理实验二的语法分析实验报告面向计算机科学与技术等专业正在学习编译原理、需要完成LL(1)语法分析器实验的学生。内容围绕设计、编制并调试一个LL(1)语法分析器展开涵盖检测并消除左递归、求解FIRST集与FOLLOW集、构建LL(1)分析表以及编写LL分析程序对用户输入句子进行分析并显示过程等完整环节报告中给出了详细的求解步骤与结果。资源包为1个doc文档压缩包约937KB以实验报告形式呈现包含实验目的、原理、步骤、分析表构建及核心算法源代码与时间复杂度分析便于对照理解与复现。目前已有296人学习适合需要参考实验流程、核对集合求解结果或借鉴分析程序实现思路的同学使用。1. 南京邮电大学编译原理实验二语法分析到底在考什么如果你在南邮读计算机相关专业翻到编译原理实验二的指导书大概率会看到一段类似“对词法分析输出的 Token 序列进行语法分析判断是否符合给定文法并输出分析过程”的描述。很多同学第一反应是打开 Visual Studio 或者 Dev-C准备手写一个递归下降分析器结果发现实验要求里还提到了 LL(1) 分析表、FIRST 集、FOLLOW 集甚至要求把分析栈的变化过程打印出来。这时候才意识到实验二不是让你“感觉一下语法分析”而是让你把一整套自顶向下或自底向上的分析流程完整跑通。这个实验的核心目标很明确给定一个文法构造分析表然后对输入串进行推导或归约最终判断它是不是该文法能生成的合法句子。南邮的实验通常会给一个简化语言的文法比如赋值语句、算术表达式、if-else 结构要求你实现 LL(1) 或者 LR(1) 分析器。如果你只是把代码跑通不关心 FIRST/FOLLOW 集怎么算、分析表怎么填那实验验收的时候老师随便改一个输入串你就不知道栈里为什么报错了。适合谁看正在做南邮编译原理实验二、被 FIRST/FOLLOW 集和分析表卡住、或者代码能跑但说不清原理的同学。下面我按实际做实验的顺序把文法预处理、集合计算、分析表构造、驱动程序设计、以及调试时最容易翻车的地方拆开讲。你照着走至少能少熬两个晚上。2. 文法预处理与 FIRST/FOLLOW 集手算和代码算怎么对齐2.1 为什么实验二第一步不是写代码而是整理文法南邮实验二通常会给一个类似下面的文法不同年份可能微调但结构差不多E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id这个文法已经是消除左递归、提取左公因子之后的 LL(1) 文法。但很多同学拿到的是原始文法比如E - E T | T这时候必须先做左递归消除否则递归下降会直接死循环。实验指导书里一般会要求你“对给定文法进行预处理”但不会手把手教你每一步。我一般会先把文法写成产生式集合用|拆成单条然后检查有没有直接左递归和间接左递归。直接左递归的形式是A - A α | β消除方法是改成A - β AA - α A | ε。间接左递归需要先代入再消除。这一步如果偷懒后面 FIRST/FOLLOW 集算出来全是错的分析表也跟着错。血泪经验先把文法整理成 LL(1) 形式再动手写任何代码。2.2 FIRST 集和 FOLLOW 集的代码实现用 Python 跑一遍就清楚手算 FIRST 集的时候规则看起来简单如果 X 是终结符FIRST(X) {X}如果 X 是非终结符且有产生式 X - Y1Y2...Yk把 FIRST(Y1) 中非 ε 的符号加进去如果 Y1 能推出 ε继续看 Y2以此类推。但手算三四个非终结符还行一旦文法有十几个产生式漏掉一个 ε 就会导致后面全错。我一般用 Python 写一个小脚本把文法读进去迭代计算到不动点。# 文法用字典表示key 是非终结符value 是产生式右部列表 # 每个产生式右部用空格分隔的符号串表示ε 表示空串 grammar { E: [T E\], E\: [ T E\, ε], T: [F T\], T\: [* F T\, ε], F: [( E ), id] } non_terminals set(grammar.keys()) terminals set() for prods in grammar.values(): for prod in prods: for sym in prod.split(): if sym not in non_terminals and sym ! ε: terminals.add(sym) FIRST {nt: set() for nt in non_terminals} FOLLOW {nt: set() for nt in non_terminals} FOLLOW[E] {$} # 开始符号的 FOLLOW 集包含结束符 # 迭代计算 FIRST 集 changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: symbols prod.split() if symbols [ε]: if ε not in FIRST[nt]: FIRST[nt].add(ε) changed True continue for sym in symbols: if sym in terminals: if sym not in FIRST[nt]: FIRST[nt].add(sym) changed True break else: before len(FIRST[nt]) FIRST[nt] | (FIRST[sym] - {ε}) if len(FIRST[nt]) ! before: changed True if ε not in FIRST[sym]: break else: if ε not in FIRST[nt]: FIRST[nt].add(ε) changed True # 迭代计算 FOLLOW 集 changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: symbols prod.split() for i, sym in enumerate(symbols): if sym in non_terminals: rest symbols[i1:] if rest: first_rest set() for s in rest: if s in terminals: first_rest.add(s) break else: first_rest | (FIRST[s] - {ε}) if ε not in FIRST[s]: break else: first_rest.add(ε) before len(FOLLOW[sym]) FOLLOW[sym] | (first_rest - {ε}) if ε in first_rest: FOLLOW[sym] | FOLLOW[nt] if len(FOLLOW[sym]) ! before: changed True else: before len(FOLLOW[sym]) FOLLOW[sym] | FOLLOW[nt] if len(FOLLOW[sym]) ! before: changed True print(FIRST 集) for nt in sorted(FIRST): print(f FIRST({nt}) {sorted(FIRST[nt])}) print(FOLLOW 集) for nt in sorted(FOLLOW): print(f FOLLOW({nt}) {sorted(FOLLOW[nt])})这段代码的关键点在于FIRST 集计算时遇到非终结符要先把它的 FIRST 集去掉 ε并进来如果它不能推出 ε 就停止如果能推出 ε继续看下一个符号。FOLLOW 集计算时对每个产生式右部找到非终结符后面的符号串求这个串的 FIRST 集如果这个 FIRST 集包含 ε还要把左部非终结符的 FOLLOW 集加进来。参数说明grammar字典的 value 是产生式右部列表每个右部用空格分隔符号ε单独作为一个符号处理。跑一遍就能得到和手算一致的结果而且改文法后不用重新手算。注意很多同学在 FOLLOW 集里忘记加$导致分析表最后一列是空的遇到输入串结束时不知道用哪个产生式归约。开始符号的 FOLLOW 集一定要手动加上$。3. 构造 LL(1) 分析表从集合到二维表的映射3.1 分析表每个格子填什么用产生式编号还是产生式本身LL(1) 分析表的行是非终结符列是终结符包括$格子里填的是产生式。常见做法是给每个产生式编号比如E - T E是第 1 条E - T E是第 2 条这样打印分析过程时只显示编号看起来干净。但调试的时候我建议先填产生式本身因为编号容易对错尤其是文法一长改一条产生式就要重新编号。填表规则对每个产生式A - α计算 FIRST(α)。对于 FIRST(α) 中的每个终结符 a把A - α填入M[A][a]。如果 FIRST(α) 包含 ε那么对于 FOLLOW(A) 中的每个终结符 b把A - α填入M[A][b]。如果同一个格子被填了两次说明文法不是 LL(1) 的需要改写文法或者换用 LR 分析。# 接上面的 FIRST 和 FOLLOW 计算结果 table {nt: {} for nt in non_terminals} productions [] # 存储 (左部, 右部, 编号) for nt, prods in grammar.items(): for prod in prods: productions.append((nt, prod, len(productions) 1)) for nt, prod, pid in productions: symbols prod.split() first_alpha set() if symbols [ε]: first_alpha.add(ε) else: for sym in symbols: if sym in terminals: first_alpha.add(sym) break else: first_alpha | (FIRST[sym] - {ε}) if ε not in FIRST[sym]: break else: first_alpha.add(ε) for a in first_alpha - {ε}: if a in table[nt]: print(f冲突M[{nt}][{a}] 已有 {table[nt][a]}现在要填 {pid}) table[nt][a] pid if ε in first_alpha: for b in FOLLOW[nt]: if b in table[nt]: print(f冲突M[{nt}][{b}] 已有 {table[nt][b]}现在要填 {pid}) table[nt][b] pid # 打印分析表 all_terminals sorted(terminals | {$}) print(LL(1) 分析表) print(f{:8}, end) for t in all_terminals: print(f{t:8}, end) print() for nt in sorted(non_terminals): print(f{nt:8}, end) for t in all_terminals: pid table[nt].get(t, ) print(f{pid:8}, end) print()这段代码里productions列表把每个产生式编号方便后面驱动程序引用。填表时先处理 FIRST 集中的终结符再处理 ε 情况下的 FOLLOW 集。如果出现冲突打印出来这就是文法不是 LL(1) 的证据。参数说明table是二维字典table[nt][t]存储产生式编号。打印时用固定宽度对齐方便肉眼检查。3.2 用栈驱动 LL(1) 分析器把分析过程打印成一张表分析表构造好之后驱动程序就是一个循环初始化栈为[$, E]E 是开始符号输入指针指向第一个 Token然后看栈顶和当前输入符号。如果栈顶是终结符且和当前输入匹配弹出栈顶并移动输入指针如果栈顶是非终结符查分析表把栈顶替换成产生式右部的逆序如果栈顶是$且输入也是$接受否则报错。def ll1_parse(input_tokens, table, start_symbolE): stack [$, start_symbol] pos 0 steps [] while stack: top stack[-1] current input_tokens[pos] if pos len(input_tokens) else $ steps.append((list(stack), current, )) if top $ and current $: steps[-1] (list(stack), current, 接受) break if top in terminals or top $: if top current: stack.pop() pos 1 steps[-1] (list(stack), current, f匹配 {top}) else: steps[-1] (list(stack), current, f报错期望 {top}实际 {current}) break else: pid table.get(top, {}).get(current) if pid is None: steps[-1] (list(stack), current, f报错M[{top}][{current}] 为空) break prod productions[pid - 1][1] stack.pop() if prod ! ε: for sym in reversed(prod.split()): stack.append(sym) steps[-1] (list(stack), current, f用产生式 {pid}: {top} - {prod}) return steps # 测试输入id id * id tokens [id, , id, *, id, $] steps ll1_parse(tokens, table) print(f{栈:30} {当前输入:10} {动作}) for s in steps: print(f{ .join(s[0]):30} {s[1]:10} {s[2]})这段代码把每一步的栈内容、当前输入符号和动作都记录下来最后打印成表格。参数说明input_tokens是词法分析输出的 Token 列表末尾要加$table是上一步构造的分析表start_symbol默认是E。跑id id * id应该能一路接受跑id * id会在某一步报错。这个打印格式可以直接贴到实验报告里老师一看就知道你确实理解了栈的变化过程。提示如果实验要求用 LR 分析思路类似但栈里存的是状态而不是符号分析表是 ACTION 和 GOTO 两张表。南邮实验二多数年份默认 LL(1)但指导书如果写了 SLR 或 LR(1)就按 LR 的来。4. 避坑与排查语法分析实验里最容易翻车的五个地方4.1 现象程序能跑但所有输入串都报错原因FIRST 集或 FOLLOW 集算错导致分析表里很多格子是空的。最常见的是忘记处理 ε 产生式或者 FOLLOW 集没有传递。解决把 FIRST 和 FOLLOW 集打印出来和手算结果逐行对比。重点检查E和T这种带 ε 的产生式它们的 FOLLOW 集应该包含左部非终结符的 FOLLOW 集。4.2 现象输入id id能过输入( id id ) * id就崩原因括号匹配处理有问题。LL(1) 分析器本身不检查括号是否匹配它只按文法推导。如果文法里F - ( E )写对了分析表也填对了括号嵌套应该能处理。崩的原因往往是词法分析输出的 Token 里括号被识别成了别的符号或者输入串末尾忘了加$。解决先单独测试词法分析输出确认(和)是独立的 Token再检查分析器输入末尾有没有$。4.3 现象分析表出现冲突程序不知道该选哪条产生式原因文法不是 LL(1) 的。比如A - aB | aC这种左公因子没提取或者存在左递归。解决先消除左递归再提取左公因子。如果改完还有冲突说明这个文法本身不是 LL(1)需要换 LR 分析方法。南邮实验二一般给的是 LL(1) 文法如果出现冲突先检查自己有没有抄错产生式。4.4 现象栈里符号顺序反了导致匹配不上原因用产生式替换栈顶时右部符号入栈顺序搞反了。比如产生式E - T E应该先把E入栈再把T入栈这样栈顶才是T。如果先入T再入E栈顶变成E下一步就查错了。解决入栈时用reversed(prod.split())或者手动从右往左压栈。4.5 现象实验报告里分析过程打印成一坨老师看不懂原因没有格式化输出。解决用表格打印每一步的栈、当前输入和动作栈用空格分隔动作写清楚是“匹配”还是“用产生式 X”。如果实验要求输出推导过程可以把每一步用的产生式编号单独列出来形成最左推导序列。这样报告看起来专业验收时也能快速定位问题。5. 从 LL(1) 到 LR实验二想拿高分可以多走一步南邮编译原理实验二的评分通常分几档能跑通给及格能打印分析过程给良好能处理错误输入并给出有意义报错给优秀。如果你已经完成了 LL(1) 分析器想再往上走一步我建议把 LR 分析也实现一遍至少把 SLR(1) 的 ACTION 表和 GOTO 表构造出来。原因很简单LL(1) 的文法限制比较强很多实际语言的文法不是 LL(1) 的而 LR 能处理的文法范围更广。实验二如果只做 LL(1)老师可能会问“如果文法有左递归怎么办”这时候你能说出 LR 的思路印象分直接拉满。具体做法在 LL(1) 的基础上增加项目集规范族的构造。先定义增广文法比如S - E然后从I0 closure({S - ·E})开始对每个项目集和每个文法符号求 GOTO直到没有新的项目集产生。然后根据项目集之间的转移关系填 ACTION 和 GOTO 表。ACTION 表里如果项目A - α·aβ且 a 是终结符填移进如果项目A - α·对 FOLLOW(A) 中的每个符号填归约如果项目S - S·遇到$填接受。冲突处理是 SLR(1) 的难点如果出现移进-归约冲突默认移进如果出现归约-归约冲突说明文法不是 SLR(1) 的。我当年做实验二的时候LL(1) 部分花了两个晚上LR 部分又花了一个周末。但把 LR 分析器跑通之后再看编译原理后面的语义分析和中间代码生成思路清晰了很多。因为 LR 分析器天然适合在归约时执行语义动作后面做语法制导翻译会顺手很多。如果你时间紧至少把 SLR(1) 的框架搭出来能对简单表达式文法跑通就行。最后一个习惯每次改文法先把 FIRST/FOLLOW 集重新打印一遍确认没变错再跑分析器。不要觉得“只改了一个符号应该没事”我见过太多因为改了一个产生式导致分析表全错、然后熬夜找 bug 的情况。希望帮到你。本文还有配套的精品资源点击获取