简介这份压缩包提供编译原理课程中词法分析器和语法分析器的C实现面向计算机及相关专业学生、对编译器实现感兴趣的开发者以及需要完成课程设计或实验报告的初学者。内容覆盖从词法规则定义、有限自动机建模到递归下降或LL(1)语法分析、抽象语法树构建的完整编译前端流程并处理了非法字符、格式错误数字等词法错误以及语法错误、类型错误等常见问题。包内共9个文件包含2个C源码词法分析.cpp与语法分析.cpp、2个可直接运行的exe程序、4个txt文本文法/规则说明如文法.txt、token表.txt、2型文法.txt等及1个README.md工程说明整体仅937KB便于快速打开和本地调试。已有736人学习使用可作为课程设计或实验报告的完整参考方案通过阅读源码可以理解有限自动机、上下文无关文法、递归下降解析等核心原理直接运行exe还能快速验证分析结果适合从零搭建自己的编译器前端。1. 编译原理词法分析器和语法分析器的实现C这门课设到底要你做什么如果你正在为“编译原理词法分析器和语法分析器的实现C.zip”这个课程设计发愁先别急着在搜索引擎里翻源码包。这门课设的本质不是让你写出一个能编译 C 的编译器而是让你亲手走一遍“字符流 → 单词符号 → 语法树”这条最经典的编译流水线。绝大多数高校的实验要求都落在同一个范围用 C 实现一个针对某子集语言的词法分析器识别关键字、标识符、数字、运算符和界符再配合一个语法分析器常用递归下降或 LR 分析验证一串输入是否符合文法。它不是工业级 Clang也不是对抗性测试它是一个让你“看懂龙书前几章”的动手项目。这个项目适合三类人正在修编译原理课程的本科生拿分是刚需、准备考研复试需要项目经历的考生这个题目面试官基本都会追问以及想补“程序如何理解程序”这一课的自学者。我见过太多人直接下载网上的 .zip 源码交差结果答辩时被问“你这个 DFA 状态表是怎么画的”直接语塞。这篇笔记要做的是把最常见的实现路径拆成你可以真正理解、复现并讲清楚的步骤同时把最容易让你翻车的几个坑提前踩平。先记住一个结论词法分析器考的是状态机建模能力语法分析器考的是递归与栈的运用两者合起来才是对“形式语言”这回事的完整认知。2. 词法分析器的最小实现从字符流到 Token 序列2.1 为什么选择“手动构造有限自动机”而不是 Flex词法分析器的实现路线大致有三条用 Flex 工具自动生成、用手写状态机实现、用正则表达式逐条匹配。对于课程设计我强烈建议你走第二条路。Flex 生成的代码虽然工整但你在答辩时很难解释清楚那张跳转表的构造过程正则逐条匹配在小语言上勉强能用一旦运算符重叠比如和同时存在就会出现优先级问题。手写状态机看起来原始但它逼着你把“识别标识符”和“识别数字”的状态转移画清楚而这恰恰是考核要点。一个常见的误区是把状态机做成“读一个字符就 switch 一次”的散装逻辑。这种做法不是不行但状态一多代码就变成一锅粥。我一般会先把语言的关键字、运算符、界符、标识符和数字分类定义成枚举再用一个二维表描述状态转移关系。这样写的优势是逻辑集中、可测试性强而且答辩时你可以直接说“这张表就是我这个 DFA 的图形化表示”。2.2 词法分析器的完整代码框架状态转移表与驱动函数下面给出一个可直接复现的最小词法分析器实现它针对的源语言包含if、else、while、int四个关键字 - * / 等运算符以及标识符和整数。我们用枚举定义状态和符号类型用std::vector存储转移表。#include iostream #include string #include vector #include cctype // 符号类型定义 enum class TokenType { KEYWORD, IDENTIFIER, INTEGER, OPERATOR, DELIMITER, END }; // 状态定义0 为初态-1 为接受态直接返回 enum State { ST_START 0, ST_ID, ST_NUM, ST_OP, ST_DONE }; // 全局关键字表 std::vectorstd::string keywords {if, else, while, int}; // 判断是否为关键字 bool isKeyword(const std::string s) { for (const auto kw : keywords) { if (s kw) return true; } return false; } // 词法分析器主体 std::vectorstd::pairTokenType, std::string lexer(const std::string src) { std::vectorstd::pairTokenType, std::string tokens; int i 0; int line 1; // 记录行号用于报错信息 while (i src.length()) { char c src[i]; // 跳过空白字符换行时行号自增 if (isspace(c)) { if (c \n) line; i; continue; } // 识别标识符或关键字 if (isalpha(c) || c _) { std::string token; while (i src.length() (isalnum(src[i]) || src[i] _)) { token src[i]; i; } if (isKeyword(token)) { tokens.push_back({TokenType::KEYWORD, token}); } else { tokens.push_back({TokenType::IDENTIFIER, token}); } continue; } // 识别整数 if (isdigit(c)) { std::string token; while (i src.length() isdigit(src[i])) { token src[i]; i; } tokens.push_back({TokenType::INTEGER, token}); continue; } // 识别运算符和界符这里处理多字符运算符 std::string op; bool matched false; for (const std::string oper : {, , , !}) { if (src.compare(i, 2, oper) 0) { op oper; i 2; matched true; break; } } if (!matched std::string(-*/).find(c) ! std::string::npos) { op c; i; matched true; } if (matched) { tokens.push_back({TokenType::OPERATOR, op}); continue; } // 识别界符 if (c ( || c ) || c { || c } || c ;) { tokens.push_back({TokenType::DELIMITER, std::string(1, c)}); i; continue; } // 无法识别报错 std::cerr 词法错误: 第 line 行出现非法字符 c std::endl; i; } tokens.push_back({TokenType::END, }); return tokens; }这段代码的逻辑核心不是状态转移表而是一个“扫描 分类”的循环。为什么我还是称它为状态机因为每一类识别分支标识符、数字、运算符本质上都是一段确定性的转移判断遇到字母进入“标识符收集”状态直到遇到非字母数字字符才退出。这里的matched变量用于处理多字符运算符的匹配优先级先检查长度更长的组合避免把拆成两个再报错。关键参数说明line变量的维护是很多初学者容易遗漏的点报错时带行号能让后续调试省力一个量级。keywords表用std::vector存储是因为量小用顺序查找足够如果你是追求性能的进阶选手换成std::unordered_set也只是顺手的事。src.compare(i, 2, oper)这个写法要注意边界安全当i 1已经越界时 C 的compare并不会抛异常而是返回不相等所以不需要额外判越界。2.3 状态转移表方案当输入语言变复杂时的可选改造如果老师要求你处理更复杂的词法规则比如字符串常量、注释、浮点数上面的“扫描 分类”结构就会变得混乱。此时我建议你回到真正的表驱动状态机。思路是定义一张 N x M 的转移矩阵行是状态、列是字符分类字母、数字、运算符、界符、其他矩阵元素是“下一个状态”。运行时就一个循环int state 0; while (state ! ERROR_STATE) { int col getCharType(ch); state transitionTable[state][col]; // 根据状态决定收集字符、输出 Token 或切换状态 }这张表的优点是你可以像画状态图一样在纸上推演一遍再写进代码评审老师一眼就能看懂。缺点是状态一多表会变得很稀疏而且“根据状态决定动作”的逻辑仍然需要一段switch来承担。所以我的建议是课程设计的词法部分扫描 分类法优先级最高除非老师明确要求 DFA 图形化展示否则不给自己加戏。如果要做注释跳过//和/* */在那个位置加一个分支即可注意用一个commentDepth变量在/和*之间切换状态这块逻辑不复杂但很考验细心。3. 语法分析器怎么选递归下降和 LR 的取舍与落地3.1 递归下降的代码结构一个函数对应一个产生式语法分析器的实现选择比词法更关键。主流课程设计一般要求你实现“LL(1) 递归下降”或“LR(0)/SLR(1) 移进归约”。我的个人建议是除非老师专门要求 LR 分析表否则无脑选递归下降。原因很简单递归下降的代码结构和文法产生式一一对应写起来像翻译注释排错时看函数调用栈就能定位到具体产生式。而 LR 的关键在于分析表的构造手工算 LR(0) 项目集族很容易出错用工具生成又讲不清楚原理。下面是一段针对简单表达式文法的递归下降代码文法大致为expr - term rest rest - term rest | - term rest | ε term - factor term_rest term_rest - * factor term_rest | / factor term_rest | ε factor - ( expr ) | num#include iostream #include vector #include string class Parser { private: std::vectorstd::pairTokenType, std::string tokens; int pos 0; // 检查当前 Token 类型是否匹配匹配则前进 bool match(TokenType type) { if (pos tokens.size() tokens[pos].first type) { pos; return true; } return false; } // 打印当前 Token 信息便于调试 void printToken() { if (pos tokens.size()) { std::cout 当前消耗 Token: tokens[pos].second std::endl; } } // expr 对应文法规则 expr - term rest void parseExpr() { parseTerm(); parseRest(); } // rest 对应文法规则 rest - term rest | - term rest | ε void parseRest() { printToken(); if (match(TokenType::OPERATOR) tokens[pos - 1].second ) { parseTerm(); parseRest(); } else if (match(TokenType::OPERATOR) tokens[pos - 1].second -) { parseTerm(); parseRest(); } // 其他情况为 ε 产生式直接返回 } // term 对应文法规则 term - factor term_rest void parseTerm() { parseFactor(); parseTermRest(); } // term_rest 对应文法规则 term_rest - * factor term_rest | / factor term_rest | ε void parseTermRest() { printToken(); if (match(TokenType::OPERATOR) tokens[pos - 1].second *) { parseFactor(); parseTermRest(); } else if (match(TokenType::OPERATOR) tokens[pos - 1].second /) { parseFactor(); parseTermRest(); } // ε 产生式直接返回 } // factor 对应文法规则 factor - ( expr ) | num void parseFactor() { if (match(TokenType::INTEGER)) { // 已经消费了一个整数打印简化后的语义值 std::cout 识别出整数: tokens[pos - 1].second std::endl; } else if (match(TokenType::DELIMITER) tokens[pos - 1].second () { parseExpr(); if (!match(TokenType::DELIMITER) || tokens[pos - 1].second ! )) { throw std::runtime_error(语法错误: 缺少右括号); } } else { throw std::runtime_error(语法错误: 这里应该是一个 factor); } } public: Parser(std::vectorstd::pairTokenType, std::string tokenList) : tokens(std::move(tokenList)) {} bool parse() { try { parseExpr(); // 解析结束后必须消耗完所有 Token否则说明语法串有多余内容 if (pos tokens.size() tokens[pos].first ! TokenType::END) { std::cerr 语法错误: 多余的 Token tokens[pos].second std::endl; return false; } return true; } catch (const std::exception e) { std::cerr e.what() std::endl; return false; } } };这段代码最值得学习的点不是每个函数怎么写的而是“匹配成功后再决定分支”的顺序。注意parseRest中的写法先用match去尝试匹配OPERATOR再通过tokens[pos-1]获取具体是哪个运算符。这种写法的好处是避免了提前预读lookahead带来的复杂逻辑坏处是如果运算符不匹配比如遇到*match会返回false但并没有真正消费 Token所以状态不会乱。这里用了一个常见的“消费后取反查”技巧代码里通过tokens[pos - 1]访问已消耗的内容虽然pos已经加一但这个索引在大多数情况下是安全的——因为match成功时pos必定大于等于 1。参数说明printToken()是我在调试时加进去的辅助函数正式版可以去掉。throw std::runtime_error用于携带错误信息结束本次解析这种方式比返回bool值更具表达力因为错误信息可以直接打印。pos tokens.size()的边界检查可以防止空 Token 列表导致的越界崩溃这一点对空输入文件尤其重要。3.2 LR 分析如果你非做不可至少把表对准如果你遇上了必须实现 LR(0) 或 SLR(1) 的老师或者你想给自己的代码加分那么要掌握的是一条与递归下降完全不同的路径先构造文法的 LR(0) 项目集规范族再根据项目集生成 ACTION 和 GOTO 两张表最后用一个驱动栈执行移进/归约。这个流程最繁琐的部分是项目集族的计算手工推很容易漏项目工程量巨大。我可以给你一个在 C 中落地的小建议项目集族的表示用两个容器一个存储项目形如E - T . A一个存储状态编号。驱动栈用std::vectorint存状态、std::vectorstd::string存符号。每次动作查 ACTION 表时注意“归约”动作发生后要额外弹出符号、压入左部非终结符再根据 GOTO 表跳转状态。这一处的状态转移顺序是 LR 分析最容易出错的地方建议用一个独立函数封装“执行归约”。// 归约动作的伪代码框架定位误操作的边界 void performReduction(int productionId) { // 从表格中获取产生式左部和右部长度 std::string left getProductionLeft(productionId); int rightLen getProductionRightLength(productionId); // 弹出 rightLen 个状态和符号 for (int i 0; i rightLen; i) { if (!stateStack.empty()) stateStack.pop_back(); if (!symbolStack.empty()) symbolStack.pop_back(); } // 根据当前栈顶状态和左部符号查 GOTO 表 int nextState gotoTable[stateStack.back()][nonterminalIndex(left)]; // 压入左部符号和下一个状态 symbolStack.push_back(left); stateStack.push_back(nextState); }这段代码的注意点在于stateStack和symbolStack必须保持长度一致否则归约过程中会出现栈顶状态无法索引的错位问题。另一个高频 bug 是产生式编号与右部长度表对不上归约时弹多了状态或弹少了符号都会直接导致崩溃这种情况用assert在调试期检查比肉眼排查快得多。3.3 语义动作除了验证语法还能算个表达式课程设计如果只打印“语法正确”或“语法错误”往往显得单薄。一个很小的加分项是在语法分析中嵌入语义动作比如把上面的parseExpr改造为一个返回值而不是void的函数。你可以让每个parseFactor返回整数值parseTerm返回乘除后的结果parseExpr返回加减后的结果这样最终解析完一个表达式语法树虽然没显式建但计算结果已经出来了。int parseExpr() { int termVal parseTerm(); return parseRest(termVal); } int parseRest(int leftVal) { if (match(TokenType::OPERATOR) tokens[pos - 1].second ) { int rightVal parseTerm(); return parseRest(leftVal rightVal); } if (match(TokenType::OPERATOR) tokens[pos - 1].second -) { int rightVal parseTerm(); return parseRest(leftVal - rightVal); } return leftVal; // ε 产生式携带已有值返回 }这个改造几乎不需要改动语法结构只需要把“void 函数”替换为“int 函数”并在每次递归调用的返回处做算术运算。它是通向“语法树节点值传递”的最短路径。等答辩时你就可以说“我这个分析器不仅能判断输入是否合法还能算值”这一个点就能和班上的大多数同学拉开差距。4. 从词法到语法的管道Token 流接口设计和调试信息输出4.1 两个分析器的连接方式直接传递 Token 向量词法分析器的输出是std::vectorstd::pairTokenType, std::string语法分析器直接接收这个向量作为构造参数。这个接口设计的关键是保证前后端解耦——词法分析器不关心语法规则语法分析器不关心字符流如何被读取。这种切片式的分工看起来简单但很多同学的代码里会出现词法分析器在识别if时顺便就做了语法判断的情况这会让两个模块藕断丝连后面排错时非常头痛。一个推荐做法是让 Token 结构携带行号信息方便语法报错时回溯原文位置struct Token { TokenType type; std::string lexeme; int line; };把line从词法分析器的局部变量转移到 Token 自身语法分析器报错时就不只能说“语法错误”而能说“第 5 行附近缺少右括号”。这种体验虽然只差一个字段但答辩演示时给老师的印象会好很多。4.2 调试开关打印 Token 流和分析过程想让代码在“可调试”和“可交付”之间切换最简单的做法是加一个全局或构造参数bool debug。当它为true时词法分析器每输出一个 Token 就打印一行语法分析器每次递归进入一个函数前也打印一行。这样你不需要单步断点就能看到输入int a 3 4 * 5;是被怎样一步步吃掉的。调试输出的目标不是记录“发生了什么”而是让你能顺着输出回答出三个问题当前读到了什么字符、当前进入哪个产生式函数、当前消费了哪个 Token。实践中我把这些输出集中打印到std::cerr好处是它不会和正常的程序输出混在一起重定向到文件后还可以保留排查线索。如果你在 Visual Studio 里跑可以直接在输出窗口里看不用打断点。if (debug) { std::cerr [词法] 第 token.line 行 生成 Token: tokenTypeToString(token.type) - token.lexeme std::endl; }这段代码的tokenTypeToString是辅助函数把枚举转成可读字符串。注意它放在debug分支里线上关闭debug后不会产生任何性能损耗。5. C 实现中的避坑与排查从内存崩溃到语义错误的 5 个血泪经验5.1 字符串比较“越界”不报错结果却总是错现象用src.compare(i, 2, oper)判断双字符运算符时在输入末尾比如只有一个时程序不会崩溃也不会报错但 Token 被切断成和一个非法字符。原因std::string::compare在请求的子串长度超出字符串实际长度时不会抛出异常而是将实际剩余字符与目标串比较并返回差值。这意味着你写“从 i 开始取 2 个字符”如果只有一个字符它会用那一个字符参与比较然后返回非零。解决在调用compare之前显式判断i 1 src.length()确保至少有两个字符可供比较。或者用更保险的src.substr(i, 2) oper——substr在越界时会截取到末尾不会抛异常且语义清晰。这个坑在词法分析的边界输入比如空文件、单个运算符里最容易触发建议把这类输入放进测试用例。5.2 词法分析器把识别成和两个 Token现象输入a b结果输出三个 Tokena、、、b语法分析器报错。原因单字符运算符分支先匹配了程序没有意识到后面还跟着一个于是把一个复合运算符拆散了。这是典型的“最长匹配原则”缺失——你必须先探测双字符运算符再退回单字符匹配。解决按本文第 2 节的顺序来处理先查、、、!这组双字符运算符命中就消费两个字符没命中再检查单字符运算符。这个顺序不能颠倒。我在实际代码里把双字符运算符放在一个std::vectorstd::string里顺序就是代码里的顺序绝不要贪图简单只做单字符匹配。5.3 递归下降解析12*3时直接一路向左结合现象输入12*3期望结果是乘法优先但计算结果是(12)*39。原因文法层次没有体现优先级。如果你把加减法写成expr - term expr这种右递归却让term里的乘除法先递归那么优先级虽然正确但结合性会变。更常见的问题是很多人只写了一个parseExpr直接处理所有运算符导致表达式的解析结果完全取决于函数内分支顺序。解决坚持使用多层文法加法和减法放最外层parseExpr乘法和除法放中间层parseTerm括号和数字放最底层parseFactor。这个结构是经过无数验证的标准方案不要在优先级上做无谓的发挥。验证优先级是否正确的简单方法是打印计算值23*4应当输出14而不是20。5.4 分析器进入死循环卡死在while (i src.length())现象输入包含未被定义的字符比如中文标点i不前进程序卡死。原因词法分析循环里遇到非字母、非数字、非运算符的字符时如果处理分支里没有i就会在原地打转。很多初学者在“报错”逻辑里漏了i于是报错之后下一次循环还是同一个字符。解决在词法错误的分支里强制i更好的是在循环体开头先判断c是否属于已知字符集合不属于则打印错误并i把“未知字符”当作一种可跳过的 Token。此处的血泪教训是任何分支都必须有一个“消费字符”或“改变状态”的动作否则就是死循环。5.5 调试输出有内容但语法树/算法层面的结果总是差一截现象Token 流打印出来正确递归下降也没报错但最终没有输出任何语义值或语法树节点。原因大部分情况下是“返回值的传播链断裂”——某一个parseTerm的返回值在parseRest中未参与计算或者某个分支返回了默认值0导致整个表达式的值被吞掉。这种问题隐蔽性极高因为语法分析本身不报错。解决给每层函数加一个断言式的调试输出打印该层函数的返回值和消耗的 Token 位置。如果你写了语义动作建议先用最简单的表达式比如3测试确认返回值是3再测34确认7再测34*5逐步加码。我一般会做一个三层的测试列表单值、同优先级运算符、跨优先级和括号混合每层通过再进下一层而不是一把梭。6. 验证与进阶三个直接能用的测试方法和一个编译器方向的延伸入口要判断你的分析器是否真的“能用”至少要通过下面三类测试。第一类是边界输入空字符串、只有空白字符的输入、只有单个字符的输入、末尾不完整的运算符如a。这些测试考察的是崩溃耐受性。第二类是正确的表达串int a 1 2 * 3;应当输出“语法正确”且计算结果为7。第三类是错误串int a 3;、int 1;、(12;——这些都必须给出错误信息且不崩溃。对于第三类测试我见过太多人的程序一遇到错误就直接“崩溃退出”这会给老师留下非常不好的印象。所以最基本的验收标准不是“正确输入跑通了”而是“错误输入不死、不卡、报错信息有位置”。哪怕你在错误处理里只是打印一行第 X 行语法错误也比Segmentation fault强一百倍。再往上走一步如果时间允许建议把语法分析的结果保存为一个“抽象语法树”结构而不是简单地传递返回值。定义一个ASTNode结构体包含节点类型整数、加法、赋值等和左右子节点指针然后在递归下降中用堆指针构建树。这一步做完你才算真正实现了“从 Token 到树”的完整链路——将来做代码生成器时只需要遍历这棵树即可。学校课程设计的下一步往往是“生成中间代码”或“目标代码”有了 AST 你就已经站在了下一级台阶上。最后分享一个我自己的习惯每次写完一个分析器模块我会用一张 Excel 表维护测试用例和预期结果用例编号、输入、期望输出、实际输出四列。这看起来笨重但当你修改代码后能半分钟内回归全部用例这在答辩前的赶工之夜能救你命。做编译原理这个项目最大的敌人不是文法复杂而是改了甲处坏了乙处的连锁反应一套顺手的最小测试清单就是后悔药。希望这篇笔记能帮你把那条最经典的分析器路径走顺也希望你在调试时遇到的每一个玄学问题最后都能变成你讲得清、道得明的底气。本文还有配套的精品资源点击获取
