简介西南科技大学编译原理课程实验报告主题为设计词法分析程序面向计算机科学与软件工程等专业本科生及自学编译原理的读者。报告以TEST语言为例先给出标识符、保留字、无符号整数、分界符、运算符、单行注释等词法规则的正则表达式再逐步构造NFA、合并、确定化并化简为最小DFA同时确定了单词分类和输出格式最终用Python实现完整的词法分析程序包含字符类别判断函数及对应的DFA状态转移表能够识别多种单词类型关键字、标识符、数字、运算符、分界符与注释并附有输入实例的运行结果供对照验证。资源共为1个doc文档压缩包大小约444KB目前已有477人学习下载适合作为编译原理实验报告撰写和词法分析入门复习的参考资料。1. 设计词法分析程序从正则到最小DFA这份编译原理实验报告到底在解决什么如果你在学编译原理或者正在做那个绕不过去的词法分析实验你大概率会撞上“TEST语言”这组词法规则标识符、保留字、无符号整数、分界符、运算符、单行注释。很多人一上来就写if判断遇到.就判断是不是数字、遇到/就判断是不是注释结果规则一多直接失控。而这份实验报告走的是完整路线先用正则表达式描述每个token再构造NFA合并后确定化最小化得到DFA最后用Python实现。它解决的是“token识别逻辑怎么组织才不翻车”而不是“这个字符是不是字母”。适合正在做词法分析实验的学生、对自动机理论一知半解但想落地的人也适合想看看别人的DFA状态表怎么设计的一线开发。报告篇幅不长但关键的坑和调试记录都给了。2. 用正则描述词法规则TEST语言的六类token与NFA构造2.1 六类token的边界保留字和标识符为什么必须拆开TEST语言的词法规则在报告里列得很清爽一共六类。标识符是字母开头后面跟零个或多个字母数字无符号整数要么是单0要么是1-9开头后跟数字运算符有 - * / ! 分界符是括号、花括号、分号保留字是int if else while for read write do注释是//开头。唯一让我膈应的是报告里注释的正则写成/|/这明显是个笔误。单行注释的正则应该是//[^\n]*也就是两个斜杠后跟任意非换行字符否则没法解释它怎么匹配到行尾。保留字和标识符的关系是第一个容易踩的坑。如果正则写成(if|else|...|(letter)(letter|digit)*)那么字符串if会同时被两条路接受。教科书里的标准解法是“先按标识符识别再查保留字表”而不是在自动机里为每个保留字单独造状态。你想想如果保留字有50个DFA状态会多大所以状态机里只留ID这一个类别动作上查表即可。这样做还有个好处你以后加一个保留字只需要改表不用动DFA。报告里没有明确说这个查表动作但把保留字单独列成一类意思就是这个。分界符和运算符在报告里被混在一起了。分界符( ) ; { }和运算符 - * / 在Python代码里统一归成了OPERATOR_DELIMITER类别。这倒也省事反正最终输出时都可以细分为具体的符号。但如果你后面做语法分析分界符和运算符的语义不同最好在token类型里区分开。比如输出Delimiter: ;和Operator: 这对后续递归下降分析帮助很大不然语法分析器每次都要猜。2.2 手写NFA一个token一个子图别混在一起构造NFA的常见做法是每个token单独画一张小状态图然后用ε边把它们接到一个新的起始状态。以标识符为例NFA有两个状态起始状态S_id读入letter到A_idA_id读入letter或digit仍然回到A_idA_id是接受态。无符号整数需要两条分支一条读0直接到接受态A_num另一条读1-9到B_numB_num读0-9自循环B_num也是接受态。注意0后面如果跟数字怎么办按报告的正则是不允许的但NFA里如果不小心在A_num加了数字自循环就会接受0123。这个取舍要提前想好因为很多C变体语言允许前导零而TEST语言这里正则明显不允许。运算符和分界符的NFA最简单每个符号就是一条边。但、、、!这类双字符运算符要写成两个状态读到中间态再读到接受态。而单独的也要有一个接受态。这样确定化后才能根据“当前是否还有更长的匹配”来决定输出哪个token。这个细节就是最长匹配原则的自动机实现基础。你如果不画双字符的分支只画单个字符那后面最小化DFA时会被拆成两个token。写NFA时我习惯用一张表记录每个状态状态编号、是普通态还是接受态、如果是接受态对应哪个token类型。不记录的话后面确定化成状态集合时你会分不清{A_id, B_num}到底该输出什么。报告里没有给出NFA图的具体状态表只画了图所以你需要自己补这一步。我一般会把表头列成状态名、对letter、对digit、对symbol、是否接受、token类别。这样后面写程序时直接照着填字典。2.3 合并NFA时最容易犯的错起始状态和终态全串了合并NFA不是把几个图叠在一起就行。正确姿势是新建一个START状态从START发ε边到每个子图的起始状态子图的接受态各自保留互不干扰。为什么要这样因为如果不加START直接共用初始状态比如标识符的初始态和数字的初始态都是同一个那遇到1和遇到a就不知道该走哪个分支NFA就真成了“不确定”的机器——当然NFA本来就是不确定的但这里的不确定不是理论上的多条ε路径而是状态图结构错误。还有一种常见错法是所有接受态合并成一个。比如标识符的接受态和运算符的接受态并起来那以后匹配完一个单词你不知道它属于哪类。所以接受态上要打标签。我一般会在状态表里加一列“token类别”这一步花了功夫后面确定化到最小化就不会晕。报告里合并后直接画DFA省略了合并NFA的中间图对初学者来说有点跳跃。我建议你自己补一张合并后的NFA草图不用画得漂亮但要标清楚每个状态的归属。合并完之后检查一遍从新START出发每个字符类别是否都有清晰的路径如果没有说明某个token的NFA没画对。检查的方法是用纸顺着每个token的样例走一遍比如abc123、123、、//。不要偷懒这个检查能省掉后面代码调试的一半时间。3. NFA确定化与最小化从理论到可执行的DFA3.1 子集构造法把ε-closure和move一步步算出来确定化就是把NFA的“状态集合”变成DFA的“状态”。核心操作是ε闭包和move。从起始状态出发先计算ε闭包包含所有能通过ε边到达的状态然后对每个字符类别计算闭包中所有状态经该类别转移后到达的新状态再取新状态的ε闭包得到DFA的一个新状态。拿上面那两个子图举例。假设合并后起始状态为SS有ε边到S_id和S_num。那么起始状态的ε闭包是{S, S_id, S_num}。输入字母letter集合里S_id有一条边到A_idS和S_num没有字母边所以move结果是{A_id}再取ε闭包仍然是{A_id}。于是DFA起始状态对字母转移到状态{A_id}。输入数字digit集合里S_num有两条边0和1-9得到{A_num, B_num}闭包后依旧是这个集合。这样DFA起始表就有了两行转移。实际操作中我建议写一个小脚本自动算手算容易漏。脚本逻辑很直接先定义NFA的转移表再BFS生成子集。但实验报告里通常要求手画所以我给你一个检查方法算完子集后把每个子集里的状态都列出来看看有没有遗漏的ε边。比如标识符的A_id如果有一条ε边到终态你没算闭包后面就会莫名其妙走到空状态。以TEST语言这种规模子集数量不会超过二十个手算完全可行但每算完一行务必回到NFA图上核对一遍。3.2 最小化DFA用划分法把等价状态合并最小化的目的是去掉冗余状态。做法是先按“是否接受态”分成两组然后不停地把组内状态按“对某字符的转移是否落在同一个组”来细分。什么时候停止所有组内部状态对每个字符类别的转移目标都在同一组那就不能再拆了。比如DFA里有状态P和Q两者都是接受态都对应标识符。它们对字母都转移到接受组对数字也都转移到接受组对其他字符都回退那它们等价可以合并。但如果P对数字转移到非接受态、Q对数字转移到接受态它们立即被拆开。分割法的好处是不用枚举所有状态对复杂度低。从{接受态组}和{非接受态组}开始按字符类别逐个细分通常三轮内收敛。报告里最终DFA状态就七个明显是压过的。我压的时候发现一个现象运算符和分界符如果被归为同一类那么OPERATOR状态就可以吃掉所有符号导致最小化后分界符和运算符不容易区分。这也是为什么我在字符分类那一层就把它们拆开宁可状态多一点也别让token类型混淆。最小化不是目的可维护才是。状态少但含义含混的DFA写代码时照样要打补丁。3.3 实验里最终DFA状态映射到token的对应关系报告给出的dfa字典和状态图可以对照着看。我把关键转移整理成一张表注意这里用的是原报告的类别名当前状态输入类别下一状态备注STARTALPHABETID进入标识符STARTDIGITNUM进入整数STARTOPERATOR_DELIMITEROPERATOR进入运算符/分界符STARTSLASHCOMMENT原表这样写但实际有bugIDALPHABETID继续IDDIGITID继续IDOPERATOR_DELIMITERID这里错误地吞掉了运算符NUMDIGITNUM继续NUMALPHABETERROR报错OPERATOROPERATOR_DELIMITEROPERATOR继续COMMENTSLASHCOMMENT只处理//不行这张表最大的问题在于ID的第四行标识符后面跟运算符时不应该留在ID状态。正确逻辑是把当前标识符输出然后从START重新处理运算符。这个坑直接导致abc abc这种带等号的表达式会被拆错。你在照着写自己的DFA时把ID对OPERATOR_DELIMITER的转移删掉让主循环去处理“回退”。另外COMMENT状态对字母和数字都是ERROR意味着注释里的内容根本没法识别这也是报告调试记录里“处理注释符出错”的根源。4. 用Python实现DFA词法分析器代码逐行拆解4.1 字符分类函数为什么返回类别而不是直接返回字符报告给的Python代码用一个get_char_category函数把字符归类而不是直接在状态转移字典里判断具体字符。这是对的——如果状态转移表直接写字符那状态表会巨大无比而且这不符合DFA的精神。但这份代码有个明显的bugdef get_char_category(char): if char.isalpha(): return ALPHABET elif char.isdigit(): return DIGIT elif char in {, -, *, /, , , , !, (, ), {, }, ;}: return OPERATOR_DELIMITER elif char.isspace(): return WHITESPACE elif char /: return SLASH else: return OTHER注意那个操作符和分界符集合里包含了/所以elif char /永远不会执行。结果是//注释被当成两个除号运算符这就是报告实验调试记录里说的“无法处理除运算符号/”和“处理注释符时会出现错误”的直接原因。类别划分本身没问题问题在于顺序和重复。常见的做法是把/单独提到最前面判断或者把/从OPERATOR_DELIMITER集合里去掉。另外这里把运算符和分界符合成一个类别OPERATOR_DELIMITER导致后面的DFA状态里DELIMITER形同虚设。你在写自己的分类函数时最好让类别和状态表一一对应宁可多几个类别也别用一个大杂烩。4.2 状态转移表用字典模拟DFA状态和类别都要可控报告里的dfa字典是这样的dfa { START: {ALPHABET: ID, DIGIT: NUM, OPERATOR_DELIMITER: OPERATOR, SLASH: COMMENT, OTHER: ERROR}, ID: {ALPHABET: ID, DIGIT: ID, OPERATOR_DELIMITER: ID, SLASH: ID, OTHER: ERROR}, NUM: {ALPHABET: ERROR, DIGIT: NUM, OPERATOR_DELIMITER: ERROR, SLASH: ERROR, OTHER: ERROR}, OPERATOR: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: OPERATOR, SLASH: ERROR, OTHER: ERROR}, DELIMITER: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: DELIMITER, SLASH: ERROR, OTHER: ERROR}, COMMENT: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: ERROR, SLASH: COMMENT, OTHER: ERROR}, ERROR: {ALPHABET: ERROR, DIGIT: ERROR, OPERATOR_DELIMITER: ERROR, SLASH: ERROR, OTHER: ERROR} }这里有个细节ID状态对OPERATOR_DELIMITER的转移是保持在ID这不对。当标识符后面紧跟一个运算符或分界符时应该先结束当前标识符再处理这个运算符。报告里这个表的意思似乎是“把运算符也吞进ID”那id就会被识别成标识符id。这显然不符合最长匹配。真正需要在主循环里做“回退”——当状态不是终态且遇到不能转移的字符时把当前字符退回输入流。再看NUM状态遇到OPERATOR_DELIMITER转ERROR意思是123;会报错实际上123后面跟分号应该是合法的只不过分号是另一个token。正确的做法是回退分号输出NUM再从START处理分号。所以这个状态表只能算教学示意直接拿来跑必定翻车。我在实现时会把它改成每个状态记录“是否接受态”并且对某些类别不写转移而在主循环里做回退。4.3 主循环与token输出缓冲区、状态重置与最后处理报告里的主循环def lex_analysis(input_string): current_state START current_token tokens [] for char in input_string: category get_char_category(char) if category in dfa[current_state]: current_state dfa[current_state][category] current_token char else: if current_state not in {WHITESPACE, COMMENT, ERROR}: tokens.append((current_state, current_token)) current_state START current_token if category ! WHITESPACE: current_state dfa[current_state][category] current_token char if current_state not in {WHITESPACE, COMMENT, ERROR}: tokens.append((current_state, current_token)) return tokens这个写法有代表性用一个current_token累积字符遇到无法转移的字符时先把缓冲区里的token输出再重新开始。但它没有处理“标识符后面跟空格”的情况实际上int x;第一个空格会触发else输出ID状态下的int重置。然后空格被跳过x进入ID循环结束前输出x。逻辑看似可行但最大的问题是它把WHITESPACE也当成一种状态参与判断而WHITESPACE根本不是DFA状态。更隐蔽的问题是它没有处理EOF时的状态比如文件结尾是注释那循环结束后current_state还在COMMENT直接丢弃这倒还好。但如果结尾是运算符比如最后一行没有换行current_token里剩下一个也能正常输出。输出方面报告里给的示例输出是Keyword: int、Identifier: x这种但代码里输出的是Token: int, Type: ID。所以还需要一个从DFA状态到token类别的映射表比如ID可能映射成Identifier或Keyword具体看单词在不在保留字表里。这部分报告没写全是实验报告常见的“只做一半”。4.4 修正版主循环加回退、加映射、写文件我基于原问题重写了一个能跑的主循环。注意这不是唯一方案但可以对照着看RESERVED {int, if, else, while, for, read, write, do} def get_char_category(char): if char.isalpha(): return ALPHABET if char.isdigit(): return DIGIT if char.isspace(): return WHITESPACE if char /: return SLASH # 先把 / 单独拿出来 if char in -*!(){};: return SYMBOL # 其余符号统一 return OTHER dfa { START: {ALPHABET: ID, DIGIT: NUM, SLASH: SLASH, SYMBOL: SYMBOL}, ID: {ALPHABET: ID, DIGIT: ID}, NUM: {DIGIT: NUM}, SLASH: {SLASH: COMMENT}, COMMENT: {cat: COMMENT for cat in [ALPHABET,DIGIT,SYMBOL,SLASH,OTHER,WHITESPACE]}, SYMBOL: {SYMBOL: SYMBOL}, } def lex_analysis(input_string): i 0 tokens [] line 1 length len(input_string) while i length: ch input_string[i] if ch \n: line 1 i 1 continue cat get_char_category(ch) state dfa[START].get(cat) if state is None: print(fLine {line}: 无法识别的字符 {ch!r}) i 1 continue start_i i while i length: c input_string[i] c_cat get_char_category(c) nxt dfa[state].get(c_cat) if nxt is None: break state nxt i 1 if state COMMENT: while i length and input_string[i] ! \n: i 1 break token input_string[start_i:i] if state ID: ttype Keyword if token in RESERVED else Identifier elif state NUM: ttype UnsignedInt elif state SYMBOL: ttype OperatorOrDelimiter else: ttype state tokens.append((ttype, token, line)) return tokens这里做了四个关键改动/单独成SLASH类别、SLASH后接SLASH进COMMENT、注释吃到换行、主循环用while手工回退而不是for盲目累加。输出时顺便记了行号方便报告错误位置。这个版本正好能处理报告测试程序里的//This a test program.。注意SYMBOL状态没有做最长匹配去区分和严格说还需要多读一个字符做判断但这个留到后面说。5. 避坑记录/的分叉、状态表漏洞与lex.txt输出5.1 现象//被拆成两个除号注释行全乱报告实验调试记录里写得很直白“代码运行结果中不能处理除运算符号/处理注释符时会出现错误”。我在拿到代码第一眼就发现了get_char_category前面那个集合包含了/所以SLASH分支是死代码。你输入int a b / c;没问题因为/作为运算符被识别。但一旦输入// comment第一个/被归类为OPERATOR_DELIMITER进入OPERATOR状态第二个/同样最终得到两个/运算符后面的内容全部被当成语法错误或者连续运算符注释功能完全失效。测试程序里那行{ //This a test program.整个注释行都会变成一堆报错。5.2 原因get_char_category分支顺序和状态表不匹配根本原因有两个一是字符分类函数里/被重复列入两个类别二是DFA状态表里COMMENT状态根本没有设计成“接受注释内容”。你看报告里的dfa字典COMMENT对ALPHABET、DIGIT都是ERROR只对SLASH转移。这意味着即使你成功进入了COMMENT状态一旦遇到注释里的任何字母立刻变成ERROR。这完全违背“单行注释”的定义。所以这份代码实际上是半成品状态机不能直接复现。至于怎么发现我一般会在写完后拿一个//的用例测一遍再看状态转移。如果你用纸画DFA一眼就能看出来COMMENT只有一条边不可能吃内容。5.3 解决把/单独拉出来增加COMMENT状态的自循环修复方法字符分类里把/从运算符集合中移出单独返回SLASHDFA里增加START --SLASH-- SLASH_STATESLASH_STATE --SLASH-- COMMENTCOMMENT对除换行外的所有字符自循环遇到换行走START。伪代码def get_char_category(char): if char /: return SLASH if char.isalpha(): return ALPHABET if char.isdigit(): return DIGIT if char in -*!(){};: return SYMBOL if char.isspace(): return WHITESPACE return OTHER dfa[SLASH] {SLASH: COMMENT} dfa[COMMENT] {cat: COMMENT for cat in [ALPHABET,DIGIT,SYMBOL,SLASH,WHITESPACE,OTHER]}更好的做法是在主循环检测到COMMENT状态后直接读到换行符不依赖状态表逐字符转移性能和逻辑都简单。我给的修正版就是这么干的。5.4 另外三个坑非法字符定位、标识符误判、输出文件丢失非法字符定位报告的测试程序里有$和。原代码遇到OTHER会进入ERROR状态但ERROR态不输出任何东西token就静默丢了。你需要记录行号和列号遇到ERROR打印错误位置。我一般在循环里维护line和col两个变量遇到\n行号1、列号清零。报告里要求“报告词法错误及其位置”但给的代码没有位置信息这必须自己加。标识符误判2a这种以数字开头的串原DFA在NUM状态遇到ALPHABET会转ERROR这合理。但123呢NUM遇到OTHER也转ERROR但这时123本身是合法的无符号整数应该先输出123然后报告错误。也就是要在转移失败时先回退并输出当前缓冲而不是直接把整个状态标成ERROR。很多新手在这里栽跟头把整个token吞掉。输出文件丢失报告要求“将合法单词存入lex.txt”但给的程序只用print打屏幕。你需要加两行with open(lex.txt, w, encodingutf-8) as f: for token in tokens: f.write(f{token[0]}: {token[1]}\n)注意编码如果源程序里只有英文无所谓。如果以后要处理中文注释建议统一UTF-8。5.5 跑词法分析器前先列一张“歧义表”我现在的习惯是在写代码前把语言里所有“同一个字符能开多个 token”的情况列出来比如/可能是除号或注释开头可能是单独运算符或的一部分可能是赋值也可能是的一部分。这张歧义表直接决定你的DFA要哪些中间状态。不做这一步后面调试会非常费劲。这份实验报告的/问题本质上就是没做歧义分析——/和//在正则层面都没有写清楚。你可以用两列表格记起始字符后续可能字符对应token类型。对着表设计状态比对着代码猜要靠谱得多。6. 验证与进阶用测试程序跑通再看最长匹配原则的实现6.1 用原始测试代码做回归哪些token必须对哪些错误必须报报告给了五段测试代码其中第三段是精华int abc123$; int 123; int 2a; abc 012345;。用修好的词法分析器跑应该得到abc123是有效标识符$报非法字符123是数字报非法字符2是数字a按我的修正版会报“数字后面跟字母”的错本质是2a既不属于整数也不属于标识符012345按正则应该是0和12345两个数字但如果你按DFA的NUM状态吃所有数字它会成为一个数字。这里两种取舍都行关键要一致。我自己的习惯是设置一个ALLOW_LEADING_ZERO开关如果为True则012345是合法整数否则拆成两个。这份报告的正则写法表明它不支持前导零但DFA状态表又支持这是它没写明白的地方你需要自己决策。6.2 最长匹配的两种实现forward扫描与状态内判断报告里讨论到了“最长匹配原则”也就是不能被识别成和。实现有两种常见方式一种是我前面修正版里用的手工回退在SYMBOL状态下读取字符如果发现后续字符能构成更长的运算符比如先读再读下一个字符是就继续吞否则回退。代码长一点但逻辑直白。另一种是标准DFA的“最后接受态”记录法每读入一个字符如果当前状态是接受态就记录这个位置为“候选终点”继续往下读直到进入死状态或无转移时回退到最近的一个候选终点把中间这段输出。比如读当读到时接受态记录继续读还是接受态记录遇到空格停止输出。这种方法不用写特殊判断通用性强适合规则多的情况。我推荐你用后者因为加新运算符时不用改分支逻辑。6.3 从词法到语法你的token流怎么喂给语法分析器最后一步很实际词法分析器的输出不是给人看的是给语法分析器的。所以别只打印Keyword: int最好返回结构化的token列表每条包含(类型, 值, 行号, 列号)。这样后面的递归下降或LR分析器可以直接消费。这也是我在做实验时最大的教训——一开始为了图方便把token直接拼成字符串结果写语法分析时又要重新解析浪费时间。从那以后我每次写词法分析器都强制走一遍正则→NFA→DFA→最小化→带位置信息的token流→回归测试。这份实验报告虽然代码有瑕疵但整个流程骨架是标准的照着补上这些细节你也能得到一个能应付后续实验的词法模块。希望帮到你。本文还有配套的精品资源点击获取