简介这份西南科技大学编译原理实验报告一围绕「设计词法分析程序」展开面向正在学习编译原理、需要完成课程实验的高校学生与自学者重点解决从正则表达式到词法分析程序落地的完整链路问题。报告按实验目的、实验设计、实验过程、程序实现四部分组织先用正则表达式描述 TEST 语言的标识符、保留字、无符号整数、分界符、运算符与注释符规则再依次构造 NFA合并、确定化并化简为最小 DFA随后给出单词分类与输出方案并以 Python 状态机含字符分类函数与 DFA 状态转移表演示扫描流程同时点出错误处理、缓冲区管理与回溯等后续要点。整包为 1 个 doc 文档约 444KB保留了实验名称、指导教师、日期等完整实验报告格式可直接参照撰写或对照自查。已有 479 人学习下载适合作为课程实验的参考范本与期末复习材料。1. 一段二十行样例里的三处硬伤导师把一段不到二十行的 TEST 语言源程序放在桌上里面塞了int abc123$;、int 2a;、abc abc / i;三行要求输出完整 token 序列同时指出每个问题出现在哪一行、哪一列。多数人第一次做编译原理的词法分析实验报告就卡在这三行$没人管2a被拆成2和a两个合法单词糊弄过去/到底是除号还是单行注释的开头全凭运气。这套方案要把正则表达式、NFA、确定化与最小化、DFA 状态表、表驱动扫描器、错误队列串成一条能跑的链路最终产出一份带lex.txt和错误清单的实验交付物。适合正在做编译原理实验一「设计词法分析程序」的同学也适合需要一份可改的扫描器骨架的从业者。2. 词法规则建模把七类单词写成能对着画图的正则2.1 先把单词表钉死正则才有落笔的地方上手就写正则是这类实验里最常见的时间浪费。七类单词里只要有一类的边界没定清楚后面 NFA 合并时就会返工。我一般的顺序是先列一张单词分类表把「输出标记」这一列一并定下来因为扫描器最终吐给语法分析器的就是这一列不是中文名。类别正则表达式示例输出标记标识符(a|…|z|A|…|Z)(a|…|z|A|…|Z|0|…|9)*abc123、xID关键字int|if|else|for|while|do|read|writeint、whileKEYWORD无符号整数((1|…|9)(0|…|9)*)|00、123NUM分界符(|)|;|{|}|:{、;DELIMITER运算符|-|*|/||||||!|、OPERATOR注释符//[^\n]*//This a test program.COMMENT表里刻意没把「保留字」单列成第七类。原始素材的关键字列表里有int保留字列表里又是int两套机制同时存在最后输出时必然打架同一个int既可能被标成KEYWORD也可能被标成保留字测试用例一多就露馅。工程上的做法只有一种——关键字表唯一用字典查查中即改标这件事放到 2.3 讲。无符号整数这条正则也要盯一眼。写成(0|…|9)当然更省事但abc 012345;这行会被整段吃成合法整数而实验样例里它是故意埋的一个点。把首位限制成1-9、单独给0开一条分支012345就会在扫描到0之后把12345留成下一个 token错误处理阶段才有机会报出来。这种「正则写法直接决定程序能不能报错」的细节实验报告里最好明写一句答辩时是加分项。2.2 正则到 NFAThompjson 构造只需要三种拼装把正则变成 NFA不用背一整套形式化定义只要会三种基本拼装剩下的都是嵌套。第一种是连接ab就是两个子图首尾接上中间加一条 ε 边。第二种是选择a|b新建一个入口状态用两条 ε 边分别跳到 a 和 b 的子图再各用一条 ε 边汇到一个新出口。第三种是闭包a*在子图入口和出口之间加一条回边同时加一条从入口直通出口的 ε 边保证零次匹配也能过。按这个套路标识符的 NFA 大致长这样入口 ε 分叉出一条到「字母」边的路径字母边指向一个中间状态这个中间状态既接受字母也接受数字并自环同时 ε 连到出口。读起来有点绕但只要在纸上画过一次就会发现它跟正则表达式是逐字符对应的。无符号整数要单独说一句因为它是本实验里唯一带优先级的规则。0单独一条边直达接受状态1-9走另一条边再自环吃0-9。两条分支的接受状态不同但都标成NUM这正是后面最小化时要合并的那类状态。运算符的 NFA 是整个图里最容易被画糊的部分。、、、!这四个双字符运算符必须在读完第二个字符之后才允许进入接受状态。也就是说后面接一个中间状态这个中间状态本身可以作为「大于号」的接受状态同时有一条边通向另一个「大于等于」的接受状态。这个中间状态是后面的关键扫描器读到时先记下这里可以结束再看下一个字符是就继续走不是就退回来。最长匹配的全部原理就藏在这个中间状态里。还有一条容易被忽略!本身不是 TEST 语言的合法运算符只有!是。所以!后面那个中间状态不能标成接受状态。如果偷懒直接把所有单字符都设成接受遇到孤零零一个!时会静默通过测试用例里的i ! n写错成i ! n就查不出来了。2.3 关键字不做进 DFA识别完再查表为什么不让 DFA 直接识别while因为把八个关键字和标识符一起做进状态图状态数会从十几个膨胀到几十个图没法画表也没法看而且每加一个关键字就要重画整张图。教科书的通行做法是DFA 只认标识符扫描器拿到词素之后查一次哈希表命中就改类型。# 关键字表只有一份不放第二条「保留字」通道 KEYWORDS {int, if, else, for, while, do, read, write} def classify(lexeme, base_type): base_type 来自 DFA 的接受状态这里只做一次回填。 if base_type ID and lexeme in KEYWORDS: return KEYWORD return base_type这段逻辑的价值不在于代码短而在于它把「词法形态」和「语义归类」拆开了。DFA 负责判断这串字符长得像不像一个标识符字典负责判断它在语言里是不是有特殊身份。好处很直接加关键字只改字典不动状态图答辩时被问到「新增一个关键字要改几处」答案是改一行这个问题基本就稳了。需要提醒的是回填的时机。必须等一个标识符完整识别完、确认它结束于非字母数字字符之后才能查表。中途查表会把intx误判成关键字int加x这是初学者最常犯的一个错。查表发生在「一个 token 已经确定边界」之后这个顺序不能反。2.4 注释符不是普通单词它得单独定义处理规则//这条规则有个尴尬之处按实验要求它属于七类单词之一要写正则、要进 NFA但按编译器的实际行为注释在词法阶段就被丢弃根本不进 token 流。这两件事并不冲突处理方式是把注释也纳入状态机但主循环拿到COMMENT类型的 token 后直接扔掉只更新行号和列号。正则写成//[^\n]*而不是//.*原因很实在.在很多实现里默认不匹配换行符但一旦有人开了 dotall 模式.*就会把整个文件吞成一条注释。写[^\n]*是显式声明「注释到行尾为止」这个习惯我保留了很长时间因为它不依赖任何引擎的默认开关。另一处细节是注释内部允许出现任意字符包括$、这些在外面属于非法字符的东西。样例程序第一行是{ //This a test program.如果状态机在注释里还老老实实做字符集校验$之类的东西就会被误报成词法错误。注释状态应该对所有非换行字符一律放行这是一条硬规则。3. 从 NFA 到最小 DFA状态表才是能写进代码的东西3.1 合并与子集构造把 ε 闭包算清楚就行把六张 NFA 合并成一张最省事的办法是加一个新的总入口状态用 ε 边分别连到六张子图的入口。合并之后它仍然是个 NFA一个状态遇到一个字符可能跳到多个次态还带一堆 ε 边。确定化子集构造要做的就是把「状态集合」当成新状态。流程是三步循环从初始状态的 ε 闭包开始对每个输入字符算一次 move 得到新集合再对新集合求 ε 闭包如果这个集合没出现过就给它编号入队直到队列空。def epsilon_closure(states, eps_edges): eps_edges: state - set(states)求传递闭包 stack list(states) closure set(states) while stack: s stack.pop() for t in eps_edges.get(s, ()): if t not in closure: closure.add(t) stack.append(t) return frozenset(closure) def subset_construct(start, trans, eps_edges, alphabet): trans: (state, char) - set(states) start_set epsilon_closure({start}, eps_edges) dfa {start_set: 0} # 子集 - DFA 状态编号 order [start_set] table {} i 0 while i len(order): cur order[i] for ch in alphabet: moved set() for s in cur: moved | trans.get((s, ch), set()) if not moved: continue nxt epsilon_closure(moved, eps_edges) if nxt not in dfa: dfa[nxt] len(order) order.append(nxt) table[(i, ch)] dfa[nxt] i 1 return order, table这三个函数的关系是epsilon_closure是工具subset_construct是主循环外层驱动按字母表逐字符推进。字母表不需要真的列 52 个字母用「字母类 / 数字类 / 具体符号」做等价类就够了表能小一个数量级。这段代码写进实验报告时注释里最好标明「此处对应实验步骤三的确定化」。确定化之后要标接受状态。一个子集只要含有任意一个原子图的接受状态它就是接受状态接受类型取那个原子图对应的类型。如果一个子集同时含两种接受状态说明正则之间有重叠这是设计错误必须回去改正则而不是在代码里随便挑一个。3.2 最小化划分时接受类型必须分桶最小化的标准做法是划分法初始把状态分成「非接受」和「接受」两组然后反复检查同组内两个状态遇到同一字符是否跳到同一组不同就拆开直到不再变化。这里有一个必须强调的细节。初始划分不能只分「接受 / 非接受」两桶必须按接受类型分桶也就是ID一桶、NUM一桶、OPERATOR一桶、DELIMITER一桶其余为非接受桶。如果只按接受与否分的接受状态和的接受状态会被判成等价合并掉最后输出成样例程序里i n那一行立刻崩。这个坑我在第一次做的时候就踩过症状是运算符全变成同一个符号查了半天状态图问题其实在划分的初始条件。最小化的收益也要说清楚不要为了流程完整而做。合并前的 DFA 可能有三十来个状态合并后通常能压到二十个以内对程序性能影响不大对实验报告的意义在于「证明你理解了等价状态」。答辩被问到「最小化省了多少状态」能报出具体数字和合并掉的是哪几个状态比背定义有用得多。3.3 状态表落地用字符直接做键的字典最小化后的 DFA 最终要变成代码里的数据结构。我倾向用嵌套字典外层是状态名内层是输入值是次态。字母和数字用两个伪键表示其余字符直接用它本身做键这样表可以照着状态图一行一行抄下来不容易抄错。# 最小化后的 DFA 转移表节选覆盖标识符、整数、运算符、分界符、注释 DFA { S: {ALPHA: ID, DIGIT: NUM, /: SLASH, : OP, -: OP, *: OP, : EQ, : LT, : GT, !: BANG, (: LP, ): RP, {: LB, }: RB, ;: SEMI, :: COLON}, ID: {ALPHA: ID, DIGIT: ID}, NUM: {DIGIT: NUM}, SLASH: {/: COMMENT}, # 只有第二个 / 才进注释 EQ: {: OP2}, # LT: {: OP2}, # GT: {: OP2}, # BANG: {: OP2}, # ! 单独的 ! 不是合法 token } # 接受状态 - 输出类型 ACCEPT { ID: ID, NUM: NUM, OP: OPERATOR, SLASH: OPERATOR, EQ: OPERATOR, LT: OPERATOR, GT: OPERATOR, OP2: OPERATOR, LP: DELIMITER, RP: DELIMITER, LB: DELIMITER, RB: DELIMITER, SEMI: DELIMITER, COLON: DELIMITER, COMMENT: COMMENT, }表里有两个地方值得单独解释。第一SLASH同时是接受状态除号和有出边的状态注释开头这种「可接受但未终结」的状态正是最长匹配的载体。第二BANG不在ACCEPT里孤立的!会走到一个既不能接受也没有出边的位置扫描器返回失败报「非法运算符」这是有意留的。3.4 手工验证拿三个字符串走一遍表在写扫描器之前最好先手工跑三个串确认表是对的。这是整个实验里最省时间的一步很多人跳过它结果在代码里找了一晚上 bug。abc123从S出发a走ALPHA到IDb、c自环1、2、3走DIGIT自环仍然在ID。字符串结束ID是接受状态输出标识符。从S出发到GTGT是接受状态先记下「这里可以结束」接着读到OP2OP2也是接受状态更新记录再往后没有字符返回OP2的接受结果得到。这就是最长匹配。单独出现时读到到GT记下可结束下一个字符是空格GT对空格没有出边循环终止回退到上次记录的结束位置只吃掉。如果没有这个「记录 回退」扫描器会把空格也吞进来或者在读时就急急忙忙返回。4. 扫描器实现表驱动主循环加最长匹配回退4.1 逐字符迁移的写法有三个硬伤原始素材里那份参考程序把状态迁移写成了「当前状态 当前字符类别」的二维查表看上去挺规整但有三处会直接导致结果错。第一标识符状态的转移行里遇到OPERATOR_DELIMITER还留在ID。也就是说x;会整段被当成一个标识符分号丢失。第二注释状态遇到/还是留在COMMENT遇到其他字符也进ERROR完全没有「吃到行尾」的概念。第三整个循环没有「回退」这个概念读到之后如果下一个是没法把单独作为一个 token 吐出去。这三个问题的共性是把「状态」和「token 边界」混为一谈了。修正思路很简单状态机只负责往前探什么时候结束由「最后一次见到的接受状态」决定探不动了就退回来。4.2 核心一个带回退的匹配函数把匹配拆成两层一层负责单步转移一层负责在一个位置上尽可能往前吃并记录最后一个可接受点。def key_of(ch): 把字符归成转移表里的键字母、数字、或字符本身 if ch.isalpha(): return ALPHA if ch.isdigit(): return DIGIT return ch def step(state, ch): 单步转移处理不了返回 None注释状态单独吃整行 if state COMMENT: return COMMENT if ch ! \n else None return DFA.get(state, {}).get(key_of(ch)) def match_token(src, start): 从 start 开始做最长匹配。 返回 (token_type, end_index)识别失败返回 None。 state S j start best None # (type, end) 最后一次可接受的位置 n len(src) while j n: nxt step(state, src[j]) if nxt is None: break state nxt j 1 if state in ACCEPT: best (ACCEPT[state], j) # 只记录不返回 return bestmatch_token的关键在于「不提前返回」。每走到一个接受状态就把(类型, 结束位置)存进best一直走到走不动为止最后返回best。这样后面跟时GT会被记一次OP2会被再记一次并覆盖前者最终按OP2返回后面跟空格时GT被记一次再往下走不动返回GT。同一个函数同时覆盖了单字符和双字符运算符不需要为写任何特判。step里对注释的处理是实用主义的注释状态不看字符集只要不是换行就继续吃。这相当于把「注释内部允许任意字符」这条规则写在了转移逻辑里代价是注释状态不像其他状态那样由表驱动收益是不用给几十个非法字符一个个建转移。这种小妥协在实验报告里写一句「注释状态的处理从简」就够了。4.3 主循环跳过空白、丢弃注释、同步行列号有了match_token主循环就只剩下调度和记账。这里最容易出错的不是识别是行号和列号的维护。def scan(src): tokens, errors [], [] i, line, col 0, 1, 1 n len(src) while i n: ch src[i] if ch \n: i 1; line 1; col 1 continue if ch in \t\r: i 1; col 1 continue best match_token(src, i) if best is None: errors.append((line, col, illegal character %r % ch)) i 1; col 1 continue ttype, end best lexeme src[i:end] # 数字后面紧跟字母词法上能拆开语义上没有意义单独报错 if ttype NUM and end n and (src[end].isalpha() or src[end] _): k end while k n and (src[k].isalnum() or src[k] _): k 1 errors.append((line, col, illegal number %r % src[i:k])) col k - i i k continue if ttype COMMENT: for c in lexeme: # 注释丢弃但行列要跟着走 if c \n: line 1; col 1 else: col 1 i end continue if ttype ID and lexeme in KEYWORDS: ttype KEYWORD tokens.append((ttype, lexeme, line, col)) col end - i i end return tokens, errors四个分支的顺序不能换。换行和空白必须最先处理否则match_token会在空白处返回None整个文件到处都是「非法字符」错误。注释必须在标识符前面判因为/已经被SLASH状态接走了走到COMMENT时不会再回到运算符分支。数字后跟字母的检查放在最后、token 入列之前它不改识别结果只额外记一条错误。那个for c in lexeme的小循环看着笨其实是在还债注释可能是整行里面有且仅有一个换行但注释本身不产生 token如果直接把i推到end而不更新行列号下一行所有 token 的行号都会少 1。这类错误在短样例里看不出来样例一长就全乱。同样的账在col end - i那一行也记了一次两次记账的规则统一成「谁推进了 i谁负责更新 line 和 col」是我后来强制自己遵守的规矩。4.4 输出 lex.txt 与错误清单结果落盘分两个文件一个存合法单词一个存错误。格式不用花哨每行一条字段之间用固定分隔符方便后面写脚本比对。def dump(tokens, errors, token_pathlex.txt, err_pathlex_err.txt): with open(token_path, w, encodingutf-8) as f: for ttype, lexeme, line, col in tokens: f.write(%s\t%s\t%d\t%d\n % (ttype, lexeme, line, col)) with open(err_path, w, encodingutf-8) as f: for line, col, msg in errors: f.write(%d:%d\t%s\n % (line, col, msg))拿样例程序跑一遍期望的输出大致是这样第一行的{是分界符随后整段//This a test program.被当注释丢弃不占 tokenint abc123$;会先输出KEYWORD int、ID abc123然后在$处报一个「illegal character $」int 123;输出KEYWORD int、NUM 123在处报错int 2a;会先输出KEYWORD int然后在2a处报「illegal number 2a」而不是把2和a分两条默默放过去。最后这条需要说明一下立场。严格按词法规则2a完全可以拆成NUM 2和ID a两个合法 token编译器没有义务报错但实验要求明确把2a列为错误那就得加一条语法层面的启发式检查。写报告时把这一层说明白比硬说「词法规则规定数字后不能跟字母」要可信得多答辩时被追问也不至于卡住。5. 排查清单五个最容易翻车的点5.1 除号被当成注释开头整行消失现象abc abc / i;这一行后面的 token 全部丢失lex.txt里只剩到abc为止。原因状态机里SLASH状态读到/之后直接跳到注释状态但代码在SLASH这一层就判断「这是注释」把后面的内容一直吃到行尾。实际上第一个/是除号只有连续两个/才是注释。解决SLASH必须是接受状态且类型是OPERATOR只有在它继续读到第二个/时才转入COMMENT。依靠 4.2 里的最长匹配机制/会停在SLASH并按除号输出//会走到COMMENT并按注释丢弃。改完之后拿abc abc / i;和// test两行分别验一遍两类都能过才算修好。5.2 最长匹配丢失被拆成两个符号现象i n输出成OPERATOR 加OPERATOR token 数比预期多一倍。原因match_token里一进接受状态就return读到的时候LT恰好是接受状态函数立刻返回根本没机会看后面的。解决接受状态只记录不返回用一个best变量保存「目前最长的可接受结果」循环跑到走不动为止再返回best。改完用、、!、!四个串各测一次前三个应该有输出最后一个应该报错。5.3 标识符状态吞掉后面的分号现象int x;只输出两个 tokenx;被合成一个标识符。原因DFA 表里ID状态的转移行写得太宽把运算符、分界符的字符类也留在了ID上。这多半是从 NFA 直接抄表时把「状态可以接受任意字符」误解成了「状态对所有字符都有出边」。解决ID状态只保留ALPHA和DIGIT两条自环其余字符一律无出边靠回退结束 token。这条规则对所有接受状态都适用——接受状态意味着「可以在这里停」不意味着「可以继续吃任何字符」。改完后拿abc123$验一遍期望得到ID abc123加一个非法字符错误。5.4 错误位置漂移行号列号对不上现象报错指向第 3 行实际错误在第 4 行或者同一行里第二个错误的位置总是比实际靠前几位。原因跳过一个非法字符时只写了i 1忘了col 1或者注释里含换行直接i end跳过去line没有跟着加。两种漏记都会让后面的计数整体偏移而且偏移量会累积。解决所有推进i的地方都成对更新line和col包括跳过空白、跳过非法字符、跳过注释、正常吐出 token 四条路径。写完拿一段每行都埋一个错误的程序跑一遍逐个核对报错坐标比读代码快得多。5.5 前导零整数一路绿灯现象abc 012345;输出成OPERATOR 加NUM 012345没有任何报错。原因无符号整数的正则写成了(0|…|9)首位是0也合法整串自然被吃成一个数字。样例里这一行是故意放的不报错就等于漏了一个测试点。解决正则改成((1|…|9)(0|…|9)*)|0DFA 里0单独一条边直达接受状态1-9走另一条边再自环。这样扫描到012345时会先吃下0作为一个整数剩下的12345作为下一个整数中间没有分隔符再叠一条「数字后紧跟数字但已被前一个 token 截断」的检查就能把这一行报出来。6. 验收与答辩用三张表讲完整个设计验收这一步多数人栽在「程序跑通了但讲不清」。导师不会盯着代码看他会问三个问题规则是怎么变成状态图的、状态图是怎么变成代码的、错了怎么定位。把这三件事各准备一张表演示就能顺着走完。验收项检查方式合格标准规则完整性对照单词表逐类构造测试串六类单词各至少一条正例、一条反例自动机正确性手工走表验证、abc123、0123三串结果与预期一致最长匹配输入ab与abtoken 数分别为 5 和 5运算符类型正确错误定位输入样例程序两处错误行号列号准确lex.txt内容完整注释处理输入含//与/混合的程序注释丢弃、除号保留行号不偏移答辩时我最常用的开场是拿出 DFA 状态表指着SLASH那一行说「这个状态既是接受状态又有出边它是整个设计里唯一需要回退的地方也是我调试时间最长的地方。」这句话一出后面的问题基本都会围绕最长匹配展开而这块恰好是我准备最充分的。反过来如果一上来就讲正则表达式怎么推导很容易被追问 NFA 的 ε 闭包细节那些东西在纸上画得清、嘴上说不清。演示顺序建议固定成先跑一遍正确程序展示lex.txt再跑一遍错误程序展示报错坐标最后打开状态表说明错误是怎么被这张表定位的。三步走完大概五分钟剩下的时间留给提问。提前把lex.txt的内容打印一份带在身上比当场翻文件稳。有件事我吃过亏第一次验收时程序在样例上跑得挺好导师随手加了一行while (i n) do结果do被识别成了标识符因为关键字表里漏了它。从那以后我每次交这类实验都会把关键字表里的每个词单独丢进扫描器跑一遍八个词八行输出全对才敢往下走。一个具体的提问套路也提前准备好「你这个 DFA 有多少个状态最小化省了几个省掉的是哪几个」标准答案要能说出具体数字和合并掉的类型比如「合并前三十一个合并后十九个合掉的是几个只认单个分界符的终态」。答得出数字说明你真的跑过最小化算法而不是抄了一张图。希望帮到你。本文还有配套的精品资源点击获取
