简介东南大学编译原理课程词法分析器实验报告聚焦用 C 实现可识别 C 关键词、界符、运算符、标识符、数字等词法单元并具备跳过错误局部继续分析的能力。报告系统阐述了实验目的与内容详解 NFA 到 DFA 再到 DFA0 的自动机构造过程针对各类 token 给出相应自动机描述与流程图并重点剖析 token 结构、关键词表/界符表/运算符表/id 表/数字表等核心数据结构以及 addToken 和 lexical 等关键算法实现便于理解词法分析的整体工程组织与编码细节。资源为 1 个 docx 文档大小约 415KB内容层次分明。已有 761 人学习下载适合编译原理课程实验、期末复习或自学实践参考。1. 编译原理词法分析器实验这份报告把状态机讲透了做编译原理实验卡住的时候最缺的不是书上的 NFA、DFA 定义而是一份能直接落地的 C 词法分析器实现。这份东南大学实验报告的价值就在这它没有偷懒用正则库或者 Flex而是老老实实走了NFA → DFA → DFA0的构建流程手写了一个能识别关键字、界符、运算符、id、整型与浮点常数的状态机还自带错误恢复能力——遇到3a这种非法输入会记录错误并跳过错误局部继续往下分析。对正在赶编译原理实验的人它是可以照抄骨架的模板对准备复试或复习自动机理论的人它把纸上谈兵的状态转换真正变成了可以断点调试的代码。我拆完这份报告最想提醒你的是代码本身不难难在状态编号、字符回退和错误吞并这三个地方坑都埋在细节里。2. NFA→DFA→DFA0为什么先画自动机再写代码拿到词法分析器题目第一反应往往是打开编辑器直接写一个大循环遇到字母拼标识符遇到数字拼常数遇到运算符就 push 一个 token。这种做法对二十行的玩具代码没问题但词法类别一多——关键字、界符、单目运算符、双目运算符、关系运算符、带小数的数字——if-else 马上会缠成一团。报告的思路是先建模再编码把问题拆成三个阶段。2.1 分类建 FA每个词类先独立再合并统一开始符报告里写得很清楚对关键词、id、数字、运算符、界符、空白符等先分别建立自己的有限自动机FA然后用产生式连接起来设置一个唯一的开始符终结符不合并。为什么终结符不合并我的理解是每个词类的 FA 都有自己独立的终结状态合并终结符会让词类边界变得模糊回头做 token 分类时还得额外加标记。比如 id 的 FA 终结于字母或数字循环结束的状态数字的 FA 终结于数字串结束的状态这两个终结状态虽然都可能触发 addToken但归属类别完全不同。保持终结符独立token 的 type 就可以直接从终结状态推导出来。具体到每个词类的正规式报告里写了 id/keywords、digit、空白的定义方向但没有把正规式完整展开。按照常规做法补齐id 和关键字共用letter(letter|digit)*这个模式数字是digit并支持小数点小数点后必须跟数字否则按错误处理。空白由空格、制表符、回车和换行组成直接跳过不产生 token。这个设计把关键字和 id 放在同一个 FA 上只在最后查表区分是简化状态图的关键决定。2.2 确定化和等价态合并代码里的 state 编号就是 DFA0 的状态名NFA 转 DFA 那套子集构造法课本上讲了一大堆落到实验里其实就是为了得到一个确定性状态转换表。报告先对各个简单部分画自动机合并后得到一个 NFA再做确定化得到 DFA最后把等价状态合并成 DFA0。这一步做完写代码就变成了体力活DFA0 的每个状态对应代码里 switch-case 的一个 case每个状态上的输入字符决定跳转到下一个状态。你会发现报告给出的状态编号 0、1、6、9、13、15、20、44、47、50 都不是随便写的它们就是 DFA0 压缩之后剩下的状态。比如 0 号状态是全局开始符1 到 5 负责处理开头的情况13/14 负责字母与下划线开头的标识符15 到 18 负责数字20 到 23 负责双字符运算符50 是错误状态。这就是为什么代码里没有一张显式的状态转换表而是用硬编码的 switch-case——因为状态图已经确定化了每个 case 的分支是唯一的。2.3 对比直接 if-else状态机写法在答辩和排错上的优势有人可能觉得switch-case 也是一层层的分支判断跟 if-else 有什么区别区别在可验证性。状态机每读一个字符只做一次状态迁移每个状态有明确的输入边界你可以对照状态转换图一行行推演int a2这串输入是怎么从 0 号状态走到数字终点、再回到 0 号状态的。出问题的时候打印一个state变量就能定位到具体状态而不是一头扎进逻辑里。另外一点很实际这毕竟是编译原理实验老师答辩大概率会问一句你这个转换器是怎么构造出来的。如果代码是硬写的正则扫描你只能答我是按正规式手写的但跟着报告走 NFA→DFA→DFA0 再做等价态合并整个推导路径是可以在黑板上画出来的。报告第八节出现的问题与解决方案里也特别强调先对每一部分画自动机合并等价状态后代码量被大大简化逻辑也更清晰。这不是套话是我做完这一套之后真实感受到的收益。3. 核心数据结构与 addToken查表设计的两个关键点词法分析器输出的本质是一个 token 序列但报告的核心数据结构不只是存 token 的 vector更重要的是那几张 map 表。读这份报告先把数据结构整体过一遍再去看 addToken 里的分派逻辑否则容易在 type 编号的 switch-case 里绕晕。3.1 token 结构体name、type、attr 三个字段为什么够用报告定义的结构体是这样的struct token { string name; // 从源文件里摘出来的原始字符串 string type; // keywords / id / separator / op / relop / num / error int attr; // 该词类内部的编号错误时为 -1 };三个字段各管一件事name保留原样文本后面做语法分析时还要拿它跟符号表比对type是词法层面的大类attr是词法小类或编号。比如关键字intname 是inttype 是keywordsattr 是关键字表里给int分配的编号用户自定义的funname 是funtype 是idattr 是 id 表里分配的唯一编号。attr还有一个额外作用同一个 id 第二次出现时词法分析器不再生成新的编号而是复用之前的编号。这就相当于在词法分析阶段提前做了一次轻量级的符号表去重。语法分析阶段如果要检查变量是否重新声明可以直接拿 attr 比对不用回看 name 字符串。attr -1是错误 token 的哨兵值方便上层快速筛掉非法输入。3.2 map 建表五张静态表加两张动态表报告用到的数据结构除了 vector 之外全部是 map。关键字表、界符表、关系运算符表、其他运算符表是静态的程序启动时填好id 表和数字表是动态的每发现一个新名字或新数字就插入一条记录。#include iostream #include fstream #include map #include vector using namespace std; mapstring, int Keywords; // 关键字表 mapstring, int Sep; // 界符表 mapstring, int Relop; // 关系运算符表 mapstring, int Op; // 其他运算符表 mapstring, int id; // id 编号表动态增长 mapstring, int num; // 数字编号表动态增长 vectortoken Token; // token 序列 // 初始化把 C 关键字填入 Keywords void initKeywords() { string kw[] {asm, auto, bool, break, case, catch, char, class, const, const_cast, continue, default, delete, do, double, else, enum, false, float, for, friend, goto, if, inline, int, long, namespace, new, operator, private, protected, public, register, return, short, signed, sizeof, static, struct, switch, template, this, throw, true, try, typedef, union, unsigned, virtual, void, volatile, while}; for (int i 0; i sizeof(kw) / sizeof(kw[0]); i) { Keywords[kw[i]] i; // attr 值就是数组下标 } }报告原文说 map 查找可以大大提高时间复杂度严谨地讲std::map是红黑树实现的find()的时间复杂度是 O(log n)不是 O(1)。但对词法分析这种词表规模只有几十个条目的场景O(log n) 和 O(1) 的差别可以忽略换来的是代码简洁和表项自动排序。如果真想追求 O(1)把map换成unordered_map就行其他逻辑一行都不用改。3.3 addToken 的 type 分派先查大类再进小类addToken 是整个分析器的出口lexical() 每识别完一个单词都调它把 token 插入序列。难点在于 type 参数只给了 1 到 5 五个大方向同一个方向下还要查不同的表。比如 type 为 1 时既可能是关键字也可能是用户标识符必须先在 Keywords 表里找找不到再去 id 表里查。int idNum 1; // 新 id 的下一个编号 int nNum 1; // 新数字的下一个编号 void addToken(string s, int type) { mapstring, int::iterator it; switch (type) { case 1: // 关键字或 id it Keywords.find(s); if (it ! Keywords.end()) { Token.push_back({s, keywords, it-second}); } else { it id.find(s); if (it id.end()) { id[s] idNum; Token.push_back({s, id, idNum}); } else { Token.push_back({s, id, it-second}); } } break; case 2: // 界符 it Sep.find(s); if (it ! Sep.end()) { Token.push_back({s, separatrix, it-second}); } break; case 3: // 运算符 it Op.find(s); if (it ! Op.end()) { Token.push_back({s, op, it-second}); } break; case 4: // 关系运算符 it Relop.find(s); if (it ! Relop.end()) { Token.push_back({s, relop, it-second}); } break; case 5: // 数字 it num.find(s); if (it num.end()) { num[s] nNum; Token.push_back({s, num, nNum}); } else { Token.push_back({s, num, it-second}); } break; default: // 错误 Token.push_back({s, error, -1}); break; } }这段代码看起来长核心逻辑只有一句话各个类别查各自的表id 和数字做去重编号。type 为 2、3、4 的分支之所以打那么满是因为如果 s 不在对应表里不能凭空把它加进去——界符表里没有的字符串说明是识别流程出了问题静默丢弃比硬塞一个错误 token 更危险所以报告选择什么都不做等 lexical() 的后续逻辑去发现覆盖不到的情况。type 为 1 的先查关键字再查 id顺序很重要C 关键字都是合法标识符形态如果不先查 Keywords 表int会被当成一个自定义 id词法分析就废了。type 为 5 的数字分支没有先查表再决定类型的问题数字只可能是数字去重只是为了让两个相同的数字常量共享一个编号。4. lexical() 状态机逐字符扫描与两个容易写错的分支词法分析器的主体是 lexical() 函数它按字符读入源文件用一个 state 变量维护当前状态每读一个字符做一次状态迁移。报告把状态分得很细从 0 到 50 都有编号。理解这几十个 case关键不是背每个编号而是抓住三条主线状态 0 的分流、双字符运算符的回退、数字与标识符的错误边界。4.1 状态 0 的分流一个字符决定整个词性走向状态 0 是全局起点也是每个 token 结束后的落点。它读取一个字符后根据字符类别跳到不同的处理线case 0: ch ln.get(); s ch; if (ch 13 || ch 10 || ch 32 || ch 9) { state 0; // 空白符、制表符、回车、换行直接忽略 s ; } else if (ch ) { state 1; // 进入 开头的运算符/关系符 } else if (ch ) { state 6; } else if (ch ) { state 9; } else if (isLetter(ch)) { state 13; // 标识符/关键字 } else if (isDigit(ch)) { state 15; // 数字 } else if (ch || ch - || ch * || ch / || ch || ch |) { state 20; tempch ch; // 缓存首字符后面判断是否是双字符运算符 } else if (ch ^) { state 44; } else if (isSep(ch) ! -1) { state 47; // 界符直接收 } else if (isOp(s) ! -1) { state 48; } else if (isRelop(s) ! -1) { state 49; } else { state 50; // 无法识别的字符进错误处理 } break;这串 if-else 本质上就是 DFA0 的转移函数输入字母走 id 线输入数字走数字线输入走关系符线输入这类可能组成双字符的运算符走运算符线。注意isSep、isOp、isRelop三个辅助函数返回的是表内的编号不是 0 和 1 的布尔值所以它们可以直接和 -1 做比较来判定是否查表命中。4.2 双字符运算符识别与 seekg 回退多读的字符必须退回去处理、、、这类运算符最大的坑是多读了一个字符。报告用 tempch 暂存第一个运算符字符然后读取下一个字符做判断。如果是同样的字符或组成双字符运算符否则说明当前是单字符运算符刚才多读的那个字符需要还给文件流。case 20: ch ln.get(); if (ch tempch || ch ) { s ch; // 组成 或 这类双字符 addToken(s, 3); state 0; } else { addToken(s, 3); // 先输出单字符运算符 ln.seekg(-1, ios::cur); // 回退一个字符 state 0; } break;seekg(-1, ios::cur)是这段代码里最容易被忽略的一行。它的含义是把文件流指针往回拨一个字符让刚才 get() 读到的那个字符在下一轮循环里重新参与状态判断。比如输入a1读到进 state 20get() 把1也读进来了发现1不等于也不等于于是 addToken() 之后必须把1退回否则数字 1 就丢了。同样的回退逻辑出现在 case 5、case 8、case 12、case 23、case 46 这些单字符收尾的分支里。报告里每个这样的分支都写了ln.seekg(-1, ios::cur)这其实是一个宁可多读不可少读的设计策略状态机先尝试向后读一个字符来判断最长匹配读完发现不匹配就退回再按单字符处理。理解了seekg的语义整份报告一半的代码就看懂了。4.3 数字与标识符的边界3a 错误是怎么一步步走出来的数字识别从 case 15 开始支持小数但设计了一个容易被忽略的约束小数点后必须跟数字否则直接进错误状态。case 15: ch ln.get(); if (isDigit(ch)) { s ch; // 整数部分继续 } else if (ch .) { s ch; state 16; // 进入小数处理 } else { state 18; // 数字到此结束 } break; case 16: ch ln.get(); s ch; // 先把小数点后的字符拼进去 if (isDigit(ch)) { state 17; // 小数部分合法 } else { state 50; // 3. 这种结构直接报错 } break; case 17: ch ln.get(); if (isDigit(ch)) { s ch; state 17; // 继续拼小数位 } else { state 18; // 数字结束回退由 18 负责 } break; case 18: if (isLetter(ch)) { s ch; // 数字后面直接跟字母例如 3a state 50; // 拼进错误串进错误恢复 } else { addToken(s, 5); // 正常数字 ln.seekg(-1, ios::cur); state 0; } break;测试用例里的3a就是在这里被拦截的读到3进 state 15再读a不是数字也不是小数点进 state 18在 18 里发现a是字母于是把a拼到s后面变成3a状态拨到 50。错误恢复会继续往后读直到遇到空白或界符才停下来把3a整体作为一个 error token 输出然后回到状态 0。这个行为对应了报告实验内容里跳过错误局部继续显示的要求——不是把3报成数字、把a报成 id而是把非法整体吞掉。4.4 状态编号速查表把报告里的状态归纳一下调试时对照这份表会比直接翻代码快很多状态编号处理对象说明0起点/空白每读一个字符决定去向1-5开头、双字符否则回退单字符6-8开头双字符否则单字符9-12开头、双字符否则回退13-14字母开头拼 identifier到终结查关键字/id 表15-18数字开头整数、小数、错误边界20-23运算符开头 - * / |双字符判断44-46^开头^、^双字符判断47-49界符/单字符查表直接收 token50错误恢复读到空白或界符为止这份表对应的是报告里 DFA0 压缩之后的状态不是原始 NFA 的状态。所以你在代码里看不到 3、19、24 这些编号——它们要么被合并掉了要么根本没有被分配到语义。查代码时看到某个状态号跳变不要觉得是写错了先回这张表对一遍。5. 避坑指南词法分析器里我踩过的五个硬坑这份报告整体思路清晰但文件读取、回退、EOF 判断这些环节藏着不少玄学。我自己在做类似实验时踩过的坑加上报告代码里几个容易翻车的位置汇总成五条每一条都按现象、原因、解决来写。5.13a被整个吞成错误 token而不是分开报错现象输入int c 3a;期待输出是数字3和 ida两个 token实际 out.txt 里只有一条 error token内容是3a。原因case 18 里isLetter(ch)的判断成立时代码先把a拼进s再进入 state 50。state 50 的错误恢复逻辑会一直读到空白或界符才停所以3a是一整段被吞掉的。这个行为不是 bug是报告故意设计的跳过错误局部策略但初看代码时很容易误以为状态 15 应该把3先输出、把a交给 id 流程。解决如果实验要求每个非法字符单独定位就应该在 case 18 里删掉s ch;直接 addToken(3, 5) 再回退让a走字母流程。如果实验要求就是跳过错误局部那就保留现在的写法但答辩时要说清楚错误恢复的粒度是整个非法串而不是单字符。5.2 漏写seekg(-1, ios::cur)导致之后的普通字符丢失现象输入a b输出的 token 序列里b不见了或者后面紧跟着一个莫名其妙的 token。原因处理的 case 1 先读下一个字符组成后 addToken。这没问题。但如果是a bcase 1 读到空格走 case 5 的单字符分支。case 5 里如果忘记seekg(-1, ios::cur)那个空格不会造成大问题真正的灾难发生在a bc这种输入b被case 1提前 get() 走又没有退回去下一轮状态 0 直接拿了c开拼b就莫名消失了。解决凡是先读后判、发现不匹配的状态必须在收尾分支里执行ln.seekg(-1, ios::cur)。我给自己的 check list 是这样单字符运算符 addToken 之后必须回退单字符界符没有多读不用回退数字识别到非数字字符后进 case 18 时也要先看是否要回退。5.3while (!ln.eof())会让最后一个 token 重复或者多出一条空记录现象文件最后一行只有一个数字5输出里却出现了两条 name 为5的 num token或者出现一条 name 为空的 error token。原因C 的 eof() 标志位是在读取越过文件末尾之后才置位的不是读到最后一个字符就置位。while (!ln.eof())的判断时机是进入循环体之前所以会多执行一次循环体此时 get() 已经越过 EOF返回的字符内容不可控。解决改成while (ln.peek() ! EOF)来预判或者用先读后判的写法// 推荐用法一peek 预判 while (ln.peek() ! EOF) { // 原循环体直接用 get() 读 } // 推荐用法二先读读不到再退出 char ch; while (ln.get(ch)) { // 用 ch 走状态机 }报告原文用的是while (!ln.eof())在 Windows 环境多跑几轮一般也能出结果但拿它做自动化回归的时候末尾多出的一条空 token 会直接让校验脚本报错。5.4 回车符\r在 Windows 下会被当成可打印字符现象在 Windows 下用\n分行输出的 token 末尾偶尔会混入\r字符串比对永远失败。原因Windows 文本文件的换行是\r\n两个字符。状态 0 的判断条件里写了ch 13 || ch 10也就是把\r和\n都当空白忽略了这没问题。但如果自己改造代码时只判断ch \n\r就会进入后续的 else 分支被当成普通字符拼接进 token。解决空白判断必须同时涵盖 13\r、10\n、32空格、9制表符四个值。用isblank(ch)或者isspace(ch)会更省心但要注意isspace会把 12换页符也算进去按 C 词法严格来说也可以接受。5.5被归进 relop 类却被归进 op 类分类标准不一致现象输出文件里的 type 是op的 type 却是relop。初看觉得无所谓但语法分析阶段如果要区分移位运算和关系运算这个分类会让你多写一次判断。原因报告的状态机里开头的双字符走了 case 4addToken 用 type 3运算符开头的双字符走了 case 2addToken 用 type 4关系运算符。也就是说被当成左移运算符却被当成了关系运算符。严格讲在 C 里可能是右移运算符也可能是从输入流读数据的操作符归到 relop 是 DFA0 合并时的简化处理。解决如果实验要求对标 C 词法把单独拆出来在 case 2 里判断是还是后者走 Op 表。代码改动不大但答辩时有老师问起关系运算符和移位运算符怎么区分这段就能讲出东西来。6. 进阶把实验报告变成可以回归验证的小工具实验报告写到测试用例和输出结果就交付了但我建议你再往前走一步给 out.txt 写一个校验脚本把词法分析器的输出变成可重复验证的结果。以后改状态机、修 bug跑一遍脚本就知道有没有破坏原有行为。思路很简单先手工整理一份期望 token 序列然后用脚本逐行比对自己的输出。词法阶段的 token 序列是确定性的同样的输入必然产生同样的输出这一点比语法分析阶段好验证得多。# verify_tokens.py # 假设 out.txt 每行格式为name type attr字段间用空格分隔 # 期望序列按测试用例手工整理只保留 name 和 type 两个字段 expected [ (void, keywords), (fun, id), ((, separatrix), (), separatrix), ({, separatrix), (int, keywords), (a, id), (, op), (2, num), (,, separatrix), (b, id), (, op), (3, num), (,, separatrix), (3a, error), # 这一行验证错误恢复是否正确 (;, separatrix), (a, id), (, op), (;, separatrix), # ... 其余按实际输出补齐 ] with open(out.txt, r, encodingutf-8) as f: lines [line.strip() for line in f if line.strip()] if len(lines) ! len(expected): print(ftoken 数量不一致期望 {len(expected)}实际 {len(lines)}) exit(1) for i, (line, exp) in enumerate(zip(lines, expected)): fields line.split() if len(fields) 2: print(f第 {i} 行格式异常{line}) exit(1) if (fields[0], fields[1]) ! exp: print(f第 {i} 个 token 不匹配实际 {fields[0]},{fields[1]}期望 {exp}) exit(1) print(校验通过所有 token 与期望一致)这个脚本虽然简单但能让你的实验报告从跑过一次升级成持续可回归。我做完词法分析器之后养成的习惯是把正常用例、错误用例、边界用例比如3.、3a、a全部整理成期望表每次改完代码先在内存里跑一遍全部用例再拿真实文件验证。从那以后我每写一个状态机都强制走一遍错误用例加回退日志的验证流程再也不敢只看正常 token 就交差。这份词法分析器报告的价值就在于把那些容易翻车的边界都摆到了明面上照着复现一遍比自己从头踩坑省太多时间。希望帮到你。本文还有配套的精品资源点击获取