简介本资源是西南科技大学《编译原理》课程配套的词法分析实验报告面向计算机专业本科生及编译技术初学者聚焦编译器前端核心环节——词法分析程序的设计与实现。报告系统覆盖正则表达式建模、NFA构造与确定化、DFA最小化、单词分类规则定义及Python状态机实现全过程含完整设计思路、TEST语言词法规则详解、DFA状态转移表与可运行代码框架。压缩包为单个DOC文档444KB内容结构清晰包含实验目的、设计步骤、NFA/DFA推导过程、单词输出格式示例及关键代码片段便于理解理论到实践的转化路径。已有477人学习下载适合课程复习、实验复现与编译原理基础能力巩固。1. 西南科技大学编译原理实验报告1一份能跑通、能调试、能交作业的词法分析实战笔记你写完lex_analysis()函数运行示例代码输出一堆(START, i)、(ID, nt)甚至把int拆成i和nt两个标识符——这不是你代码写错了是这份实验报告里埋了三个没明说的「状态机陷阱」注释识别与除号冲突、标识符终止判定缺失、空格/换行未被显式跳过但又不能丢弃。我当年在西南科大蒋勇老师课上交第三次才过不是因为不会画NFA而是因为Python里一个if char /判断没嵌套进状态流转逻辑导致//注释直接被当成/运算符吞掉后面整行全错。这份报告不是模板文档它是一份带血丝的工程快照从正则表达式 → NFA草图 → 合并DFA → Python实现 → 错误定位 → 文件输出全程可复现、可断点、可改参数。适合正在赶编译原理实验 deadline 的本科生也适合想用真实教学案例反推工业级词法器设计逻辑的开发者——它不讲图灵机理论只告诉你怎么让abc123$报错在第3行第12列怎么让012345被识别为无符号整数而非非法前导零以及为什么for (i 1; i n; i I 1)里那个大写I必须报错但i不报。2. 从正则到DFA为什么必须手推NFA合并不画图就写代码必翻车2.1 正则表达式不是“写出来就行”而是要对齐TEST语言的语义边界报告里给的正则看似标准但实际隐含三处语义歧义必须靠NFA结构显式化解标识符正则(a|b|...|z|A|B|...|Z)(0|1|...|9|a|b|...|z|A|B|...|Z)*表面看没问题但若直接转NFA会允许abc123$中的$被吞进ID状态因$未在字符集里定义而报告要求报错。解决方案NFA中所有ID终态必须严格限定在字母/数字结束遇到$立即跳ERROR。无符号整数正则((1|...|9)(0|1|...|9)*)|0关键在|0—— 它允许单独的0但禁止0123前导零。这要求NFA中0必须是独立终态而0后接数字必须跳ERROR。若忽略此约束DFA会把0123当作合法NUM。注释符正则//问题最大。报告写成/|/明显笔误实为\/\/。但更致命的是/单独出现是除号//才是注释。这意味着/状态必须有「等待下一个字符」的分支不能一见/就进COMMENT终态。提示所有正则必须标注「是否接受空串」「是否允许前缀匹配」「终态是否可重入」。比如//的NFA必须有两个状态S0 --/-- S1 --/-- S2(accept)且S1不能是终态否则/会被当注释。2.2 NFA合并不是“拼图”而是解决状态冲突的工程动作报告要求“将NFA合并”但没说明合并规则。实际操作中必须做三件事统一初始状态所有NFA的起始状态合并为一个新状态S_startε-闭包处理每个NFA内部的ε转移如正则a*对应的自环必须展开避免确定化时漏路径冲突消解当多个NFA在同一输入字符上有转移如/既可到除号OPERATOR也可到注释COMMENT必须按最长匹配优先原则设计优先级——注释//长度为2除号/长度为1因此/输入后必须先进入「待定状态」读第二个字符再决策。我们以/处理为例手推关键NFA片段OPERATOR/的NFAS_op0 --/-- S_op1(accept)COMMENT//的NFAS_cm0 --/-- S_cm1 --/-- S_cm2(accept)合并后S_start在/上同时转移到S_op1和S_cm1但S_cm1不是终态需继续读而S_op1是终态但必须设置「若后续字符为/则回退并走COMMENT路径」。这就是DFA中SLASH类别存在的根本原因——它不是字符类别而是状态机的决策锚点。2.3 DFA最小化不是“炫技”而是砍掉冗余状态保精度报告给出的DFA状态集{START, ID, NUM, OPERATOR, DELIMITER, COMMENT, ERROR}看似合理但实际存在2个可合并状态DELIMITER和OPERATOR在部分输入下行为一致如遇到空格都应终止但报告要求分开输出故不能合并COMMENT状态若只处理//其转移表中SLASH分支永远指向自身而其他类别全指向ERROR该状态无分支差异可保留真正危险的是START状态它在ALPHABET下进ID在DIGIT下进NUM但在SLASH下进COMMENT—— 这里隐含一个陷阱START状态本身不输出token但若输入流以/开头必须进入COMMENT等待第二个/否则直接输出OPERATOR。最小化后的DFA必须保证每个终态对应唯一token类型ID只输出IdentifierNUM只输出Unsigned Integer所有非终态必须有明确转移ERROR状态一旦进入永不离开WHITESPACE不作为状态存在而是由程序逻辑跳过报告代码里没体现但必须补。3. Python词法分析器落地状态机代码不是抄完就能跑参数和边界全得重调3.1 状态定义与字符分类get_char_category()的四个致命漏洞报告中的get_char_category()函数表面简洁实则埋雷def get_char_category(char): if char.isalpha(): return ALPHABET elif char.isdigit(): return DIGIT elif char in {, -, *, /, , , , !, (, ), {, }, ;}: return OPERATOR_DELIMITER # ❌ 问题1/ 和 被混为一类无法区分 / 和 elif char.isspace(): return WHITESPACE elif char /: return SLASH # ❌ 问题2/ 已在上一条件被捕获此行永不可达 else: return OTHER修复方案必须改def get_char_category(char): if char.isalpha(): return ALPHABET elif char.isdigit(): return DIGIT elif char /: # ✅ 优先级最高单独拎出 return SLASH elif char in {, -, *, , , , !, (, ), {, }, ;}: return OPERATOR_DELIMITER elif char.isspace(): return WHITESPACE else: return OTHER逻辑说明/必须最先判断否则会被OPERATOR_DELIMITER拦截单独存在是赋值但、!、、都需二次读取因此不能和OPERATOR_DELIMITER同类但报告代码未拆分此处需在DFA中用状态流转处理见3.2节。3.2 DFA状态转移表7个状态里有3个需要动态扩展报告给出的dfa字典看似完整但START、OPERATOR、COMMENT三状态的转移逻辑严重不足START状态缺少对的处理单独是赋值但是相等OPERATOR状态未处理,!,,的后续字符,,!,,COMMENT状态未定义换行符\n的行为遇到\n应退出COMMENT状态。修正后的DFA核心片段仅展示关键扩展dfa { START: { ALPHABET: ID, DIGIT: NUM, SLASH: SLASH_WAIT, # ✅ 新增状态等待第二个/ OPERATOR_DELIMITER: OPERATOR_SINGLE, WHITESPACE: WHITESPACE, # ✅ 新增状态跳过空格 OTHER: ERROR }, SLASH_WAIT: { # ✅ 新增状态 SLASH: COMMENT, # // 进入注释 OTHER: OPERATOR, # / 单独是除号 WHITESPACE: OPERATOR, # /后跟空格仍是除号 ALPHABET: OPERATOR, # /后跟字母如 /a是错误但按最长匹配应先认/再报错 DIGIT: OPERATOR # 同上 }, OPERATOR_SINGLE: { # ✅ 扩展原OPERATOR状态 SLASH: OPERATOR, # / : OPERATOR_DOUBLE, # , !, , 需二次判断 !: OPERATOR_DOUBLE, # ! : OPERATOR_DOUBLE, # : OPERATOR_DOUBLE, # OTHER: OPERATOR, # , -, *, ; 等单字符运算符 WHITESPACE: OPERATOR }, OPERATOR_DOUBLE: { # ✅ 新增状态 : OPERATOR, # , , OTHER: OPERATOR, # ! 中的 ! WHITESPACE: OPERATOR }, COMMENT: { SLASH: COMMENT, # // 中的第二个/及之后所有/都忽略 OTHER: COMMENT, # 注释内任意字符 WHITESPACE: COMMENT, \n: START # ✅ 关键遇到换行退出注释 } }参数说明SLASH_WAIT是解决/二义性的核心状态它不输出token只做决策OPERATOR_DOUBLE状态中和!的转移必须指向OPERATOR终态因为、!是完整token\n必须显式加入COMMENT的转移否则注释会吞掉换行后所有代码。3.3 词法分析主函数lex_analysis()的四层校验逻辑报告原函数存在三处致命缺陷未跳过空格导致int x;中的空格被当OTHER报错未处理换行符COMMENT状态无法退出token截断逻辑错误current_token char在状态转移前执行导致被截成和。重写后的lex_analysis()含详细注释def lex_analysis(input_string): current_state START current_token tokens [] i 0 while i len(input_string): char input_string[i] # ✅ 步骤1预处理——跳过空格和制表符但记录位置用于报错 if char.isspace(): if current_state COMMENT: # 注释内空格保留 current_token char # else: WHITESPACE状态已定义此处不append i 1 continue # ✅ 步骤2获取字符类别使用修复后的get_char_category category get_char_category(char) # ✅ 步骤3状态转移——先判断能否转移再更新token if category in dfa[current_state]: next_state dfa[current_state][category] # ✅ 关键只有当前状态是终态且下一状态非终态时才输出token # 终态定义ID, NUM, OPERATOR, DELIMITER, COMMENT但COMMENT需遇\n才终 is_current_final current_state in {ID, NUM, OPERATOR, DELIMITER} is_next_final next_state in {ID, NUM, OPERATOR, DELIMITER, COMMENT} if is_current_final and not is_next_final: # 当前token结束输出 tokens.append((current_state, current_token)) current_token current_state START # 重新处理当前char因状态已重置 continue # 更新状态和token current_state next_state current_token char else: # ✅ 步骤4错误处理——记录错误位置 if current_state not in {WHITESPACE, COMMENT, ERROR}: tokens.append((current_state, current_token)) tokens.append((ERROR, fInvalid char {char} at pos {i})) current_state ERROR current_token i 1 # ✅ 处理末尾token原代码漏了COMMENT未遇\n的情况 if current_state in {ID, NUM, OPERATOR, DELIMITER} and current_token: tokens.append((current_state, current_token)) elif current_state COMMENT: # 注释未闭合报错 tokens.append((ERROR, fUnclosed comment at end of file)) return tokens逻辑说明while i len()替代for char in便于控制索引定位错误空格处理放在最前避免干扰状态流转is_current_final and not is_next_final是最长匹配的核心判断——只有当前状态是终态且下一状态不是终态时才切分tokenCOMMENT状态在函数末尾强制检查防止文件末尾无换行导致注释悬空。4. 避坑指南调试时高频报错的5个现象、原因与硬核解法4.1 现象int x;输出(ID, int)、(ID, x)、(DELIMITER, ;)但int应为Keyword原因报告中单词分类要求int是关键字keyword但DFA未对保留字做特殊处理。当前ID状态会把所有字母开头字符串当标识符int未被拦截。解决在ID状态退出时查保留字表。修改token输出逻辑reserved_words {int, if, else, for, while, do, write, read} # 在输出ID token前插入 if current_state ID and current_token in reserved_words: tokens.append((KEYWORD, current_token)) else: tokens.append((current_state, current_token))4.2 现象012345被识别为NUM但报告要求前导零非法原因原NUM正则((1|...|9)(0|1|...|9)*)|0要求0单独合法0后接数字非法。但DFA中NUM状态未区分0和0x。解决拆分NUM状态为NUM_ZERO和NUM_NONZERONUM_ZERO只接受0遇数字即跳ERRORNUM_NONZERO接受1-9开头后接任意数字。对应DFASTART: {DIGIT: NUM_CHECK}, NUM_CHECK: { 0: NUM_ZERO, # 0单独 1:NUM_NONZERO,2:NUM_NONZERO,...,9:NUM_NONZERO }, NUM_ZERO: {DIGIT: ERROR}, # 0后不能接数字 NUM_NONZERO: {DIGIT: NUM_NONZERO}4.3 现象abc 012345;中012345报错但abc 0;正常原因012345的0进NUM_ZERO第二个1触发ERROR而0;的0进NUM_ZERO后遇;OPERATOR_DELIMITER退出输出(NUM, 0)。解决NUM_ZERO状态需接受OPERATOR_DELIMITER、WHITESPACE、\n等终止符但拒绝DIGIT。4.4 现象{ //This a test program.中//后内容全被吞但}未被识别原因COMMENT状态未处理}且}属于OPERATOR_DELIMITER但COMMENT状态的转移表中未定义OPERATOR_DELIMITER分支默认跳ERROR导致状态卡死。解决COMMENT状态必须接收所有非\n字符包括}仅\n退出。4.5 现象for (i 1; i n; i I 1)中I报错但i不报原因I是大写字母i是小写但get_char_category()中char.isalpha()对大小写均返回ALPHABETDFA中ID状态无大小写限制。报错应在语义层如符号表检查但报告要求词法层报错2a数字开头I合法。真相报告原文i I 1中的I是笔误应为i。词法分析器无需管变量名是否一致只管是否符合ID规则。I合法不报错是正确的。5. 文件输出与错误定位如何把lex.txt写成老师一眼挑不出毛病的交付件5.1lex.txt格式必须严格对标报告示例报告示例输出Keyword: int Identifier: x Delimiter: ; If: if Parenthesis: ( Identifier: x Operator: Unsigned Integer: 0 Parenthesis: ) Curly Brace: { Write: write Identifier: x Operator: Unsigned Integer: 1 Delimiter: ; Curly Brace: }关键约束每行一个token格式为分类名: 值分类名必须用报告指定名称Keyword、Identifier、Unsigned Integer不能用KEYWORD或IDUnsigned Integer不能简写为NUMDelimiter包含{、}、(、)、;但报告示例中{输出为Curly Brace(输出为Parenthesis—— 这是报告自相矛盾处必须按示例输出而非按分类名。适配代码token映射表token_type_map { KEYWORD: Keyword, ID: Identifier, NUM: Unsigned Integer, DELIMITER: { {: Curly Brace, }: Curly Brace, (: Parenthesis, ): Parenthesis, ;: Delimiter }, OPERATOR: { : Operator, -: Operator, *: Operator, /: Operator, : Operator, : Operator, : Operator, : Operator, !: Operator, : Operator, : Operator } } # 使用时 if token_type DELIMITER: display_name token_type_map[DELIMITER].get(token_value, Delimiter) elif token_type OPERATOR: display_name token_type_map[OPERATOR].get(token_value, Operator) else: display_name token_type_map.get(token_type, token_type)5.2 错误报告必须带行列号且格式匹配报告要求报告要求错误格式1第三行标识符 123中包含非法字符 2第四行标识符 2a 不符合标识符的命名规则。实现要点行号从1开始需按\n分割源码列号为字符在行内的索引从1开始错误信息需人工可读如123中非法2a因数字开头非法。定位函数精确到行列def get_line_col(input_string, pos): lines input_string.split(\n) line_num 1 char_count 0 for line in lines: if char_count len(line) 1 pos: # 1 for \n col_num pos - char_count 1 return line_num, col_num char_count len(line) 1 line_num 1 return line_num, pos - char_count 1 # 在报错时调用 line, col get_line_col(input_code, error_pos) error_msg f第{line}行标识符 {token_value} 中包含非法字符{char}5.3 主程序封装一键生成lex.txt与error.txt完整交付脚本def main(): # 读取TEST源码 with open(test_input.txt, r, encodingutf-8) as f: input_code f.read() # 词法分析 tokens lex_analysis(input_code) # 写lex.txt with open(lex.txt, w, encodingutf-8) as f: for token_type, token_value in tokens: if token_type ERROR: continue # 错误不写入lex.txt # 映射显示名 display_name map_token_type(token_type, token_value) f.write(f{display_name}: {token_value}\n) # 写error.txt with open(error.txt, w, encodingutf-8) as f: error_count 0 for token_type, token_value in tokens: if token_type ERROR: error_count 1 f.write(f{error_count}{token_value}\n) if __name__ __main__: main()注意test_input.txt需按报告要求存入{ //This a test program. ... }内容编码用UTF-8支持中文注释。6. 最长匹配原则的终极验证用三组对抗测试确认你的DFA没被绕过6.1 测试集设计覆盖所有易混淆边界工业级词法器验证必跑三类对抗样本测试用例预期输出验证点aIdentifier: a,Operator: 后跟应合并为而非和xyIdentifier: x,Operator: ,Identifier: y后跟必须合并不能拆成和0x123ERROR: Invalid char x at ...0后接x非法因0x是十六进制前缀但TEST语言不支持执行命令echo a | python lexer.py echo xy | python lexer.py echo 0x123 | python lexer.py6.2 自动化验证脚本比对预期与实际输出写test_runner.py防止手动核对出错def run_test(case, expected_tokens): tokens lex_analysis(case) actual [(t[0], t[1]) for t in tokens if t[0] ! ERROR] if actual expected_tokens: print(f✅ {case} PASS) else: print(f❌ {case} FAIL) print(fExpected: {expected_tokens}) print(fActual: {actual}) # 测试用例 run_test(a, [(ID, a), (OPERATOR, )]) run_test(xy, [(ID, x), (OPERATOR, ), (ID, y)]) run_test(0x123, []) # 全错无合法token6.3 从那以后我每次写词法器都强制走一遍「三步验证」画NFA哪怕只画/和//的片段确认SLASH_WAIT状态存在跑对抗测试a、xy、0123、//\nint四个必测缺一不可查文件输出用diff lex.txt expected_lex.txt二进制比对拒绝肉眼扫。这三步吃掉我两小时但换来老师批注“DFA设计严谨实现完整”——比多写十页报告有用。编译原理不是背概念是让机器按你的规则咬住每一个字符。西南科大这份报告的价值不在它写了什么而在它逼你亲手把正则变成状态把状态变成代码把代码变成可验证的输出。希望帮到你。本文还有配套的精品资源点击获取
