编译原理实验：从词法分析到LL(1)/LR(1)与逆波兰式的完整实现

简介：编译原理实验代码词法分析器设计」是一套面向计算机专业学生的编译原理核心实验资料，围绕词法分析器、LL(1)分析法、逆波兰式的生成与计算、LR(1)分析法四大模块展开，覆盖从源码扫描到语法分析的主要流程。项目使用C++实现，并配有实验报告、说明文档及README.md运行指引，适合正在学习编译原理、准备课程设计或希望动手验证理论的学习者。压缩包共35个文件，以txt、docx、md文档和cpp源码为主，另有xls表格、png示意图等辅助材料，整体大小仅789KB，结构清晰、便于查阅下载。目前已有149人学习下载。资源附带的文档说明了代码功能、使用方法和调试思路，下载后还可私聊远程教学，能帮助读者快速搭建环境、运行实验。通过实际运行四个实验并修改代码，可以深入理解词法单元识别、预测分析表构造、后缀表达式栈式计算及LR(1)状态机等核心机制，是一份兼顾原理讲解与代码实践的完整学习参考。 很多人第一次打开这份实验题，第一反应是“四个题目怎么这么多”。但把词法分析器、LL(1)分析法、逆波兰式的生成及计算、LR(1)分析法放到一起看，它们刚好是同一条编译流水线的四个连续阶段：词法分析器负责把源码切成 token 流，LL(1) 或 LR(1) 负责在 token 流上建立语法结构，语法分析过程中的语义动作把表达式转成逆波兰式，最后再对后缀式求值。课程实验通常会把文法简化到一周能完成一个模块的程度，但正是这种简化版本，能让人把“正则到状态机、文法到分析表、语法树到中间代码”这条主线一次性理清楚。这篇文章按照“理论依据、参数怎么设、代码怎么写、坑在哪里”的顺序，把四个模块里最值得拆解的细节展开讲，适合正在写编译原理实验的学生，也适合需要快速建立编译入门知识体系的一线开发。

1. 从词法到 LR(1)：一个编译原理实验里藏着整条编译流水线

编译器最容易被新接触的人高估的是“智能”，实际做起来却发现每一步都是形式化的机械过程。词法分析器解决的问题是“字符序列如何变成单词”，LL(1) 与 LR(1) 解决的问题是“单词序列如何变成语法树”，逆波兰式则是语法树的一种扁平化输出。课程实验中这四个模块往往被当成四次独立作业提交，但如果你把上一阶段的输出接上下一个阶段的输入，会发现自己写的已经是编译器的前三步了。了解这一点，不仅能让实验代码更好整理，也能在期末笔试里建立整体感——选择题里那些“哪个阶段处理标识符”“递归下降属于哪一类分析法”之类的题，背答案总不如真的写一遍记得牢。

这篇文章默认你已经具备基本的离散数学和数据结构基础，不需要看过完整教材就能跟下来。每一段都给出可以直接运行的代码，同时解释代码背后的状态、表结构和设计取舍。最后会给你一套把四个模块串起来做回归测试的方法，这是“项目源码 + 文档说明”里最容易做出亮点的部分。

2. 词法分析器：状态机、最长匹配与错误恢复的实现

2.1 从正则到状态机，手写词法分析器为什么不直接用正则库

词法规则本身几乎都是正则语言，所以一个很自然的想法是直接调用正则表达式库做匹配，例如在 Python 里用re.finditer一次性把单词切出来。这个做法在原型验证阶段没问题，但编译器教材和大多数课程实验要求手写状态机，背后的原因有两个。其一是教学目的，你要理解“正则表达式等价于有限自动机”到底意味着什么；其二是工程意义，词法分析器要处理最长匹配、回溯位置、错误恢复和行列号统计，用正则库去拼这些逻辑反而会把代码写得绕。

手写方案的标准套路是三步走：先把所有合法单词归类，例如关键字、标识符、整数常量、运算符、分隔符；再为每一类设计对应的 DFA，或者合并成一张大的状态转换表；最后用一个驱动函数循环读入字符，每读一个字符就做状态迁移，到无法迁移的位置停下。大多数课程允许你把 DFA 的状态转移直接展开成if/elif分支，虽然看上去不够“表格化”，但可读性好，出错后容易调试。

2.2 一个最小可运行的词法分析器实现

下面这个 Python 版本的词法分析器可以识别关键字、标识符、整数、四则运算符、括号和赋值号，足够支撑后续 LL(1) 和逆波兰式的实验。它的核心思想是字符分类：按当前字符是否字母/数字/符号决定进入哪一个读取分支，每个分支内用循环吃进尽可能长的合法字符序列。

# -*- coding: utf-8 -*- import sys KEYWORDS = {"if", "else", "while", "return", "int"} def tokenize(src: str): tokens = [] i, n = 0, len(src) line = 1 while i < n: c = src[i] if c in ' \t\r': i += 1 continue if c == '\n': line += 1 i += 1 continue if c.isalpha() or c == '_': start = i while i < n and (src[i].isalnum() or src[i] == '_'): i += 1 word = src[start:i] kind = 'KEYWORD' if word in KEYWORDS else 'IDENT' tokens.append((kind, word, line)) continue if c.isdigit(): start = i while i < n and src[i].isdigit(): i += 1 tokens.append(('INT', src[start:i], line)) continue matched = False for op in ('>=', '<=', '==', '!='): if src.startswith(op, i): tokens.append(('OP', op, line)) i += len(op) matched = True break if matched: continue if c in '+-*/()=<>;': tokens.append(('OP', c, line)) i += 1 continue raise SyntaxError(f"line {line}: unexpected char {c!r}") tokens.append(('EOF', '#', line)) return tokens if __name__ == '__main__': data = sys.stdin.read() for tok in tokenize(data): print(tok)

这段代码把字符读入、分类、单词截断和错误定位集中在一个函数里，结构上很接近手写状态机的展开形式。参数说明如下：KEYWORDS是保留字集合，判别顺序必须是“先按词法读完整单词，再查集合”，不能像“见首字母是 i 就当关键字”那样边读边判；运算符循环里利用startswith尝试匹配双字符运算符，这一步体现的就是最长匹配原则，否则==会被拆成两个=；line变量在错误信息里用来定位行号，课程验收时这个字段经常是加分项。

2.3 最长匹配与错误恢复，这两个细节是词法实验的扣分重灾区

最长匹配的具体含义是：输入>=时不能先识别出>，剩下的=再识别成赋值号，必须优先匹配更长的合法符号。上面的代码用“先尝试双字符运算符，再单字符兜底”的顺序处理了这个问题，但在更复杂的场景里，例如可变长度的关键字后接标识符，最长匹配意味着我们要记录“最后一次处于接受态的位置”，一旦继续读入字符后进入死状态，就回退到上次接受位置。很多同学在遇到空格缺失的输入intx=1时会把intx整体识别成标识符，从词法角度看这反而是正确行为，因为长度优先于关键字优先。

错误恢复方案需要在实验文档里写明。最简单的策略是遇到非法字符时抛出带行列号的异常并终止分析，适合绝大多数课程。更工程化的做法是跳过当前字符、记录错误、继续分析，让一次运行报告尽量多的错误。实现时只需要在raise SyntaxError分支里改成打印错误信息并i += 1，但要注意后续阶段的输入已经是部分错误的 token 流，调试时要关注第一个错误。

3. LL(1) 分析法：FIRST/FOLLOW 集、预测分析表与表驱动实现

3.1 FIRST/FOLLOW 集：判断一个文法能不能用 LL(1) 分析

LL(1) 要求分析器只看当前栈顶的非终结符 A 和输入缓冲区最前面的终结符 a，就能唯一决定下一步使用哪条产生式。要做到这一点，我们需要对文法的每个非终结符计算两个集合。FIRST(A) 表示 A 经过若干步推导后能出现在开头位置的所有终结符；FOLLOW(A) 表示在某个句型中紧跟在 A 后面的所有终结符。计算 FOLLOW 时要注意两点：如果 A 是文法的开始符号，$一定在 FOLLOW(A) 里；如果有产生式 A → αBβ，则 FIRST(β) 中的非 ε 终结符全部进入 FOLLOW(B)，若 β 能推出空串，那么 FOLLOW(A) 也要并入 FOLLOW(B)。

一个文法能构造无冲突 LL(1) 分析表的判定条件是：对每个非终结符 A 的任意两条产生式 A → α 和 A → β，若 FIRST(α) 与 FIRST(β) 有交集则发生冲突；若其中某一方能推导出 ε，则还要额外检查该 FIRST 集与 FOLLOW(A) 是否相交。相交就说明不能只凭一个向前看符号决定选择，需要改写文法。

3.2 构造预测分析表 M[A, a]

以经典的表达式文法为例：

E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → ( E ) | i

手工构造分析表时，对每条产生式 A → α 执行两步操作：先找出 FIRST(α) 中所有非 ε 终结符，把产生式填入这些列；如果 α 可能推导出 ε，再把 FOLLOW(A) 里的所有终结符（包括$）填入 ε 产生式对应的列。下面是上例文法的预测分析表，行是非终结符，列是终结符和$，单元格里标注产生式编号。

表里空白单元格就是语法错误的位置。注意 E' 的 ε 产生式同时出现在)和$列，这正是 FOLLOW(E') = {+, ), $} 的直接结果，归约时机完全由输入符号决定，这就是 LL(1) 与 LL(0) 之类方法的本质区别。

3.3 表驱动 LL(1) 分析器的 Python 实现

分析驱动循环用“栈 + 查询表”实现，逻辑非常固定。栈底先放$，再压入开始符号 E；每次取栈顶符号 X 和当前输入符号 a：如果 X 是终结符，就直接与 a 匹配；如果 X 是非终结符，就去查表 M[X, a]，查到的产生式右部逆序压栈；空表项报语法错误。

# 文法产生式用整数编号，例如 4 代表 T' -> * F T' NON_TERM = {"E", "E'", "T", "T'", "F"} PROD = { 1: ("E", ["T", "E'"]), 2: ("E'", ["+", "T", "E'"]), 3: ("E'", []), # ε 4: ("T", ["F", "T'"]), 5: ("T'", ["*", "F", "T'"]), 6: ("T'", []), # ε 7: ("F", ["(", "E", ")"]), 8: ("F", ["i"]), } TABLE = { ("E", "i"): 1, ("E", "("): 1, ("E'", "+"): 2, ("E'", ")"): 3, ("E'", "$"): 3, ("T", "i"): 4, ("T", "("): 4, ("T'", "+"): 6, ("T'", "*"): 5, ("T'", ")"): 6, ("T'", "$"): 6, ("F", "i"): 8, ("F", "("): 7, } def ll1_parse(tokens): tokens = list(tokens) + ["$"] stack = ["$", "E"] pos = 0 while stack: top = stack.pop() a = tokens[pos] if top == a: # 终结符匹配 pos += 1 elif top in NON_TERM: prod_no = TABLE.get((top, a)) if prod_no is None: raise SyntaxError(f"unexpected token {a}") _, right = PROD[prod_no] stack.extend(reversed(right)) # 右部逆序入栈 else: raise SyntaxError(f"expect {top}, got {a}") return True

代码里的关键参数是PROD和TABLE：PROD把产生式右部保存为列表，空列表表示 ε，不需要在栈里压入任何符号；stack.extend(reversed(right))这句决定了“最左边符号最先被处理”，是 LL 系列分析的核心特征。如果运行时出现栈顶终结符和输入不匹配的错误，还要在报错信息里带上输入位置，方便和词法分析器的行号对应。

3.4 左递归消除与提取左因子，动手前必须先做的两件事

直接按课本原始文法写分析表会失败，因为左递归文法会让预测分析表某个单元格里存在多条产生式。消除左递归的标准变换是：把 A → Aα | β 改写成 A → βA' 和 A' → αA' | ε。另一个常见冲突来自左公共因子，形如 A → αβ1 | αβ2 的产生式会让 FIRST 集合产生交集，改写成 A → αA' 后由 A' → β1 | β2 承接差异。这两步变换在实验报告中必须写过程，期末试题里也经常要求在试卷上手工推导。做完变换后再检验 FIRST 和 FOLLOW 是否冲突，能省下后面所有调试时间。

4. 逆波兰式的生成及计算：语义动作与调度场算法

4.1 后缀式为什么适合中间代码

逆波兰式也就是后缀表达式，把操作符放在操作数之后，例如中缀i + i * i变成i i * +。后缀式最大的优点是计算时不需要括号，也不需要关心运算符优先级，只需要一个操作数栈从左到右扫描。正因为计算逻辑简单、适合作为虚拟机指令的输入，经典编译教材才把后缀式作为最简单的中间代码形式。它与语法树的关系是扁平化的：对表达式树做后序遍历得到的就是后缀式，因此语法分析过程中完全可以边做归约边输出后缀式，不需要显式建树。

4.2 调度场算法：手工生成后缀式最直接的做法

如果不经过语法分析，用 Dijkstra 调度场算法可以直接完成中缀到后缀的转换。算法维护一个输出队列和一个操作符栈，数字直接进输出队列；操作符入栈前，先把栈顶优先级不低于它的操作符弹出到输出；左括号直接入栈，右括号弹出操作符直到左括号；最后清空操作符栈。

PREC = {'+': 1, '-': 1, '*': 2, '/': 2, 'u-': 3} LEFT_ASSOC = {'+', '-', '*', '/'} def infix_to_postfix(tokens): out = [] ops = [] prev = None for tok in tokens: if tok in ('INT', 'IDENT'): # 操作数直接输出 out.append(tok) elif tok == '(': ops.append('(') elif tok == ')': while ops and ops[-1] != '(': out.append(ops.pop()) ops.pop() elif tok in PREC: if tok == '-' and (prev is None or prev in PREC or prev == '('): tok = 'u-' # 一元负号 while (ops and ops[-1] != '(' and (PREC[ops[-1]] > PREC[tok] or (PREC[ops[-1]] == PREC[tok] and tok in LEFT_ASSOC))): out.append(ops.pop()) ops.append(tok) prev = tok while ops: out.append(ops.pop()) return out

这段代码里最容易理解错的参数是prev和一元负号的处理。prev记录上一个 token，用来区分“减法”和“取负”：一元负号的优先级比乘除高，因此用单独标记u-并给优先级 3。操作符弹出的条件里出现了两次比较：栈顶优先级更高时一定弹出；优先级相同时，只有当前操作符是左结合才弹出，右结合时（例如幂运算^）则不弹出。考试中手工模拟这个算法时，建议把每一步的out和ops写成两列表格，防止算错。

4.3 后缀式的计算：一个栈就够了

后缀式求值比生成更简单，扫描每个 token，操作数压栈，遇到操作符就弹出两个操作数计算，再把结果压栈。顺序关系尤为重要：碰到-和/时，先弹出的是右操作数，后弹出的是左操作数，写成left, right = stack.pop(), stack.pop()会把两个操作数顺序搞反。

def eval_postfix(postfix): stack = [] for tok in postfix: if tok in ('INT', 'IDENT'): stack.append(int(tok)) elif tok == 'u-': stack.append(-stack.pop()) else: right = stack.pop() left = stack.pop() if tok == '+': stack.append(left + right) elif tok == '-': stack.append(left - right) elif tok == '*': stack.append(left * right) elif tok == '/': stack.append(left // right) return stack[0]

代码顺序right = stack.pop(); left = stack.pop()对应了后缀式a b -中 b 先出栈的客观事实。除法这里用了整除，是为了让实验结果保持一致，实际语言里应该按语义定义保留浮点结果。这个纯栈算法的计算复杂度是 O(n)，与表达式长度线性相关，非常适合作为实验文档里时间复杂度的分析示例。

4.4 在 LL(1) 分析过程中同步生成后缀式

调度场算法虽然好用，但课程实验更希望你能把语义动作直接挂在语法分析产生式上。常见做法是在每条产生式右部末尾附加输出动作：对于第 1 章示例文法，分析i+i*i时，碰到F → i输出i；归约T' → * F T'时输出*；归约E' → + T E'时输出+。最终得到i i i * +，与调度场算法结果一致。这个同步输出过程说明后缀式不是独立的结构，而是语法树的后序遍历结果，在实验文档里把这条对应关系写清楚，通常比贴代码更能得分。

5. LR(1) 分析法：项目集构造、ACTION/GOTO 表与驱动循环

5.1 LR(1) 比 SLR(1) 多出的信息：向前看符号

LR(1) 的项目形式是[A → α · β, a]，其中a是向前看终结符，表示“用这条产生式归约之后，下一个输入符号应当是 a”。LR(0) 只看点右边的符号，SLR(1) 用 FOLLOW 集近似代替归约条件，而 LR(1) 把对下一个符号的精确约束记录在项目里。为什么需要这种精确性？经典例子是文法 S → L = R | R、L → * R | id、R → L。在某个状态下，分析器同时持有[S → L · = R]和[R → L ·]，如果只看 FOLLOW(R)，=会被错误地允许作为归约后的合法后继，于是产生移进-归约冲突；但 LR(1) 项目的向前看符号区分了“必须移进 =”和“只有在$出现才能归约”，冲突不存在。这个例子在笔试题里经常出现，理解它也就理解了 SLR 的近似性到底近似在哪。

5.2 构造 LR(1) 项目集族与 ACTION/GOTO 表

项目集族的构造分三个步骤。第一步，求初始项目集 I0，内容是[S' → · S, $]的闭包；第二步，对每个项目集 I 和文法符号 X，计算GOTO(I, X)，它等于所有点后为 X 的项目移动点位置后再取闭包；第三步，重复第二步直到没有新的项目集产生。闭包运算中有一条递归规则：如果项目是[A → α · Bβ, a]且 B → γ 是产生式，那么对每个b ∈ FIRST(βa)，项目[B → · γ, b]都要加入闭包。

下面是用结构清晰的流程描述这个算法的伪代码式实现，实际课程实验中用字典保存项目集和边：

def closure(project_set, grammar, first_sets): queue = list(project_set) while queue: # 形如 (lhs, rhs, pos, lookahead) 的项目 lhs, rhs, pos, lookahead = queue.pop() if pos < len(rhs) and rhs[pos] in grammar.nonterms: B = rhs[pos] # FIRST(beta + lookahead) for b in first_sets.seq(rhs[pos+1:] + [lookahead]): new_item = (B, grammar.prods[B][0], 0, b) if new_item not in project_set: project_set.add(new_item) queue.append(new_item) return project_set

闭包计算容易漏掉的就是b的取值范围，它是FIRST(βa)而不是FOLLOW(B)，正是这个细节区分了 LR(1) 和 SLR(1)。构造完项目集族之后，ACTION 表的填法分三类情况：点后是终结符时填s移进到对应状态；项目[A → α ·, a]在 ACTION[I, a] 填r归约；接受项目[S' → S ·, $]填acc。GOTO 表则记录点后是非终结符时的转移状态。

5.3 LR(1) 分析驱动循环的最小实现

分析初始化时把状态 0 压栈，每个状态栈元素实际上应该和历史符号栈交替存放。驱动循环根据当前状态栈顶和输入符号查 ACTION 表，动作有三种：移进时同时把当前输入符号和新状态压栈；归约时按产生式右部长度弹出对应数量的状态，再查 GOTO 表压入左部非终结符与下一个状态；接受时返回成功。

def lr1_parse(tokens, action, goto): tokens = list(tokens) + ["$"] stack = [0] pos = 0 while True: state = stack[-1] a = tokens[pos] act = action.get((state, a)) if act is None: raise SyntaxError(f"state {state}, token {a}") if act[0] == 's': # 移进 stack.append(a) stack.append(act[1]) pos += 1 elif act[0] == 'r': # 归约 lhs, length = act[1], act[2] while length > 0: stack.pop() stack.pop() length -= 1 prev_state = stack[-1] stack.append(lhs) stack.append(goto[(prev_state, lhs)]) elif act[0] == 'acc': return True

这里所有存储形式都是(状态, 符号)交替入栈，所以归约时每弹出一个符号的状态要两次pop()。与 LL(1) 分析器相比，两种驱动的根本差异在于表的内容：LL(1) 表是“非终结符 × 终结符 → 产生式”，LR(1) 表是“状态 × 终结符 → 动作”，但驱动循环的复杂度都只有 O(n)。

5.4 用 Yacc/Bison 或 PLY 自动生成 LR 系列分析器

课程实验如果允许使用工具，最省时间的路径是用 PLY（Python Lex-Yacc）定义 tokens 和产生式，自动生成 LALR(1) 分析器。需要明确的是 PLY 默认生成 LALR(1)，它是 LR(1) 的压缩变体，表达能力弱于完整 LR(1)，但对大多数表达式文法完全够用。

from ply import lex, yacc tokens = ('ID', 'PLUS', 'TIMES', 'LPAREN', 'RPAREN') t_PLUS = r'\+' t_TIMES = r'\*' t_LPAREN = r'\(' t_RPAREN = r'\)' def p_expression(p): '''expression : expression PLUS term | term''' if len(p) == 4: p[0] = ('+', p[1], p[3]) else: p[0] = p[1] # 需要继续定义 term 产生式，并用 precedence 声明优先级 parser = yacc.yacc()

用这类生成器时，最常见的坑是冲突报告。如果 PLY 输出 “shift/reduce conflict” 或 “reduce/reduce conflict”，先用parser.out文件查看冲突发生的状态，再检查文法是否含二义性。优先使用%left这类优先级声明，而不是临时改文法，这是工程实践中最常见的做法。但要注意，如果课程明确要求手写 LR(1) 分析表，生成器只能用来交叉验证正确性，不能替代手算。

6. 把四段代码串成一条可回归测试的流水线

课程实验提交的“项目源码 + 文档说明”里，文档最容易被忽视的就是验证过程。强烈建议不要只贴“我输入了一个表达式，输出正确”的截图，而是把四个模块实现为命令行工具并用脚本串联，让一次运行完成从源码到计算结果的完整验证。我会把每个模块设计成过滤器：词法分析器读入源文件，输出一行一个 token 的文本；LL(1) 分析器读入 token 流，一边分析一边输出后缀式；后缀式计算模块读入后缀式并打印结果。这样每一段都可以单独测试，也可以用管道串成整条编译路径。

在 Linux 或 macOS 环境下，一个极简回归测试脚本可以这样写：

#!/bin/bash # usage: ./regression.sh tests/ cases; 每个 .mini 文件配一个 .expect for f in tests/*.mini; do python lexer.py < "$f" \ | python ll1_parser.py \ | python postfix_calc.py > /tmp/out.txt if diff -q /tmp/out.txt "${f%.mini}.expect" > /dev/null; then echo "PASS: $f" else echo "FAIL: $f" diff /tmp/out.txt "${f%.mini}.expect" fi done

diff -q只比较是否有差异，不打印详情；失败时再完整输出差异，这样既能快速扫出功能回归，又能保留定位信息。测试用例建议覆盖这几类边界：单个数字和单个标识符；i+i*i与(i+i)*i优先级差异；i--i这类连续一元运算符；带括号到不带括号的嵌套表达式；词法层的==与=区分；语法错误输入，例如i+*i必须报错而不是静默通过。这些用例中“最长匹配”和“一元负号”是最容易翻车的两个点，我在自己的实验里几乎每次都靠这类用例找出状态机与操作符栈的细节问题。

文档说明里除了测试脚本，还至少需要四张手工推导过程的图或表：词法规则的 DFA 状态图、FIRST/FOLLOW 集合的手算过程、LL(1) 预测分析表的最终形态、LR(1) 项目集族至少一个非平凡状态的开闭包推导。动手写代码前先在草稿纸上把这几份表做出来，你写分析表驱动的速度会明显更快，因为表的每一个格子对应到哪里、哪个状态会移进哪个会归约，已经被预先验证过了。把==和=的边界用例放进回归脚本，这是查状态机最长匹配是否做对的最快方式。

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