语法分析器)
简介：这是一份面向计算机专业学生与编译器爱好者的编译原理前端实践资源，聚焦词法分析与语法分析两大核心模块的C++实现。资源包共9个文件，以cpp源码、txt文法与token说明、exe可执行程序及md说明文档为主，压缩包约937KB，体积轻便，便于直接运行验证与阅读源码。内容围绕有限自动机构建词法分析器、基于上下文无关文法与递归下降或LL(1)方法实现语法分析器，并涉及词法错误与语法错误的处理思路，可帮助读者理解从源代码到词法单元序列再到抽象语法树（AST）的完整流程。已有736人学习下载，适合作为课程实验、编译原理课程设计或自学练手项目，读者可借助源码与可执行文件对照调试，掌握分析器设计细节，为后续学习语义分析、代码生成及程序分析打下基础。
1. 编译原理课设绕不开的坎：从零手写词法分析器和语法分析器
很多人学编译原理，教材翻到第二章就开始发懵——正则表达式、NFA、DFA、LL(1) 分析表，每个概念单看都能理解，但一到课程设计要交一个能跑的完整程序，就不知道从哪下手。这份 C++ 实现的词法分析器和语法分析器源码包，解决的正是这个断层：它把教材里那些抽象的状态转移和产生式推导，落成了一份可以直接编译、可以断点调试、可以改文法规则的工程代码。适合正在做编译原理实验的本科生，也适合想重新捡起编译器前端基础的 C++ 开发者。你拿到手就能看到词法分析怎么把字符流切成 token 序列，语法分析怎么用分析栈一步步推导出语法树，而不是对着 PPT 上的伪代码干瞪眼。
2. 词法分析器拆解：正则到 DFA 的工程化落地
2.1 为什么词法分析要单独抽一层
很多同学第一次做课设，喜欢把词法分析和语法分析揉在一个函数里，边读字符边判断语法。这种写法在小规模输入下能跑通，但一旦文法规则超过十条，代码就会变成一团乱麻。常见做法是把词法分析独立成一个Lexer类，对外只暴露一个getNextToken()接口，语法分析器每次需要下一个 token 时调用一次。这样做的核心好处是职责分离：词法层只关心“这个字符序列是什么类型的词”，语法层只关心“这个 token 序列符不符合文法”。
从理论上看，词法分析对应的是正则语言，用有限自动机就能完整描述。工程上通常走这条路径：先用手写或工具生成的方式，把每条 token 规则写成正则表达式，再转换成 NFA，最后确定化成 DFA。但实际课设里，更常见的做法是直接写一个状态转移的 switch-case 结构，本质上就是一个手工构造的 DFA。这份源码走的就是这条路，代码结构清晰，适合逐行对照教材理解。
2.2 核心数据结构与状态转移
词法分析器的核心是一个字符指针和一个状态变量。每读入一个字符，根据当前状态和字符类型决定下一步跳转到哪个状态。下面这段代码展示了 token 结构体和词法分析器的主循环骨架：
// token 结构体：类型 + 原始字符串 + 行号 struct Token { TokenType type; // 枚举类型：ID、NUM、OP、KEYWORD 等 std::string value; // 原始词素，如 "int"、"123"、"+" int line; // 所在行号，报错时定位用 }; class Lexer { public: Lexer(const std::string& src) : source(src), pos(0), line(1) {} Token getNextToken() { skipWhitespaceAndComments(); // 跳过空白和注释 if (pos >= source.size()) return {TokenType::END, "", line}; char ch = source[pos]; if (isalpha(ch)) return parseIdentifierOrKeyword(); if (isdigit(ch)) return parseNumber(); if (isOperator(ch)) return parseOperator(); // 无法识别的字符，报错并跳过 throw LexerError("Unexpected character: " + std::string(1, ch), line); } private: std::string source; size_t pos; int line; };这段代码的逻辑很直白：每次取 token 前先跳过空白和注释，然后根据当前字符的首字符类型分派到不同的解析函数。parseIdentifierOrKeyword会一直读字母和数字，读完后再查关键字表，决定是标识符还是保留字。parseNumber处理整数和小数，parseOperator处理单字符和双字符运算符（比如==和=要区分开）。
参数方面，source是完整的源代码字符串，pos是当前读取位置，line用于报错定位。这里有个容易翻车的地方：行号更新必须放在跳过换行符的逻辑里，而不是在getNextToken开头统一加，否则多行注释里的换行会导致行号错乱。
2.3 关键字表与符号表的处理差异
关键字和标识符在词法层面长得一模一样，都是字母开头、字母数字下划线组成。区别在于关键字是语言预留的，不能作为变量名。常见做法是维护一个std::unordered_set<std::string>存所有关键字，解析完一个单词后查一次表：
static const std::unordered_set<std::string> keywords = { "int", "float", "if", "else", "while", "return", "void" }; Token Lexer::parseIdentifierOrKeyword() { size_t start = pos; while (pos < source.size() && (isalnum(source[pos]) || source[pos] == '_')) { pos++; } std::string word = source.substr(start, pos - start); if (keywords.count(word)) { return {TokenType::KEYWORD, word, line}; } return {TokenType::ID, word, line}; }符号表则是另一回事。词法分析阶段通常只负责识别标识符，不负责管理作用域和类型信息。符号表的构建一般放在语法分析或语义分析阶段。有些课设要求把符号表操作塞进词法分析器，这会导致职责混乱，后期改文法时非常痛苦。我一般会建议把符号表单独抽成一个类，由语法分析器在归约产生式时调用插入和查找。
3. 语法分析器拆解：LL(1) 分析表的构造与驱动
3.1 选 LL(1) 还是 LR：课设场景下的取舍
语法分析有两大家族：自顶向下的 LL 分析和自底向上的 LR 分析。LL(1) 的优点是分析表构造直观，手写递归下降分析器非常容易调试，适合文法不太复杂的课设题目。LR 分析能力更强，能处理左递归文法，但分析表构造和冲突处理对本科生来说门槛偏高。
这份源码采用的是 LL(1) 预测分析法，核心思路是：对每个非终结符和每个终结符，查表决定用哪条产生式展开。如果表中某个格子有多条产生式，说明文法不是 LL(1) 的，需要提取左公因子或消除左递归。课设里常见的表达式文法、if-else 文法，经过适当改写后基本都能满足 LL(1) 条件。
3.2 FIRST 集和 FOLLOW 集的代码实现
构造分析表之前，必须先算 FIRST 集和 FOLLOW 集。FIRST(A) 是从 A 出发能推导出的所有可能的开头终结符集合，FOLLOW(A) 是 A 后面可能紧跟的终结符集合。这两个集合的算法在教材里写得很清楚，但手写代码时容易在“空产生式”的处理上出错。
// 计算 FIRST 集：迭代直到不再变化 void Grammar::computeFirst() { bool changed = true; while (changed) { changed = false; for (auto& prod : productions) { std::string lhs = prod.lhs; auto& rhs = prod.rhs; // 如果右部第一个符号是终结符，直接加入 FIRST if (isTerminal(rhs[0])) { if (first[lhs].insert(rhs[0]).second) changed = true; } else { // 非终结符：把它的 FIRST 集（去掉 epsilon）加入当前 FIRST for (char sym : first[rhs[0]]) { if (sym != 'e') { if (first[lhs].insert(sym).second) changed = true; } } // 如果 rhs[0] 能推导出 epsilon，继续看下一个符号 if (first[rhs[0]].count('e')) { // ... 处理后续符号，逻辑同上 } } } } }这段代码的关键在于changed标志：FIRST 集的计算是一个不动点迭代过程，必须反复扫描所有产生式，直到某一轮没有任何集合发生变化才能停止。很多同学写的时候只扫一遍就结束，导致嵌套非终结符的 FIRST 集不完整，后面分析表就会出现莫名其妙的空缺。
FOLLOW 集的计算规则稍微复杂一些：起始符号的 FOLLOW 集包含结束符$；对于产生式A -> αBβ，把 FIRST(β) 去掉 epsilon 后加入 FOLLOW(B)；如果 β 能推导出 epsilon，把 FOLLOW(A) 加入 FOLLOW(B)。实现时同样需要迭代到不动点。
3.3 预测分析表的构造与驱动循环
有了 FIRST 和 FOLLOW，构造分析表就是填格子：对每条产生式A -> α，对 FIRST(α) 中每个终结符 a，把A -> α填入table[A][a]；如果 α 能推导出 epsilon，则对 FOLLOW(A) 中每个终结符 b，把A -> α填入table[A][b]。
驱动循环用一个栈来模拟推导过程：
bool Parser::parse(const std::vector<Token>& tokens) { std::stack<char> stk; stk.push('$'); stk.push(startSymbol); // 起始非终结符入栈 size_t idx = 0; while (!stk.empty()) { char top = stk.top(); char cur = tokens[idx].type; // 当前输入 token 对应的终结符 if (top == '$' && cur == '$') return true; // 成功 if (isTerminal(top)) { if (top == cur) { stk.pop(); idx++; } // 匹配，同时弹出和前进 else return error("Expected " + top); } else { auto prod = table[top][cur]; if (prod.empty()) return error("No production for " + top); stk.pop(); // 逆序压栈，保证左部先展开 for (int i = prod.rhs.size() - 1; i >= 0; i--) { if (prod.rhs[i] != 'e') stk.push(prod.rhs[i]); } } } return false; }这里有个细节：产生式右部压栈时必须逆序，因为栈是后进先出，逆序压入才能保证最左边的符号最先被处理。另外，epsilon 产生式不需要压入任何符号，直接跳过即可。驱动循环的每一步都可以打印当前栈内容和剩余输入，方便调试时观察推导过程。
4. 避坑与排查：课设里最容易翻车的五个地方
4.1 现象：词法分析把==识别成两个=
原因：parseOperator里只判断了单字符，没有向前看一位。解决：遇到=、<、>、!这类可能是双字符运算符的首字符时，先检查pos+1位置的字符，能组成双字符运算符就一起消费掉。
4.2 现象：语法分析表出现多重入口，程序随机选一条导致解析结果不稳定
原因：文法存在左公因子或左递归，不满足 LL(1) 条件。解决：提取左公因子，消除左递归。比如A -> aB | aC改写成A -> aA'，A' -> B | C。改完后重新计算 FIRST 和 FOLLOW，确认表中每个格子最多一条产生式。
4.3 现象：输入合法表达式却报“unexpected end of input”
原因：词法分析器在文件末尾没有返回 END token，或者语法分析器的结束符$没有和 END token 正确对应。解决：确保getNextToken在pos >= source.size()时返回TokenType::END，并在语法分析器里把 END 映射为$。
4.4 现象：嵌套 if-else 解析时 else 匹配到了错误的 if
原因：经典的悬挂 else 问题，文法有歧义。解决：在文法层面规定 else 与最近的未匹配 if 结合，通常改写成stmt -> matched | unmatched的形式，让语法结构强制唯一解析。
4.5 现象：程序在 Windows 上编译通过，换到 Linux 报错
原因：源码里用了#include <windows.h>或_getch()之类的平台相关调用。解决：把平台相关代码抽到单独文件，用宏隔离；或者直接去掉非必要依赖，保持纯标准 C++。课设代码建议只依赖 STL，跨平台无痛编译。
5. 进阶技巧：用递归下降替代分析表，以及如何验证解析正确性
LL(1) 分析表虽然直观，但写起来代码量大，调试时对着二维表找产生式也累。实际课设里，如果文法已经消除了左递归，我更倾向于直接写递归下降分析器——每个非终结符对应一个函数，函数体里根据当前 token 决定走哪条分支。代码量通常比分析表方案少三分之一，而且断点调试时调用栈一目了然。
递归下降的核心写法：
// expr -> term { (+|-) term } void Parser::parseExpr() { parseTerm(); while (currentToken.type == TokenType::OP && (currentToken.value == "+" || currentToken.value == "-")) { advance(); // 消费运算符 parseTerm(); // 递归解析右操作数 } }这段代码对应表达式文法expr -> term { (+|-) term }，用循环处理左递归的等价形式。advance()负责调用词法分析器取下一个 token。每个非终结符函数只做自己那一层的事，遇到不属于自己的 token 就返回，由上层决定怎么处理。
验证解析是否正确，最直接的办法是让语法分析器在归约或展开时输出推导过程。比如每展开一条产生式就打印A -> α，最后看输出的序列能不能还原出原始输入。另一个办法是构造语法树，然后对树做后序遍历，看能不能生成等价的中缀表达式。我一般会准备一组测试用例：合法表达式、缺少右括号、多余运算符、空输入、嵌套括号，逐个跑一遍，确认报错信息能定位到具体行号和 token。
从那以后我每次写完语法分析器，都强制走一遍“打印推导序列 + 五组边界用例”的流程，确认没有玄学报错才提交。希望帮到你。
本文还有配套的精品资源，点击获取
