南邮编译原理实验二：LL(1)语法分析器实现与避坑指南

简介这份资源是南京邮电大学编译原理实验二的语法分析实验报告面向计算机科学与技术等专业正在学习编译原理、需要完成LL(1)语法分析器实验的学生。内容围绕设计、编制并调试一个LL(1)语法分析器展开涵盖检测并消除左递归、求解FIRST集与FOLLOW集、构建LL(1)分析表以及编写分析程序对用户输入句子进行识别并显示分析过程完整呈现了从原始文法改写、集合求解过程到分析表构建与核心算法源码的实现思路。资源包为1个doc文档约937KB以实验报告形式组织包含实验目的、原理、步骤与带注释的C源代码便于对照理解算法细节与时间复杂度分析。目前已有296人学习适合需要参考实验流程、核对集合求解结果或借鉴分析程序实现的读者。1. 南邮编译原理实验二语法分析器到底要交什么如果你正在搜“南京邮电大学编译原理实验二”大概率是实验课布置了语法分析任务但讲义只给了几句模糊描述你打开 IDE 却不知道从哪下手。这个实验的核心是给定一个文法通常是赋值语句或表达式文法要求你实现一个语法分析器能判断输入串是否合法并输出分析过程。南邮的实验二一般落在 LL(1) 或 LR(1) 上具体用哪个取决于老师当年的要求。我见过最多的版本是 LL(1) 预测分析表法因为代码量可控调试直观。适合谁正在赶实验报告、需要一份能跑通的参考实现、或者想搞懂“FIRST 集到底怎么算”的本科生。下面我从文法定义一路拆到代码落地把踩过的坑全摊开。2. 文法定义与 FIRST/FOLLOW 集手算和代码怎么对齐2.1 先确认你的文法属于哪一类南邮实验二常见的文法长这样E - E T | T T - T * F | F F - ( E ) | id这是经典的表达式文法但它不是 LL(1) 文法因为存在左递归和公共左因子。如果你直接拿它去建预测分析表会发现表里有冲突项。所以第一步永远是消除左递归、提取左因子。很多同学跳过这步直接写代码结果分析表里一个格子填了两个产生式程序直接崩。消除左递归后的形式E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id这一步手算必须做对代码只是把手算结果翻译成数据结构。我一般建议先在纸上把转换后的文法写清楚再开始写任何一行代码。2.2 FIRST 集和 FOLLOW 集的代码实现手算 FIRST 集规则不复杂遇到终结符直接加入遇到非终结符看它的 FIRST遇到 ε 要继续看下一个符号。但写成代码时最容易翻车的地方是迭代终止条件。FIRST 集需要反复扫描直到不再变化很多人只扫一遍就完事导致某些非终结符的 FIRST 集不全。下面是我常用的 Python 实现骨架# 文法用字典表示key 是非终结符value 是产生式右部列表 grammar { E: [[T, E]], E: [[, T, E], [ε]], T: [[F, T]], T: [[*, F, T], [ε]], F: [[(, E, )], [id]] } terminals {, *, (, ), id, ε} non_terminals set(grammar.keys()) def compute_first(): first {nt: set() for nt in non_terminals} # 终结符的 FIRST 就是它自己 for t in terminals: first[t] {t} changed True while changed: changed False for nt, productions in grammar.items(): for prod in productions: for symbol in prod: before_len len(first[nt]) first[nt] | (first[symbol] - {ε}) if ε not in first[symbol]: break if before_len ! len(first[nt]): changed True else: # 所有符号都能推出 ε则 ε 属于 FIRST(nt) if ε not in first[nt]: first[nt].add(ε) changed True return first逻辑说明外层while changed保证迭代到不动点。内层对每条产生式逐个符号扫描如果当前符号的 FIRST 不含 ε就停止扫描这条产生式如果整条产生式所有符号都能推出 ε才把 ε 加入左部非终结符的 FIRST 集。参数方面grammar字典的 value 是产生式右部的列表每个产生式右部本身是一个符号列表ε 用字符串ε表示。FOLLOW 集的计算依赖 FIRST规则是起始符号的 FOLLOW 包含$对于产生式A - αBβ把 FIRST(β) - {ε} 加入 FOLLOW(B)如果 β 能推出 ε把 FOLLOW(A) 加入 FOLLOW(B)。代码结构类似也是迭代到不动点。2.3 预测分析表的构建与冲突检测有了 FIRST 和 FOLLOW建表逻辑就直白了def build_parsing_table(first, follow): table {} for nt, productions in grammar.items(): for prod in productions: # 计算该产生式右部的 FIRST 序列 first_seq set() for symbol in prod: first_seq | (first[symbol] - {ε}) if ε not in first[symbol]: break else: first_seq.add(ε) for t in first_seq - {ε}: if (nt, t) in table: print(f冲突: ({nt}, {t}) 已有 {table[(nt, t)]}现在要填 {prod}) table[(nt, t)] prod if ε in first_seq: for t in follow[nt]: if (nt, t) in table: print(f冲突: ({nt}, {t}) 已有 {table[(nt, t)]}现在要填 {prod}) table[(nt, t)] prod return table这段代码里我特意加了冲突打印。如果你跑出来有冲突说明文法还不是 LL(1)需要回去继续改造。常见做法是检查是否有左递归没消干净或者公共左因子没提取完整。参数first和follow就是上一步算出来的字典table的 key 是(非终结符, 终结符)元组value 是产生式右部列表。3. 驱动代码怎么写从分析栈到输出格式3.1 分析栈的核心循环预测分析器的运行时就是一个栈加一个输入指针。初始状态栈里放$和起始符号输入缓冲区末尾也放$。每一步看栈顶和当前输入符号查表决定动作。def parse(input_string, table): stack [$, E] tokens input_string.split() [$] idx 0 step 0 print(f{步骤:6}{栈:30}{当前输入:15}{动作}) while stack: top stack[-1] current tokens[idx] step 1 if top current $: print(f{step:6}{ .join(stack):30}{current:15}接受) return True if top in terminals or top $: if top current: stack.pop() idx 1 print(f{step:6}{ .join(stack):30}{current:15}匹配 {top}) else: print(f{step:6}{ .join(stack):30}{current:15}错误期望 {top}实际 {current}) return False else: prod table.get((top, current)) if prod is None: print(f{step:6}{ .join(stack):30}{current:15}错误无产生式) return False stack.pop() if prod ! [ε]: for symbol in reversed(prod): stack.append(symbol) print(f{step:6}{ .join(stack):30}{current:15}{top} - { .join(prod)}) return False逻辑说明stack用列表模拟末尾是栈顶。tokens是输入串按空格切分后的列表末尾补$。每次循环先判断栈顶和当前输入是否都是$是则接受。如果栈顶是终结符必须和当前输入匹配匹配成功就同时弹出栈顶并前进输入指针。如果栈顶是非终结符查预测分析表把产生式右部逆序压栈保证最左符号在栈顶。参数input_string是类似id id * id的字符串table就是上一步建好的预测分析表。3.2 输出格式怎么对齐实验报告要求南邮实验报告通常要求输出分析过程包括步骤号、栈内容、当前输入、所用产生式。上面代码里的print已经覆盖了这些字段。但有几个细节容易被扣分栈的输出顺序有的老师要求从栈底到栈顶打印有的要求从栈顶到栈底。我一般按 .join(stack)从底到顶输出因为这样和教材表格一致。ε 产生式的处理当产生式是E - ε时栈里不压任何东西但动作列要写E - ε不能留空。输入串的切分id id和idid要统一处理。常见做法是要求输入 token 之间用空格分隔或者写一个简单的词法预处理把id、、*、(、)切出来。如果你想让输出更接近教材风格可以把每一步的栈内容反转后再打印print(f{step:6}{ .join(reversed(stack)):30}{current:15}{top} - { .join(prod)})这样栈顶在最右边读起来更符合“栈顶在右”的习惯。具体用哪种翻一下你们实验讲义里的示例输出格式照着抄最稳。3.3 测试用例怎么设计才不漏至少准备四类输入输入串预期结果考察点id id * id接受基本表达式优先级正确( id id ) * id接受括号嵌套id * id拒绝非法符号序列id id )拒绝括号不匹配跑通这四类基本能覆盖实验验收的提问点。如果老师要求处理赋值语句把id换成id expr的形式文法相应扩展即可。4. 避坑与排查那些年我们调不出来的玄学 bug4.1 现象分析表建出来是空的原因FIRST 集计算时迭代没到不动点或者文法字典里产生式右部的符号写成了字符串而不是列表。比如E: [T E\]这种写法遍历时会把T E\当成一个整体符号而不是两个符号。解决确保每个产生式右部是列表如[T, E]。另外在 FIRST 计算的外层加一个最大迭代次数保护比如for _ in range(100)如果超过次数还没收敛打印当前 FIRST 集检查哪个非终结符没算对。4.2 现象程序在某个输入上死循环原因分析栈里出现了左递归残留。比如E - E T没消除干净查表后压栈又把E压回栈顶输入指针不动无限循环。解决在建表之前加一个检查如果任何产生式右部第一个符号等于左部非终结符直接报错。另外在parse循环里加一个步数上限比如step 1000就强制退出并打印当前栈和输入位置。4.3 现象ε 产生式导致栈里多出空字符串原因产生式右部写成[]或[ ]压栈时压入了一个空字符串后续查表找不到对应项。解决统一用ε表示空产生式压栈前判断if prod ! [ε]。如果从文件读文法读进来后做一次清洗把空字符串和纯空格都替换成ε。4.4 现象输入idid不切分被当成一个 token原因词法预处理缺失。语法分析器默认输入已经切好但很多同学直接拿原始字符串去 splitidid切出来是一个整体。解决写一个简单的正则切分函数import re def tokenize(s): pattern r\s*(id|\|\*|\(|\)|)\s* tokens re.findall(pattern, s) return tokens这个函数会把idid切成[id, , id]同时忽略多余空格。参数s是原始输入字符串返回 token 列表。注意正则里id要放在前面否则id里的字符可能被单独匹配。4.5 现象实验报告里分析表手算结果和代码输出不一致原因手算时 FOLLOW 集漏了某个符号或者代码里 FOLLOW 计算时没有把$加入起始符号。解决在 FOLLOW 计算完成后打印每个非终结符的 FIRST 和 FOLLOW 集和手算结果逐项对比。常见差异点是E的 FOLLOW 是否包含了)和$以及T的 FOLLOW 是否包含了和)。如果对不上优先检查产生式中 β 能推出 ε 时有没有把左部的 FOLLOW 传下去。5. 进阶技巧把语法分析器改成可配置的工具5.1 从硬编码到读文件上面代码里文法写死在字典里换个实验题目就得改代码。更省事的做法是把文法写进文本文件程序启动时读取。格式可以自定义比如每行一条产生式用-分隔左右部右部符号用空格隔开E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id解析这个文件的代码def load_grammar(filepath): grammar {} with open(filepath, r, encodingutf-8) as f: for line in f: line line.strip() if not line or line.startswith(#): continue left, right line.split(-) left left.strip() productions [] for alt in right.split(|): symbols alt.strip().split() productions.append(symbols if symbols else [ε]) grammar[left] productions return grammar逻辑说明按行读取跳过空行和注释行。-左边是左部非终结符右边按|切分成多个候选式每个候选式再按空格切分成符号列表。如果切出来是空列表说明是 ε 产生式统一替换成[ε]。参数filepath是文法文件路径返回和之前硬编码结构一致的字典。这样你只需要维护一个文法文件代码完全不用动。换题目时改文件就行实验验收也能现场演示。5.2 加一个简单的错误恢复基础版本遇到错误直接退出但实验验收时老师可能会问“能不能继续分析后面的部分”。一个简单的恐慌模式恢复策略是遇到错误时跳过输入符号直到找到一个能跟栈顶匹配的符号或者直到输入结束。def parse_with_recovery(input_string, table): stack [$, E] tokens input_string.split() [$] idx 0 errors [] while stack: top stack[-1] current tokens[idx] if top current $: break if top in terminals or top $: if top current: stack.pop() idx 1 else: errors.append(f位置 {idx}: 期望 {top}实际 {current}) # 跳过当前输入符号 idx 1 if idx len(tokens): break else: prod table.get((top, current)) if prod is None: errors.append(f位置 {idx}: 非终结符 {top} 遇到 {current} 无产生式) idx 1 if idx len(tokens): break else: stack.pop() if prod ! [ε]: for symbol in reversed(prod): stack.append(symbol) return errors这个版本不会在第一个错误处停止而是收集所有错误后统一返回。参数和之前一致返回值是错误信息列表。如果列表为空说明输入合法。注意这种恢复策略比较粗糙可能会产生级联错误但对于实验演示够用了。5.3 验证方法用已知文法的标准测试集最后一步验证我习惯用龙书上的经典表达式文法测试集跑一遍。具体做法是准备 10 个输入串5 个合法 5 个非法手动标注预期结果然后写一个批量测试脚本test_cases [ (id id * id, True), (( id id ) * id, True), (id * ( id id ), True), (id, True), (( id ), True), (id * id, False), (id id ), False), (( id id, False), ( id, False), (id id, False), ] for expr, expected in test_cases: tokens tokenize(expr) result parse( .join(tokens), table) status 通过 if result expected else 失败 print(f{expr:25} 预期{expected} 实际{result} {status})跑完如果全部通过基本可以交差。如果有失败优先检查 tokenize 的切分结果和预测分析表的冲突打印。从那以后我每次做语法分析实验都强制先手算一遍 FIRST 和 FOLLOW再和代码输出逐项对比确认一致后才开始写驱动代码。这个习惯帮我省了至少三个通宵的调试时间。希望帮到你。本文还有配套的精品资源点击获取