企业官网建设流程全解析

简介：这份资源是南京邮电大学编译原理实验二的语法分析实验报告，面向计算机科学与技术等专业正在学习编译原理、需要完成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和id+id要统一处理。常见做法是要求输入 token 之间用空格分隔，或者写一个简单的词法预处理把id、+、*、(、)切出来。

如果你想让输出更接近教材风格，可以把每一步的栈内容反转后再打印：

print(f"{step:<6}{' '.join(reversed(stack)):<30}{current:<15}{top} -> {' '.join(prod)}")

这样栈顶在最右边，读起来更符合“栈顶在右”的习惯。具体用哪种，翻一下你们实验讲义里的示例输出格式，照着抄最稳。

3.3 测试用例怎么设计才不漏

至少准备四类输入：

跑通这四类，基本能覆盖实验验收的提问点。如果老师要求处理赋值语句，把id换成id = expr的形式，文法相应扩展即可。

4. 避坑与排查：那些年我们调不出来的玄学 bug

4.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 现象：输入id+id不切分，被当成一个 token

原因：词法预处理缺失。语法分析器默认输入已经切好，但很多同学直接拿原始字符串去 split，id+id切出来是一个整体。

解决：写一个简单的正则切分函数：

import re def tokenize(s): pattern = r'\s*(id|\+|\*|\(|\)|=)\s*' tokens = re.findall(pattern, s) return tokens

这个函数会把id+id切成['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', encoding='utf-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，再和代码输出逐项对比，确认一致后才开始写驱动代码。这个习惯帮我省了至少三个通宵的调试时间。希望帮到你。

本文还有配套的精品资源，点击获取