简介一份面向计算机专业学生与编译器初学者的C实现资源围绕编译原理课程中的核心实验展开完整演示了词法分析器与语法分析器的设计与编码过程。压缩包共9个文件包括两个cpp源程序、两个可直接运行的exe程序以及文法定义、token表、源程序样例等txt文档和README说明整体约937KB目录结构简洁易于按需查阅。已有736人学习适合作为课程设计或实验参考。资源价值在于既能直接运行exe观察分析结果也能结合cpp源码与文法txt理解有限自动机、递归下降或LL(1)分析等关键机制。配套的token表和二型文法文件还便于对照调试语法错误通过阅读源码可进一步掌握词法规则定义、状态转换以及语法树的生成流程是巩固编译原理理论与实践能力的实用素材。1. 编译原理实验卡在词法分析和语法分析先别急着啃整本龙书编译原理课的第一次大作业往往是同一个题目给一段源代码先用词法分析器切出 Token再用语法分析器检查结构语言限定 C。网上能找到《词法分析器和语法分析器的实现C.zip》这类压缩包但解压后真正能一次跑通、代码又能讲清楚的很少多数是几百行 if-else 堆出来的临时方案换个测试用例就翻车。我想说的反直觉结论是这个题目的核心难点不是“写一个编译器前端”而是把词法规则的边界理清楚、把递归下降的层次分配对。对多数实验和课设来说手工构造 DFA 加递归下降分析器是性价比最高的一条路不需要你完整实现 NFA 到 DFA 的子集构造算法也不需要去折腾 YACC 生成器。下面按我自己的实践顺序把从零到跑通的完整做法讲一遍适合正在赶编译原理实验、或者在准备小型语言前端预研的人照着做。2. 词法分析器先画 DFA 再写 C而不是堆一串 else if2.1 三种写法的取舍手写扫描器、正则生成器、手工 DFA 状态表词法分析器的实现方式大致分三种。第一种是纯手写扫描器看到字符就 switch 分发遇到字母就拼标识符遇到数字就拼整数。这种写法代码量看着少但关键字、运算符、注释、空白各自的边界混在一起规则一多就乱。第二种是用 Flex 这类正则生成器把词法规则写成正则表达式工具自动生成分析器。生产项目里这是正解但作业场景里老师通常会追问“你的 DFA 图是什么”你答不上来就吃亏。第三种是手工把词法规则画成 DFA再用 C 的状态转移表实现。这是作业里最稳的做法规则直观、排错方便、答辩也好讲。所谓 DFA本质是一张“当前状态 输入字符 → 下一个状态”的表外加一张终态表。你不需要把每个状态都手写出来只需要把字符归类再按归好的类去查表。我一般这样建表先枚举 Token 类型再给字符分成若干类比如字母、数字、运算符、括号、空白。DFA 的起始状态是 0每个状态对应一个正在识别的“半成品”。在 C 里用一个std::vectorstd::vectorint存状态表行是当前状态列是字符类别值是下一个状态。无关转移一律填 -1表示无路可走。2.2 Token 结构体和字符流接口先定数据模型再写逻辑写词法分析器之前先把 Token 的结构定下来。Token 不是简单的字符串它至少要带类型、原始文本、行号和列号。行号列号是语法分析器报错时定位用的没有它们后面的“第几行有错”就无从谈起。enum TokenType { T_INT, T_RETURN, T_IF, T_ELSE, T_WHILE, // 关键字 T_IDENT, T_NUMBER, // 标识符和数字 T_PLUS, T_MINUS, T_STAR, T_SLASH, // 算术运算符 T_ASSIGN, T_EQ, T_NEQ, T_LT, T_LE, T_GT, T_GE, // 关系运算符 T_LPAREN, T_RPAREN, T_LBRACE, T_RBRACE, T_SEMI, T_EOF, T_ERROR }; struct Token { TokenType type; std::string lexeme; int line; int col; };这个结构很简单但有两个细节要注意。lexeme必须保存原始文本不能只存类型因为后面符号表登记、语法树输出都要用到。col列号建议按字符下标记录遇到\t时先简单按 1 处理或者单独处理制表符展开作业里按 1 处理不会有人挑毛病。字符流接口我用一个简单的类包住源代码字符串带一个指针下标的推进逻辑class CharStream { const std::string src; size_t pos; int line; public: CharStream(const std::string s) : src(s), pos(0), line(1) {} char peek() const { return (pos src.size()) ? src[pos] : \0; } char get() { char c peek(); if (c \n) line; if (c ! \0) pos; return c; } int currentLine() const { return line; } int currentCol() const { return static_castint(pos); } };这个类的要点是get()返回当前字符并前进peek()只看不取。词法分析最怕的就是字符读过头peek 给了你一个后悔药最长匹配失败时能回退到安全位置。换行处理也在这里集中做词法分析器本体不用关心行号维护这是我一直建议的拆分方式各模块各干各的。2.3 状态转移表与最长匹配识别主循环的正确姿势字符分类函数是状态表的前置。种类太少会丢失细节太多会让表膨胀。我按这个小语言的语法把字符归成 16 类enum CharClass { C_LETTER, C_DIGIT, C_PLUS, C_MINUS, C_STAR, C_SLASH, C_ASSIGN, C_LT, C_GT, C_LPAREN, C_RPAREN, C_LBRACE, C_RBRACE, C_SEMI, C_SPACE, C_OTHER }; CharClass getCharClass(char c) { if (isalpha(c) || c _) return C_LETTER; if (isdigit(c)) return C_DIGIT; switch (c) { case : return C_PLUS; case -: return C_MINUS; case *: return C_STAR; case /: return C_SLASH; case : return C_ASSIGN; case : return C_LT; case : return C_GT; case (: return C_LPAREN; case ): return C_RPAREN; case {: return C_LBRACE; case }: return C_RBRACE; case ;: return C_SEMI; case : case \t: case \n: case \r: return C_SPACE; default: return C_OTHER; } }注意单独归成一类是因为它既能当赋值号又是、、的第一个字符。这是最长匹配最容易出问题的地方后面第 5 章会单独讲。识别主循环是词法分析器的核心。基本写法是从状态 0 开始逐个读字符查转移表每进入一个终态就记录一下位置和状态一旦遇到非法转移回退到最近一次终态位置产出对应的 TokenToken Lexer::nextToken() { while (true) { // 跳过空白 // 从当前 pos 开始识别 int state 0; int lastFinal -1; size_t lastFinalPos stream.pos; std::string lexeme; while (state ! -1) { char c stream.peek(); CharClass cc getCharClass(c); int next delta[state][cc]; if (next -1) break; lexeme.push_back(c); stream.get(); state next; // 记录最近一次遇到终态的位置 if (isFinal[state]) { lastFinal state; lastFinalPos stream.pos; } } stream.pos lastFinalPos; // 回退到终态位置 lexeme.resize(lastFinalPos - startPos); // 根据 lastFinal 生成 Token } }这里有三个参数是最关键的。delta状态转移表isFinal终态标记数组lastFinalPos最近终态位置。没有lastFinalPos的回退会被切成一个和一个因为识别到时已经是终态继续读才进入更大的终态。最长匹配原则就是靠“记录最近的终态并回退到它”这个机制实现的。2.4 标识符去重与关键字判定查表时机决定成败标识符和关键字的区分是作业里最高频的翻车点。常见错误是把关键字表写在判断逻辑里每读一个字符就查一次。正确做法是先按最长匹配把整个标识符拼完再去查关键字表命中就改成对应 Token 类型没命中就是普通T_IDENT。bool isKeyword(const std::string s) { static const std::unordered_mapstd::string, TokenType kw { {int, T_INT}, {return, T_RETURN}, {if, T_IF}, {else, T_ELSE}, {while, T_WHILE} }; auto it kw.find(s); return it ! kw.end(); }查完之后才考虑符号表登记。如果实验要求输出符号表用std::unordered_mapstd::string, int记录标识符名和首次出现行号即可。注意登记时机也要放在整个标识符识别完成之后不能边读边登记否则int还在拼intx时就被当关键字登记了。数字字面量的处理同理。拼完整段数字再stoi拼接过程中如果遇到字母就按“非法标识符”报错。这两个判定顺序写反词法分析器的正确率会直线下滑而且是那种换了用例才暴露的隐性错。3. 语法分析器递归下降的写法比 LR 更适合作业场景3.1 为什么是递归下降报错定位、可读性、调试体验语法分析的主流方案是递归下降和 LRYacc/Bison。作业层面我强烈建议递归下降理由很现实。第一LR 生成器生成的表格老师要你画状态图时你根本不知道从哪讲起第二LR 的错误恢复信息默认是给人看的不是给课程答辩看的第三也是最关键的递归下降的代码是“每个非终结符一个函数”报错时能直接指定正在解析哪个产生式调试体验远好于查一张跳转表。递归下降的本质是用语言的文法直接写程序非终结符是函数终结符是匹配函数。它要求文法没有左递归这对 C 风格的小语言完全没有压力。分支多的地方稍微用点回溯思想但实际不需要回溯——只要文法写得好向前看一个 Token 就能决定走哪个分支。3.2 文法设计EBNF 怎么写、左递归怎么消在设计递归下降分析器前先把文法写成 EBNF。以下是小语言的核心文法我没有用教科书那种繁复的 BNF而是加了方括号表示可选星号表示零次或多次Program : StmtList StmtList : Stmt StmtList | ε Stmt : DeclStmt | AssignStmt | IfStmt | WhileStmt | ReturnStmt | Block Block : { StmtList } DeclStmt : int IDENT ; AssignStmt: IDENT Expr ; IfStmt : if ( Expr ) Stmt [else Stmt] WhileStmt : while ( Expr ) Stmt ReturnStmt: return Expr ; Expr : Term (( | -) Term)* Term : Factor ((* | /) Factor)* Factor : NUMBER | IDENT | ( Expr )这里 Expr 到 Term 到 Factor 的三层结构就是在处理运算符优先级加减最外层乘除中间层括号和操作数最内层。如果你把这三层写成一个函数表达式优先级就废了23*4会被算成(23)*4。这段文法本身没有直接左递归因此可以落地。注意 StmtList 里的ε空产生式它对应的是语句列表结束的情况写成 C 时就是一个“什么都不做”的 if 分支。空产生式处理不好是递归下降常见的死循环来源下一节会看到具体对应。3.3 Parser 骨架每个非终结符一个函数的落地Parser 类持有词法分析器和两个 Token当前 Token 和一个前瞻 Token。为什么要两个因为if后面要看到(才能决定走哪个分支只看当前 Token 不够需要 lookahead。这个前瞻可以用“拉取两个 Token”实现也可以用一个缓冲区。class Parser { Lexer lexer; Token cur; Token look; void advance() { cur look; look lexer.nextToken(); } bool match(TokenType t) { if (cur.type t) { advance(); return true; } return false; } void expect(TokenType t) { if (!match(t)) { throw ParseError(expect tokenName(t) but got cur.lexeme, cur.line); } } };cur是当前正要处理的 Tokenlook是预读的下一个。match成功即消费当前 Token 并推进expect在失败时直接抛出带行号的异常。这是整个分析器最核心的基建所有非终结符函数都建立在它之上。下面看表达式三层和语句分派void Parser::parseExpr() { parseTerm(); while (cur.type T_PLUS || cur.type T_MINUS) { advance(); parseTerm(); } } void Parser::parseTerm() { parseFactor(); while (cur.type T_STAR || cur.type T_SLASH) { advance(); parseFactor(); } } void Parser::parseFactor() { if (cur.type T_NUMBER) { advance(); } else if (cur.type T_IDENT) { advance(); } else if (cur.type T_LPAREN) { advance(); parseExpr(); expect(T_RPAREN); } else { throw ParseError(unexpected token in factor, cur.line); } }parseExpr先调parseTerm再循环处理加减号这样123这样左结合的表达式不需要额外的消左递归处理循环天然承担了“递归地右移”的任务。parseFactor的分支判断只看当前 Token 类型数字、标识符或左括号其余全部抛错。注意我没有在这里处理负号-1如果文法里没有定义一元负号会直接报错如果需要支持应该在parseExpr里加一层一元运算符处理。语句分派也是同样的模式但要注意StmtList里的空产生式。我用一个isStmtStart()函数判断当前 Token 是否属于某类语句开头不是就直接返回上一层让调用方决定是否报错。void Parser::parseStmtList() { while (isStmtStart(cur.type)) { parseStmt(); } } void Parser::parseStmt() { if (cur.type T_IF) parseIfStmt(); else if (cur.type T_WHILE) parseWhileStmt(); else if (cur.type T_INT) parseDeclStmt(); else if (cur.type T_IDENT) parseAssignStmt(); else if (cur.type T_RETURN) parseReturnStmt(); else if (cur.type T_LBRACE) parseBlock(); else throw ParseError(invalid statement start, cur.line); }while循环代替了StmtList → Stmt StmtList | ε的递归既避免了右递归带来的栈深度问题也让代码更贴合实际解析流程。语句块的解析在这里递归调用parseStmtList天然支持任意嵌套只要栈不爆。3.4 轻量错误恢复同步 Token 集合的实战值教科书里的错误恢复讲 panic mode做法是定义同步 Token 集合出错时丢弃 Token 直到遇到一个同步 Token 再重新开始。作业里很多人直接throw终止答辩时老师问“你怎么从错误里恢复”答不上来。我一般给 Parser 加一个synchronize()方法解析语句时出错就不断advance()吞掉 Token直到遇到分号、右花括号或T_EOF然后回到语句列表循环。这样做的好处是一个文件里的多个错误能一次报完而不是发现第一个错就停工。void Parser::synchronize() { while (cur.type ! T_EOF) { if (cur.type T_SEMI) { advance(); return; } if (cur.type T_RBRACE) { return; // 让上层 handle } advance(); } }注意T_RBRACE出现时不要直接消费因为右花括号是块结束标志应该交给外层语句的结束处理来消费否则块会提前闭合。这个细节是我自己的血泪经验第一次实现时把}也吞了结果整个嵌套结构错位报错位置全偏。同步集合选什么 Token要根据文法里哪些 Token 能明确标志“一条语句结束了”来定不是随便选的。4. 把两个模块串起来Token 流、符号表、输出格式与构建配置4.1 拉取式配合词法器一次一个 TokenParser 按需索取词法分析器和语法分析器的接口设计要么是词法器先把所有 Token 放进一个队列语法分析器再从这个队列里取要么是拉取式Parser 需要时再向 Lexer 要下一个。前者代码直观但要预先读完整个文件文件大时内存不划算而且peek前瞻不便后者每步只处理一个 Token内存占用固定还能配合前瞻做流式处理。拉取式的关键是 Lexer 对外只暴露两个方法nextToken()返回下一个 Token以及恢复词法分析状态的 reset。Parser 内部维护cur和look两个 Token每次advance()就把look推进到下一个。这样 Lexer 不需要保存 Token 历史状态只有pos、line和col。在实践中我发现拉取式还有一个隐藏好处调试时容易单测。你可以先手动调用nextToken()打印出全部 Token确认词法没问题后再把同一段源码喂给 Parser。词法和语法两个模块的错误被隔离开排查范围直接缩小一半。4.2 主循环与文件读取C 读源码的编码与安全坑词法分析和语法分析都准备好后main 函数要做的事情很琐碎读文件、构造 Lexer、构造 Parser、跑分析、输出结果。这个主循环看着简单坑全藏在文件读取里。C 用ifstream读文件时直接while (in line)是灾难因为运算符会按空白自动分词源代码换行和空格信息全丢了。要按字符完整读入std::string readSource(const std::string path) { std::ifstream in(path, std::ios::binary); if (!in.is_open()) { throw std::runtime_error(cannot open source file); } std::stringstream ss; ss in.rdbuf(); return ss.str(); }这里用二进制模式打开是有意的。文本模式在 Windows 上会把\r\n自动转成\n看起来方便但如果你的词法分析器要按原始字节统计列号转换反而会造成行列号错位。用二进制模式读回来自己统一处理\n和\r行为在所有平台上一致。另外如果题目的测试文件是 UTF-8 带 BOM 的前三个字节EF BB BF会被当作普通字符读进来第一行 Token 全部错乱。解决也很简单判断字符串前三个字节是否为 BOM是则erase掉。这个坑在 Windows 记事本保存的文件上几乎是必现的属于一百个学生里有八十个会踩的类型。4.3 实验报告要的输出先定格式再写代码实验指导书一般要求两种输出词法分析结果是一份 Token 列表语法分析结果是程序结构是否正确。输出格式最好先定下来再写代码不然调试时满屏乱打根本没法对比正确性。我习惯用纯文本、制表符分隔的表格Token Type Line Col int T_INT 1 1 a T_IDENT 1 5 T_ASSIGN 1 7 42 T_NUMBER 1 9 ; T_SEMI 1 10语法分析器跑完如果没抛异常打印Syntax OK.如果抛了异常打印Error at line N: ...。这样写的好处是结果能直接和同学的、和老师的输出样例做 diff。调试阶段不要用二进制格式或 Python 脚本包装输出纯文本最直接命令行 diff 一眼就能看出来多切了一个 Token 还是缺了一个分号。构建配置方面实验文件夹的 Makefile 我一般写成这样CXX g CXXFLAGS -stdc17 -Wall -Wextra -g SRCS lexer.cpp parser.cpp main.cpp OBJS $(SRCS:.cpp.o) TARGET compiler_frontend $(TARGET): $(OBJS) $(CXX) $(CXXFLAGS) -o $ $^ %.o: %.cpp $(CXX) $(CXXFLAGS) -c $ clean: rm -f $(OBJS) $(TARGET)-g一定要保留调试器断点靠它。-Wall -Wextra在词法分析器的隐式转换、未使用的变量这类问题上能提前报警。实验里交代码时这些告警全清掉答辩查代码的印象分会好很多。如果你是在 vscode 里配的 C/C 环境注意 task.json 里要把文件列表写全别只编译 main.cpp否则链接阶段全是未定义符号。5. 编译原理实验五个常见坑现象、原因、解法5.1 中文路径和 UTF-8 BOMVSCode 里好好的换台机器就崩现象代码在本机能跑拷贝到实验室电脑上ifstream打开文件失败或者第一个字符变成乱码词法分析第一行就报T_ERROR。原因有两个。一是中文路径在 Windows 上涉及编码转换老旧的fopen传const char*按本地代码页处理二是记事本存成 UTF-8 带 BOM前三个字节被当成内容读进来。解决路径上坚决不用中文统一用std::ifstream配合二进制模式读入检测EF BB BF后手工去掉。这两个问题同时发生时调试视角会非常迷惑建议先确认文件字节再进词法环节。5.2 CRLF 换行让行号错乱报错定位到了错误行现象同一个测试文件在本机行号全对在 Windows 上打开后所有错误行号比预期多一或者偏到上一行。原因Windows 文本模式把\r\n转成\n而你在 CharStream 里对\r也做了某种处理统计行号时机不一致。解决全文统一按二进制读入CharStream 里只对\n增加 line遇到\r直接跳过不参与 Token 拼装。最重要的是让 getCharClass 把\r归到 C_SPACE这样它不会成为非法字符。这个小改动看似不起眼实际能把跨平台的所有行号问题一次清干净。5.3 关键字被当成标识符或反之现象intx整体被识别成T_INT或者int被当成普通标识符。原因识别标识符时没有做最长匹配就查关键字表比如读到i就开始比对关键字列表后面跟了n和t就提前命中。解决先把从起始字符到回退位置前的完整文本取出来整个字符串查一次关键字表查不到再按T_IDENT登记。注意intx这种形式最长匹配得到的是intx查表落空正确输出为标识符。反过来的情形是关键字表在字符扫描中间查也就是“边扫边查”识别int和intx就区分不开了。把查表时机严格放在整个词素拼接完成后这类问题直接消失。5.4 最长匹配没回退被切成了和现象输入ab输出两个 Token 分别是和语法分析器报错。原因状态转移表里是终态遇到也能进入的终态但如果你的循环在到达这个终态时立即生成 Token没有继续试探下一个字符最长匹配就失败了。解决主循环里每到达一个终态记录lastFinalPos但不立即停止只有遇到非法转移时才回退到该位置。代码上就是stream.pos lastFinalPos;这一行它相当于把所有 Token 的边界都“迟滞”到了非终态才确定。、、!同理都是这一个机制统一处理的。5.5 发布出来的工程跑不起来运行库版本对不上现象下载的现成压缩包里有 exe双击报“缺少 VCRUNTIME140.dll”或“0xc000007b”VSCode 里重新编译又提示环境问题。原因目标机器上没装对应版本的 Visual C Redistributable 运行库或者装了 32 位而你的是 64 位程序编译环境切换时工具链版本不一致也会产生新的二进制依赖。解决自己写的话只依赖 C 标准库用g -stdc17静态链接或打包时放一份依赖说明从网上拿的压缩包别直接用现成 exe把它当参考读完代码后在自己环境重新编译。vscode 里面配 C/C 环境时重点检查编译器的位数和链接器选项是否一致这能排除一大半“我代码没问题为什么跑不起来”的假象。6. 从能跑到能演示基线用例、状态跟踪和调试技巧6.1 基线用例把“预期输出”写进注释跑一次就知道对错准备一份固定的测试文件test1.src覆盖全部 Token 类型和语句结构预期结果用注释直接贴在测试文件旁边。我常用的基线用例长这样int main() { int a 1; if (a 0) { a a 2; } else { a a - 1; } while (a 10) { a a * 2; } return a; }这个文件虽然只有十几行但覆盖了关键字、标识符、数字、赋值、关系运算、算术运算、嵌套块、if-else、while、return语法分析的正确性基本能一次验证。跑之前先想清楚期望的 Token 数量跑完数一下数量不对就说明某个字符被吞了或切错了。真正的验证方法是两个输出对比用 diff 工具把你的输出和手写的期望文件逐行比较比人眼盯屏高效得多。6.2 状态跟踪把 DFA 每一步转移打出来词法问题当场显形词法分析器出问题时最有效的调试手段是把状态转移过程打印出来。我习惯在识别主循环里加一个宏开关编译时定义DEBUG_LEXER才启用否则零开销#ifdef DEBUG_LEXER fprintf(stderr, [line %d] state %d - %c\n, stream.currentLine(), state, c); #endif这样跑一遍就能看到 DFA 在哪个字符上跳进了 -1是字符归类错了还是转移表漏了状态一目了然。语法分析阶段的跟踪更简单在每个非终结符函数入口打印函数名和当前 Token就能看到解析路径走到了哪里、卡在哪个分支。这两个开关一直留到答辩前再关掉配置里用宏而不是直接删代码方便临时复开。最后分享一个我自己的教训早年做这个实验时我觉得状态表麻烦用几十个 else if 硬写词法写的时候很爽换测试用例后不断踩边角越补越乱。后来下定决心改成状态转移表把字符分类、终态表、回退逻辑拆成三个独立模块问题一次性清干净。这个工程里DFA 的表驱动设计不是为了炫技而是让词法规则变得“看得见、查得到、改得动”。如果你正在做的编译原理实验也被词法或语法的边界问题折磨我的建议是先停下补丁式修改回到表和文法本身去重构。希望帮到你。本文还有配套的精品资源点击获取
简介一份面向计算机专业学生与编译器初学者的C实现资源围绕编译原理课程中的核心实验展开完整演示了词法分析器与语法分析器的设计与编码过程。压缩包共9个文件包括两个cpp源程序、两个可直接运行的exe程序以及文法定义、token表、源程序样例等txt文档和README说明整体约937KB目录结构简洁易于按需查阅。已有736人学习适合作为课程设计或实验参考。资源价值在于既能直接运行exe观察分析结果也能结合cpp源码与文法txt理解有限自动机、递归下降或LL(1)分析等关键机制。配套的token表和二型文法文件还便于对照调试语法错误通过阅读源码可进一步掌握词法规则定义、状态转换以及语法树的生成流程是巩固编译原理理论与实践能力的实用素材。1. 编译原理实验卡在词法分析和语法分析先别急着啃整本龙书编译原理课的第一次大作业往往是同一个题目给一段源代码先用词法分析器切出 Token再用语法分析器检查结构语言限定 C。网上能找到《词法分析器和语法分析器的实现C.zip》这类压缩包但解压后真正能一次跑通、代码又能讲清楚的很少多数是几百行 if-else 堆出来的临时方案换个测试用例就翻车。我想说的反直觉结论是这个题目的核心难点不是“写一个编译器前端”而是把词法规则的边界理清楚、把递归下降的层次分配对。对多数实验和课设来说手工构造 DFA 加递归下降分析器是性价比最高的一条路不需要你完整实现 NFA 到 DFA 的子集构造算法也不需要去折腾 YACC 生成器。下面按我自己的实践顺序把从零到跑通的完整做法讲一遍适合正在赶编译原理实验、或者在准备小型语言前端预研的人照着做。2. 词法分析器先画 DFA 再写 C而不是堆一串 else if2.1 三种写法的取舍手写扫描器、正则生成器、手工 DFA 状态表词法分析器的实现方式大致分三种。第一种是纯手写扫描器看到字符就 switch 分发遇到字母就拼标识符遇到数字就拼整数。这种写法代码量看着少但关键字、运算符、注释、空白各自的边界混在一起规则一多就乱。第二种是用 Flex 这类正则生成器把词法规则写成正则表达式工具自动生成分析器。生产项目里这是正解但作业场景里老师通常会追问“你的 DFA 图是什么”你答不上来就吃亏。第三种是手工把词法规则画成 DFA再用 C 的状态转移表实现。这是作业里最稳的做法规则直观、排错方便、答辩也好讲。所谓 DFA本质是一张“当前状态 输入字符 → 下一个状态”的表外加一张终态表。你不需要把每个状态都手写出来只需要把字符归类再按归好的类去查表。我一般这样建表先枚举 Token 类型再给字符分成若干类比如字母、数字、运算符、括号、空白。DFA 的起始状态是 0每个状态对应一个正在识别的“半成品”。在 C 里用一个std::vectorstd::vectorint存状态表行是当前状态列是字符类别值是下一个状态。无关转移一律填 -1表示无路可走。2.2 Token 结构体和字符流接口先定数据模型再写逻辑写词法分析器之前先把 Token 的结构定下来。Token 不是简单的字符串它至少要带类型、原始文本、行号和列号。行号列号是语法分析器报错时定位用的没有它们后面的“第几行有错”就无从谈起。enum TokenType { T_INT, T_RETURN, T_IF, T_ELSE, T_WHILE, // 关键字 T_IDENT, T_NUMBER, // 标识符和数字 T_PLUS, T_MINUS, T_STAR, T_SLASH, // 算术运算符 T_ASSIGN, T_EQ, T_NEQ, T_LT, T_LE, T_GT, T_GE, // 关系运算符 T_LPAREN, T_RPAREN, T_LBRACE, T_RBRACE, T_SEMI, T_EOF, T_ERROR }; struct Token { TokenType type; std::string lexeme; int line; int col; };这个结构很简单但有两个细节要注意。lexeme必须保存原始文本不能只存类型因为后面符号表登记、语法树输出都要用到。col列号建议按字符下标记录遇到\t时先简单按 1 处理或者单独处理制表符展开作业里按 1 处理不会有人挑毛病。字符流接口我用一个简单的类包住源代码字符串带一个指针下标的推进逻辑class CharStream { const std::string src; size_t pos; int line; public: CharStream(const std::string s) : src(s), pos(0), line(1) {} char peek() const { return (pos src.size()) ? src[pos] : \0; } char get() { char c peek(); if (c \n) line; if (c ! \0) pos; return c; } int currentLine() const { return line; } int currentCol() const { return static_castint(pos); } };这个类的要点是get()返回当前字符并前进peek()只看不取。词法分析最怕的就是字符读过头peek 给了你一个后悔药最长匹配失败时能回退到安全位置。换行处理也在这里集中做词法分析器本体不用关心行号维护这是我一直建议的拆分方式各模块各干各的。2.3 状态转移表与最长匹配识别主循环的正确姿势字符分类函数是状态表的前置。种类太少会丢失细节太多会让表膨胀。我按这个小语言的语法把字符归成 16 类enum CharClass { C_LETTER, C_DIGIT, C_PLUS, C_MINUS, C_STAR, C_SLASH, C_ASSIGN, C_LT, C_GT, C_LPAREN, C_RPAREN, C_LBRACE, C_RBRACE, C_SEMI, C_SPACE, C_OTHER }; CharClass getCharClass(char c) { if (isalpha(c) || c _) return C_LETTER; if (isdigit(c)) return C_DIGIT; switch (c) { case : return C_PLUS; case -: return C_MINUS; case *: return C_STAR; case /: return C_SLASH; case : return C_ASSIGN; case : return C_LT; case : return C_GT; case (: return C_LPAREN; case ): return C_RPAREN; case {: return C_LBRACE; case }: return C_RBRACE; case ;: return C_SEMI; case : case \t: case \n: case \r: return C_SPACE; default: return C_OTHER; } }注意单独归成一类是因为它既能当赋值号又是、、的第一个字符。这是最长匹配最容易出问题的地方后面第 5 章会单独讲。识别主循环是词法分析器的核心。基本写法是从状态 0 开始逐个读字符查转移表每进入一个终态就记录一下位置和状态一旦遇到非法转移回退到最近一次终态位置产出对应的 TokenToken Lexer::nextToken() { while (true) { // 跳过空白 // 从当前 pos 开始识别 int state 0; int lastFinal -1; size_t lastFinalPos stream.pos; std::string lexeme; while (state ! -1) { char c stream.peek(); CharClass cc getCharClass(c); int next delta[state][cc]; if (next -1) break; lexeme.push_back(c); stream.get(); state next; // 记录最近一次遇到终态的位置 if (isFinal[state]) { lastFinal state; lastFinalPos stream.pos; } } stream.pos lastFinalPos; // 回退到终态位置 lexeme.resize(lastFinalPos - startPos); // 根据 lastFinal 生成 Token } }这里有三个参数是最关键的。delta状态转移表isFinal终态标记数组lastFinalPos最近终态位置。没有lastFinalPos的回退会被切成一个和一个因为识别到时已经是终态继续读才进入更大的终态。最长匹配原则就是靠“记录最近的终态并回退到它”这个机制实现的。2.4 标识符去重与关键字判定查表时机决定成败标识符和关键字的区分是作业里最高频的翻车点。常见错误是把关键字表写在判断逻辑里每读一个字符就查一次。正确做法是先按最长匹配把整个标识符拼完再去查关键字表命中就改成对应 Token 类型没命中就是普通T_IDENT。bool isKeyword(const std::string s) { static const std::unordered_mapstd::string, TokenType kw { {int, T_INT}, {return, T_RETURN}, {if, T_IF}, {else, T_ELSE}, {while, T_WHILE} }; auto it kw.find(s); return it ! kw.end(); }查完之后才考虑符号表登记。如果实验要求输出符号表用std::unordered_mapstd::string, int记录标识符名和首次出现行号即可。注意登记时机也要放在整个标识符识别完成之后不能边读边登记否则int还在拼intx时就被当关键字登记了。数字字面量的处理同理。拼完整段数字再stoi拼接过程中如果遇到字母就按“非法标识符”报错。这两个判定顺序写反词法分析器的正确率会直线下滑而且是那种换了用例才暴露的隐性错。3. 语法分析器递归下降的写法比 LR 更适合作业场景3.1 为什么是递归下降报错定位、可读性、调试体验语法分析的主流方案是递归下降和 LRYacc/Bison。作业层面我强烈建议递归下降理由很现实。第一LR 生成器生成的表格老师要你画状态图时你根本不知道从哪讲起第二LR 的错误恢复信息默认是给人看的不是给课程答辩看的第三也是最关键的递归下降的代码是“每个非终结符一个函数”报错时能直接指定正在解析哪个产生式调试体验远好于查一张跳转表。递归下降的本质是用语言的文法直接写程序非终结符是函数终结符是匹配函数。它要求文法没有左递归这对 C 风格的小语言完全没有压力。分支多的地方稍微用点回溯思想但实际不需要回溯——只要文法写得好向前看一个 Token 就能决定走哪个分支。3.2 文法设计EBNF 怎么写、左递归怎么消在设计递归下降分析器前先把文法写成 EBNF。以下是小语言的核心文法我没有用教科书那种繁复的 BNF而是加了方括号表示可选星号表示零次或多次Program : StmtList StmtList : Stmt StmtList | ε Stmt : DeclStmt | AssignStmt | IfStmt | WhileStmt | ReturnStmt | Block Block : { StmtList } DeclStmt : int IDENT ; AssignStmt: IDENT Expr ; IfStmt : if ( Expr ) Stmt [else Stmt] WhileStmt : while ( Expr ) Stmt ReturnStmt: return Expr ; Expr : Term (( | -) Term)* Term : Factor ((* | /) Factor)* Factor : NUMBER | IDENT | ( Expr )这里 Expr 到 Term 到 Factor 的三层结构就是在处理运算符优先级加减最外层乘除中间层括号和操作数最内层。如果你把这三层写成一个函数表达式优先级就废了23*4会被算成(23)*4。这段文法本身没有直接左递归因此可以落地。注意 StmtList 里的ε空产生式它对应的是语句列表结束的情况写成 C 时就是一个“什么都不做”的 if 分支。空产生式处理不好是递归下降常见的死循环来源下一节会看到具体对应。3.3 Parser 骨架每个非终结符一个函数的落地Parser 类持有词法分析器和两个 Token当前 Token 和一个前瞻 Token。为什么要两个因为if后面要看到(才能决定走哪个分支只看当前 Token 不够需要 lookahead。这个前瞻可以用“拉取两个 Token”实现也可以用一个缓冲区。class Parser { Lexer lexer; Token cur; Token look; void advance() { cur look; look lexer.nextToken(); } bool match(TokenType t) { if (cur.type t) { advance(); return true; } return false; } void expect(TokenType t) { if (!match(t)) { throw ParseError(expect tokenName(t) but got cur.lexeme, cur.line); } } };cur是当前正要处理的 Tokenlook是预读的下一个。match成功即消费当前 Token 并推进expect在失败时直接抛出带行号的异常。这是整个分析器最核心的基建所有非终结符函数都建立在它之上。下面看表达式三层和语句分派void Parser::parseExpr() { parseTerm(); while (cur.type T_PLUS || cur.type T_MINUS) { advance(); parseTerm(); } } void Parser::parseTerm() { parseFactor(); while (cur.type T_STAR || cur.type T_SLASH) { advance(); parseFactor(); } } void Parser::parseFactor() { if (cur.type T_NUMBER) { advance(); } else if (cur.type T_IDENT) { advance(); } else if (cur.type T_LPAREN) { advance(); parseExpr(); expect(T_RPAREN); } else { throw ParseError(unexpected token in factor, cur.line); } }parseExpr先调parseTerm再循环处理加减号这样123这样左结合的表达式不需要额外的消左递归处理循环天然承担了“递归地右移”的任务。parseFactor的分支判断只看当前 Token 类型数字、标识符或左括号其余全部抛错。注意我没有在这里处理负号-1如果文法里没有定义一元负号会直接报错如果需要支持应该在parseExpr里加一层一元运算符处理。语句分派也是同样的模式但要注意StmtList里的空产生式。我用一个isStmtStart()函数判断当前 Token 是否属于某类语句开头不是就直接返回上一层让调用方决定是否报错。void Parser::parseStmtList() { while (isStmtStart(cur.type)) { parseStmt(); } } void Parser::parseStmt() { if (cur.type T_IF) parseIfStmt(); else if (cur.type T_WHILE) parseWhileStmt(); else if (cur.type T_INT) parseDeclStmt(); else if (cur.type T_IDENT) parseAssignStmt(); else if (cur.type T_RETURN) parseReturnStmt(); else if (cur.type T_LBRACE) parseBlock(); else throw ParseError(invalid statement start, cur.line); }while循环代替了StmtList → Stmt StmtList | ε的递归既避免了右递归带来的栈深度问题也让代码更贴合实际解析流程。语句块的解析在这里递归调用parseStmtList天然支持任意嵌套只要栈不爆。3.4 轻量错误恢复同步 Token 集合的实战值教科书里的错误恢复讲 panic mode做法是定义同步 Token 集合出错时丢弃 Token 直到遇到一个同步 Token 再重新开始。作业里很多人直接throw终止答辩时老师问“你怎么从错误里恢复”答不上来。我一般给 Parser 加一个synchronize()方法解析语句时出错就不断advance()吞掉 Token直到遇到分号、右花括号或T_EOF然后回到语句列表循环。这样做的好处是一个文件里的多个错误能一次报完而不是发现第一个错就停工。void Parser::synchronize() { while (cur.type ! T_EOF) { if (cur.type T_SEMI) { advance(); return; } if (cur.type T_RBRACE) { return; // 让上层 handle } advance(); } }注意T_RBRACE出现时不要直接消费因为右花括号是块结束标志应该交给外层语句的结束处理来消费否则块会提前闭合。这个细节是我自己的血泪经验第一次实现时把}也吞了结果整个嵌套结构错位报错位置全偏。同步集合选什么 Token要根据文法里哪些 Token 能明确标志“一条语句结束了”来定不是随便选的。4. 把两个模块串起来Token 流、符号表、输出格式与构建配置4.1 拉取式配合词法器一次一个 TokenParser 按需索取词法分析器和语法分析器的接口设计要么是词法器先把所有 Token 放进一个队列语法分析器再从这个队列里取要么是拉取式Parser 需要时再向 Lexer 要下一个。前者代码直观但要预先读完整个文件文件大时内存不划算而且peek前瞻不便后者每步只处理一个 Token内存占用固定还能配合前瞻做流式处理。拉取式的关键是 Lexer 对外只暴露两个方法nextToken()返回下一个 Token以及恢复词法分析状态的 reset。Parser 内部维护cur和look两个 Token每次advance()就把look推进到下一个。这样 Lexer 不需要保存 Token 历史状态只有pos、line和col。在实践中我发现拉取式还有一个隐藏好处调试时容易单测。你可以先手动调用nextToken()打印出全部 Token确认词法没问题后再把同一段源码喂给 Parser。词法和语法两个模块的错误被隔离开排查范围直接缩小一半。4.2 主循环与文件读取C 读源码的编码与安全坑词法分析和语法分析都准备好后main 函数要做的事情很琐碎读文件、构造 Lexer、构造 Parser、跑分析、输出结果。这个主循环看着简单坑全藏在文件读取里。C 用ifstream读文件时直接while (in line)是灾难因为运算符会按空白自动分词源代码换行和空格信息全丢了。要按字符完整读入std::string readSource(const std::string path) { std::ifstream in(path, std::ios::binary); if (!in.is_open()) { throw std::runtime_error(cannot open source file); } std::stringstream ss; ss in.rdbuf(); return ss.str(); }这里用二进制模式打开是有意的。文本模式在 Windows 上会把\r\n自动转成\n看起来方便但如果你的词法分析器要按原始字节统计列号转换反而会造成行列号错位。用二进制模式读回来自己统一处理\n和\r行为在所有平台上一致。另外如果题目的测试文件是 UTF-8 带 BOM 的前三个字节EF BB BF会被当作普通字符读进来第一行 Token 全部错乱。解决也很简单判断字符串前三个字节是否为 BOM是则erase掉。这个坑在 Windows 记事本保存的文件上几乎是必现的属于一百个学生里有八十个会踩的类型。4.3 实验报告要的输出先定格式再写代码实验指导书一般要求两种输出词法分析结果是一份 Token 列表语法分析结果是程序结构是否正确。输出格式最好先定下来再写代码不然调试时满屏乱打根本没法对比正确性。我习惯用纯文本、制表符分隔的表格Token Type Line Col int T_INT 1 1 a T_IDENT 1 5 T_ASSIGN 1 7 42 T_NUMBER 1 9 ; T_SEMI 1 10语法分析器跑完如果没抛异常打印Syntax OK.如果抛了异常打印Error at line N: ...。这样写的好处是结果能直接和同学的、和老师的输出样例做 diff。调试阶段不要用二进制格式或 Python 脚本包装输出纯文本最直接命令行 diff 一眼就能看出来多切了一个 Token 还是缺了一个分号。构建配置方面实验文件夹的 Makefile 我一般写成这样CXX g CXXFLAGS -stdc17 -Wall -Wextra -g SRCS lexer.cpp parser.cpp main.cpp OBJS $(SRCS:.cpp.o) TARGET compiler_frontend $(TARGET): $(OBJS) $(CXX) $(CXXFLAGS) -o $ $^ %.o: %.cpp $(CXX) $(CXXFLAGS) -c $ clean: rm -f $(OBJS) $(TARGET)-g一定要保留调试器断点靠它。-Wall -Wextra在词法分析器的隐式转换、未使用的变量这类问题上能提前报警。实验里交代码时这些告警全清掉答辩查代码的印象分会好很多。如果你是在 vscode 里配的 C/C 环境注意 task.json 里要把文件列表写全别只编译 main.cpp否则链接阶段全是未定义符号。5. 编译原理实验五个常见坑现象、原因、解法5.1 中文路径和 UTF-8 BOMVSCode 里好好的换台机器就崩现象代码在本机能跑拷贝到实验室电脑上ifstream打开文件失败或者第一个字符变成乱码词法分析第一行就报T_ERROR。原因有两个。一是中文路径在 Windows 上涉及编码转换老旧的fopen传const char*按本地代码页处理二是记事本存成 UTF-8 带 BOM前三个字节被当成内容读进来。解决路径上坚决不用中文统一用std::ifstream配合二进制模式读入检测EF BB BF后手工去掉。这两个问题同时发生时调试视角会非常迷惑建议先确认文件字节再进词法环节。5.2 CRLF 换行让行号错乱报错定位到了错误行现象同一个测试文件在本机行号全对在 Windows 上打开后所有错误行号比预期多一或者偏到上一行。原因Windows 文本模式把\r\n转成\n而你在 CharStream 里对\r也做了某种处理统计行号时机不一致。解决全文统一按二进制读入CharStream 里只对\n增加 line遇到\r直接跳过不参与 Token 拼装。最重要的是让 getCharClass 把\r归到 C_SPACE这样它不会成为非法字符。这个小改动看似不起眼实际能把跨平台的所有行号问题一次清干净。5.3 关键字被当成标识符或反之现象intx整体被识别成T_INT或者int被当成普通标识符。原因识别标识符时没有做最长匹配就查关键字表比如读到i就开始比对关键字列表后面跟了n和t就提前命中。解决先把从起始字符到回退位置前的完整文本取出来整个字符串查一次关键字表查不到再按T_IDENT登记。注意intx这种形式最长匹配得到的是intx查表落空正确输出为标识符。反过来的情形是关键字表在字符扫描中间查也就是“边扫边查”识别int和intx就区分不开了。把查表时机严格放在整个词素拼接完成后这类问题直接消失。5.4 最长匹配没回退被切成了和现象输入ab输出两个 Token 分别是和语法分析器报错。原因状态转移表里是终态遇到也能进入的终态但如果你的循环在到达这个终态时立即生成 Token没有继续试探下一个字符最长匹配就失败了。解决主循环里每到达一个终态记录lastFinalPos但不立即停止只有遇到非法转移时才回退到该位置。代码上就是stream.pos lastFinalPos;这一行它相当于把所有 Token 的边界都“迟滞”到了非终态才确定。、、!同理都是这一个机制统一处理的。5.5 发布出来的工程跑不起来运行库版本对不上现象下载的现成压缩包里有 exe双击报“缺少 VCRUNTIME140.dll”或“0xc000007b”VSCode 里重新编译又提示环境问题。原因目标机器上没装对应版本的 Visual C Redistributable 运行库或者装了 32 位而你的是 64 位程序编译环境切换时工具链版本不一致也会产生新的二进制依赖。解决自己写的话只依赖 C 标准库用g -stdc17静态链接或打包时放一份依赖说明从网上拿的压缩包别直接用现成 exe把它当参考读完代码后在自己环境重新编译。vscode 里面配 C/C 环境时重点检查编译器的位数和链接器选项是否一致这能排除一大半“我代码没问题为什么跑不起来”的假象。6. 从能跑到能演示基线用例、状态跟踪和调试技巧6.1 基线用例把“预期输出”写进注释跑一次就知道对错准备一份固定的测试文件test1.src覆盖全部 Token 类型和语句结构预期结果用注释直接贴在测试文件旁边。我常用的基线用例长这样int main() { int a 1; if (a 0) { a a 2; } else { a a - 1; } while (a 10) { a a * 2; } return a; }这个文件虽然只有十几行但覆盖了关键字、标识符、数字、赋值、关系运算、算术运算、嵌套块、if-else、while、return语法分析的正确性基本能一次验证。跑之前先想清楚期望的 Token 数量跑完数一下数量不对就说明某个字符被吞了或切错了。真正的验证方法是两个输出对比用 diff 工具把你的输出和手写的期望文件逐行比较比人眼盯屏高效得多。6.2 状态跟踪把 DFA 每一步转移打出来词法问题当场显形词法分析器出问题时最有效的调试手段是把状态转移过程打印出来。我习惯在识别主循环里加一个宏开关编译时定义DEBUG_LEXER才启用否则零开销#ifdef DEBUG_LEXER fprintf(stderr, [line %d] state %d - %c\n, stream.currentLine(), state, c); #endif这样跑一遍就能看到 DFA 在哪个字符上跳进了 -1是字符归类错了还是转移表漏了状态一目了然。语法分析阶段的跟踪更简单在每个非终结符函数入口打印函数名和当前 Token就能看到解析路径走到了哪里、卡在哪个分支。这两个开关一直留到答辩前再关掉配置里用宏而不是直接删代码方便临时复开。最后分享一个我自己的教训早年做这个实验时我觉得状态表麻烦用几十个 else if 硬写词法写的时候很爽换测试用例后不断踩边角越补越乱。后来下定决心改成状态转移表把字符分类、终态表、回退逻辑拆成三个独立模块问题一次性清干净。这个工程里DFA 的表驱动设计不是为了炫技而是让词法规则变得“看得见、查得到、改得动”。如果你正在做的编译原理实验也被词法或语法的边界问题折磨我的建议是先停下补丁式修改回到表和文法本身去重构。希望帮到你。本文还有配套的精品资源点击获取
