简介这是一份编译原理课程的无符号数词法分析实验报告适合高校计算机专业学生、考研复习者及需要完成同类实验的开发者参考。报告以本科实验报告形式呈现完整覆盖从文法规则、程序流程图到Java代码实现与运行结果的全过程重点讲解词法分析基本思想、无符号整数与实数的识别规则以及科学计数法输出等细节。资源共1个PDF文件压缩包大小约201KB内容结构清晰便于直接查阅打印。该资源已有1562人学习下载配套实验代码可直接运行验证能帮助读者快速理解词法分析程序的实现思路也可作为撰写课程实验报告或设计小型编译器的参考资料。1. 编译原理这门课为什么一本薄讲义比厚教材更值得过一遍你手上这份「编译原理-太原理工大学[参照].pdf」名字平平无奇但这类课程讲义往往比八百页的经典教材更适合当入门路线图。我见过太多人把编译原理学成“背名词解释”正则、文法、LL(1)、LR(1)全都认识合上书连一个词法分析器都写不出来。问题不在人在于教材的编排是为了“讲全”而讲义的编排是为了“讲完一门课”。对着一份讲义学编译原理最大的收益是它帮你划出了最小必做集词法分析做一遍、语法分析做一遍、中间代码生成摸一遍你才算真正入行而不是在“编译原理实验”的作业里抄完答案就扔。我接下来要讲的就是照着这份讲义把一个能跑的最小编译器拆出来的完整路径包括代码、参数、以及我这些年踩过的坑。2. 把讲义当工程手册读先跑通三个最小程序2.1 用讲义里的词法分析章节搭一个带最长匹配的词法分析器词法分析是所有编译实验的入口也是很多人的第一个翻车点。讲义里通常先给正则表达式接着讲 DFA 状态图看上去很简单但一写代码就会遇到一个关键问题同一个字符序列可能匹配多个 token你必须实现“最长匹配”否则会被拆成和while会被拆成wh和ile。我一般会直接用 Python 写一个手动控制的匹配循环把词法规则按优先级排列每次都选出匹配长度最长的那条规则而不是用re.finditer一把梭。核心代码如下import re TOKEN_SPEC [ (KEYWORD, rif|else|while|return|int|void), (IDENT, r[A-Za-z_][A-Za-z0-9_]*), (NUMBER, r\d(\.\d)?), (OP, r|!|||\|-|\*|/|[\{\}\(\);,]), (SPACE, r[ \t\n\r]), ] def tokenize(src: str) - list: tokens [] pos 0 while pos len(src): best_len -1 best_type None best_text None for typ, pat in TOKEN_SPEC: m re.match(pat, src[pos:]) if m and len(m.group(0)) best_len: best_len len(m.group(0)) best_type typ best_text m.group(0) if best_len 0: raise SyntaxError(f第 {pos} 个字符无法识别: {src[pos]!r}) if best_type ! SPACE: tokens.append((best_type, best_text)) pos best_len return tokens这段代码最关键的设计是best_len这个变量。它把五类规则放在同一个循环里比较最终胜出的不是“先匹配到的规则”而是“匹配得最长的规则”。TOKEN_SPEC的顺序也有讲究双字符运算符、必须排在单字符、前面尽管最长匹配本身能解决一部分问题但规则顺序仍会影响相同长度时的取舍。SPACE规则放在最后兜底匹配到空白就跳过不进入 token 列表。这样写出来的词法分析器行为与讲义里的 DFA 是等价的但肉眼可读出了错也能直接跟踪到具体第几个字符。2.2 按讲义语法分析章节写一个不跳进左递归死循环的递归下降解析器语法分析是编译原理的核心也是讲义中篇幅最大的部分。递归下降是最好上手、也最适合手工实现的策略但直接把讲义里的 BNF 文法抄成函数会立刻遇到左递归问题E - E T这种规则写成def E(): E(); match(); T()调用栈会无限膨胀最终RecursionError。问题不是文法错了而是机械翻译文法行不通。解法是先消除左递归再把文法改写成等价的迭代循环。以表达式文法为例消除左递归后变成parse_table { (E, id): [T, E\], (E, (): [T, E\], (E\, ): [, T, E\], (E\, )): [], # ε 产生式 (E\, $): [], # ε 产生式 (T, id): [F, T\], (T, (): [F, T\], (T\, *): [*, F, T\], (T\, ): [], # ε (T\, )): [], # ε (T\, $): [], # ε (F, id): [id], (F, (): [(, E, )], } def predict(stack, tokens): while stack: top stack[-1] lookahead tokens[0] if top lookahead: stack.pop() tokens.pop(0) continue production parse_table.get((top, lookahead)) if production is None: raise SyntaxError(f预测分析失败: 栈顶 {top}, 前瞻 {lookahead}) stack.pop() stack.extend(reversed(production)) return True这段代码模拟的是预测分析表驱动的下推自动机栈里存文法符号tokens是词法分析产出的终结符流。每次循环先看栈顶是不是终结符是就直接匹配不是终结符就查预测分析表找到对应的产生式把栈顶弹出再把产生式右部逆序压栈。[]表示 ε 产生式意思是什么都不压栈直接消掉栈顶的非终结符。reversed(production)这个细节不能省因为压栈顺序决定了展开顺序不逆序就会把产生式右部倒着匹配。2.3 语义分析和中间代码生成讲义讲理论代码要自己补太原理工大学这份讲义在语义分析部分通常会讲到语法制导翻译、属性文法、中间代码形式但讲义里很少给出完整可运行的代码这一节是很多人觉得“黑匣子”的地方。其实中间代码生成不需要一次做完整只需要在语法分析的过程中把归约动作翻译成四元组即可。四元组的形式是(op, arg1, arg2, result)比如(, a, b, t1)表示t1 : a b。表达式生成中间代码本质是在递归下降的求值函数里插入 emit 动作quads [] temp_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count - 1} def emit(op, arg1, arg2, result): quads.append((op, arg1, arg2, result)) return result def expr(): left term() while lookahead : match() right term() left emit(, left, right, new_temp()) return left这里的逻辑是表达式被解析成左操作数和右操作数emit生成一条加法四元组并把结果临时变量作为下一个操作数参与后续运算。a b c会被拆成两条四元组(, a, b, t1)和(, t1, c, t2)这就是经典的三地址码。这个模式的价值在于它把分析过程与翻译过程合二为一不需要单独建一棵完整的 AST 再去遍历。讲义里的“语法制导翻译”章节要求你理解每个产生式对应什么语义动作。我的建议是动手给每个非终结符的求值函数加一个返回值让它在返回时携带“这个符号代表的值或地址”这样中间代码生成就是顺水推舟的事。3. 讲义里的理论不是摆设FIRST、FOLLOW、LR 表都要亲手算3.1 文法和 LL(1) 分析表为什么必须亲手算一遍很多人看讲义上的 FIRST、FOLLOW 集合推导过程觉得很简单就是“扫一眼”然后直接跳到预测分析表。这是个致命的错觉。考试也许能蒙对但写代码时你会发现自己根本不知道集合的迭代过程是怎么收敛的。FIRST 集合的算法是一个不动点迭代给每个终结符的 FIRST 集合初始化为它自己给每个非终结符初始化为空集然后不断遍历所有产生式把右部首符号的 FIRST 集合并入左部的 FIRST 集合直到集合不再变化。以讲义里最常见的表达式文法为例E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id手工计算的中间结果长这样符号FIRST 集合E{ (, id }E{ , ε }T{ (, id }T{ *, ε }F{ (, id }这里最值得注意的地方是 ε 的出现E 的 FIRST 里有 ε意味着 E 可以被展开为空串。当 ε 进入某个非终结符的 FIRST 集合后FOLLOW 集合计算就会受到牵连进而影响预测分析表的空白格填充。如果你把 ε 漏了后面分析表中E遇到)或$时会直接报错而不是走 ε 产生式。我建议你至少手工做两遍第一遍用笔推导第二遍写一个脚本用集合迭代验证。写脚本时用while changed循环就够关键是要把“本次迭代新增的元素”和“上次迭代已有元素”区分开否则集合会错误地包含一个产生式右部多个符号的 FIRST 集合。3.2 自底向上分析与 LR 表讲义里那几张表到底在告诉你什么自底向上分析是讲义的另一个重头戏LR(0)、SLR(1)、LR(1) 这些名词能把初学者绕晕。从落地角度看你至少要把 LR(0) 的项目集看懂项目是一个产生式右部带一个圆点的状态圆点左边是“已经读入的部分”右边是“还没读入的部分”。每当你看到一张讲义里的 LR 分析表它本质上回答一个问题“当前栈顶状态是 i下一个输入符号是 a我应该移进、归约、接受还是报错” 表里的每个格子都是一个决策。SLR(1) 与 LR(0) 的区别就是在归约项目产生冲突时用 FOLLOW 集合来排除那些不该归约的输入符号。这里有个实操方法不要试图把整个 LR 表背下来而是构造一个小文法比如只包含S - L R | R和L - * R | id把它的自动机手动画一遍自己画出状态转移图。画图的过程会让你彻底理解“项目集闭包”是什么意思当圆点后面是非终结符时要把该非终结符的所有产生式都作为新项目加进来。这个闭包计算是 LR 自动机构造里最枯燥也最容易出错的地方但一旦用代码实现过后面几十个状态都不在话下。3.3 语法制导翻译和符号表面试和实验考核都围着它转语义分析章节通常被轻视因为考试权重不高但实际做编译实验时语义分析和符号表才是真正的分水岭。讲义里的“属性文法”概念对应到代码里就是一个函数签名设计的问题。符号表的设计有三个必须想清楚的参数作用域怎么切分、标识符重名怎么处理、类型信息放在哪一层。我见过不少初学者的符号表是一个全局 dict变量重名直接覆盖结果int x; { int x; }这种合法程序被误判。正确的做法是维护一个作用域链表进入花括号时新建一层表退出时弹出当前层。查找标识符时从当前层逐层向外找这才能正确处理变量遮蔽。语法制导翻译要落地核心是把产生式对应的语义动作写在递归下降函数的合适位置。生成中间代码时赋值语句x expr的语义动作是先递归生成 expr 的中间代码再 emit 一条赋值四元组声明语句的语义动作则是在符号表里注册新名字。这两类动作的执行时机完全不同前者发生在“值”层面的归约完成时后者发生在“名”层面的声明解析时混淆了就会产出乱序的四元组。4. 照着讲义做实验最容易翻车的 5 个地方避坑与排查4.1 词法分析的正则表达式写对了状态机却跑不完整现象用re.findall扫描源码得到的结果里标识符被拆断比如int x1被识别成int和x后面跟了个孤零零的1。更诡异的是源码里明明有字符串hello输出却只剩下hello没有引号。原因这是词法分析里最经典的“匹配优先级”错误。re.findall默认从左到右按模式顺序匹配遇到第一个能匹配的模式就返回并不会在多个模式之间比较“谁匹配得更长”。标签在后面排着时只要标识符模式在数字模式之前数字尾巴就会被永远截断。字符串引号缺失则是模式里写了[a-zA-Z]却忘记把引号本身纳入匹配。解决放弃findall改用上一节那段手动比较best_len的循环。核心不是代码本身而是你要建立一个认知词法分析器的本质约束是“最长匹配 规则优先级”的联合决策不是简单地“按顺序套模式”。调试时在失败分支里打印pos和src[pos:pos20]你会很快定位到是哪个规则没兜住。4.2 递归下降碰到左递归代码直接死循环现象解析a b c时程序不报错但 CPU 占用拉满最后抛出RecursionError: maximum recursion depth exceeded。原因文法里E - E T被直接当成递归下降函数。左递归产生式的右部第一个符号还是 E函数E()第一行就调E()永远不会走到match()。这不是代码 bug而是文法形态与算法不匹配。解决在写解析器之前先把所有左递归产生式消除掉。常见做法是把E - E T | T改写成E - T E和E - T E | ε或者更实用地直接用循环表达结合性expr()先解析一个term()然后while lookahead 循环解析后续 term。后者不需要引入额外非终结符代码也更贴近运算符的结合性。记住递归下降可以处理右递归天然不处理左递归。4.3 手工算 FIRST、FOLLOW 时漏了 ε预测表出现冲突现象生成的预测分析表里同一行同一列有两个产生式代码运行时查表走到这个格子不知道该选哪个。更隐蔽的情况是表里某些格子为空输入合法也会报“语法错误”。原因计算 FIRST 集合时没把 ε 传播到位。比如E - T E | ε这个产生式E 的 FIRST 必须包含 ε如果漏了FOLLOW(E) 就无法正确计算最终影响M[E, 期望输入符号]的填表。所有“空表”都不是真的无解而是 ε 产生式没有正确触发。解决把 FIRST 集合计算写成不动点循环不要用一次遍历。循环体里先处理所有“右部第一个符号是终结符”的规则再处理“右部第一个符号是非终结符”的规则最后处理 ε 直接出现在右部的规则。算完 FIRST 再算 FOLLOW FOLLOW 计算时会用到 FIRST 集合里去掉 ε 的部分。把这两个函数做成独立的调试函数输入文法直接打印所有集合你会发现手算时漏掉的东西一目了然。4.4 符号表作用域处理错变量遮蔽和重复声明全乱现象程序里有外层变量x和内层变量x编译器要么把内层识别成重声明要么在外层作用域里读到了内层的类型信息。更烦人的是两个平行的兄弟块作用域里的同名变量互相覆盖。原因整个符号表只有一个全局字典没有作用域分层。兄弟块共享同一层表导致同一个名字被第二次声明时误判为重复定义。解决给符号表加一个作用域链表或者直接用 Python 的列表模拟栈scopes [dict()]进入块时scopes.append(dict())退出块时scopes.pop()。查找变量时从scopes[-1]一路找到scopes[0]只要有一层命中就返回。插入变量时只往scopes[-1]里写。这样内层变量遮蔽外层变量是天然行为重复声明检查只需要看当前层是否已存在同名条目。这是个三十分钟的改造却能解决一系列后续类型检查的诡异 bug。4.5 讲义里的工具链版本和你本地的对不上现象按照讲义里的步骤用 Flex/Bison 编译实验代码命令报了一堆错但讲义截图里明明是同样的命令。报错原因从undefined reference to yywrap到bison: option --enable-parsing五花八门。原因讲义基于某个特定版本的 Linux/Windows 实验环境写成而本地装的工具链版本可能更高接口和行为都变了。比如新旧 Flex 对yywrap的处理不同新版本不再默认链接libflBison 新旧版本生成的解析器默认头文件位置和函数签名也不同。解决先看报错的第一行而不是最后一行。yywrap问题最常用的解法是在词法文件末尾手动加int yywrap() { return 1; }Bison 报错则优先检查.output文件里的冲突报告。更省时间的办法是先跑讲义自带的最小示例而不是直接编译自己的整个项目。如果最小示例能过说明环境没问题问题在自己写的文法里如果最小示例都不能过再去查工具链版本差异。这个排查顺序能帮你节省几个小时。5. 把 PDF 讲义变成调试能力给自己做一个“分析过程观察器”很多人读完讲义、做完实验遇到“这个编译器的内部状态到底是怎么变的”这样的问题还是无从下手。我自己的一个习惯是不只在递归下降和预测分析的表驱动代码里塞 print而是做一个统一的分析过程观察器把栈变化、当前输入符号、执行动作三件事同时打出来。关键代码其实很短debug_enabled True def trace(stack, lookahead, action): if debug_enabled: print(f栈: {stack[:5]}... 前瞻: {lookahead!r} 动作: {action})把trace放在预测分析循环的每次迭代开头或者递归下降每个产生式的入口。这个习惯的价值在于当你写一个复杂表达式解析出错时你能直接看到“栈顶是什么、输入走到了哪个 token”而不是面对一行SyntaxError瞎猜。配合这个工具把讲义里那张 LR 分析表逐步跑一遍你会亲眼看到移进、规约动作的序列是如何对应到推导树的。另一件值得做的事是把讲义末尾的练习题当调试用例而不是当考试题。每道题自己构造输入用写好的词法分析器和语法分析器去跑看错误发生在哪一步。这个过程会让你发现真正难的从来不是背与分析表而是把讲义与代码样本之间的“接口”打通。我当年最大的收获就是找了一个很简单的 C 语言子集把词法、语法、四元组生成串成一条完整的流水线之后再看任何编译技术的资料都像在复习老朋友。希望这份路径和坑位清单能帮到你少走弯路早点把讲义变成你自己的调式工具。本文还有配套的精品资源点击获取