简介这份编译原理语法分析实验资源面向正在学习编译原理、需要完成递归子程序法语法分析作业的高校学生与自学者重点解决在已有词法分析基础上识别各类语法成分、并按自动评测要求组织输出结果的问题。压缩包为zip格式共2个文件约17KB包含1份doc实验说明与1份cpp实现代码便于对照文法规则理解递归下降程序结构。目前已有6110人学习或下载具备较好的参考价值。代码在CG实验平台满分通过读者可据此了解如何对文法定义的全部语法成分逐一分析掌握按单词识别顺序逐行输出词法信息、在指定语法成分结束前另起一行输出“常量说明”等标记的实现思路并借鉴testfile.txt与output.txt的输入输出组织方式快速排查递归子程序分析中的常见问题适合课程实验提交前对照复盘。1. 编译原理课设里的语法分析为什么手写 parser 反而更快出结果编译原理的语法分析实验不少人第一反应是找个 LR 分析表生成器结果先被状态机构造和冲突处理绕晕实验报告写了三页还没跑通一个int a 1 2 * 3;。这份 C 版的实现走的是另一条路手写词法扫描加递归下降把一段 mini-C 源码直接解析成能打印的抽象语法树出错时给出行列号和可读的诊断。它适合三类人课程实验要交可运行代码的学生、想把一个轻量 parser 塞进自己小工具的开发者、以及只想知道「编译原理落到代码里长什么样」的自学者。整包不依赖第三方库一份 CMakeLists 加十几个源文件就能编出来改起来也没有黑匣子。2. 骨架与选型词法、语法、AST 三层怎么切递归下降还是表驱动拿到源码包先不要急着敲cmake先花十分钟看目录怎么切分。切分方式决定了后面加语法特性时疼不疼如果词法、语法、AST 节点全揉在main.cpp里加一条for语句要改五个地方如果按职责分好层加for只是多一个parseFor()和一个节点类型。这个项目的目录属于后者切得比较克制没有多余的抽象层也没有为了「工程化」硬塞设计模式。2.1 目录结构词法、语法、AST、诊断各自独立syntax-lab/ ├── CMakeLists.txt ├── include/ │ ├── token.h # TokenType 枚举与 Token 结构 │ ├── scanner.h # 字符流 - Token 流 │ ├── ast.h # AST 节点与 dump │ ├── parser.h # 递归下降的每个非终结符一个方法 │ └── diag.h # 错误收集行、列、级别、消息 ├── src/ │ ├── scanner.cpp │ ├── ast.cpp │ ├── parser.cpp │ ├── diag.cpp │ └── main.cpp # 命令行入口读文件、跑分析、按开关输出 └── tests/ ├── ok_basic.c # 正常用例 ├── ok_nested.c # 嵌套块与 if-else 悬挂 ├── err_missing_semi.c ├── err_bad_expr.c └── run_tests.sh文件职责二次开发时改动频率token.h定义所有记号的类型低加关键字时动一次scanner.cpp字符到记号的扫描、行列号维护中加运算符或字面量时改parser.cpp语法规则的具体落地高加语句类型必改ast.h / ast.cpp节点结构与树打印中加节点种类时改diag.cpp错误汇总与格式化低这个切法有一个隐含好处scanner只依赖token.hparser只依赖scanner和ast谁都不认识main。想单独测词法写个十行的小程序喂字符串进去就行不用把整个工程拖进来。2.2 为什么手写递归下降而不是查表驱动LL(1) 表驱动和 LR 表驱动都更「像编译原理课本」但在这个场景里不一定划算。表驱动需要额外写一个构造 FIRST/FOLLOW 集的程序再写一个分析表驱动引擎调 bug 时面对的是「状态 17 遇到;该走哪条产生式」这种问题断点进去也看不出业务语义。递归下降的每个函数名就是文法里的非终结符parseIf()里出问题你一眼就知道是 if 语句的哪一段错了。维度递归下降表驱动 LL(1)/LR上手成本低照着文法抄函数高先要把表算对调试体验断点停在具体规则上断在状态转移需要对照表看文法限制不能有左递归需要提取左公因子LL(1) 同理LR 宽松些扩展新语句加一个函数加一个分支改文法、重算表、可能引入冲突教学价值规则与代码一一对应更能体现自动机思想我的做法通常是先用递归下降把整条链路跑通让 AST 能正确打出来再考虑要不要为了实验报告补一个 FIRST/FOLLOW 计算器做对照。两套结果一致报告里的表也就有了依据。2.3 文法先改再写消除左递归是动手前的第一件事原始表达式文法里最常见的是这种写法Expr - Expr Term | Expr - Term | Term Term - Term * Factor | Term / Factor | Factor Factor- NUMBER | IDENT | ( Expr )照抄成代码就是parseExpr()第一行调parseExpr()跑起来直接栈溢出。正确做法是改写成右递归或者直接用循环项目里采用的是循环版本文法整理如下Program - StmtList END StmtList - Stmt StmtList | ε Stmt - Decl | Assign | If | While | Block Decl - int IDENT ( Expr)? ; Assign - IDENT Expr ; If - if ( Expr ) Stmt (else Stmt)? While - while ( Expr ) Stmt Block - { StmtList } Expr - Rel Rel - Add ((|||||!) Add)? Add - Mul ((|-) Mul)* Mul - Unary ((*|/) Unary)* Unary - - Unary | Primary Primary - NUMBER | IDENT | ( Expr )配套的 FIRST 集在动手前算一遍能省掉后面大量「明明文法写对了却解析错」的怀疑非终结符FIRST 集Programintifwhile{IDENTENDStmtintifwhile{IDENTExpr/Rel/Add/Mul-NUMBERIDENT(PrimaryNUMBERIDENT(注意Stmt的 FIRST 集里IDENT会同时出现在声明和赋值两个候选式里吗不会声明一定以int开头赋值一定以IDENT开头两者不冲突所以这里不需要提取左公因子。真正需要多看一眼的是悬挂 elseif (a) if (b) x 1; else x 2;里 else 归谁递归下降天然是「就近匹配」跟 C 语言一致这点在写parseIf()时不用特意处理但要在测试用例里固定下来。提示文法的 FIRST 集不必手工算完整先算Stmt和Expr这两层就够用了大部分歧义都出在这两处。3. 核心链路拆解一个 12*3 从字符流走到 AST 的全过程这条链路上有三个关键节点Token 的切分、表达式优先级的落地、语法树的构造与错误恢复。三段代码加起来不到三百行但每一段都有一两个容易写错的地方。下面按数据流动的顺序拆。3.1 Token 与 Scanner最长匹配是唯一准则Token 结构本身没什么花头关键是它要带上行列号否则后面报错只能告诉用户「第 N 个 token 有问题」这在几十行的测试文件里还能数换成几百行就没法用了。// include/token.h #pragma once #include string enum class TokenType { KW_INT, KW_IF, KW_ELSE, KW_WHILE, // 关键字 IDENT, NUMBER, // 标识符与数字字面量 PLUS, MINUS, STAR, SLASH, ASSIGN, EQ, NE, LT, LE, GT, GE, LPAREN, RPAREN, LBRACE, RBRACE, SEMI, COMMA, END, ERROR }; struct Token { TokenType type; std::string lexeme; int line 1; int col 1; };扫描器的主循环只做一件事跳过空白和注释然后按首字符分派。// src/scanner.cpp Token Scanner::next() { skipTrivia(); // 空格、换行、// 与 /* */ 全在这里吃掉 if (atEnd()) return Token{TokenType::END, eof, line_, col_}; const int startLine line_, startCol col_; char c peek(); if (std::isdigit(static_castunsigned char(c))) return scanNumber(startLine, startCol); if (std::isalpha(static_castunsigned char(c)) || c _) return scanIdentOrKeyword(startLine, startCol); advance(); // 先消费当前字符再判断双字符运算符 switch (c) { case : return Token{TokenType::PLUS, , startLine, startCol}; case -: return Token{TokenType::MINUS, -, startLine, startCol}; case *: return Token{TokenType::STAR, *, startLine, startCol}; case /: return Token{TokenType::SLASH, /, startLine, startCol}; case (: return Token{TokenType::LPAREN,(, startLine, startCol}; case ): return Token{TokenType::RPAREN,), startLine, startCol}; case {: return Token{TokenType::LBRACE,{, startLine, startCol}; case }: return Token{TokenType::RBRACE,}, startLine, startCol}; case ;: return Token{TokenType::SEMI, ;, startLine, startCol}; case ,: return Token{TokenType::COMMA, ,, startLine, startCol}; case : if (peek() ) { advance(); return Token{TokenType::EQ, , startLine, startCol}; } return Token{TokenType::ASSIGN, , startLine, startCol}; case : if (peek() ) { advance(); return Token{TokenType::LE, , startLine, startCol}; } return Token{TokenType::LT, , startLine, startCol}; case : if (peek() ) { advance(); return Token{TokenType::GE, , startLine, startCol}; } return Token{TokenType::GT, , startLine, startCol}; case !: if (peek() ) { advance(); return Token{TokenType::NE, !, startLine, startCol}; } return Token{TokenType::ERROR, !, startLine, startCol}; default: return Token{TokenType::ERROR, std::string(1, c), startLine, startCol}; } }逻辑上有两点必须讲清楚。第一advance()只负责推进指针并维护行列号不做类型判断这样所有位置信息只有一个更新点不会出现「某些字符跳过了行号统计」的问题。第二双字符运算符必须先看第二个字符再决定和、和分属不同分支写反了会让a b被切成两个赋值。标识符和关键字的处理靠最长匹配先一次性扫完整个词再查关键字表Token Scanner::scanIdentOrKeyword(int l, int c) { std::string s; while (!atEnd() (std::isalnum(static_castunsigned char(peek())) || peek() _)) s.push_back(advance()); // 一次扫到底中途不判断关键字 static const std::unordered_mapstd::string, TokenType kKeywords { {int, TokenType::KW_INT}, {if, TokenType::KW_IF}, {else, TokenType::KW_ELSE}, {while, TokenType::KW_WHILE} }; auto it kKeywords.find(s); return Token{it kKeywords.end() ? TokenType::IDENT : it-second, s, l, c}; }这个顺序不能反。如果边扫边判断「当前前缀是不是关键字」intx会被切成一个int加一个x后面语法分析就会莫名其妙地报「期望标识符」。同理scanNumber()扫完数字后要再检查下一个字符是不是字母或下划线是的话最好直接报一个ERROR而不是默默切成123和abc。3.2 递归下降主体parseExpr 怎么吃掉 12*3表达式是整份代码里最容易写错的部分因为它涉及优先级和结合性。项目采用分层下降从优先级最低的关系运算开始一层层往下调每层内部用while循环吃掉同级的连续运算。// src/parser.cpp —— 优先级从低到高逐层下降 std::unique_ptrNode Parser::parseExpr() { return parseRel(); } std::unique_ptrNode Parser::parseRel() { auto lhs parseAdd(); while (check(TokenType::LT) || check(TokenType::LE) || check(TokenType::GT) || check(TokenType::GE) || check(TokenType::EQ) || check(TokenType::NE)) { Token op advance(); auto rhs parseAdd(); lhs makeBinary(op.lexeme, std::move(lhs), std::move(rhs), op.line); } return lhs; } std::unique_ptrNode Parser::parseAdd() { auto lhs parseMul(); while (check(TokenType::PLUS) || check(TokenType::MINUS)) { Token op advance(); auto rhs parseMul(); // 右侧仍然从更高优先级开始 lhs makeBinary(op.lexeme, std::move(lhs), std::move(rhs), op.line); } return lhs; } std::unique_ptrNode Parser::parseMul() { auto lhs parseUnary(); while (check(TokenType::STAR) || check(TokenType::SLASH)) { Token op advance(); auto rhs parseUnary(); lhs makeBinary(op.lexeme, std::move(lhs), std::move(rhs), op.line); } return lhs; } std::unique_ptrNode Parser::parseUnary() { if (check(TokenType::MINUS)) { // 一元负号右结合 Token op advance(); return makeNode(Unary, op.lexeme, op.line, parseUnary()); } return parsePrimary(); } std::unique_ptrNode Parser::parsePrimary() { if (check(TokenType::NUMBER) || check(TokenType::IDENT)) { Token t advance(); return makeNode(t.type TokenType::NUMBER ? Number : Ident, t.lexeme, t.line); } if (check(TokenType::LPAREN)) { advance(); auto inner parseExpr(); expect(TokenType::RPAREN, 缺少右括号 )); return inner; } return errorExpr(期望一个表达式); }这段代码能正确处理1 2 * 3parseAdd先拿到左操作数1看到就把右边交给parseMulparseMul会一路把2 * 3收成一个子树再返回最终结构是(1, *(2, 3))而不是*((1, 2), 3)。左结合也是靠while循环自然得到的——每轮把已解析的lhs作为新的左子树包进去a - b - c就会变成-( -(a, b), c )跟数学约定一致。语句层同样是一个分派函数加一堆具体规则std::unique_ptrNode Parser::parseStmt() { switch (peek().type) { case TokenType::KW_INT: return parseDecl(); case TokenType::KW_IF: return parseIf(); case TokenType::KW_WHILE: return parseWhile(); case TokenType::LBRACE: return parseBlock(); case TokenType::IDENT: return parseAssign(); // 变量名开头只可能是赋值 case TokenType::SEMI: advance(); return makeNode(Empty, , prev().line); default: return errorStmt(期望一条语句); } }parseIf()里有一处值得留意解析完 then 分支后要先看有没有else有就继续解析没有就直接返回。悬挂 else 的归属由调用顺序决定if (a) if (b) x 1; else x 2;中内层parseIf()会先看到else并把它吃掉得到的语义是「就近匹配」与常见语言一致。3.3 AST 节点设计与错误恢复别让一个分号毁掉整趟分析节点结构用unique_ptr组合子节点避免手写析构也不用担心深拷贝// include/ast.h #pragma once #include memory #include string #include vector struct Node { std::string kind; // Program VarDecl Binary If ... std::string value; // 变量名、字面量、运算符 int line 0; std::vectorstd::unique_ptrNode kids; Node(std::string k, std::string v {}, int ln 0) : kind(std::move(k)), value(std::move(v)), line(ln) {} }; std::unique_ptrNode makeNode(std::string kind, std::string value {}, int line 0); std::unique_ptrNode makeBinary(std::string op, std::unique_ptrNode lhs, std::unique_ptrNode rhs, int line); void dump(const Node* n, std::ostream os, const std::string prefix , bool last true);kind用英文短名是有意为之一是打印对齐好看二是后面接 JSON 或 DOT 时不用做转义三是避免不同终端编码下出现乱码。错误恢复采用 panic mode出错后不抛异常而是丢 token 直到看见语句边界然后继续往下解析这样一次运行能报出多个错误。// src/parser.cpp void Parser::synchronize() { while (!check(TokenType::END)) { if (prev().type TokenType::SEMI) return; // 上一句刚好收尾可以直接续上 switch (peek().type) { case TokenType::KW_INT: case TokenType::KW_IF: case TokenType::KW_WHILE: case TokenType::RBRACE: return; // 遇到新语句或块结束重新对齐 default: advance(); } } } std::unique_ptrNode Parser::errorStmt(const std::string msg) { diag_.error(peek().line, peek().col, msg 实际读到 peek().lexeme ); synchronize(); return makeNode(ErrorStmt, msg, peek().line); // 占位节点保证上层拿到非空指针 }返回占位节点这一步不能省。如果出错时直接return nullptr上面parseBlock()往kids里push_back一个空指针打印 AST 时就是段错误排查起来比语法错误本身还费劲。注意synchronize()里先判断prev()再判断peek()顺序反了会导致x 1; 这种输入在分号处多吞一个 token。4. 跑起来CMake 构建、命令行开关与回归用例代码结构清楚之后跑通只需要三步配构建、给输入、看输出。这份工程的构建脚本很薄没有引入任何第三方依赖所以不管是在 Linux 还是 Windows 上问题基本都出在编译器标准和路径上不在依赖上。4.1 两条构建路径CMake 与单文件 gcmake_minimum_required(VERSION 3.16) project(syntax_lab CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_executable(syntax-lab src/main.cpp src/scanner.cpp src/parser.cpp src/ast.cpp src/diag.cpp ) target_include_directories(syntax-lab PRIVATE include) if (MSVC) target_compile_options(syntax-lab PRIVATE /W4) else() target_compile_options(syntax-lab PRIVATE -Wall -Wextra) endif()构建命令就两行第二行跑完能在build/下拿到可执行文件cmake -S . -B build -DCMAKE_BUILD_TYPEDebug cmake --build build -j如果只是想快速验证某个函数不想走 CMake直接一条命令也能编g -stdc17 -Wall -Wextra -Iinclude src/*.cpp -o syntax-lab用-stdc17是因为代码里用了std::unique_ptr、enum class和结构化绑定用-stdc11会在auto [a, b]这类地方报错。Debug 类型建议保留递归下降出错时栈帧信息很有用。4.2 命令行开关与一次完整运行main.cpp的入口很朴素读文件、建 Scanner、建 Parser、按开关输出。./build/syntax-lab tests/ok_basic.c --tokens --dump-ast--tokens打印词法结果--dump-ast打印语法树两个都不给时只做分析并输出错误数。写一个最小用例int a 1 2 * 3; int b; b a - 4; if (b 0) { b b * 2; } else { b 0; }期望的树形输出大致是这样缩进层级直接反映嵌套关系Program ├─ VarDecl a │ └─ Binary() │ ├─ Number 1 │ └─ Binary(*) │ ├─ Number 2 │ └─ Number 3 ├─ VarDecl b ├─ Assign b │ └─ Binary(-) │ ├─ Ident a │ └─ Number 4 └─ If ├─ Binary() │ ├─ Ident b │ └─ Number 0 ├─ Block │ └─ Assign b │ └─ Binary(*) │ ├─ Ident b │ └─ Number 2 └─ Block └─ Assign b └─ Number 0看到Binary(*)在Binary()的右子树里就说明优先级处理对了看到Assign的两个孩子分别是Ident b和表达式就说明语句层没把赋值当成表达式。4.3 回归用例把「看着对」变成「比对得出来」手工看树形输出只能覆盖几条用例改成脚本比对才靠得住。tests/run_tests.sh的思路很简单正常用例必须退出码为 0错误用例必须退出码非 0。#!/usr/bin/env bash # tests/run_tests.sh —— 正常用例要过错误用例必须报错 set -u BIN./build/syntax-lab fail0 for f in tests/ok_*.c; do if ! $BIN $f --dump-ast /dev/null 21; then echo FAIL(should pass): $f; fail1 fi done for f in tests/err_*.c; do if $BIN $f --dump-ast /dev/null 21; then echo FAIL(should fail): $f; fail1 fi done [ $fail -eq 0 ] echo all cases passed exit $fail这套脚本的价值在于锁住错误恢复行为。加了新语句之后很容易出现「错误用例不再报错」的退化人眼看树是看不出来的脚本一跑就露馅。想让比对更严格可以把--dump-ast的输出重定向到文件跟tests/expected/下的基线做diff第一次跑的时候人工确认基线之后就不用再看了。5. 避坑与排查五类把实验拖到凌晨的问题下面这几条基本覆盖了语法分析实验里 80% 的翻车现场按「现象 → 原因 → 解决」写遇到对得上的直接照方抓药。5.1 递归与文法相关的坑现象程序编译通过一跑就段错误或者在aaa...这种长表达式上直接崩。原因把课本上的左递归文法原样翻译成代码parseExpr()第一句调parseExpr()无限递归直到栈耗尽。解决把E - E T | T改写成E - T ( T)*代码里就是先解析左操作数再while循环吃运算符。改完检查一遍所有解析函数确认没有哪个函数的第一句是调自己。现象if (a) if (b) x1; else x2;解析出来的树里else挂在了外层。原因parseIf()写成先无条件找else或者parseBlock()把内层 if 之后的 token 提前吃掉了。解决parseIf()里只在 then 分支解析完之后检查一次check(KW_ELSE)不要在parseBlock()里处理else测试用例里固定一条悬挂 else把期望的树形写进基线。5.2 词法与位置信息的坑现象源码里写intx 1;报错却提示「第 1 行第 1 列附近有问题」或者干脆把intx当成关键字int加标识符x。原因标识符扫描时边扫边判断关键字没有走最长匹配。解决先把整个标识符扫完再查关键字表查不到才归为IDENT数字同理扫完后检查下一字符不是字母或下划线。现象报错的行号总是比实际少一行尤其是文件开头有注释时。原因skipTrivia()里自己处理了\n但没同步更新line_而advance()里的更新又没被走到。解决所有字符消费统一走advance()行号和列号只在一个地方更新注释跳过函数只负责判断边界不负责改状态。现象1 2能过12也过了但ab报「期望表达式」。原因双字符运算符只判断了后面没看第二个字符直接把返回。解决所有可能组成双字符的运算符在switch分支里先peek()一次匹配上就advance()再返回长 token不匹配就返回短的。5.3 构建与编码的坑现象Windows 上 AST 打印是乱码Linux 上正常。原因节点里存了中文运算符名或诊断信息控制台默认代码页跟源文件编码不一致。解决AST 的kind和value一律用 ASCII 短名中文只出现在诊断消息里确需中文输出时在main开头把控制台输出代码页切到 UTF-8或者干脆把diag输出重定向到文件。现象error: make_unique is not a member of std。原因编译时没加-stdc17或者 CMake 里CMAKE_CXX_STANDARD被后面的target_compile_features覆盖了。解决显式指定标准并且在 CMake 里加set(CMAKE_CXX_EXTENSIONS OFF)别依赖编译器的默认值命令行编译时把-stdc17写死在脚本里。6. 二次开发从算术表达式扩到带函数调用的 mini-C想在这份代码上加东西顺序比内容重要。我的习惯是先把扩展点按「词法 → AST → 语法 → 测试」排好一次只改一层每层跑一次用例这样出错时能立刻定位到是哪一层引入的。扩展点改动位置工作量加for循环token.h加关键字、scanner加表项、parseFor()、Node复用While结构半天加函数定义与调用parseFuncDecl()、parseCall()放进parsePrimary()、新增Call节点一天加符号表与简单类型检查新建sema.cpp遍历 AST 记录声明一天AST 导出 JSON加一个 visitor不动 parser两小时函数调用最值得先做因为它是检验「表达式和语句边界是否切干净」的试金石。具体做法是在parsePrimary()的IDENT分支里多看一眼后面是不是(std::unique_ptrNode Parser::parsePrimary() { if (check(TokenType::NUMBER)) { Token t advance(); return makeNode(Number, t.lexeme, t.line); } if (check(TokenType::IDENT)) { Token t advance(); if (!check(TokenType::LPAREN)) // 普通标识符 return makeNode(Ident, t.lexeme, t.line); advance(); // 吃掉 ( auto call makeNode(Call, t.lexeme, t.line); if (!check(TokenType::RPAREN)) { call-kids.push_back(parseExpr()); // 实参先用表达式兜住 while (check(TokenType::COMMA)) { advance(); call-kids.push_back(parseExpr()); } } expect(TokenType::RPAREN, 函数调用的实参列表缺少 )); return call; } if (check(TokenType::LPAREN)) { /* 括号表达式同前 */ } return errorExpr(期望一个表达式); }改完这一段parsePrimary()就同时承担了变量、字面量、括号表达式和函数调用四种情况注意check(LPAREN)一定要在advance()之后判断否则会把普通变量误判成调用。验证方法是给三条用例f();、f(1, 2);、f(g(x), 1 2);三条的树都对了再回头补parseFuncDecl()。如果不想动 parserAST 导出 JSON 是性价比最高的改造加一个二十行的 visitor 就够后面前端可视化或者用脚本比对基线都能直接吃// src/jsonvisitor.cpp —— 不侵入 parser只遍历已有 AST struct JsonVisitor { std::ostream os; void visit(const Node* n) { os {\kind\:\ n-kind \; if (!n-value.empty()) os ,\value\:\ n-value \; os ,\line\: n-line; if (!n-kids.empty()) { os ,\kids\:[; for (size_t i 0; i n-kids.size(); i) { if (i) os ,; visit(n-kids[i].get()); } os ]; } os }; } };从那以后我每次动 parser 之前都强制先跑一遍tests/run_tests.sh并把--dump-ast的输出存成基线改完再跑一遍做 diff——语法分析这种东西靠肉眼看树形输出判断对错太不可靠了血泪经验。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/11/2 7:10:14 · 阅读 1.2k C++手写递归下降语法分析器：词法扫描到AST与错误恢复
简介这份编译原理语法分析实验资源面向正在学习编译原理、需要完成递归子程序法语法分析作业的高校学生与自学者重点解决在已有词法分析基础上识别各类语法成分、并按自动评测要求组织输出结果的问题。压缩包为zip格式共2个文件约17KB包含1份doc实验说明与1份cpp实现代码便于对照文法规则理解递归下降程序结构。目前已有6110人学习或下载具备较好的参考价值。代码在CG实验平台满分通过读者可据此了解如何对文法定义的全部语法成分逐一分析掌握按单词识别顺序逐行输出词法信息、在指定语法成分结束前另起一行输出“常量说明”等标记的实现思路并借鉴testfile.txt与output.txt的输入输出组织方式快速排查递归子程序分析中的常见问题适合课程实验提交前对照复盘。1. 编译原理课设里的语法分析为什么手写 parser 反而更快出结果编译原理的语法分析实验不少人第一反应是找个 LR 分析表生成器结果先被状态机构造和冲突处理绕晕实验报告写了三页还没跑通一个int a 1 2 * 3;。这份 C 版的实现走的是另一条路手写词法扫描加递归下降把一段 mini-C 源码直接解析成能打印的抽象语法树出错时给出行列号和可读的诊断。它适合三类人课程实验要交可运行代码的学生、想把一个轻量 parser 塞进自己小工具的开发者、以及只想知道「编译原理落到代码里长什么样」的自学者。整包不依赖第三方库一份 CMakeLists 加十几个源文件就能编出来改起来也没有黑匣子。2. 骨架与选型词法、语法、AST 三层怎么切递归下降还是表驱动拿到源码包先不要急着敲cmake先花十分钟看目录怎么切分。切分方式决定了后面加语法特性时疼不疼如果词法、语法、AST 节点全揉在main.cpp里加一条for语句要改五个地方如果按职责分好层加for只是多一个parseFor()和一个节点类型。这个项目的目录属于后者切得比较克制没有多余的抽象层也没有为了「工程化」硬塞设计模式。2.1 目录结构词法、语法、AST、诊断各自独立syntax-lab/ ├── CMakeLists.txt ├── include/ │ ├── token.h # TokenType 枚举与 Token 结构 │ ├── scanner.h # 字符流 - Token 流 │ ├── ast.h # AST 节点与 dump │ ├── parser.h # 递归下降的每个非终结符一个方法 │ └── diag.h # 错误收集行、列、级别、消息 ├── src/ │ ├── scanner.cpp │ ├── ast.cpp │ ├── parser.cpp │ ├── diag.cpp │ └── main.cpp # 命令行入口读文件、跑分析、按开关输出 └── tests/ ├── ok_basic.c # 正常用例 ├── ok_nested.c # 嵌套块与 if-else 悬挂 ├── err_missing_semi.c ├── err_bad_expr.c └── run_tests.sh文件职责二次开发时改动频率token.h定义所有记号的类型低加关键字时动一次scanner.cpp字符到记号的扫描、行列号维护中加运算符或字面量时改parser.cpp语法规则的具体落地高加语句类型必改ast.h / ast.cpp节点结构与树打印中加节点种类时改diag.cpp错误汇总与格式化低这个切法有一个隐含好处scanner只依赖token.hparser只依赖scanner和ast谁都不认识main。想单独测词法写个十行的小程序喂字符串进去就行不用把整个工程拖进来。2.2 为什么手写递归下降而不是查表驱动LL(1) 表驱动和 LR 表驱动都更「像编译原理课本」但在这个场景里不一定划算。表驱动需要额外写一个构造 FIRST/FOLLOW 集的程序再写一个分析表驱动引擎调 bug 时面对的是「状态 17 遇到;该走哪条产生式」这种问题断点进去也看不出业务语义。递归下降的每个函数名就是文法里的非终结符parseIf()里出问题你一眼就知道是 if 语句的哪一段错了。维度递归下降表驱动 LL(1)/LR上手成本低照着文法抄函数高先要把表算对调试体验断点停在具体规则上断在状态转移需要对照表看文法限制不能有左递归需要提取左公因子LL(1) 同理LR 宽松些扩展新语句加一个函数加一个分支改文法、重算表、可能引入冲突教学价值规则与代码一一对应更能体现自动机思想我的做法通常是先用递归下降把整条链路跑通让 AST 能正确打出来再考虑要不要为了实验报告补一个 FIRST/FOLLOW 计算器做对照。两套结果一致报告里的表也就有了依据。2.3 文法先改再写消除左递归是动手前的第一件事原始表达式文法里最常见的是这种写法Expr - Expr Term | Expr - Term | Term Term - Term * Factor | Term / Factor | Factor Factor- NUMBER | IDENT | ( Expr )照抄成代码就是parseExpr()第一行调parseExpr()跑起来直接栈溢出。正确做法是改写成右递归或者直接用循环项目里采用的是循环版本文法整理如下Program - StmtList END StmtList - Stmt StmtList | ε Stmt - Decl | Assign | If | While | Block Decl - int IDENT ( Expr)? ; Assign - IDENT Expr ; If - if ( Expr ) Stmt (else Stmt)? While - while ( Expr ) Stmt Block - { StmtList } Expr - Rel Rel - Add ((|||||!) Add)? Add - Mul ((|-) Mul)* Mul - Unary ((*|/) Unary)* Unary - - Unary | Primary Primary - NUMBER | IDENT | ( Expr )配套的 FIRST 集在动手前算一遍能省掉后面大量「明明文法写对了却解析错」的怀疑非终结符FIRST 集Programintifwhile{IDENTENDStmtintifwhile{IDENTExpr/Rel/Add/Mul-NUMBERIDENT(PrimaryNUMBERIDENT(注意Stmt的 FIRST 集里IDENT会同时出现在声明和赋值两个候选式里吗不会声明一定以int开头赋值一定以IDENT开头两者不冲突所以这里不需要提取左公因子。真正需要多看一眼的是悬挂 elseif (a) if (b) x 1; else x 2;里 else 归谁递归下降天然是「就近匹配」跟 C 语言一致这点在写parseIf()时不用特意处理但要在测试用例里固定下来。提示文法的 FIRST 集不必手工算完整先算Stmt和Expr这两层就够用了大部分歧义都出在这两处。3. 核心链路拆解一个 12*3 从字符流走到 AST 的全过程这条链路上有三个关键节点Token 的切分、表达式优先级的落地、语法树的构造与错误恢复。三段代码加起来不到三百行但每一段都有一两个容易写错的地方。下面按数据流动的顺序拆。3.1 Token 与 Scanner最长匹配是唯一准则Token 结构本身没什么花头关键是它要带上行列号否则后面报错只能告诉用户「第 N 个 token 有问题」这在几十行的测试文件里还能数换成几百行就没法用了。// include/token.h #pragma once #include string enum class TokenType { KW_INT, KW_IF, KW_ELSE, KW_WHILE, // 关键字 IDENT, NUMBER, // 标识符与数字字面量 PLUS, MINUS, STAR, SLASH, ASSIGN, EQ, NE, LT, LE, GT, GE, LPAREN, RPAREN, LBRACE, RBRACE, SEMI, COMMA, END, ERROR }; struct Token { TokenType type; std::string lexeme; int line 1; int col 1; };扫描器的主循环只做一件事跳过空白和注释然后按首字符分派。// src/scanner.cpp Token Scanner::next() { skipTrivia(); // 空格、换行、// 与 /* */ 全在这里吃掉 if (atEnd()) return Token{TokenType::END, eof, line_, col_}; const int startLine line_, startCol col_; char c peek(); if (std::isdigit(static_castunsigned char(c))) return scanNumber(startLine, startCol); if (std::isalpha(static_castunsigned char(c)) || c _) return scanIdentOrKeyword(startLine, startCol); advance(); // 先消费当前字符再判断双字符运算符 switch (c) { case : return Token{TokenType::PLUS, , startLine, startCol}; case -: return Token{TokenType::MINUS, -, startLine, startCol}; case *: return Token{TokenType::STAR, *, startLine, startCol}; case /: return Token{TokenType::SLASH, /, startLine, startCol}; case (: return Token{TokenType::LPAREN,(, startLine, startCol}; case ): return Token{TokenType::RPAREN,), startLine, startCol}; case {: return Token{TokenType::LBRACE,{, startLine, startCol}; case }: return Token{TokenType::RBRACE,}, startLine, startCol}; case ;: return Token{TokenType::SEMI, ;, startLine, startCol}; case ,: return Token{TokenType::COMMA, ,, startLine, startCol}; case : if (peek() ) { advance(); return Token{TokenType::EQ, , startLine, startCol}; } return Token{TokenType::ASSIGN, , startLine, startCol}; case : if (peek() ) { advance(); return Token{TokenType::LE, , startLine, startCol}; } return Token{TokenType::LT, , startLine, startCol}; case : if (peek() ) { advance(); return Token{TokenType::GE, , startLine, startCol}; } return Token{TokenType::GT, , startLine, startCol}; case !: if (peek() ) { advance(); return Token{TokenType::NE, !, startLine, startCol}; } return Token{TokenType::ERROR, !, startLine, startCol}; default: return Token{TokenType::ERROR, std::string(1, c), startLine, startCol}; } }逻辑上有两点必须讲清楚。第一advance()只负责推进指针并维护行列号不做类型判断这样所有位置信息只有一个更新点不会出现「某些字符跳过了行号统计」的问题。第二双字符运算符必须先看第二个字符再决定和、和分属不同分支写反了会让a b被切成两个赋值。标识符和关键字的处理靠最长匹配先一次性扫完整个词再查关键字表Token Scanner::scanIdentOrKeyword(int l, int c) { std::string s; while (!atEnd() (std::isalnum(static_castunsigned char(peek())) || peek() _)) s.push_back(advance()); // 一次扫到底中途不判断关键字 static const std::unordered_mapstd::string, TokenType kKeywords { {int, TokenType::KW_INT}, {if, TokenType::KW_IF}, {else, TokenType::KW_ELSE}, {while, TokenType::KW_WHILE} }; auto it kKeywords.find(s); return Token{it kKeywords.end() ? TokenType::IDENT : it-second, s, l, c}; }这个顺序不能反。如果边扫边判断「当前前缀是不是关键字」intx会被切成一个int加一个x后面语法分析就会莫名其妙地报「期望标识符」。同理scanNumber()扫完数字后要再检查下一个字符是不是字母或下划线是的话最好直接报一个ERROR而不是默默切成123和abc。3.2 递归下降主体parseExpr 怎么吃掉 12*3表达式是整份代码里最容易写错的部分因为它涉及优先级和结合性。项目采用分层下降从优先级最低的关系运算开始一层层往下调每层内部用while循环吃掉同级的连续运算。// src/parser.cpp —— 优先级从低到高逐层下降 std::unique_ptrNode Parser::parseExpr() { return parseRel(); } std::unique_ptrNode Parser::parseRel() { auto lhs parseAdd(); while (check(TokenType::LT) || check(TokenType::LE) || check(TokenType::GT) || check(TokenType::GE) || check(TokenType::EQ) || check(TokenType::NE)) { Token op advance(); auto rhs parseAdd(); lhs makeBinary(op.lexeme, std::move(lhs), std::move(rhs), op.line); } return lhs; } std::unique_ptrNode Parser::parseAdd() { auto lhs parseMul(); while (check(TokenType::PLUS) || check(TokenType::MINUS)) { Token op advance(); auto rhs parseMul(); // 右侧仍然从更高优先级开始 lhs makeBinary(op.lexeme, std::move(lhs), std::move(rhs), op.line); } return lhs; } std::unique_ptrNode Parser::parseMul() { auto lhs parseUnary(); while (check(TokenType::STAR) || check(TokenType::SLASH)) { Token op advance(); auto rhs parseUnary(); lhs makeBinary(op.lexeme, std::move(lhs), std::move(rhs), op.line); } return lhs; } std::unique_ptrNode Parser::parseUnary() { if (check(TokenType::MINUS)) { // 一元负号右结合 Token op advance(); return makeNode(Unary, op.lexeme, op.line, parseUnary()); } return parsePrimary(); } std::unique_ptrNode Parser::parsePrimary() { if (check(TokenType::NUMBER) || check(TokenType::IDENT)) { Token t advance(); return makeNode(t.type TokenType::NUMBER ? Number : Ident, t.lexeme, t.line); } if (check(TokenType::LPAREN)) { advance(); auto inner parseExpr(); expect(TokenType::RPAREN, 缺少右括号 )); return inner; } return errorExpr(期望一个表达式); }这段代码能正确处理1 2 * 3parseAdd先拿到左操作数1看到就把右边交给parseMulparseMul会一路把2 * 3收成一个子树再返回最终结构是(1, *(2, 3))而不是*((1, 2), 3)。左结合也是靠while循环自然得到的——每轮把已解析的lhs作为新的左子树包进去a - b - c就会变成-( -(a, b), c )跟数学约定一致。语句层同样是一个分派函数加一堆具体规则std::unique_ptrNode Parser::parseStmt() { switch (peek().type) { case TokenType::KW_INT: return parseDecl(); case TokenType::KW_IF: return parseIf(); case TokenType::KW_WHILE: return parseWhile(); case TokenType::LBRACE: return parseBlock(); case TokenType::IDENT: return parseAssign(); // 变量名开头只可能是赋值 case TokenType::SEMI: advance(); return makeNode(Empty, , prev().line); default: return errorStmt(期望一条语句); } }parseIf()里有一处值得留意解析完 then 分支后要先看有没有else有就继续解析没有就直接返回。悬挂 else 的归属由调用顺序决定if (a) if (b) x 1; else x 2;中内层parseIf()会先看到else并把它吃掉得到的语义是「就近匹配」与常见语言一致。3.3 AST 节点设计与错误恢复别让一个分号毁掉整趟分析节点结构用unique_ptr组合子节点避免手写析构也不用担心深拷贝// include/ast.h #pragma once #include memory #include string #include vector struct Node { std::string kind; // Program VarDecl Binary If ... std::string value; // 变量名、字面量、运算符 int line 0; std::vectorstd::unique_ptrNode kids; Node(std::string k, std::string v {}, int ln 0) : kind(std::move(k)), value(std::move(v)), line(ln) {} }; std::unique_ptrNode makeNode(std::string kind, std::string value {}, int line 0); std::unique_ptrNode makeBinary(std::string op, std::unique_ptrNode lhs, std::unique_ptrNode rhs, int line); void dump(const Node* n, std::ostream os, const std::string prefix , bool last true);kind用英文短名是有意为之一是打印对齐好看二是后面接 JSON 或 DOT 时不用做转义三是避免不同终端编码下出现乱码。错误恢复采用 panic mode出错后不抛异常而是丢 token 直到看见语句边界然后继续往下解析这样一次运行能报出多个错误。// src/parser.cpp void Parser::synchronize() { while (!check(TokenType::END)) { if (prev().type TokenType::SEMI) return; // 上一句刚好收尾可以直接续上 switch (peek().type) { case TokenType::KW_INT: case TokenType::KW_IF: case TokenType::KW_WHILE: case TokenType::RBRACE: return; // 遇到新语句或块结束重新对齐 default: advance(); } } } std::unique_ptrNode Parser::errorStmt(const std::string msg) { diag_.error(peek().line, peek().col, msg 实际读到 peek().lexeme ); synchronize(); return makeNode(ErrorStmt, msg, peek().line); // 占位节点保证上层拿到非空指针 }返回占位节点这一步不能省。如果出错时直接return nullptr上面parseBlock()往kids里push_back一个空指针打印 AST 时就是段错误排查起来比语法错误本身还费劲。注意synchronize()里先判断prev()再判断peek()顺序反了会导致x 1; 这种输入在分号处多吞一个 token。4. 跑起来CMake 构建、命令行开关与回归用例代码结构清楚之后跑通只需要三步配构建、给输入、看输出。这份工程的构建脚本很薄没有引入任何第三方依赖所以不管是在 Linux 还是 Windows 上问题基本都出在编译器标准和路径上不在依赖上。4.1 两条构建路径CMake 与单文件 gcmake_minimum_required(VERSION 3.16) project(syntax_lab CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_executable(syntax-lab src/main.cpp src/scanner.cpp src/parser.cpp src/ast.cpp src/diag.cpp ) target_include_directories(syntax-lab PRIVATE include) if (MSVC) target_compile_options(syntax-lab PRIVATE /W4) else() target_compile_options(syntax-lab PRIVATE -Wall -Wextra) endif()构建命令就两行第二行跑完能在build/下拿到可执行文件cmake -S . -B build -DCMAKE_BUILD_TYPEDebug cmake --build build -j如果只是想快速验证某个函数不想走 CMake直接一条命令也能编g -stdc17 -Wall -Wextra -Iinclude src/*.cpp -o syntax-lab用-stdc17是因为代码里用了std::unique_ptr、enum class和结构化绑定用-stdc11会在auto [a, b]这类地方报错。Debug 类型建议保留递归下降出错时栈帧信息很有用。4.2 命令行开关与一次完整运行main.cpp的入口很朴素读文件、建 Scanner、建 Parser、按开关输出。./build/syntax-lab tests/ok_basic.c --tokens --dump-ast--tokens打印词法结果--dump-ast打印语法树两个都不给时只做分析并输出错误数。写一个最小用例int a 1 2 * 3; int b; b a - 4; if (b 0) { b b * 2; } else { b 0; }期望的树形输出大致是这样缩进层级直接反映嵌套关系Program ├─ VarDecl a │ └─ Binary() │ ├─ Number 1 │ └─ Binary(*) │ ├─ Number 2 │ └─ Number 3 ├─ VarDecl b ├─ Assign b │ └─ Binary(-) │ ├─ Ident a │ └─ Number 4 └─ If ├─ Binary() │ ├─ Ident b │ └─ Number 0 ├─ Block │ └─ Assign b │ └─ Binary(*) │ ├─ Ident b │ └─ Number 2 └─ Block └─ Assign b └─ Number 0看到Binary(*)在Binary()的右子树里就说明优先级处理对了看到Assign的两个孩子分别是Ident b和表达式就说明语句层没把赋值当成表达式。4.3 回归用例把「看着对」变成「比对得出来」手工看树形输出只能覆盖几条用例改成脚本比对才靠得住。tests/run_tests.sh的思路很简单正常用例必须退出码为 0错误用例必须退出码非 0。#!/usr/bin/env bash # tests/run_tests.sh —— 正常用例要过错误用例必须报错 set -u BIN./build/syntax-lab fail0 for f in tests/ok_*.c; do if ! $BIN $f --dump-ast /dev/null 21; then echo FAIL(should pass): $f; fail1 fi done for f in tests/err_*.c; do if $BIN $f --dump-ast /dev/null 21; then echo FAIL(should fail): $f; fail1 fi done [ $fail -eq 0 ] echo all cases passed exit $fail这套脚本的价值在于锁住错误恢复行为。加了新语句之后很容易出现「错误用例不再报错」的退化人眼看树是看不出来的脚本一跑就露馅。想让比对更严格可以把--dump-ast的输出重定向到文件跟tests/expected/下的基线做diff第一次跑的时候人工确认基线之后就不用再看了。5. 避坑与排查五类把实验拖到凌晨的问题下面这几条基本覆盖了语法分析实验里 80% 的翻车现场按「现象 → 原因 → 解决」写遇到对得上的直接照方抓药。5.1 递归与文法相关的坑现象程序编译通过一跑就段错误或者在aaa...这种长表达式上直接崩。原因把课本上的左递归文法原样翻译成代码parseExpr()第一句调parseExpr()无限递归直到栈耗尽。解决把E - E T | T改写成E - T ( T)*代码里就是先解析左操作数再while循环吃运算符。改完检查一遍所有解析函数确认没有哪个函数的第一句是调自己。现象if (a) if (b) x1; else x2;解析出来的树里else挂在了外层。原因parseIf()写成先无条件找else或者parseBlock()把内层 if 之后的 token 提前吃掉了。解决parseIf()里只在 then 分支解析完之后检查一次check(KW_ELSE)不要在parseBlock()里处理else测试用例里固定一条悬挂 else把期望的树形写进基线。5.2 词法与位置信息的坑现象源码里写intx 1;报错却提示「第 1 行第 1 列附近有问题」或者干脆把intx当成关键字int加标识符x。原因标识符扫描时边扫边判断关键字没有走最长匹配。解决先把整个标识符扫完再查关键字表查不到才归为IDENT数字同理扫完后检查下一字符不是字母或下划线。现象报错的行号总是比实际少一行尤其是文件开头有注释时。原因skipTrivia()里自己处理了\n但没同步更新line_而advance()里的更新又没被走到。解决所有字符消费统一走advance()行号和列号只在一个地方更新注释跳过函数只负责判断边界不负责改状态。现象1 2能过12也过了但ab报「期望表达式」。原因双字符运算符只判断了后面没看第二个字符直接把返回。解决所有可能组成双字符的运算符在switch分支里先peek()一次匹配上就advance()再返回长 token不匹配就返回短的。5.3 构建与编码的坑现象Windows 上 AST 打印是乱码Linux 上正常。原因节点里存了中文运算符名或诊断信息控制台默认代码页跟源文件编码不一致。解决AST 的kind和value一律用 ASCII 短名中文只出现在诊断消息里确需中文输出时在main开头把控制台输出代码页切到 UTF-8或者干脆把diag输出重定向到文件。现象error: make_unique is not a member of std。原因编译时没加-stdc17或者 CMake 里CMAKE_CXX_STANDARD被后面的target_compile_features覆盖了。解决显式指定标准并且在 CMake 里加set(CMAKE_CXX_EXTENSIONS OFF)别依赖编译器的默认值命令行编译时把-stdc17写死在脚本里。6. 二次开发从算术表达式扩到带函数调用的 mini-C想在这份代码上加东西顺序比内容重要。我的习惯是先把扩展点按「词法 → AST → 语法 → 测试」排好一次只改一层每层跑一次用例这样出错时能立刻定位到是哪一层引入的。扩展点改动位置工作量加for循环token.h加关键字、scanner加表项、parseFor()、Node复用While结构半天加函数定义与调用parseFuncDecl()、parseCall()放进parsePrimary()、新增Call节点一天加符号表与简单类型检查新建sema.cpp遍历 AST 记录声明一天AST 导出 JSON加一个 visitor不动 parser两小时函数调用最值得先做因为它是检验「表达式和语句边界是否切干净」的试金石。具体做法是在parsePrimary()的IDENT分支里多看一眼后面是不是(std::unique_ptrNode Parser::parsePrimary() { if (check(TokenType::NUMBER)) { Token t advance(); return makeNode(Number, t.lexeme, t.line); } if (check(TokenType::IDENT)) { Token t advance(); if (!check(TokenType::LPAREN)) // 普通标识符 return makeNode(Ident, t.lexeme, t.line); advance(); // 吃掉 ( auto call makeNode(Call, t.lexeme, t.line); if (!check(TokenType::RPAREN)) { call-kids.push_back(parseExpr()); // 实参先用表达式兜住 while (check(TokenType::COMMA)) { advance(); call-kids.push_back(parseExpr()); } } expect(TokenType::RPAREN, 函数调用的实参列表缺少 )); return call; } if (check(TokenType::LPAREN)) { /* 括号表达式同前 */ } return errorExpr(期望一个表达式); }改完这一段parsePrimary()就同时承担了变量、字面量、括号表达式和函数调用四种情况注意check(LPAREN)一定要在advance()之后判断否则会把普通变量误判成调用。验证方法是给三条用例f();、f(1, 2);、f(g(x), 1 2);三条的树都对了再回头补parseFuncDecl()。如果不想动 parserAST 导出 JSON 是性价比最高的改造加一个二十行的 visitor 就够后面前端可视化或者用脚本比对基线都能直接吃// src/jsonvisitor.cpp —— 不侵入 parser只遍历已有 AST struct JsonVisitor { std::ostream os; void visit(const Node* n) { os {\kind\:\ n-kind \; if (!n-value.empty()) os ,\value\:\ n-value \; os ,\line\: n-line; if (!n-kids.empty()) { os ,\kids\:[; for (size_t i 0; i n-kids.size(); i) { if (i) os ,; visit(n-kids[i].get()); } os ]; } os }; } };从那以后我每次动 parser 之前都强制先跑一遍tests/run_tests.sh并把--dump-ast的输出存成基线改完再跑一遍做 diff——语法分析这种东西靠肉眼看树形输出判断对错太不可靠了血泪经验。希望帮到你。本文还有配套的精品资源点击获取