简介编译原理实验代码词法分析器设计」是一套面向计算机专业学生的编译原理核心实验资料围绕词法分析器、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(fline {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 最长匹配与错误恢复这两个细节是词法实验的扣分重灾区最长匹配的具体含义是输入时不能先识别出剩下的再识别成赋值号必须优先匹配更长的合法符号。上面的代码用“先尝试双字符运算符再单字符兜底”的顺序处理了这个问题但在更复杂的场景里例如可变长度的关键字后接标识符最长匹配意味着我们要记录“最后一次处于接受态的位置”一旦继续读入字符后进入死状态就回退到上次接受位置。很多同学在遇到空格缺失的输入intx1时会把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) 里的所有终结符包括$填入 ε 产生式对应的列。下面是上例文法的预测分析表行是非终结符列是终结符和$单元格里标注产生式编号。非终结符*()i$EE → T EE → T EEE → T EE → εE → εTT → F TT → F TTT → εT → * F TT → εT → εFF → ( E )F → i表里空白单元格就是语法错误的位置。注意 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(funexpected token {a}) _, right PROD[prod_no] stack.extend(reversed(right)) # 右部逆序入栈 else: raise SyntaxError(fexpect {top}, got {a}) return True代码里的关键参数是PROD和TABLEPROD把产生式右部保存为列表空列表表示 ε不需要在栈里压入任何符号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 章示例文法分析ii*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[pos1:] [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(fstate {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 系列分析器课程实验如果允许使用工具最省时间的路径是用 PLYPython 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 donediff -q只比较是否有差异不打印详情失败时再完整输出差异这样既能快速扫出功能回归又能保留定位信息。测试用例建议覆盖这几类边界单个数字和单个标识符ii*i与(ii)*i优先级差异i--i这类连续一元运算符带括号到不带括号的嵌套表达式词法层的与区分语法错误输入例如i*i必须报错而不是静默通过。这些用例中“最长匹配”和“一元负号”是最容易翻车的两个点我在自己的实验里几乎每次都靠这类用例找出状态机与操作符栈的细节问题。文档说明里除了测试脚本还至少需要四张手工推导过程的图或表词法规则的 DFA 状态图、FIRST/FOLLOW 集合的手算过程、LL(1) 预测分析表的最终形态、LR(1) 项目集族至少一个非平凡状态的开闭包推导。动手写代码前先在草稿纸上把这几份表做出来你写分析表驱动的速度会明显更快因为表的每一个格子对应到哪里、哪个状态会移进哪个会归约已经被预先验证过了。把和的边界用例放进回归脚本这是查状态机最长匹配是否做对的最快方式。本文还有配套的精品资源点击获取