简介这是一份西南科技大学《编译系统综合设计》课程的编译原理实验报告主题为“设计词法分析程序”适合计算机专业本科生在编译原理实验、期末设计或考研复习时参考。报告完整记录了实验目的、词法规则设计、NFA构造、NFA确定化与最小化DFA的推导过程并给出了标识符、关键字、无符号整数、分界符、运算符、注释符等单词分类及输出方案配有Python词法分析程序的状态转移表和关键代码便于对照理解词法分析器的核心流程与实现细节。压缩包内仅包含1个doc格式实验报告文档文件量小、结构清晰整体大小约444KB可满足快速预览与学习需求资源上线后已有477人浏览学习是编译原理入门阶段较为实用的实验参考资料。1. 编译原理第一个实验就翻车斜杠被当成注释除法直接消失做编译原理词法分析实验的人十有八九会在第一次跑测试用例时遇到这个现象丢进去一段a / b * c出来的 token 只有a、b、c中间的除号不见了再放一段//开头的单行注释注释里的内容反而被当成标识符吐出来。整个结果看起来就像「除法被吃掉了注释被放出来了」。这类问题最折腾人的地方在于它不是崩溃、不是抛异常而是静默地多 token、少 token。程序能跑通输出也有模有样只有最后跟预期结果逐行核对时才发现对不上。源码里三种写法会让问题无限放大——a / b、a // b、a b它们共享同一个坑前缀相同后缀决定身份。这篇笔记从一次词法分析程序实验的完整排错过程出发把斜杠歧义、注释识别、多字符运算符、非法字符定位这几个点逐个拆开给出能直接照做的解决顺序。2. 词法规则先写对从正则到最小 DFA 的完整落地2.1 TEST 语言的词法规则每一条都要能写成正则表达式词法分析的第一步不是写代码而是把语言里每一类单词用正则表达式描述清楚。报告里给出的 TEST 语言规则一共六类我整理成下面这张表单词类别正则表达式说明标识符(a|b|...|z|A|B|...|Z)(0|1|...|9|a|b|...|z|A|B|...|Z)*字母开头后跟零个或多个字母或数字等价写法[a-zA-Z][a-zA-Z0-9]*保留字/关键字if|else|for|while|do|int|write|read语言预定义识别出来要单独归类无符号整数((1|...|9)(0|1|...|9)*)|0零单独算一个正整数不以 0 开头分界符(|)|;|{|}结构分隔符号运算符|-|*|/||||||!|注意这里有单字符和多字符两种注释符//原报告里写的是 /这条正则清单看着简单实际每个选择都有讲究。以无符号整数为例((1|...|9)(0|1|...|9)*)|0把 0 单独剥出来意味着0123这种前导零写法不在「单个整数」的规则里。后面测试程序里出现了abc 012345;如果严格按这条正则跑它会先识别出0再识别出12345而不是整体一个整数。实验报告最终把它当合法单词存入了 lex.txt说明当时的实现选择了容忍这种写法但这恰恰是词法设计里需要提前拍板的问题前导零到底是报错、拆分还是作为一个合法整数必须在正则阶段定清楚。注释符在正则里只有一条//但实现时它是最容易翻车的地方因为单个/同时也是运算符。这就是第 3 章要重点展开的歧义来源正则可以并列写出/和//DFA 状态却只有一个入口。谁先抢到状态谁就决定了程序行为。2.2 正则转 NFA、合并、确定化、最小化最终 DFA 状态表从哪来有了正则表达式之后下一步是构造 NFA。每个正则表达式都可以用最基本的 Thompson 构造法拼出一个 NFA单个字符是「起始状态 → 接受状态」的一条边串联用 ε 边连接并联用 ε 分支汇合闭包则加回环。标识符的正则 a-zA-Z 开头后跟字母数字它的 NFA 就是开头一条字母边接受状态上挂一个字母或数字的自循环。六类规则分别构造出六棵 NFA 之后需要把它们合并成一个大 NFA。常见的做法是新建一个全局起始状态从这个状态分别拉 ε 边到六个子 NFA 的起始状态。这一步的目的是让所有词法规则共享同一个识别入口之后的确定化才有意义。合并后的 NFA 是带 ε 边的非确定自动机直接写程序没法逐字符查表所以要用子集构造法把它确定化成 DFA。子集构造法的本质是按字符看「NFA 从当前状态集合能到达哪些状态集合」把状态集合当作新状态消除 ε 边和分支。最后是最小化把那些「接受性相同、对所有输入字符到达的状态也相同」的等价状态合并。报告里的 DFA 最后落在 START、ID、NUM、OPERATOR、DELIMITER、COMMENT、ERROR 这几个状态上就是从这一串手工推导里提炼出来的。我一般会让学生在画完最小 DFA 之后把每个状态的职责写在一行注释里比如ID状态的含义是「当前累积的是一个标识符前缀后面还能跟字母或数字」。这个习惯后面写代码时非常有用——DFA 转移表里的每一行对应着你脑子里对这类单词的完整认知任何一个转移填错都会直接体现为识别结果错乱。2.3 单词分类与输出方案和后续语法分析怎么衔接TEST 语言的单词分类方案是七类关键字keyword、标识符Identifier、无符号整数Unsigned Integer、分界符Delimiter、运算符Operator、注释符Comment、保留字Reserved Word。这里有个细节值得注意int既出现在关键字列表里又出现在保留字列表里。实验里它们实际指向同一个集合所谓保留字就是语言保留了用途的单词实现上把int、if、else、while、for、read、write放进同一张表即可查表命中就是关键字没命中就是普通标识符。输出方案决定了词法分析程序跟语法分析程序之间的接口长什么样。报告给的示例输出是按源程序顺序打印每一行的类型和值比如int x;输出Keyword: int、Identifier: x、Delimiter: ;。但继续往下看会发现输出名不统一(输出成Parenthesis{输出成Curly Brace;输出成Delimiter。同一个分界符类别用了三种叫法这对后面的语法分析很不友好。我的建议是输出类型统一用单词分类里的类别名比如全部输出Delimiter: (、Delimiter: {这样下游要按类型做映射时只需要查一个固定集合不会出现同一种符号有三种标签的情况。单词分类还有一个容易被忽略的价值它直接决定了语法分析阶段的工作量。运算符里、、、!是多字符运算符如果词法阶段把它们拆成两个单字符运算符语法分析器就得自己重新拼装等于把词法的责任推给了语法。所以词法分析程序必须保证这些运算符以整体形式出现在 token 流里这也是后面第三、第五两章反复提到的「最长匹配原则」的实际意义。3. 除号消失与注释错乱根因是「/」的双重身份和缺失的预读3.1 报错现场除法算不出、注释全乱码实验调试记录里写了两个问题表现程序不能处理除运算符号/处理注释符时出现错误。先还原一下报错现场。用初版程序分析x a / b;收集 token 时从a后面读到空格token 结束输出标识符a接着遇到/字符分类函数把它归成SLASHDFA 从 START 状态直接跳进 COMMENT 状态然后把这个/累加进 current_token。下一个字符是空格COMMENT 状态对 WHITESPACE 没有定义转移token 收集提前中断COMMENT 状态的 token 又被过滤掉不输出。一次循环下来除号没了后面b被当成独立标识符输出。再看//注释的情况。源程序里写了{ //This a test program.初版程序读到第一个/进 COMMENT第二个/也进 COMMENT理论上注释开始得还行但 next 字符T是 ALPHABETCOMMENT 状态的转移表里 ALPHABET 指向 ERROR。于是注释内容This a test program.要么被报成错误要么被当前状态判成非法字符——注释内的正常文本反而触发了词法错误这就是「处理注释符时会出现错误」的直接来源。这两个现象本质上是一个问题初版 DFA 把斜杠单列成SLASH类别START 状态遇到斜杠无条件进 COMMENT等于默认「所有斜杠都是注释开头」。但语言里/还是除运算符。一个字符两种身份转移表却只给了它一条路于是总有一边的程序是错的。3.2 根因分析SLASH 类别抢走了运算符的位置更缺最长匹配深挖根因要回到 DFA 状态设计本身。字符分类函数里先判断char in {, -, *, /, , , , !, ...}返回OPERATOR_DELIMITER后面又单独判断char /返回SLASH。Python 的 if-elif 顺序里/会先命中OPERATOR_DELIMITER分支还是SLASH分支取决于代码排列——初版把 SLASH 分支放在后面但 DFA 转移表 START 状态里又写了SLASH: COMMENT两个定义互相打架。识别/时到底走哪条转移全靠巧合和运气这就是典型的黑匣子式翻车你能跑出一个结果但说不清它为什么是这个结果。更本质的缺陷是缺失了「向前看一个字符」的机制。词法分析里的最长匹配原则说的是识别出的单词有混淆时按长度最长的确定。和共享前缀!和!共享!前缀/和//共享/前缀。这类规则光靠逐字符读入无法区分读到第一个/时必须再看一眼下一个字符是不是/才能决定是除号还是注释。原文 DFA 没有预读能力遇到/就做出决定自然无法满足最长匹配。同样的缺陷也影响多字符运算符。如果按初版逻辑从 START 进 OPERATOR读到后下一个字符仍是 OPERATOR_DELIMITER 类别OPERATOR 状态继续累积理论上碰巧能把拼成一个 token。但!里的!在字符分类里也属于 OPERATOR_DELIMITER逻辑上也是通的。问题在于这套状态表对「该在哪里停下」没有约束这种语言里根本不存在的组合也会被拼出来然后当作合法运算符输出。状态机只负责吞字符不负责校验「吞出来的东西在不在单词表里」。3.3 修复方案预读一个字符把「//」和「/」分开处理修复的思路不复杂对/做一次预读。读到/时先不急着决定类别看下一个字符——如果是/进入行注释处理一直读到换行符为止如果不是/按除运算符输出。这样a / b里的/后面跟着空格走正常运算符分支//This里的第一个/后面是另一个/走注释分支。两者从根源上被分开。# 修复前一个斜杠直接进 COMMENT 状态除号被吞 if c /: state COMMENT # 修复后预读一个字符是 / 才进注释否则是除号 if c /: if i 1 n and input_code[i 1] /: # 行注释一直读到行尾不产生 token while i n and input_code[i] ! \n: i 1 continue else: tokens.append((Operator, /, line)) i 1 continue这段代码的逻辑说明i是当前扫描下标n是源程序总长度。i 1 n保证预读不会越界也就是源程序最后恰好以/结尾时不会误判成注释开头。进入注释分支后用一个 while 循环吃掉整行直到遇到换行符\n停止continue让外层循环继续处理下一行。除号分支直接把/登记为 Operator token然后下标后移一位继续扫描。这里要特别注意一点预读只是帮助「分类」不负责「吃掉」注释内容。注释内容应该在注释分支里直接跳过而不是继续走 DFA 的字符累积逻辑。很多实现改到一半注释是识别出来了但注释里的字母数字又顺着 COMMENT 状态进入 ERROR报一堆莫名其妙的非法字符错误。正确处理方式是注释判断永远放在主扫描逻辑最前面斜杠一旦确认是注释开头后续字符全部跳过不参与任何 token 累积。这样的预读机制推广到多字符运算符上也成立预读得到!预读得到!预读得到都遵循同一套「先看后决定」的逻辑。4. 实跑 TEST 源程序输出 lex.txt 并定位 123 与 2a 的词法错误4.1 完整可运行的词法分析程序基于修复思路我重写了一个可以直接跑通的完整版本。它保留 DFA 状态转移表的骨架加入了注释预读、关键字查表、非法字符定位三类能力代码里关键位置都加了注释。import sys # 关键字集合标识符识别完后查这张表区分 Keyword 与 Identifier KEYWORDS {int, if, else, while, for, read, write} # 合法运算符集合状态机拼出候选后必须在这里校验 OPERATORS {, -, *, /, , , , , , , !} DELIMITERS {(, ), {, }, ;} def char_cat(c): 字符分类决定 DFA 用哪条转移边 if (a c z) or (A c Z): return ALPHABET if 0 c 9: return DIGIT if c in -*/!: return OPERATOR if c in DELIMITERS: return DELIMITER if c.isspace(): return WHITESPACE return OTHER # DFA 状态转移表每个状态只保留自己关心的输入类别 dfa { START: {ALPHABET: ID, DIGIT: NUM, OPERATOR: OPERATOR, DELIMITER: DELIMITER}, ID: {ALPHABET: ID, DIGIT: ID}, NUM: {DIGIT: NUM}, OPERATOR: {OPERATOR: OPERATOR}, DELIMITER: {}, } def lex(source): tokens, errors [], [] i, line 0, 1 n len(source) while i n: c source[i] # 换行计数保证错误和 token 都带行号 if c \n: line 1 i 1 continue # 空白字符直接跳过 if c.isspace(): i 1 continue # 斜杠预读// 是注释/ 是运算符 if c /: if i 1 n and source[i 1] /: while i n and source[i] ! \n: i 1 continue tokens.append((Operator, /, line)) i 1 continue start_line, col line, i 1 # 记录 token 起点的行号和列号 state, token START, while i n: cc char_cat(source[i]) if state START: # 起始状态按首字符决定进入哪个子状态 nxt {ALPHABET: ID, DIGIT: NUM, OPERATOR: OPERATOR, DELIMITER: DELIMITER}.get(cc) if nxt is None: break state nxt else: nxt dfa[state].get(cc) if nxt is None: break state nxt token source[i] i 1 # 一个字符都没积累起来说明是非法字符 if not token: errors.append(f第{line}行第{col}列非法字符 {c!r}) i 1 continue # 数字后紧跟字母典型错误2a if state NUM and i n and char_cat(source[i]) ALPHABET: while i n and char_cat(source[i]) in (ALPHABET, DIGIT): token source[i] i 1 errors.append(f第{start_line}行第{col}列{token!r} 不能以数字开头) continue # token 定级 if state ID: kind Keyword if token in KEYWORDS else Identifier elif state NUM: kind Unsigned Integer elif state OPERATOR: # 运算符候选必须出现在合法集合里防止吞出 这种组合 if token not in OPERATORS: errors.append(f第{start_line}行第{col}列无法识别的运算符 {token!r}) continue kind Operator else: kind Delimiter tokens.append((kind, token, start_line)) return tokens, errors def main(): # test.txt 放 TEST 语言源程序lex.txt 放合法单词 with open(test.txt, r, encodingutf-8) as f: source f.read() tokens, errors lex(source) with open(lex.txt, w, encodingutf-8) as f: for kind, val, line in tokens: f.write(f{line}: {kind} {val}\n) for err in errors: print(err) if __name__ __main__: main()参数说明source是整个源程序字符串tokens列表存(类型, 单词, 行号)errors列表存错误描述。i是全局扫描下标line是当前行号每遇到\n加一。col在每次 token 开始时记录列号用于准确定位非法字符。dfa转移表里DELIMITER和ERROR状态留空字典表示这些状态一旦到达就结束当前 token不再继续吞字符。OPERATOR状态吞到合法运算符集合之外时会被token not in OPERATORS拦截并报错避免、这类组合悄悄混过去。这个版本里最值得关注的设计是「先按 DFA 累积、再按集合校验」的两步走。DFA 负责把连续同类字符拼成一个候选运算符白名单负责判断这个候选在不在语言里。前者解决识别问题后者解决合法性问题两者凑齐才叫完整的词法分析。4.2 词法错误怎么报告行号、列号、非法字符一个都不能少实验要求里明确写了一句「报告词法错误及其位置」这意味着错误信息至少要包含三样东西出错的行号、出错的列号、非法字符本身。初版程序只输出ERROR状态和累积的 token没有行号列号等于告诉你有错但不告诉你在哪排查起来要从头逐行数。报告里给出的两个错误来自这段测试源程序{ //This a test program. int abc123$; int 123; int 2a; abc 012345; for (i 1; i n; i I 1) { if(i ! n) abc ab c* i else abc abc / i; } }一个在第 3 行123以数字开头后面跟了非法字符另一个在第 4 行2a以数字开头跟字母不符合标识符「字母开头」的命名规则。这两个位置的共同点是错误都不发生在 token 的第一个字符而是发生在 token 累积到中途时遇到了不该出现的字符。所以错误定位必须在 token 累积的循环里记录起点行号和列号等到 break 跳出时用起点信息去描述整个失败的 token。int 2a这行值得单独说。按 DFA 逻辑2先进 NUM 状态接着a是字母NUM 状态转移表里没有 ALPHABET 的转移边循环 break。此时 token 是2下一个字符是a。修复版代码检测到「NUM 状态 下一个字符是字母」的组合就把连续字母数字都并进来输出一条专门错误。这样不会出现「先输出一个合法的整数 2再把 a 当独立标识符输出」的误导性结果。词法错误的处理原则本来就是一旦发现一个单词不合法尽量把它整体报出来而不是拆成半截合法半截非法来掩盖问题。4.3 输出结果核对合法单词入库非法单词留下精确位置用修复版程序跑上面那段测试源程序lex.txt里会得到按行组织的结果。开头几行长这样5: Identifier abc 5: Operator 5: Unsigned Integer 012345 6: Keyword for 6: Delimiter ( 6: Identifier i 6: Operator 6: Unsigned Integer 1 6: Delimiter ; ...注释行//This a test program.整体被跳过不在 lex.txt 里也没有报错。abc123$里的abc123作为合法标识符入库$在下一个扫描位置被单独报为非法字符——这里有一个实现差异值得说明报告只列了123和2a两个错误但测试程序里$同样不属于任何合法类别。严谨的词法分析器应该把它也报出来报告没列可能是因为当时只检查了用例里明示的两个点。实际工程里所有不在字符分类表里的符号都必须走非法分支漏掉任何一个都意味着后面语法分析会拿到脏 token。对照实验预期逐项核验int全部输出为 Keyword普通变量名输出为 Identifier数字输出为 Unsigned Integer、!、/都作为完整 Operator 输出没有拆成单字符//注释没有污染 token 流。三个最初的问题——除号消失、注释错乱、错误无定位——在这个版本里全部消失。输出文件里每个合法单词都带行号错误信息也带行号和列号拿它去跟语法分析器对接或人工核对都能直接定位到源程序对应位置。5. 词法分析常见问题避坑清单五种翻车现场与对应修法5.1 注释内容被当成合法单词输出现象//后面的注释文本出现在 token 输出里比如注释里的test被识别成 Identifier。原因注释分支没有把后续字符完全跳过COMMENT 状态在转移表里只覆盖了少数类别遇到字母数字就中断并把已经累积的内容当作 token 返回。解决注释判断放在扫描主逻辑最前确认进入注释后直接循环到行尾全程不参与 token 累积。判断的标准是一个词法分析器如果输出的 token 里出现了注释里的单词就说明注释处理没有真正生效。5.2 除号被当成注释开头吞掉现象a / b输出里没有/b直接跟在a后面。原因DFA 把/无条件指向 COMMENT 状态所有斜杠都被当作注释入口。解决读/时预读下一个字符//才进注释否则输出 Operator。最容易踩的坑是预读越界——源程序最后一个字符是/时i 1 n必须先判断再取字符否则直接访问会越界。5.3、、!被拆成两个运算符现象x 0输出三个 tokenx、、、0。原因OPERATOR 状态每遇到一个运算符字符就收尾没有做最长匹配。解决OPERATOR 状态持续吞运算符字符吞完后用 OPERATORS 白名单校验在白名单里就以整体输出。OBS 里还要留意单独作为赋值运算符的存在赋值和多字符比较靠预读就能区分但前提是预读逻辑写在对的层级——判断下一个是不是或或决定它是赋值还是比较的一部分。5.4 关键字和标识符没区分int 被输出成 Identifier现象int x;输出Identifier: int而不是Keyword: int。原因DFA 只负责把连续的字母数字拼成一个 token它本身不具备语义判断能力关键字表没有接入。解决ID 状态的 token 收集完整后先去 KEYWORDS 集合查一轮命中输出 Keyword未命中输出 Identifier。这个查表动作必须在 token 完整识别之后做不能在读到i时就判断是不是if否则int的前两个字符会误命中。5.5 非法字符只报 ERROR不报行号和列号现象程序输出Token: , Type: ERROR但不知道 在源文件哪一行哪一列。原因token 累积循环没有记录起点位置错误分支也没有把(行号, 列号)带进错误信息。解决每个 token 开始扫描前记录start_line和coltoken 积累失败时用这两个值拼错误描述。判断一个词法分析器定位能力是否合格直接看错误信息里有没有「第几行第几列」就够了。实验要求明确要报告词法错误及其位置行号列号是硬性指标不是可选项。6. 快速定位词法分析问题三组测试用例就够了6.1 第一组单字符与多字符运算符词法分析的大多数 bug 集中在多字符运算符和单字符运算符的边界上。我每次拿到一个词法分析器第一件事就是跑三行输入a b a ! b a b预期输出分别是Identifier a、Operator 、Identifier bIdentifier a、Operator !、Identifier bIdentifier a、Operator 、Identifier b。如果输出里出现单独的、、!说明最长匹配没生效。确认办法是给三个用例各加一行对照a b、a b、a !b。能同时正确处理这两组运算符部分的边界才算稳。6.2 第二组注释与除号的边界第二组专门测/的双重身份输入三行x / y x // y x // y z第一行必须输出Operator /第二行注释整体跳过不产生 token第三行注释从//开始到行尾全部跳过和z如果出现在注释后面就不该出现。最容易迷惑的情况是第三行——如果实现只在读到//时跳过两个字符而不是跳过整行y z就会漏出来。6.3 第三组非法字符与数字开头标识符第三组测错误定位能力int 2a; int 123;预期结果不是「程序崩溃」而是给出类似「第 1 行第 5 列2a 不能以数字开头」「第 2 行第 5 列非法字符 」的错误信息。如果错误信息里没有行号列号或者2a被拆成合法整数2加标识符a说明错误处理策略有问题。定位问题的方法说来也简单先看字符分类函数char_cat是否把目标字符归对了类再看对应状态在转移表里有没有需要的边最后用「逐字符走表」的方式把出错输入在纸上过一遍。输入不长的时候这种方法十分钟内就能把问题范围缩小到一两行代码。遇到复杂点的输入就按行二分先在中间行加打印看错误出现在前半还是后半再继续缩小。从那以后我每写完一个词法分析器都会强制自己先跑这三组用例再跑完整测试程序三组全过才敢说代码能交。三组用例背后的三个问题——最长匹配、注释跳过、错误定位——正是报告里那几次调试记录的根源所在。希望帮到你。本文还有配套的精品资源点击获取