简介这份西南科技大学编译原理实验报告围绕“设计词法分析程序”展开面向正在学习编译原理、需要完成课程实验或复盘词法分析流程的高校学生。内容从实验目的、实验设计、实验过程到程序实现依次组织重点梳理正则表达式描述词法规则、由正则表达式构造NFA、合并并确定化为DFA、进一步最小化DFA以及单词分类与输出方案的完整链路。报告中结合TEST语言给出标识符、保留字、无符号整数、分界符、运算符和注释符等规则示例并附有基于Python状态转移表的词法分析程序框架便于读者理解状态机如何识别不同Token同时提示错误处理、缓冲区管理和回溯等后续完善方向。资源包共1个doc文件约444KB适合作为实验报告参考和考前复习材料。已有479人学习可帮助读者快速把握编译原理实验一的核心任务与实现思路。1. 编译原理实验报告踩坑实录套用这份设计型报告前先弄清楚“正则→NFA→DFA→代码”各环节的衔接编译原理实验报告最容易卡在两个环节NFA 画得出来DFA 却确定化失败DFA 画得出来代码却跑不对。这份围绕 TEST 语言编写词法分析程序的设计型实验报告走的是最传统也最稳妥的链路——先用正则描述六类词法规则再用 Thompson 构造法生成 NFA然后合并、子集构造确定化、划分法最小化最后用一张状态转移表写成 Python 分析器附带把合法单词写入 lex.txt、把词法错误连同行列号报告出来。它本质上是一份可以直接拿来对照的工程底稿而非单纯讲解概念的教材。你卡在哪个格子就翻到对应那一节。适合三类人正在交这份实验报告的人、想从零手写第一个 lexer 却停在状态表上的人、以及想搞清楚“//和/为什么总打架”的后端或工具链方向开发者。2. 正则到 NFA六类词法规则先整理成便于计算的表示这一章最容易被跳过去因为正则写起来太像“自然会做的事”。但词法分析里绝大部分纠缠不清的问题都出在正则阶段没把歧义处理干净——直接带着歧义进入 DFA后面画多少张图都白搭。下面按规则拆分、构造、合并三步来看。2.1 先把 TEST 语言的六类词拆成正则与优先级报告里给出的规则是标识符、保留字、无符号整数、分界符、运算符、注释符六类。原文那几行正则写得比较口语实操时需要补充精确化主要补充两个地方注释符那条写成/|/明显是笔误应当是//[^\n]*保留字那条和后面的单词分类表是重叠的——分类表里int同时出现在“关键字”和“保留字”里if/else/while也两边都列。这种笔误交作业时很常见但在实现层面必须先选定一种方案。我的习惯是让正则层面只保留“标识符”保留字不参与 NFA 构造识别出标识符之后再回查一张哈希表。理由很直接保留字在字符构成上完全是标识符的子集如果你给它单独构造 NFA合并之后i、in、int这些前缀重合的路径会让子集构造多出一堆互不可分的状态而最小化阶段又会因为终态标签不同而分不开最终带来不必要的麻烦。回查一张表只需要一次字典查找代价几乎为零。落实到字符类简写优先级从高到低大致是这样词法规则正则字符类简写优先级处理的歧义单行注释//[^\n]*1与除号/抢首字符双字符运算符!2与单字符、、、!抢前缀单字符运算符|-|*|/|||3注释和双字符之外的剩余情况分界符\(|\)|\{|\}|;|:3无保留字if|else|for|while|do|int|write|read4用回查表代替 NFA标识符[a-zA-Z][a-zA-Z0-9]*5与保留字、与数字开头串冲突无符号整数0|[1-9][0-9]*5与标识符抢首字符这张表里最值得琢磨的是优先级 1 和 2。注释和除号的首字符都是/双字符运算符和单字符运算符互为前缀这两组如果在正则层面不区分开后面状态表里就会出现“某一格既该去 A 又该去 B”的情况。教材上的标准答案是靠最长匹配加规则优先来解决但落到代码里最省事的做法是在进入状态机之前做一次定长前瞻具体在 4.3 节展开。提示0|[1-9][0-9]*这条正则背后的意思是“不允许前导零”。报告里那个abc 012345;的例子如果你按字面写[0-9]012345会被整体识别成一个大整数按上面这条正则它会被拆成0和12345两个 token。两种都不算错但你在实验报告里得说清楚自己按哪一种处理否则结果对不上。2.2 Thompson 构造每条正则怎么生成带 ε 边的 NFA正则到 NFA 的转换有现成套路不需要自己设计。Thompson 构造只依赖三条基本规则加一条组合规则单个字符a对应两个状态一条标a的边连接就是把上一段的接受状态用 ε 边接到下一段的初态选择就是在分叉处加新初态两条 ε 边分别进两个分支两个分支的接受态再用 ε 边汇到新终态闭包*则是在分支前后各加一条 ε 回边。拿标识符这条最常用的规则走一遍[a-zA-Z][a-zA-Z0-9]*展开后是一个“先一个字母再任意多个字母或数字”的结构状态输入后继说明q0字母q1首字符必须是字母q1字母、数字q1循环体闭包的回边q1εq2出循环q2——接受态打ID标签严格按 Thompson 构造*结构外面还会多套两层 ε 状态上面这张表已经是压过一道的版本。这一步的化简在纸面上做掉不亏每省一个状态后面子集构造就少算一次闭包而且手工演算时更不容易抄错。无符号整数那条0|[1-9][0-9]*因为带选择NFA 会长成一个两分支结构新初态用 ε 分叉一路到单个0的接受态一路进[1-9]再循环[0-9]。双字符运算符|||!同理是四条两字符路径的并联。这两类规则状态数不多但 ε 边多手算闭包时最容易被漏掉。构造完这一轮你会得到一个状态数在几十这个量级的分散 NFA 集合。注意这个量级不是巧合——六类规则里状态最多的是双字符运算符和分界符各自都是短路径真正让状态数膨胀的是 ε 边的密度而不是分支本身。2.3 合并 NFA一个统一初态省掉后面的重复活分散的 NFA 没法直接确定化得先合并。标准做法是新建一个初态 S0用 ε 边分别指向每一条规则 NFA 的初态其余结构原样保留。这样从 S0 出发的一步闭包就能同时覆盖“第一个字符可能是字母、数字、运算符、括号、斜杠”的所有情形正好对应词法分析器面对源码时的真实处境。合并时有一个必须做的动作给每个终态打上类别标签。标识符的接受态标ID整数的标NUM运算符的标OP分界符的标DELIM。没有这个标签确定化之后你只知道“这个子集里含接受态”却不知道它到底该输出哪种 token前面的构造全白做。注意合并时不要图省事把所有终态用 ε 边汇到一个统一终态上。那样做确实能让图看起来干净但代价是终态信息全部丢失最小化阶段ID和NUM会被并成一类最后abc和123输出同一个类型。这是新手最常踩的一个“看起来更优雅”的坑。合并完之后可以数一下规模六类规则加一个统一初态状态总数大致在三十到四十之间ε 边占了将近一半。这个数字决定了下一章手算子集构造的工作量——如果超过五十个状态还没有化简基本都是正则写宽松了比如把保留字也单独构造进去。3. NFA 确定化与最小化子集构造和划分法怎么手算不糊从 NFA 到能写进代码的状态表中间隔着确定化和最小化两道工序。课本上的算法描述都很简短真正动手时会发现麻烦在于“闭包算漏一个状态就得整表重来”。这一章把两道工序拆成可以逐步核对的步骤。3.1 子集构造ε-closure 与 move 的三步循环子集构造的核心是两个函数ε-closure(T)求集合 T 里所有状态经任意条 ε 边能到达的状态集合move(T, a)求集合 T 里所有状态经一条标a的边能到达的状态集合。确定化就是一个不断“取闭包、走一步、再取闭包”的循环。写成代码更好核对下面这段只做演示不追求性能# 演示用的闭包计算eps 是 {状态: [后继状态, ...]} 的邻接表 def eps_closure(states, eps): stack list(states) out set(states) while stack: s stack.pop() for t in eps.get(s, ()): # 沿 ε 边走 if t not in out: out.add(t) stack.append(t) # 新状态也要继续展开 return frozenset(out) # 走一条标 a 的边得到目标状态集合不含闭包 def move(states, a, trans): out set() for s in states: for (sym, t) in trans.get(s, ()): if sym a: out.add(t) return outeps_closure用显式栈而不是递归是因为 NFA 里存在 ε 回路闭包结构必然产生递归写法在环上会直接爆栈。move里那个sym a的判断是子集构造唯一需要区分输入符号的地方其余全是集合运算。主循环的写法是把eps_closure({S0})作为第一个集合标记为未处理反复取一个未处理集合 T对字母表里每个符号 a 算出U eps_closure(move(T, a))如果 U 非空且没出现过就加入集合族同时在转移表里记下T --a-- U直到所有集合都处理完。这里的字母表是关键参数。别拿完整 ASCII 当字母表那会出来上百列手工算根本算不完。按 2.1 节的字符类压缩成六类就够ALPHA、DIGIT、OP、DELIM、SPACE、OTHER。压缩之后转移表的列数从 128 降到 6行数也就是确定化出来的子集个数通常十几到二十几行一张 A4 纸画得下。下面是从合并 NFA 确定化出来后几个关键子集的样子符号用上面六类简写子集命名含有的 NFA 状态接受标签说明S0统一初态的 ε 闭包无起始状态S1标识符 NFA 的循环态ID读到字母后进入S2整数 NFA 的数字循环态NUM读到数字后进入S3运算符 NFA 的中间态OP读到运算符后进入S4分界符 NFA 的接受态DELIM读到括号、分号后进入E空集或错误态无任何未定义转移的去向表里那个E错误态值得单独留一格。很多同学画 DFA 时把未定义的转移直接省略结果写代码的时候遇到、$这种字符就不知道往哪走程序要么抛异常要么死循环。显式保留一个错误状态反而让代码结构更干净。手工演算时有一个自检办法数一下确定化之后的行数如果比 NFA 的状态数还多八成是某个集合的闭包算错了多生成了不该存在的子集。正常的确定化子集个数一般不超过原状态数。3.2 最小化初始划分和反复分裂的判定条件确定化出来的 DFA 往往还有冗余状态——两个状态对所有输入符号的反应完全相同那就没有分开的必要。划分法最小化就是不断把“行为一致”的状态合并到一起的迭代过程。第一刀是初始划分这是最容易做错的地方。教材上的标准写法是按“终态 / 非终态”分成两组但词法分析的 DFA 不能这么分。原因前面提过一次终态带着类别标签ID和NUM都是终态但对同一个输入符号的反应完全不同ID 吃字母NUM 吃数字合并之后类型信息就丢了。正确的初始划分是按标签分组{ID 组}、{NUM 组}、{OP 组}、{DELIM 组}、{非终态组}一共五组。之后的每一轮对每个组里的每个状态检查它对每个输入符号的去向是否仍落在同一个组里。如果有状态在某一个符号上跑到了别的组这个组就要拆。拆到某一轮没有任何组发生变化划分就稳定了。手工做的时候用一张表对着勾最清楚轮次划分结果触发分裂的符号Π0{ID}, {NUM}, {OP}, {DELIM}, {非终态}初始按标签分Π1{ID}, {NUM}, {OP}, {DELIM}, {起始态}, {中间态}起始态与中间态对 ALPHA 的去向不同Π2与 Π1 相同无稳定真实规模下这个表大概要迭代三四轮。每轮都要把所有组、所有状态、所有输入符号过一遍纸面上大概要写满一页。这一步没什么捷径但有个省力办法先把明显不同的组拆开起始态和中间态对几乎所有符号的反应都不同剩下那些“看起来差不多”的状态才需要逐符号比对。最小化完成之后状态数通常会从二十几降到七八个。报告里最终那张表的七个状态——START、ID、NUM、OPERATOR、DELIMITER、COMMENT、ERROR——就是这个量级说明前面的构造和确定化没有多走路。3.3 把最小 DFA 转成状态转移表状态名怎么起才方便调试从图到表是最后一步纸面工作也是最影响后面写代码体验的一步。状态名建议直接起成语义名而不是q0、q1理由是调试阶段你会在日志里看到大量状态名q7这种编号过两天自己都认不出来。命名沿用报告里的那套就挺好只做一点调整把COMMENT状态拿掉理由在 4.1 节解释。剩下六个状态接受态集合是{ID, NUM, OPERATOR, DELIMITER}START和ERROR不是接受态。转移表按字符类做列写出来是这样空表示无转移会触发回退状态ALPHADIGITOPDELIMOTHERSTARTIDNUMOPERATORDELIMITER—IDIDID———NUM—NUM———OPERATOR—————DELIMITER—————ERROR—————OPERATOR和DELIMITER两行全空看起来像没写完其实是正确的一个运算符或分界符读到一个字符就该结束多读一个就得回退。这张表最大的价值不是它填了什么而是它明确地把“这些位置什么都没有”写了出来——写代码时dict.get()返回None回退逻辑自然就触发了。提示ID那行只有ALPHA和DIGIT两格有转移。如果哪天你发现自己在ID行的OP或DELIM列上填了ID那就是把“标识符后面跟分号”当成一个 token 了。报告原文里那张表恰好就有这个问题第 5 章会展开讲。4. 表驱动词法分析器一张转移表加一个回退循环纸面上的 DFA 转成代码核心就三样东西字符分类函数、转移表字典、带最长匹配的主循环。这一章按这三样逐层展开代码可以直接跑。4.1 字符分类函数与/单独处理的必要性字符分类函数决定了转移表的列数也决定了 DFA 的粒度。粒度太细按 ASCII 每个字符一列表会大到没法维护粒度太粗只分字母和“其他”又识别不出运算符。按 2.1 节压缩出来的五类正好def char_class(ch): if ch.isalpha(): return ALPHA if ch.isdigit(): return DIGIT if ch in -*/!: return OP if ch in (){};:,: return DELIM return OTHERisalpha()而不是a ch z是因为前者对大小写都成立跟 2.1 节的[a-zA-Z]对得上。OP里把/和!一起放进去看起来和注释符的特殊地位矛盾但这是有意的让/在状态机层面和别的运算符一样走OPERATOR状态、单字符接受注释的判定放在状态机外层用两字符前瞻处理比在转移表里塞一个SLASH中间态要稳。原因是 DFA 天然不擅长表达“读到这个字符后还得看下一个字符”这件事。你当然可以加一个SLASH状态让它对OP类转移到一个LINECOMMENT状态但LINECOMMENT要接受任意非换行字符等于在表里开了一整行通配最小化阶段这一行会把周围的状态全搅在一起。实际工程里的词法分析器几乎都用前瞻代替——代价是两行代码收益是转移表干净。注意char_class里没有处理空白和换行。它们在主循环开头就被拦掉不进状态机。这样做的结果是转移表少两列代价是主循环多两个if。这个交换很划算因为空白的处理逻辑换行要重置列号本来就该独立于状态机。4.2 从最小 DFA 抄出转移表哪些格子必须改把 3.3 节那张表原样写成字典就是下面这段。注意None的用法——它表示“这个格子没有转移”和“这个格子指向错误态”是两回事前者触发回退后者直接报错。TRANS { # 起始态看到什么字符就进什么状态 START: {ALPHA: ID, DIGIT: NUM, OP: OPERATOR, DELIM: DELIMITER, OTHER: None}, # 标识符只吃字母和数字其余一律无转移触发回退 ID: {ALPHA: ID, DIGIT: ID, OP: None, DELIM: None, OTHER: None}, # 整数只吃数字 NUM: {ALPHA: None, DIGIT: NUM, OP: None, DELIM: None, OTHER: None}, # 运算符与分界符单字符即接受不再往后吃 OPERATOR: {ALPHA: None, DIGIT: None, OP: None, DELIM: None, OTHER: None}, DELIMITER:{ALPHA: None, DIGIT: None, OP: None, DELIM: None, OTHER: None}, } ACCEPT {ID: Identifier, NUM: UnsignedInt, OPERATOR: Operator, DELIMITER: Delimiter}ACCEPT这个字典把状态名映射到输出类型名是 3.3 节“终态带标签”的代码版本。单独抽出来而不是写死在状态名里好处是输出格式要改比如实验报告要求输出中文类型名时只动这一处。最关键的修正在ID那一行。报告原文给出的转移表里ID状态对运算符、分界符、斜杠都填了ID意味着x;会被整段吃成一个标识符。按上面这张表ID状态读到;时get(DELIM)返回None循环立刻停下来回退到上一个接受位置x和;就分开了。4.3 最长匹配的具体实现接受状态加回退状态机本身只能“走一步看一步”最长匹配需要在外面套一层记录最近一次经过接受状态时的位置走到没路可走时回退到那个位置。KEYWORDS {int, if, else, while, for, do, write, read} TWO_CHAR_OPS {, , , !} def tokenize(src): tokens, errors [], [] i, n 0, len(src) line, col 1, 1 while i n: ch src[i] # 1) 空白与换行只推进位置不产出 token if ch in \t\r: i 1; col 1; continue if ch \n: i 1; line 1; col 1; continue # 2) 注释必须先于除号判断否则 / 会被当成运算符 if src.startswith(//, i): k src.find(\n, i) if k -1: i n # 注释一直到文件末尾 else: col p a hrefhttps://download.csdn.net/download/m0_65436422/88754609 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p