从零手写C++词法分析器与语法分析器：递归下降构建AST实战

简介这份资源是编译原理课程中词法分析与语法分析环节的C实现项目面向计算机专业学生、编译器初学者及对语言处理感兴趣的开发者帮助其把有限自动机、上下文无关文法、抽象语法树等理论落到可运行代码上。压缩包共9个文件约937KB以cpp源码、txt文法与token说明、exe可执行程序及md说明文档为主源码与文档配合便于对照阅读与直接运行验证。目前已有737人学习下载说明其在课程实践与自学场景中具有一定参考价值。项目覆盖词法规则定义、词法单元序列生成、非法字符与数字格式错误处理以及递归下降或LL(1)语法分析、AST构建和语法错误处理等关键环节读者可据此理解编译器前端从源代码到语法树的完整流程并在此基础上扩展语言子集、补充单元测试与文档为后续学习程序分析和代码生成打下实践基础。1. 从零手写词法分析器与语法分析器一份能跑通的 C 实现拆解很多人学编译原理卡在“看得懂 LL(1) 分析表却写不出一行能跑的代码”这一步。这份 C 实现的词法分析器和语法分析器正好补上这个断层——它不是伪代码也不是课堂 PPT 里的片段而是一个能编译、能输入表达式、能输出语法树的完整工程。适合正在做编译原理课程设计的学生也适合想补一补底层解析能力、却被各种生成器工具惯坏了的开发者。词法分析负责把字符流切成 token语法分析负责把 token 流组织成语法树这两步是所有编译器、解释器、甚至配置解析器的地基。下面我按“先跑起来、再拆结构、最后调参数”的顺序把这份资源从头到尾过一遍中间会穿插我实际编译时踩过的坑。2. 词法分析器从字符流到 Token 序列的完整实现2.1 词法分析器的核心任务与状态机设计词法分析器要干的事很明确读入一串字符跳过空白识别出标识符、数字、运算符、界符并给每个 token 打上类型标签。这份实现里词法分析器被封装成一个Lexer类内部维护一个pos指针和当前行号核心是一个nextToken()函数。它没有用正则表达式库而是手写了一个有限状态机——遇到字母就进入标识符状态遇到数字就进入数字状态遇到运算符就查表返回对应类型。为什么不用正则因为手写状态机更容易嵌入错误恢复逻辑比如遇到非法字符时能准确报出列号而不是抛一个笼统的“匹配失败”。常见做法是先用std::isalpha和std::isdigit做分支判断再配合一个关键字表把if、while、return这类保留字从标识符里区分出来。// Lexer.h 片段Token 类型定义与关键字表 enum class TokenType { IDENTIFIER, NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, ASSIGN, SEMICOLON, IF, WHILE, RETURN, END }; struct Token { TokenType type; std::string value; int line; int column; }; // 关键字映射表把保留字从普通标识符里剥离出来 static const std::unordered_mapstd::string, TokenType keywords { {if, TokenType::IF}, {while, TokenType::WHILE}, {return, TokenType::RETURN} };这段代码里Token结构体除了类型和值还带了line和column这是后面报错定位的关键。很多教学实现只存值不存位置结果语法分析报错时只能告诉你“第几个 token 错了”没法映射回源码行。参数上keywords表用unordered_map而不是map因为词法分析是高频操作哈希查找比红黑树快一个量级虽然差别在小型输入上不明显但养成习惯没坏处。2.2 手写 nextToken 的步骤与边界处理nextToken()的执行流程可以拆成四步跳过空白和注释、读取第一个有效字符、根据字符类型进入对应分支、返回构造好的 Token。跳过空白时要注意\r\n和\n的兼容尤其是从 Windows 拷贝的测试文件行号统计容易多算一行。读取数字时这份实现只支持整数没有处理小数点和科学计数法——如果你要扩展得在数字状态里加一个“遇到.就继续读”的分支。Token Lexer::nextToken() { // 1. 跳过空白字符同时更新行号和列号 while (pos input.size() std::isspace(input[pos])) { if (input[pos] \n) { line; column 1; } else { column; } pos; } if (pos input.size()) return {TokenType::END, , line, column}; char ch input[pos]; int startCol column; // 2. 标识符或关键字以字母或下划线开头 if (std::isalpha(ch) || ch _) { std::string ident; while (pos input.size() (std::isalnum(input[pos]) || input[pos] _)) { ident input[pos]; column; } auto it keywords.find(ident); if (it ! keywords.end()) return {it-second, ident, line, startCol}; return {TokenType::IDENTIFIER, ident, line, startCol}; } // 3. 数字连续读取数字字符 if (std::isdigit(ch)) { std::string num; while (pos input.size() std::isdigit(input[pos])) { num input[pos]; column; } return {TokenType::NUMBER, num, line, startCol}; } // 4. 运算符和界符单字符直接映射 pos; column; switch (ch) { case : return {TokenType::PLUS, , line, startCol}; case -: return {TokenType::MINUS, -, line, startCol}; case *: return {TokenType::STAR, *, line, startCol}; case /: return {TokenType::SLASH, /, line, startCol}; case (: return {TokenType::LPAREN, (, line, startCol}; case ): return {TokenType::RPAREN, ), line, startCol}; case : return {TokenType::ASSIGN, , line, startCol}; case ;: return {TokenType::SEMICOLON, ;, line, startCol}; default: throw std::runtime_error(非法字符 std::string(1, ch) 位于第 std::to_string(line) 行第 std::to_string(startCol) 列); } }逻辑上这个函数每次只消费一个 token调用方循环调用直到拿到END。参数说明input是构造函数传入的源码字符串pos是当前读取位置line和column用于错误定位。注意column在跳过空白时递增但在读取多字符 token 时是在循环里递增的这样报错列号指向 token 起始位置而不是结束位置更符合直觉。常见翻车点是忘记在switch前递增pos导致死循环——我第一版就栽在这里调试了半小时才发现指针没动。3. 语法分析器递归下降构建语法树3.1 为什么选递归下降而不是 LL(1) 分析表语法分析器有两种主流实现路径一种是查 LL(1) 分析表、用栈驱动另一种是递归下降每个非终结符写一个函数。这份资源用的是递归下降原因很实际——代码可读性高调试时能直接打断点看调用栈而 LL(1) 分析表在遇到左递归时需要额外改写文法对课程设计来说反而绕远了。递归下降的核心思想是为文法里每个非终结符写一个parseXxx()函数函数内部根据当前 token 决定走哪条产生式。比如表达式文法Expr - Term (( | -) Term)*对应的函数就是先解析一个Term然后循环看下一个 token 是不是或-是就继续解析Term并构造二元节点。这种写法天然支持运算符优先级只要把优先级低的规则放在外层函数、优先级高的放在内层函数就行。3.2 AST 节点定义与 parseExpression 实现语法树的节点用ASTNode结构体表示包含节点类型、值、左右子节点。表达式解析是语法分析里最核心的部分因为它涉及优先级和结合性。这份实现把表达式分成三层parseExpression处理加减parseTerm处理乘除parseFactor处理括号和数字/标识符。// ASTNode 定义支持二元运算、数字、标识符 struct ASTNode { std::string type; // BinaryOp, Number, Identifier std::string value; // 运算符或字面量值 std::unique_ptrASTNode left; std::unique_ptrASTNode right; }; // 解析加减表达式左结合优先级低于乘除 std::unique_ptrASTNode Parser::parseExpression() { auto left parseTerm(); // 先解析一个更高优先级的项 while (current.type TokenType::PLUS || current.type TokenType::MINUS) { std::string op current.value; advance(); // 消费运算符 auto right parseTerm(); auto node std::make_uniqueASTNode(); node-type BinaryOp; node-value op; node-left std::move(left); node-right std::move(right); left std::move(node); // 左结合新节点成为下一轮的左操作数 } return left; } // 解析乘除表达式优先级高于加减 std::unique_ptrASTNode Parser::parseTerm() { auto left parseFactor(); while (current.type TokenType::STAR || current.type TokenType::SLASH) { std::string op current.value; advance(); auto right parseFactor(); auto node std::make_uniqueASTNode(); node-type BinaryOp; node-value op; node-left std::move(left); node-right std::move(right); left std::move(node); } return left; } // 解析因子数字、标识符或括号表达式 std::unique_ptrASTNode Parser::parseFactor() { if (current.type TokenType::NUMBER) { auto node std::make_uniqueASTNode(); node-type Number; node-value current.value; advance(); return node; } if (current.type TokenType::LPAREN) { advance(); auto node parseExpression(); // 递归解析括号内表达式 expect(TokenType::RPAREN); // 强制匹配右括号 return node; } throw std::runtime_error(语法错误期望数字或 (实际得到 current.value ); }这段代码里advance()负责从词法分析器取下一个 token 并更新current。parseExpression和parseTerm的结构几乎一样区别只在判断的 token 类型不同——这正是递归下降的优雅之处优先级层级直接映射到函数调用层级。参数上left用std::unique_ptr管理避免手动deletestd::move转移所有权防止悬空指针。常见错误是忘记在循环里更新left导致只解析了第一个操作数就返回结果123被解析成(12)丢掉了3。4. 避坑与排查编译、运行、扩展时的五个血泪教训4.1 现象编译报错 “unique_ptr 不可复制”原因ASTNode里用了std::unique_ptr作为子节点但某处代码试图按值传递或拷贝节点。解决所有涉及节点传递的函数参数用std::unique_ptrASTNode或直接std::move返回值用std::unique_ptr而不是裸指针。如果确实需要共享改用std::shared_ptr但语法树是严格的树形结构unique_ptr更合适。4.2 现象输入12*3输出结果却是(12)*3原因parseExpression里先调用了parseTerm但parseTerm内部又调用了parseFactor层级是对的问题出在parseExpression的循环条件写成了while (current.type PLUS || current.type MINUS || current.type STAR)把乘除也吞进来了。解决严格按文法分层parseExpression只处理加减乘除交给parseTerm不要越级判断。4.3 现象词法分析器遇到文件末尾死循环原因nextToken()在pos input.size()时返回了END但调用方advance()没有检查END就继续调用导致反复返回END而循环不退出。解决在advance()里加一个判断如果当前已经是END就不再前进或者在语法分析主循环里用while (current.type ! END)控制。4.4 现象行号统计在 Windows 换行符下多算一行原因\r\n被当成两个字符\n触发一次行号递增\r又被isspace跳过但没触发递增看似没问题但如果代码里先判断\r再判断\n就会多算。解决统一在跳过空白时只认\n作为换行标志\r直接忽略。或者读入文件后用std::getline按行处理从根上避开这个问题。4.5 现象扩展支持浮点数后1.2.3被解析成合法数字原因数字状态机里遇到.就继续读但没有限制小数点只能出现一次。解决加一个bool hasDot标志第一次遇到.时置位第二次遇到就报错或停止读取。这类边界在课程设计里经常被忽略但实际解析配置文件时一个非法数字可能导致整个解析器崩溃。5. 进阶技巧用 AST 求值验证解析正确性写完词法分析和语法分析怎么确认它真的对了最直接的办法是给 AST 加一个evaluate()函数把语法树算成一个数值然后跟手算结果对比。这个技巧我每次写完解析器都会用比盯着 token 序列看靠谱得多。// 对 AST 递归求值只支持整数四则运算 int evaluate(const std::unique_ptrASTNode node) { if (node-type Number) { return std::stoi(node-value); // 字符串转整数 } if (node-type BinaryOp) { int leftVal evaluate(node-left); int rightVal evaluate(node-right); if (node-value ) return leftVal rightVal; if (node-value -) return leftVal - rightVal; if (node-value *) return leftVal * rightVal; if (node-value /) { if (rightVal 0) throw std::runtime_error(除零错误); return leftVal / rightVal; } } throw std::runtime_error(未知节点类型 node-type); }这个函数递归遍历整棵树遇到数字节点就转成int返回遇到二元操作节点就分别求左右子树的值再按运算符计算。参数上std::stoi在遇到非数字字符串时会抛std::invalid_argument所以词法分析阶段必须保证Number节点的值一定是纯数字。除零判断放在这里而不是词法阶段因为词法阶段不知道上下文只有求值时才能确定分母是否为零。验证时我一般准备一组测试用例12*3期望 7(12)*3期望 910/2-3期望 22*34*5期望 26。如果某个用例挂了先看 AST 结构对不对——可以在evaluate里加一行打印节点类型和值或者单独写一个printAST函数做前序遍历。常见问题是括号解析后忘记expect(RPAREN)导致(12这种不匹配的输入被静默接受求值时才暴露成奇怪的结果。另一个进阶方向是把 AST 转成后缀表达式输出或者生成三地址码。这些扩展不需要改词法分析器只需要在语法分析构造节点时多存一些信息。我习惯在每次扩展文法后先把所有旧测试用例跑一遍确认没有回归再加新用例。从那以后我每次写完解析器都强制走一遍“词法输出 → AST 打印 → 求值对比”三步验证少一步都可能留下隐蔽的优先级 bug。希望这份拆解能帮你把编译原理的这两块硬骨头啃下来资源里的代码可以直接编译运行改一改就能当课程设计的底稿。本文还有配套的精品资源点击获取