尧图网页设计 、逆波兰式与LR(1)完整实现)
简介本资源是编译原理课程实验的完整配套资料面向计算机专业学生及需要动手实现编译前端的学习者围绕词法分析器设计、LL(1)分析法、逆波兰式生成与计算、LR(1)分析法四个核心实验展开帮助读者把课堂理论落到可运行的代码上。压缩包共35个文件约789KB以cpp源码、docx实验报告、txt与md说明文档为主另含xls数据表、png示意图及项目目录配置源码与文档相互对应便于对照理解。资源中每个实验均配有参考资料与演示目录README.md提供编译运行与调试指引读者可据此复现词法单元扫描、预测分析表构造、后缀表达式求值与LR状态栈规约等关键流程并在此基础上修改扩展。目前已有150人学习下载适合作为课程实验参考与期末复习的实操素材。1. 编译原理实验四件套从词法分析到 LR(1) 的一条完整落地路线很多人学编译原理课本翻到第三章就卡住了正则表达式、NFA、DFA 推导看着都懂真让你写一个能跑的词法分析器或者手撸一张 LL(1) 分析表立刻原形毕露。这个标题对应的正是一套把「词法分析器、LL(1) 分析法、逆波兰式生成及计算、LR(1) 分析法」串起来的实验工程配套源码和文档说明。它解决的不是单点问题而是让你亲手把编译器前端最核心的四块拼图拼完整先切词再做语法分析自上而下和自下而上两条路线中间穿插表达式求值这条贯穿线。适合正在做编译原理实验的本科生、准备考研复试手写分析器的同学以及想用 Java 或 Python 把课本理论跑成可调试代码的工程师。下面我按实际动手顺序把每一步的选择理由、参数设置和翻车点讲清楚。2. 词法分析器把字符流切成 Token 流的最小可用实现词法分析器是整个前端的入口它的输出质量直接决定后面语法分析器好不好写。这一章先把「怎么切」讲透再给一份能直接跑的代码。2.1 为什么用 DFA 而不是一堆 if-else新手最容易犯的错是拿一长串if-else判断字符遇到标识符、数字、注释就层层嵌套最后自己都读不懂。正规做法是先定义正则再转成 DFA用状态转移表驱动。核心原因是DFA 的状态和转移是数据不是控制流改词法规则时只改表不动逻辑。常见做法是手工构造 DFA或者用工具生成。实验里我一般手写状态表因为要能调试、能打印每一步状态。词法单元至少覆盖关键字、标识符、整数/浮点常量、运算符、界符、空白与注释。关键字识别有个小技巧——先按标识符规则读完整串再查关键字表不要为每个关键字单独开状态。2.2 一份可复现的 Token 定义与扫描主循环下面用 Python 写核心骨架逻辑和 Java 版一致方便对照。# token 类型常量 KEYWORDS {if, else, while, int, float, return} OPERATORS {, -, *, /, , , , , , } class Token: def __init__(self, ttype, value, line, col): self.ttype ttype # 类别ID / NUM / KW / OP / EOF self.value value # 原始字面量 self.line line # 行号报错定位用 self.col col # 列号 def tokenize(src): tokens [] i, line, col 0, 1, 1 n len(src) while i n: ch src[i] # 跳过空白同时维护行列号 if ch in \t\r: i 1; col 1; continue if ch \n: i 1; line 1; col 1; continue # 标识符 / 关键字 if ch.isalpha() or ch _: start, sc i, col while i n and (src[i].isalnum() or src[i] _): i 1; col 1 word src[start:i] ttype KW if word in KEYWORDS else ID tokens.append(Token(ttype, word, line, sc)); continue # 数字整数与小数 if ch.isdigit(): start, sc i, col while i n and src[i].isdigit(): i 1; col 1 if i n and src[i] .: i 1; col 1 while i n and src[i].isdigit(): i 1; col 1 tokens.append(Token(NUM, src[start:i], line, sc)); continue # 双字符运算符优先匹配 if i 1 n and src[i:i2] in OPERATORS: tokens.append(Token(OP, src[i:i2], line, col)) i 2; col 2; continue if ch in OPERATORS: tokens.append(Token(OP, ch, line, col)) i 1; col 1; continue raise SyntaxError(f非法字符 {ch!r} 于 {line}:{col}) tokens.append(Token(EOF, , line, col)) return tokens逻辑说明主循环按「空白 → 标识符 → 数字 → 双字符运算符 → 单字符运算符」的优先级顺序判断这个顺序不能乱。如果把单字符运算符判断放在双字符前面会被拆成两个后面语法分析直接崩。参数上line和col必须全程维护否则报错时只能告诉用户「有错」定位不到位置调试成本翻倍。提示双字符运算符一定要先于单字符匹配这是词法分析里最经典的顺序坑。2.3 词法分析器的三个必调参数与验证方法第一最长匹配原则。读到时不能停在要贪心往后看一位。第二回溯点。手工 DFA 里如果多读了一个字符才发现不匹配要能把指针退回去常见做法是记录start和当前i。第三错误恢复策略。遇到非法字符是直接抛异常还是跳过继续收集后续 Token取决于你要不要一次性报出所有错误。实验里我建议先抛异常简单可控。验证方法很直接准备一组覆盖所有 Token 类型的测试串跑完后打印 Token 序列人工核对类别和值。再准备一组故意写错的串确认报错行列号准确。3. LL(1) 分析法FIRST/FOLLOW 集怎么算、预测分析表怎么填词法过了进入自上而下的语法分析。LL(1) 是理解递归下降和预测分析的最佳跳板也是实验里最容易被 FIRST/FOLLOW 集绕晕的一章。3.1 FIRST、FOLLOW 集的手算规则与代码实现FIRST(A) 是 A 能推导出的所有串的首终结符集合。规则三条若 A → a…a 是终结符把 a 加入 FIRST(A)若 A → ε把 ε 加入 FIRST(A)若 A → B…把 FIRST(B) 中除 ε 外的元素加入 FIRST(A)若 B 能推出 ε继续看下一个符号。FOLLOW(A) 则是所有句型中紧跟在 A 后面的终结符集合起始符号的 FOLLOW 含结束符$。代码实现用不动点迭代反复扫描产生式直到集合不再变化。def first_of_seq(seq, first, nullable): # 求一个符号串的 FIRST 集 result set() for sym in seq: if sym not in first: # 终结符 result.add(sym); return result result | (first[sym] - {ε}) if ε not in first[sym]: return result result.add(ε) # 所有符号都可空 return result def build_first(grammar, nonterms, first): changed True while changed: changed False for head, bodies in grammar.items(): for body in bodies: add first_of_seq(body, first, None) if not add first[head]: first[head] | add; changed True逻辑说明first_of_seq处理的是产生式右部这个符号串遇到终结符直接收尾遇到非终结符先并入其 FIRST 去掉 ε再看它是否可空决定要不要继续。build_first用changed标志做不动点循环直到没有新元素加入。参数上grammar是{非终结符: [产生式右部列表]}的结构每个右部是符号列表。3.2 预测分析表的构造与冲突判定有了 FIRST 和 FOLLOW填表规则是对每条产生式 A → α对 FIRST(α) 中每个终结符 a把 A → α 填进M[A][a]若 α 可空对 FOLLOW(A) 中每个终结符 b也填入 A → α。填完后如果某个格子出现两条产生式这个文法就不是 LL(1)需要提取左公因子或消除左递归。步骤操作判断依据1消除左递归存在 A → Aα 形式2提取左公因子多条产生式右部前缀相同3计算 FIRST 集不动点迭代4计算 FOLLOW 集起始符含 $5填预测分析表检查格子冲突分析时用一个栈初始压入$和起始符号读入 Token 流栈顶是非终结符就查表展开是终结符就和当前 Token 比对一致则同时弹出并前进。这套流程跑通后递归下降分析器基本就是它的代码化版本。注意LL(1) 只能处理无左递归、无回溯的文法表达式文法通常要先改写别指望原样套用。4. 逆波兰式中缀转后缀、求值以及它和语法分析的关系逆波兰式后缀表达式是这套实验里最实用的一块它既是表达式求值的经典方案也是理解语法树后序遍历的直观入口。4.1 调度场算法中缀转后缀的完整实现核心是运算符栈加输出队列。遇到操作数直接输出遇到运算符把栈顶优先级不低于它的运算符弹出输出再压栈遇到左括号压栈遇到右括号弹到左括号为止。def infix_to_rpn(tokens): prec {: 1, -: 1, *: 2, /: 2} out, ops [], [] for t in tokens: if t.ttype NUM: out.append(t.value) elif t.value (: ops.append(t.value) elif t.value ): while ops and ops[-1] ! (: out.append(ops.pop()) ops.pop() # 弹出左括号 elif t.value in prec: while (ops and ops[-1] in prec and prec[ops[-1]] prec[t.value]): out.append(ops.pop()) ops.append(t.value) while ops: out.append(ops.pop()) return out逻辑说明prec定义优先级保证左结合性比如a-b-c会正确转成ab-c-。参数上输入是词法分析器产出的 Token 列表输出是字符串列表。如果支持一元负号需要在遇到-且前一个 Token 是运算符或左括号时特殊处理这是最常见的扩展点。4.2 后缀表达式求值与除零、类型处理求值用一个操作数栈遇到数字压栈遇到运算符弹出两个操作数计算后压回。def eval_rpn(rpn): stack [] for tok in rpn: if tok in {, -, *, /}: b stack.pop(); a stack.pop() if tok : stack.append(a b) elif tok -: stack.append(a - b) elif tok *: stack.append(a * b) else: if b 0: raise ZeroDivisionError(除数为零) stack.append(a / b) else: stack.append(float(tok)) return stack[0]逻辑说明注意弹出顺序是b先、a后减法和除法不满足交换律顺序反了结果就错。参数上整数和浮点统一按float处理如果实验要求区分int和float要在 Token 里保留类型标记求值时按类型分派。提示逆波兰式求值天然对应语法树的后序遍历理解这一点后面 LR 分析的语义动作就好接了。5. LR(1) 分析法项目集规范族、分析表与移进归约冲突排查LR(1) 是自下而上分析的硬骨头也是实验里最能拉开差距的部分。它比 LL(1) 强在能处理更多文法代价是状态构造复杂。5.1 LR(1) 项目与闭包、GOTO 的构造LR(1) 项目是[A → α·β, a]点表示分析位置a是向前看符号。闭包运算若项目[A → α·Bβ, a]中 B 是非终结符对每条 B 的产生式B → γ和 FIRST(βa) 中每个终结符 b把[B → ·γ, b]加入闭包。GOTO 函数则把点右移一位后求闭包。构造流程从增广文法的起始项目[S → ·S, $]出发反复求闭包和 GOTO直到没有新状态。状态数通常比 LALR(1) 多但冲突更少。5.2 分析表的 ACTION 与 GOTO 填写ACTION 表按项目类型填点后是终结符 a填移进到 GOTO 状态点是末尾且向前看符号是 a填归约[S → S·, $]填接受。GOTO 表填非终结符的转移。填完后检查冲突移进-归约冲突和归约-归约冲突。冲突类型现象常见处理移进-归约同一格子既可移进又可归约优先移进或改写文法归约-归约同一格子两条归约文法有歧义需重构状态爆炸状态数过多考虑 LALR(1) 合并同心项目集分析驱动和 LL(1) 类似用状态栈加符号栈读入 Token 查 ACTION 表决定移进还是归约归约时按产生式长度弹栈再查 GOTO。5.3 用表达式文法验证 LR(1) 分析器拿E → E T | T、T → T * F | F、F → ( E ) | id这套经典文法跑一遍输入id id * id确认分析过程正确归约最终接受。再输入id * id确认在错误位置报错。这一步能验证 ACTION/GOTO 表填得对不对也能暴露向前看符号算错的问题。6. 避坑与排查这套实验里最容易翻车的五个地方6.1 词法阶段把拆成两个现象语法分析报莫名其妙的错误表达式判断全部失效。原因单字符运算符判断放在了双字符前面或者根本没做双字符匹配。解决严格按最长匹配先查双字符表再查单字符代码里把双字符判断写在前面。6.2 FIRST/FOLLOW 集迭代不收敛现象程序死循环或者集合结果和手算对不上。原因不动点循环里没有正确判断「集合是否变化」或者first_of_seq遇到可空非终结符没有继续往后看。解决用changed标志控制循环可空判断单独用一个nullable集合维护别和 FIRST 混在一起。6.3 逆波兰式求值减法除法结果反了现象3 - 5算成26 / 2算成0.33。原因弹栈顺序写反先弹的应该是右操作数。解决固定写成b stack.pop(); a stack.pop()再做a op b别图省事。6.4 LR(1) 向前看符号算错导致归约错误现象本该移进的地方提前归约分析中途卡死。原因闭包运算里 FIRST(βa) 计算时漏掉了 β 可空的情况向前看符号集合不完整。解决单独写一个first_of_seq处理符号串β 可空时把 a 也并进去用测试文法逐状态核对。6.5 报错信息没有行列号调试全靠猜现象输入一长串代码报错只说「语法错误」不知道哪一行。原因Token 里没存位置信息或者语法分析器抛异常时没带上 Token 的位置。解决词法阶段就给每个 Token 记录line和col语法分析报错时直接引用当前 Token 的位置这是最省事的后悔药。7. 把四块拼成一个可演示的完整流程真正让这套实验值钱的不是四个独立模块而是把它们串成一条流水线源码 → 词法分析器 → Token 流 → 语法分析LL(1) 或 LR(1)→ 语法树 → 逆波兰式 → 求值结果。我一般会写一个main驱动按顺序调用中间把每步结果打印出来方便演示和答辩。def pipeline(src): tokens tokenize(src) print(Token:, [(t.ttype, t.value) for t in tokens]) rpn infix_to_rpn([t for t in tokens if t.ttype in (NUM, OP)]) print(RPN:, rpn) print(Result:, eval_rpn(rpn)) pipeline(3 5 * ( 2 - 1 ))逻辑说明这里为了演示只取了表达式相关的 Token实际工程里语法分析器会消费完整 Token 流。参数上pipeline的输入是源码字符串输出是各阶段中间结果和最终值。验证时先跑简单表达式再跑带括号和优先级的最后跑故意写错的确认报错位置准确。一个具体技巧把 LL(1) 和 LR(1) 的分析过程都做成「可单步」的每步打印栈内容、剩余输入和当前动作。答辩时老师最爱问「这一步为什么这么走」能单步演示比任何文档都有说服力。我自己当年做这个实验就是靠打印每一步状态才发现 FOLLOW 集少算了一个符号血泪经验是——别嫌日志多出问题时它就是唯一的黑匣子。希望帮到你。本文还有配套的精品资源点击获取 编译原理实验四件套：词法分析、LL(1)、逆波兰式与LR(1)完整实现
简介本资源是编译原理课程实验的完整配套资料面向计算机专业学生及需要动手实现编译前端的学习者围绕词法分析器设计、LL(1)分析法、逆波兰式生成与计算、LR(1)分析法四个核心实验展开帮助读者把课堂理论落到可运行的代码上。压缩包共35个文件约789KB以cpp源码、docx实验报告、txt与md说明文档为主另含xls数据表、png示意图及项目目录配置源码与文档相互对应便于对照理解。资源中每个实验均配有参考资料与演示目录README.md提供编译运行与调试指引读者可据此复现词法单元扫描、预测分析表构造、后缀表达式求值与LR状态栈规约等关键流程并在此基础上修改扩展。目前已有150人学习下载适合作为课程实验参考与期末复习的实操素材。1. 编译原理实验四件套从词法分析到 LR(1) 的一条完整落地路线很多人学编译原理课本翻到第三章就卡住了正则表达式、NFA、DFA 推导看着都懂真让你写一个能跑的词法分析器或者手撸一张 LL(1) 分析表立刻原形毕露。这个标题对应的正是一套把「词法分析器、LL(1) 分析法、逆波兰式生成及计算、LR(1) 分析法」串起来的实验工程配套源码和文档说明。它解决的不是单点问题而是让你亲手把编译器前端最核心的四块拼图拼完整先切词再做语法分析自上而下和自下而上两条路线中间穿插表达式求值这条贯穿线。适合正在做编译原理实验的本科生、准备考研复试手写分析器的同学以及想用 Java 或 Python 把课本理论跑成可调试代码的工程师。下面我按实际动手顺序把每一步的选择理由、参数设置和翻车点讲清楚。2. 词法分析器把字符流切成 Token 流的最小可用实现词法分析器是整个前端的入口它的输出质量直接决定后面语法分析器好不好写。这一章先把「怎么切」讲透再给一份能直接跑的代码。2.1 为什么用 DFA 而不是一堆 if-else新手最容易犯的错是拿一长串if-else判断字符遇到标识符、数字、注释就层层嵌套最后自己都读不懂。正规做法是先定义正则再转成 DFA用状态转移表驱动。核心原因是DFA 的状态和转移是数据不是控制流改词法规则时只改表不动逻辑。常见做法是手工构造 DFA或者用工具生成。实验里我一般手写状态表因为要能调试、能打印每一步状态。词法单元至少覆盖关键字、标识符、整数/浮点常量、运算符、界符、空白与注释。关键字识别有个小技巧——先按标识符规则读完整串再查关键字表不要为每个关键字单独开状态。2.2 一份可复现的 Token 定义与扫描主循环下面用 Python 写核心骨架逻辑和 Java 版一致方便对照。# token 类型常量 KEYWORDS {if, else, while, int, float, return} OPERATORS {, -, *, /, , , , , , } class Token: def __init__(self, ttype, value, line, col): self.ttype ttype # 类别ID / NUM / KW / OP / EOF self.value value # 原始字面量 self.line line # 行号报错定位用 self.col col # 列号 def tokenize(src): tokens [] i, line, col 0, 1, 1 n len(src) while i n: ch src[i] # 跳过空白同时维护行列号 if ch in \t\r: i 1; col 1; continue if ch \n: i 1; line 1; col 1; continue # 标识符 / 关键字 if ch.isalpha() or ch _: start, sc i, col while i n and (src[i].isalnum() or src[i] _): i 1; col 1 word src[start:i] ttype KW if word in KEYWORDS else ID tokens.append(Token(ttype, word, line, sc)); continue # 数字整数与小数 if ch.isdigit(): start, sc i, col while i n and src[i].isdigit(): i 1; col 1 if i n and src[i] .: i 1; col 1 while i n and src[i].isdigit(): i 1; col 1 tokens.append(Token(NUM, src[start:i], line, sc)); continue # 双字符运算符优先匹配 if i 1 n and src[i:i2] in OPERATORS: tokens.append(Token(OP, src[i:i2], line, col)) i 2; col 2; continue if ch in OPERATORS: tokens.append(Token(OP, ch, line, col)) i 1; col 1; continue raise SyntaxError(f非法字符 {ch!r} 于 {line}:{col}) tokens.append(Token(EOF, , line, col)) return tokens逻辑说明主循环按「空白 → 标识符 → 数字 → 双字符运算符 → 单字符运算符」的优先级顺序判断这个顺序不能乱。如果把单字符运算符判断放在双字符前面会被拆成两个后面语法分析直接崩。参数上line和col必须全程维护否则报错时只能告诉用户「有错」定位不到位置调试成本翻倍。提示双字符运算符一定要先于单字符匹配这是词法分析里最经典的顺序坑。2.3 词法分析器的三个必调参数与验证方法第一最长匹配原则。读到时不能停在要贪心往后看一位。第二回溯点。手工 DFA 里如果多读了一个字符才发现不匹配要能把指针退回去常见做法是记录start和当前i。第三错误恢复策略。遇到非法字符是直接抛异常还是跳过继续收集后续 Token取决于你要不要一次性报出所有错误。实验里我建议先抛异常简单可控。验证方法很直接准备一组覆盖所有 Token 类型的测试串跑完后打印 Token 序列人工核对类别和值。再准备一组故意写错的串确认报错行列号准确。3. LL(1) 分析法FIRST/FOLLOW 集怎么算、预测分析表怎么填词法过了进入自上而下的语法分析。LL(1) 是理解递归下降和预测分析的最佳跳板也是实验里最容易被 FIRST/FOLLOW 集绕晕的一章。3.1 FIRST、FOLLOW 集的手算规则与代码实现FIRST(A) 是 A 能推导出的所有串的首终结符集合。规则三条若 A → a…a 是终结符把 a 加入 FIRST(A)若 A → ε把 ε 加入 FIRST(A)若 A → B…把 FIRST(B) 中除 ε 外的元素加入 FIRST(A)若 B 能推出 ε继续看下一个符号。FOLLOW(A) 则是所有句型中紧跟在 A 后面的终结符集合起始符号的 FOLLOW 含结束符$。代码实现用不动点迭代反复扫描产生式直到集合不再变化。def first_of_seq(seq, first, nullable): # 求一个符号串的 FIRST 集 result set() for sym in seq: if sym not in first: # 终结符 result.add(sym); return result result | (first[sym] - {ε}) if ε not in first[sym]: return result result.add(ε) # 所有符号都可空 return result def build_first(grammar, nonterms, first): changed True while changed: changed False for head, bodies in grammar.items(): for body in bodies: add first_of_seq(body, first, None) if not add first[head]: first[head] | add; changed True逻辑说明first_of_seq处理的是产生式右部这个符号串遇到终结符直接收尾遇到非终结符先并入其 FIRST 去掉 ε再看它是否可空决定要不要继续。build_first用changed标志做不动点循环直到没有新元素加入。参数上grammar是{非终结符: [产生式右部列表]}的结构每个右部是符号列表。3.2 预测分析表的构造与冲突判定有了 FIRST 和 FOLLOW填表规则是对每条产生式 A → α对 FIRST(α) 中每个终结符 a把 A → α 填进M[A][a]若 α 可空对 FOLLOW(A) 中每个终结符 b也填入 A → α。填完后如果某个格子出现两条产生式这个文法就不是 LL(1)需要提取左公因子或消除左递归。步骤操作判断依据1消除左递归存在 A → Aα 形式2提取左公因子多条产生式右部前缀相同3计算 FIRST 集不动点迭代4计算 FOLLOW 集起始符含 $5填预测分析表检查格子冲突分析时用一个栈初始压入$和起始符号读入 Token 流栈顶是非终结符就查表展开是终结符就和当前 Token 比对一致则同时弹出并前进。这套流程跑通后递归下降分析器基本就是它的代码化版本。注意LL(1) 只能处理无左递归、无回溯的文法表达式文法通常要先改写别指望原样套用。4. 逆波兰式中缀转后缀、求值以及它和语法分析的关系逆波兰式后缀表达式是这套实验里最实用的一块它既是表达式求值的经典方案也是理解语法树后序遍历的直观入口。4.1 调度场算法中缀转后缀的完整实现核心是运算符栈加输出队列。遇到操作数直接输出遇到运算符把栈顶优先级不低于它的运算符弹出输出再压栈遇到左括号压栈遇到右括号弹到左括号为止。def infix_to_rpn(tokens): prec {: 1, -: 1, *: 2, /: 2} out, ops [], [] for t in tokens: if t.ttype NUM: out.append(t.value) elif t.value (: ops.append(t.value) elif t.value ): while ops and ops[-1] ! (: out.append(ops.pop()) ops.pop() # 弹出左括号 elif t.value in prec: while (ops and ops[-1] in prec and prec[ops[-1]] prec[t.value]): out.append(ops.pop()) ops.append(t.value) while ops: out.append(ops.pop()) return out逻辑说明prec定义优先级保证左结合性比如a-b-c会正确转成ab-c-。参数上输入是词法分析器产出的 Token 列表输出是字符串列表。如果支持一元负号需要在遇到-且前一个 Token 是运算符或左括号时特殊处理这是最常见的扩展点。4.2 后缀表达式求值与除零、类型处理求值用一个操作数栈遇到数字压栈遇到运算符弹出两个操作数计算后压回。def eval_rpn(rpn): stack [] for tok in rpn: if tok in {, -, *, /}: b stack.pop(); a stack.pop() if tok : stack.append(a b) elif tok -: stack.append(a - b) elif tok *: stack.append(a * b) else: if b 0: raise ZeroDivisionError(除数为零) stack.append(a / b) else: stack.append(float(tok)) return stack[0]逻辑说明注意弹出顺序是b先、a后减法和除法不满足交换律顺序反了结果就错。参数上整数和浮点统一按float处理如果实验要求区分int和float要在 Token 里保留类型标记求值时按类型分派。提示逆波兰式求值天然对应语法树的后序遍历理解这一点后面 LR 分析的语义动作就好接了。5. LR(1) 分析法项目集规范族、分析表与移进归约冲突排查LR(1) 是自下而上分析的硬骨头也是实验里最能拉开差距的部分。它比 LL(1) 强在能处理更多文法代价是状态构造复杂。5.1 LR(1) 项目与闭包、GOTO 的构造LR(1) 项目是[A → α·β, a]点表示分析位置a是向前看符号。闭包运算若项目[A → α·Bβ, a]中 B 是非终结符对每条 B 的产生式B → γ和 FIRST(βa) 中每个终结符 b把[B → ·γ, b]加入闭包。GOTO 函数则把点右移一位后求闭包。构造流程从增广文法的起始项目[S → ·S, $]出发反复求闭包和 GOTO直到没有新状态。状态数通常比 LALR(1) 多但冲突更少。5.2 分析表的 ACTION 与 GOTO 填写ACTION 表按项目类型填点后是终结符 a填移进到 GOTO 状态点是末尾且向前看符号是 a填归约[S → S·, $]填接受。GOTO 表填非终结符的转移。填完后检查冲突移进-归约冲突和归约-归约冲突。冲突类型现象常见处理移进-归约同一格子既可移进又可归约优先移进或改写文法归约-归约同一格子两条归约文法有歧义需重构状态爆炸状态数过多考虑 LALR(1) 合并同心项目集分析驱动和 LL(1) 类似用状态栈加符号栈读入 Token 查 ACTION 表决定移进还是归约归约时按产生式长度弹栈再查 GOTO。5.3 用表达式文法验证 LR(1) 分析器拿E → E T | T、T → T * F | F、F → ( E ) | id这套经典文法跑一遍输入id id * id确认分析过程正确归约最终接受。再输入id * id确认在错误位置报错。这一步能验证 ACTION/GOTO 表填得对不对也能暴露向前看符号算错的问题。6. 避坑与排查这套实验里最容易翻车的五个地方6.1 词法阶段把拆成两个现象语法分析报莫名其妙的错误表达式判断全部失效。原因单字符运算符判断放在了双字符前面或者根本没做双字符匹配。解决严格按最长匹配先查双字符表再查单字符代码里把双字符判断写在前面。6.2 FIRST/FOLLOW 集迭代不收敛现象程序死循环或者集合结果和手算对不上。原因不动点循环里没有正确判断「集合是否变化」或者first_of_seq遇到可空非终结符没有继续往后看。解决用changed标志控制循环可空判断单独用一个nullable集合维护别和 FIRST 混在一起。6.3 逆波兰式求值减法除法结果反了现象3 - 5算成26 / 2算成0.33。原因弹栈顺序写反先弹的应该是右操作数。解决固定写成b stack.pop(); a stack.pop()再做a op b别图省事。6.4 LR(1) 向前看符号算错导致归约错误现象本该移进的地方提前归约分析中途卡死。原因闭包运算里 FIRST(βa) 计算时漏掉了 β 可空的情况向前看符号集合不完整。解决单独写一个first_of_seq处理符号串β 可空时把 a 也并进去用测试文法逐状态核对。6.5 报错信息没有行列号调试全靠猜现象输入一长串代码报错只说「语法错误」不知道哪一行。原因Token 里没存位置信息或者语法分析器抛异常时没带上 Token 的位置。解决词法阶段就给每个 Token 记录line和col语法分析报错时直接引用当前 Token 的位置这是最省事的后悔药。7. 把四块拼成一个可演示的完整流程真正让这套实验值钱的不是四个独立模块而是把它们串成一条流水线源码 → 词法分析器 → Token 流 → 语法分析LL(1) 或 LR(1)→ 语法树 → 逆波兰式 → 求值结果。我一般会写一个main驱动按顺序调用中间把每步结果打印出来方便演示和答辩。def pipeline(src): tokens tokenize(src) print(Token:, [(t.ttype, t.value) for t in tokens]) rpn infix_to_rpn([t for t in tokens if t.ttype in (NUM, OP)]) print(RPN:, rpn) print(Result:, eval_rpn(rpn)) pipeline(3 5 * ( 2 - 1 ))逻辑说明这里为了演示只取了表达式相关的 Token实际工程里语法分析器会消费完整 Token 流。参数上pipeline的输入是源码字符串输出是各阶段中间结果和最终值。验证时先跑简单表达式再跑带括号和优先级的最后跑故意写错的确认报错位置准确。一个具体技巧把 LL(1) 和 LR(1) 的分析过程都做成「可单步」的每步打印栈内容、剩余输入和当前动作。答辩时老师最爱问「这一步为什么这么走」能单步演示比任何文档都有说服力。我自己当年做这个实验就是靠打印每一步状态才发现 FOLLOW 集少算了一个符号血泪经验是——别嫌日志多出问题时它就是唯一的黑匣子。希望帮到你。本文还有配套的精品资源点击获取