Python实现LL(1)语法分析器：FIRST/FOLLOW计算与预测表可视化

简介本资源是一份面向计算机专业本科生及编译原理初学者的语法分析实践教学材料聚焦编译器设计中核心环节——语法分析的原理理解与代码实现。资源完整覆盖上下文无关文法定义、LR(0)/LALR(1)分析表构造、递归下降解析器编写、抽象语法树生成及语法错误处理等关键知识点配套可运行代码与详细实验报告助力读者打通理论到实践的最后一环。压缩包共4个文件453KB含C源码语法分析.cpp、可执行程序语法分析.exe、实验报告文档语法分析.docx及分析过程输出示例file_out.txt类型互补、即下即用。目前已有3106人学习下载内容结构清晰、注释详尽既可用于课程实验复现也适合作为编译器开发入门的实操参考。1. 为什么一份“语法分析实验报告含代码”能让编译原理课不再玄学你刚写完词法分析器正对着 LL(1) 分析表发呆为什么预测分析栈里弹出的符号总和输入串对不上为什么 FIRST/FOLLOW 集算出来和教材例题差一个 ε为什么手推的递归下降函数一跑就段错误——这不是你数学不好而是语法分析这个环节必须在真实可执行、可调试、可断点的代码环境里反复验证。这份“语法分析实验报告含代码”不是交作业的 PDF 文档而是一套可本地一键运行、带完整测试用例、含错误注入与可视化推导过程的 Python 实现闭环。它覆盖从文法输入 → 消除左递归/提取左公因子 → 构造 FIRST/FOLLOW → 生成预测分析表 → 模拟栈式分析全过程所有中间结果如每个非终结符的 FIRST 集、分析栈每一步状态、匹配失败时的报错位置全部打印可查。适合编译原理初学者建立直觉也适合课程设计阶段快速验证文法设计合理性。如果你正在被“分析过程黑匣子”折磨或需要向老师展示“不只是抄书真跑通了”这篇就是你该立刻 clone 下来、改两行就能跑起来的救命方案。2. 用 Python 实现一个可调试的 LL(1) 语法分析器从文法定义到分析过程可视化语法分析不是背算法是让机器按你的规则一步步走并且每一步你都能看见、能打断、能改。我们不依赖 ANTLR 或 Bison 这类重型工具——它们抽象层太厚反而掩盖了 FIRST/FOLLOW 如何影响预测、栈顶符号为何要回退、ε 推导何时触发等关键细节。本方案用纯 Python3.8仅依赖标准库核心逻辑封装在LL1Parser类中所有函数命名直指语义compute_first,build_parsing_table,parse_step_by_step拒绝魔法方法。2.1 文法定义用 Python 字典描述支持 ε 和终结符/非终结符自动识别我们不写.y文件也不用 BNF 字符串解析——那会引入额外 parser偏离教学本质。直接用 Python 原生 dict 定义文法结构清晰、类型安全、IDE 可跳转# grammar.py GRAMMAR { E: [T E\], E: [ T E\, ε], T: [F T\], T: [* F T\, ε], F: [( E ), id] }注意这里ε是字符串字面量不是空字符串。这是为后续统一处理 ε 产生式预留的显式标记避免与空列表混淆。终结符如,*,(,),id和非终结符E,E,T等由程序自动识别所有出现在产生式右部但未作为左部出现的符号视为终结符所有作为左部出现的符号视为非终结符。这种推导方式与编译原理教材完全一致无需手动声明符号类型。2.2 FIRST 集计算递归 迭代混合支持 ε 传播链检测FIRST 集是 LL(1) 的基石也是最容易算错的地方。常见错误是忽略 ε 在右侧符号链中的传递性如A → B C,B → ε,C → d则d ∈ FIRST(A)。我们的compute_first函数采用“标记-传播”策略先初始化所有 FIRST 集为空集对每个产生式右部从左到右扫描若当前符号X的 FIRST 含 ε则继续看下一个若扫到末尾仍有 ε则该产生式左部也加入 ε。关键在于每次更新后触发一轮全局传播检查直到无新元素加入# parser.py def compute_first(self): first {nt: set() for nt in self.nonterminals} # 初始化终结符的 FIRST 就是自身 for t in self.terminals: first[t] {t} changed True while changed: changed False for nt, productions in self.grammar.items(): for prod in productions: symbols prod.split() if not symbols: # ε 产生式 if ε not in first[nt]: first[nt].add(ε) changed True continue # 扫描右部符号链 for i, sym in enumerate(symbols): if sym not in first: # 终结符已初始化非终结符才需计算 continue # 添加 FIRST(sym) for s in first[sym]: if s ! ε: if s not in first[nt]: first[nt].add(s) changed True # 若 sym 不含 ε停止传播 if ε not in first[sym]: break # 若是最后一个符号且含 ε则 nt 自身也含 ε if i len(symbols) - 1 and ε not in first[nt]: first[nt].add(ε) changed True return first这段代码的关键参数是symbols prod.split()—— 它把T E\拆成[T, E]正确处理带撇号的非终结符名if sym not in first:判断跳过终结符只对非终结符查 FIRSTif i len(symbols) - 1 and ε not in first[nt]:是 ε 传播的终止条件确保只有整条链都可空时左部才加 ε。这比教科书伪代码更贴近实际执行流调试时打个断点一眼看出哪步漏了传播。2.3 FOLLOW 集计算三类规则全覆盖支持循环依赖检测FOLLOW 集依赖 FIRST且存在隐式循环如A → B C,B → D,D → A。我们的实现严格对应龙书 P224 的三条规则FOLLOW(S) {$}S 为开始符号若A → α B β则FIRST(β) - {ε} ⊆ FOLLOW(B)若A → α B或A → α B β且ε ∈ FIRST(β)则FOLLOW(A) ⊆ FOLLOW(B)为防无限循环我们设置最大迭代轮数默认 10并在每次更新后检查是否收敛def compute_follow(self, first): follow {nt: set() for nt in self.nonterminals} follow[self.start_symbol].add($) # 规则1 changed True iteration 0 while changed and iteration 10: iteration 1 changed False for nt, productions in self.grammar.items(): for prod in productions: symbols prod.split() if not symbols: continue # 规则2 3找所有形如 X Y Z 的位置 for i, sym in enumerate(symbols): if sym not in self.nonterminals: # 跳过终结符 continue # 检查 sym 后是否有符号 if i 1 len(symbols): beta symbols[i1:] # 计算 FIRST(beta) - {ε} first_beta set() for j, b_sym in enumerate(beta): if b_sym in first: first_beta.update(first[b_sym] - {ε}) if ε not in first[b_sym]: break else: # b_sym 是终结符 first_beta.add(b_sym) break else: # 全部 beta 都含 ε if ε in first.get(beta[-1], set()): first_beta.add(ε) # 加入 FOLLOW(sym) for s in first_beta - {ε}: if s not in follow[sym]: follow[sym].add(s) changed True # 规则3若 ε ∈ FIRST(beta)则 FOLLOW(nt) ⊆ FOLLOW(sym) if ε in first_beta: for s in follow[nt]: if s not in follow[sym]: follow[sym].add(s) changed True else: # sym 在产生式末尾规则3 for s in follow[nt]: if s not in follow[sym]: follow[sym].add(s) changed True return follow重点看beta symbols[i1:]和first_beta的构建逻辑它模拟了“从第 i1 个符号开始逐个取 FIRST遇到不含 ε 的就停”。else子句处理整条 beta 都含 ε 的情况此时first_beta会包含ε从而触发规则3。这个实现能正确处理A → B,B → C,C → A这类循环文法只要 FOLLOW 集最终收敛比很多网上简版代码更鲁棒。3. 构建预测分析表并驱动栈式分析让每一步推导都可追溯、可断点有了 FIRST/FOLLOW下一步是生成预测分析表Parsing Table——这是 LL(1) 的心脏。表的行是非终结符列是终结符含$值为对应产生式编号或None。构造逻辑简单对每个产生式A → α对每个a ∈ FIRST(α)设M[A, a] A → α若ε ∈ FIRST(α)则对每个b ∈ FOLLOW(A)设M[A, b] A → α。但真正难的是错误诊断当M[A, a]为空时如何告诉用户“此处应输入什么”我们的方案在构建表时同步记录每个空格的“期望符号集”即FOLLOW(A)若 α 可空或FIRST(α)若不可空用于后续报错。3.1 预测分析表生成二维字典 期望符号集缓存def build_parsing_table(self, first, follow): table {} expected {} # { (A, a): set of expected symbols } for nt in self.nonterminals: table[nt] {} for t in self.terminals | {$}: table[nt][t] None expected[(nt, t)] set() for nt, productions in self.grammar.items(): for idx, prod in enumerate(productions): symbols prod.split() # 情况1prod 不含 ε if symbols and symbols[0] ! ε: first_alpha set() for i, sym in enumerate(symbols): if sym in first: first_alpha.update(first[sym] - {ε}) if ε not in first[sym]: break else: # 终结符 first_alpha.add(sym) break else: # 全部符号都含 ε if ε in first.get(symbols[-1], set()): first_alpha.add(ε) for a in first_alpha - {ε}: if a in self.terminals or a $: if table[nt][a] is not None: raise ValueError(fConflict in table[{nt}][{a}]: {table[nt][a]} vs {prod}) table[nt][a] (idx, prod) expected[(nt, a)] first_alpha - {ε} # 情况2prod 是 ε 产生式 if ε in [s.strip() for s in symbols] or (len(symbols) 1 and symbols[0] ε): for b in follow[nt]: if b in self.terminals or b $: if table[nt][b] is not None: raise ValueError(fConflict in table[{nt}][{b}]: {table[nt][b]} vs ε) table[nt][b] (idx, ε) expected[(nt, b)] follow[nt] return table, expected关键点在于expected字典它存储(A, a)对应的“理论上此处应出现的符号集合”。比如E → T E的FIRST是{}所以table[E\][] (0, T E\)且expected[(E\, )] {}而E → ε的FOLLOW(E) {$, )}所以table[E\][$] (1, ε)且expected[(E\, $)] {$, )}。这个expected将在解析失败时直接输出“期待符号$ 或 )但得到 ”。3.2 栈式分析器逐帧打印支持单步调试与失败定位分析器核心是一个stack初始为[$, start_symbol]和一个input_streamtoken 列表末尾加$。每轮循环取栈顶X和当前输入符号a若X a $成功若X是终结符且X a匹配弹栈读下一个 token若X是非终结符且table[X][a]有产生式则弹栈X压入该产生式右部逆序因为栈是 LIFO否则报错用expected[(X, a)]给出明确提示def parse_step_by_step(self, input_tokens): input_stream input_tokens [$] stack [$, self.start_symbol] steps [] i 0 # input pointer step_num 0 while stack: step_num 1 top stack[-1] a input_stream[i] # 成功退出 if top $ and a $: steps.append(fStep {step_num}: Accept! Stack{stack}, Input{input_stream[i:]}) break # 匹配终结符 if top in self.terminals: if top a: steps.append(fStep {step_num}: Match {top}. Stack{stack[:-1]}, Input{input_stream[i1:]}) stack.pop() i 1 else: expected_set self.expected.get((top, a), set()) if not expected_set: expected_set {top} # fallback raise SyntaxError(fStep {step_num}: Expected {expected_set}, got {a} at position {i}) # 非终结符查表 elif top in self.nonterminals: if a not in self.table[top] or self.table[top][a] is None: expected_set self.expected.get((top, a), self.follow[top]) raise SyntaxError(fStep {step_num}: No entry for {top} on {a}. Expected {expected_set}, got {a}) idx, prod self.table[top][a] stack.pop() if prod ! ε: # 逆序压入因栈顶在右 for symbol in reversed(prod.split()): stack.append(symbol) steps.append(fStep {step_num}: Apply {top} → {prod}. Stack{stack}, Input{input_stream[i:]}) else: raise RuntimeError(fUnknown symbol {top} on stack) return steps注意reversed(prod.split())这是栈式分析的关键。例如E → T E栈中E被替换为E T逆序这样T在栈顶下一轮先匹配T。steps列表记录每一步的完整状态可直接打印或写入报告。你甚至可以加一行if step_num 100: raise RuntimeError(Infinite loop detected)防止死循环。4. 避坑LL(1) 实验中最常踩的 5 个坑附现象、原因与血泪解法写语法分析器不是调通就行是得知道哪里会翻车、为什么翻车、怎么一眼定位。以下是我在带 3 届学生做实验时高频出现的 5 类问题每一条都来自真实 debug 记录。4.1 现象FIRST(E)算出来含但预测表table[E\][]是None原因文法中E → T E | εFIRST( T E) {}正确但代码里prod.split()把 T E\拆成[, T, E]而first[]未初始化因是终结符但你的first字典只初始化了非终结符。解决在compute_first开头必须显式初始化所有终结符的 FIRST 集for t in self.terminals: first[t] {t}。终结符不能靠“查不到就跳过”来处理否则后续first[sym]会 KeyError。4.2 现象FOLLOW(T)包含*但table[T\][*]仍为空原因T → * F T | ε*是终结符FIRST(* F T) {*}所以table[T\][*]应填* F T。但你的build_parsing_table里对prod.split()后的第一个符号*误判为非终结符因没检查sym in self.terminals导致跳过first_alpha计算。解决在build_parsing_table中对symbols[0]必须先判断if symbols[0] in self.terminals:若是终结符first_alpha {symbols[0]}直接赋值不进循环。4.3 现象输入id id正确但id * id报错 “No entry for T on *”原因FOLLOW(T) {, ), $}漏了*因为T → F T所以FOLLOW(T)应包含FOLLOW(T)而T出现在E → T E中FOLLOW(T) FIRST(E) - {ε} ∪ FOLLOW(E)FIRST(E) {, ε}FOLLOW(E) {$, )}故FOLLOW(T) {, $, )}FOLLOW(T) FOLLOW(T) {, $, )}——但*是T自身产生式左部T → * F T所以*不在FOLLOW(T)中它应该由FIRST(* F T)填表。报错说明table[T\][*]没填根源是prod.split()后symbols[0]是*而你的代码没处理终结符开头的产生式。解决同 4.2必须显式处理终结符开头的产生式。4.4 现象parse_step_by_step([id, , id, $])运行卡死stack变成[$, E, E\, T, T\, F, id]后不再变化原因id是终结符栈顶id与输入id匹配应弹栈。但你的匹配逻辑写成if top a: stack.pop(); i 1却忘了top是ida是id匹配成功但下一轮stack[-1]是F而input_stream[i]已是table[F][]为空应报错但你的代码没 catch 这个分支进入无限循环。解决match分支后必须continue确保每轮只执行一个动作nonterminal分支前加elif避免 fall-through最后加else: raise RuntimeError捕获未定义行为。4.5 现象报告里FIRST(F) {(, id}正确但table[F][id]是None而table[F][(]正常原因F → ( E ) | idFIRST(( E )) {(}FIRST(id) {id}两者无冲突。但你的build_parsing_table循环里对prod idsymbols [id]symbols[0]是终结符应直接first_alpha {id}但代码里for i, sym in enumerate(symbols): ...循环体没处理sym是终结符的情况导致first_alpha为空。解决在build_parsing_table的symbols循环前加判断if len(symbols) 1 and symbols[0] in self.terminals:则first_alpha {symbols[0]}。提示所有这些坑根源都是没严格区分终结符与非终结符的处理路径。建议在__init__里打印self.terminals和self.nonterminals集合确认id,,*,(,)都在terminals里E,E,T,T,F都在nonterminals里。一个字符之差满盘皆输。5. 实验报告落地如何用这套代码生成符合附录规范的完整报告实验报告不是代码截图文字堆砌而是让代码自己说话。我们用 Python 的rich库pip install rich生成带颜色、表格、缩进的终端输出再重定向到.txt或.md文件直接满足“附录代码格式”要求——代码高亮、注释对齐、关键数据加框、错误示例分隔。整个流程无需 Word 排版命令行一键生成。5.1 自动生成报告框架标题、文法、FIRST/FOLLOW 表、分析步骤# report_generator.py from rich.console import Console from rich.table import Table from rich.text import Text from rich.panel import Panel from rich.syntax import Syntax def generate_report(parser, input_tokens): console Console(recordTrue, width120) # 标题 console.print(Panel([bold cyan]LL(1) 语法分析实验报告[/bold cyan], expandFalse)) # 文法 console.print(\n[bold green]1. 输入文法[/bold green]) for nt, prods in parser.grammar.items(): console.print(f[yellow]{nt}[/yellow] → | .join([f[blue]{p}[/blue] for p in prods])) # FIRST 表 console.print(\n[bold green]2. FIRST 集[/bold green]) first_table Table(show_headerTrue, header_stylebold magenta) first_table.add_column(非终结符, stylecyan) first_table.add_column(FIRST 集, stylegreen) for nt in sorted(parser.nonterminals): first_set , .join(sorted(parser.first[nt])) first_table.add_row(nt, f{{{first_set}}}) console.print(first_table) # FOLLOW 表 console.print(\n[bold green]3. FOLLOW 集[/bold green]) follow_table Table(show_headerTrue, header_stylebold magenta) follow_table.add_column(非终结符, stylecyan) follow_table.add_column(FOLLOW 集, stylered) for nt in sorted(parser.nonterminals): follow_set , .join(sorted(parser.follow[nt])) follow_table.add_row(nt, f{{{follow_set}}}) console.print(follow_table) # 预测分析表部分 console.print(\n[bold green]4. 预测分析表节选[/bold green]) table Table(show_headerTrue, header_stylebold magenta) headers [] sorted(parser.terminals | {$})[:6] # 取前6列防过宽 table.add_column(headers[0], stylecyan) for h in headers[1:]: table.add_column(h, styleyellow) for nt in sorted(parser.nonterminals)[:4]: # 取前4行 row [nt] for t in headers[1:]: entry parser.table[nt].get(t, None) if entry is None: row.append([dim]—[/dim]) else: idx, prod entry row.append(f[blue]{prod}[/blue]) table.add_row(*row) console.print(table) # 分析过程 console.print(\n[bold green]5. 输入串分析过程[/bold green]) try: steps parser.parse_step_by_step(input_tokens) for step in steps: console.print(step) except SyntaxError as e: console.print(f[bold red]Syntax Error:[/bold red] {e}) # 附录源码 console.print(\n[bold green]附录核心代码片段[/bold green]) with open(parser.py, r, encodingutf-8) as f: code f.read() syntax Syntax(code[:2000] \n...略, python, thememonokai, line_numbersTrue) console.print(syntax) # 输出到文件 console.save_text(ll1_report.txt) print(✅ 报告已生成ll1_report.txt) if __name__ __main__: from parser import LL1Parser from grammar import GRAMMAR p LL1Parser(GRAMMAR) p.build_all() # compute first/follow/table generate_report(p, [id, , id, *, id])运行python report_generator.py输出ll1_report.txt内容如下节选┌───────────────────────────────────────────────────────────────────────────────┐ │ LL(1) 语法分析实验报告 │ └───────────────────────────────────────────────────────────────────────────────┘ 1. 输入文法 E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id 2. FIRST 集 ┌──────────┬───────────────────┐ │ 非终结符 │ FIRST 集 │ ├──────────┼───────────────────┤ │ E │ {(, id} │ │ E │ {, ε} │ │ F │ {(, id} │ │ T │ {(, id} │ │ T │ {*, ε} │ └──────────┴───────────────────┘ 3. FOLLOW 集 ┌──────────┬───────────────────┐ │ 非终结符 │ FOLLOW 集 │ ├──────────┼───────────────────┤ │ E │ {$, )} │ │ E │ {$, )} │ │ F │ {, *, ), $} │ │ T │ {, ), $} │ │ T │ {, ), $} │ └──────────┴───────────────────┘ 4. 预测分析表节选 ┌────┬────┬────┬────┬────┬────┬────┐ │ │ $ │ ( │ ) │ │ * │ id │ ├────┼────┼────┼────┼────┼────┼────┤ │ E │ — │ 0 │ — │ — │ — │ 0 │ │ E │ 1 │ — │ 1 │ 0 │ — │ — │ │ F │ — │ 0 │ — │ — │ — │ 1 │ │ T │ — │ 0 │ — │ — │ — │ 0 │ └────┴────┴────┴────┴────┴────┴────┘ 5. 输入串分析过程 Step 1: Apply E → T E. Stack[$, E\, T], Input[id, , id, *, id, $] Step 2: Apply T → F T. Stack[$, E\, T\, F], Input[id, , id, *, id, $] Step 3: Apply F → id. Stack[$, E\, T\, id], Input[id, , id, *, id, $] Step 4: Match id. Stack[$, E\, T\], Input[, id, *, id, $] ...这个报告的价值在于所有数据FIRST/FOLLOW/表/步骤都是代码实时计算、实时渲染绝无手填错误。老师抽查任意一行你都能当场python parser.py复现。5.2 附录代码格式如何让代码块符合“附录代码格式”搜索热词要求网络热词“附录代码格式”指向高校实验报告的硬性排版规范代码必须等宽字体、行号、关键行高亮、无多余空行、缩进统一为 4 空格。rich.syntax.Syntax默认满足前三点我们只需微调行号line_numbersTrue已启用等宽字体thememonokai渲染为等宽关键行高亮用highlight_lines{12, 25, 47}参数标出compute_first、build_parsing_table、parse_step_by_step的入口行缩进确保源码本身用 4 空格black格式化pip install black black parser.py# 在 generate_report 中替换 syntax 行 syntax Syntax( code, python, thememonokai, line_numbersTrue, start_line1, highlight_lines{12, 25, 47, 89}, # 手动记下这四行是核心函数 def 行 word_wrapFalse )我的习惯每次提交报告前用diff ll1_report.txt ll1_report_old.txt看差异——如果 FIRST 集变了一定是文法改了如果分析步骤数变了一定是输入串改了。代码不是报告的附件它是报告的活体心脏。希望帮到你。本文还有配套的精品资源点击获取