简介面向编译原理课程设计与自学的C词法分析器与语法分析器实现包适合计算机专业学生、对编译器运行机制感兴趣的开发者以及语言处理方向研究者。资源完整演示了从源代码到词法单元序列、再到抽象语法树的编译器前端流程包含有限自动机、上下文无关文法、递归下降/LL(1)解析等核心知识点。压缩包共9个文件约937KB其中2个cpp为源程序词法分析.cpp和语法分析.cpp分别对应两个分析器4个txt文件提供文法规则、源程序及token表输出便于对照验证另有2个exe可执行程序和1个README说明文档支持直接运行体验。目前已有736人学习下载适合需要课程设计参考或动手实践编译原理概念的学习者。通过阅读源码、查看token表与文法定义能更直观地理解分析器状态转换与语法树构建过程也可作为进一步扩展新型语法特性的起点。1. 编译原理词法分析器和语法分析器的C实现一份能直接跑通的工程编译原理的词法分析器Lexer和语法分析器Parser是C课程设计和考研复试里最常被要求现场写出来的两块。这份资源给的是一个不依赖Lex/Yacc、纯C写的小型编译器前端字符流进来经过词法分析变成Token流再经过递归下降的语法分析构建出语法树全程可以单步调试也方便你在上面继续加中间代码生成。它解决的不是“看懂定义”而是“真的跑通”——适合正在做编译原理实验、准备保研机试或者毕设里需要一个小型前端的人。接下来我把实现思路、参数设定和我实际踩过的坑拉一遍。2. 词法分析器怎么落地从状态转换图到Token流2.1 为什么是手写状态机而不是Lex生成很多教材花大篇幅讲正则表达式到NFA、NFA到DFA的子集构造这是理解自动机理论的必经路。但实际做课程设计时用Lex生成器反而限制你展示实现细节答辩时被追问“状态转移图怎么画的”容易答不实。我一般建议手写词法分析器先把每个Token类别的状态转移图画在纸上再直接编码成游标读取加判断的形式。这份资源走的就是手写路线好处是代码可控、错误定位直观。它把每个Token的识别逻辑收敛在getNextToken()一个入口里外部用不到任何生成器产物编译环境只要有一个标准C编译器就行。2.2 核心结构Token定义、符号表与游标模型词法分析器的高层设计分三块Token结构、符号表、游标推进器。先看Token定义和Lexer头文件#ifndef LEXER_H #define LEXER_H #include string #include vector enum TokenType { TOKEN_IDENTIFIER, TOKEN_NUMBER, TOKEN_KEYWORD, TOKEN_OPERATOR, TOKEN_STRING, TOKEN_EOF, TOKEN_ERROR }; struct Token { TokenType type; std::string value; int line; int column; }; class Lexer { public: explicit Lexer(const std::string source); Token getNextToken(); private: std::string src; size_t pos; int line; int column; char peek(size_t offset 0) const; void advance(); bool isKeyword(const std::string word) const; }; #endifToken里除了类型和值还记录行列号这是后面语法分析报错能定位到具体位置的根基。line从1开始column从1开始出错信息直接拼出来就行。词法分析器的主循环在getNextToken()里我用的是peek加advance的游标模型。peek(offset)只观察不移动advance()才真正推进并更新行号列号。这个模型比直接下标访问更不容易在双字符运算符上翻车#include lexer.h #include cctype #include unordered_set static const std::unordered_setstd::string keywords { int, float, if, else, while, return }; Lexer::Lexer(const std::string source) : src(source), pos(0), line(1), column(1) {} char Lexer::peek(size_t offset) const { size_t idx pos offset; if (idx src.size()) return \0; return src[idx]; } void Lexer::advance() { if (pos src.size()) { if (src[pos] \n) { line; column 1; } else { column; } pos; } } bool Lexer::isKeyword(const std::string word) const { return keywords.find(word) ! keywords.end(); } Token Lexer::getNextToken() { while (peek() || peek() \t || peek() \n) advance(); if (peek() \0) return {TOKEN_EOF, , line, column}; int startLine line, startCol column; if (isalpha(peek()) || peek() _) { std::string word; while (isalnum(peek()) || peek() _) { word.push_back(peek()); advance(); } if (isKeyword(word)) return {TOKEN_KEYWORD, word, startLine, startCol}; return {TOKEN_IDENTIFIER, word, startLine, startCol}; } if (isdigit(peek())) { std::string num; while (isdigit(peek())) { num.push_back(peek()); advance(); } if (peek() . isdigit(peek(1))) { num.push_back(.); advance(); while (isdigit(peek())) { num.push_back(peek()); advance(); } } return {TOKEN_NUMBER, num, startLine, startCol}; } std::string op(1, peek()); advance(); return {TOKEN_OPERATOR, op, startLine, startCol}; }先跳空白再判断结束这是个固定的顺序不能反过来——如果先判\0字符串末尾的空白和换行会直接让分析器漏掉真正的结束位置。关键字判定放在标识符识别之后先拼出完整词再查表避免把intx截成int加x两个Token。数字部分只处理了整数和小数没有做科学计数法。如果你的实验要求支持1e-5这种写法需要在isdigit循环之后加一个分支判断peek() e || peek() E并且后面必须跟数字或正负号加数字。运算符部分当前按单字符处理想支持、这类双字符运算符在return {TOKEN_OPERATOR, op, ...}之前加一个peek(1)的判断分支即可注意合并后要调用两次advance()。2.3 调试词法结果把Token流dump出来对拍写完词法分析器第一件事不是接语法分析器而是把Token流完整打印出来。我在主程序里挂了一个dump模式输出格式是行:列 type value一行一个Token1:1 KEYWORD int 1:5 IDENTIFIER a 1:7 OPERATOR 1:9 NUMBER 10 1:12 OPERATOR 1:14 NUMBER 20这个格式看着基础但对拍非常好用。我习惯把测试文件里的预期Token序列写进一个txt然后和程序输出做diff。词法分析器有没有把注释吃掉、字符串有没有截断、运算符有没有拆错diff一眼就出来。没有这一步后面语法分析报错时你根本分不清是词法错的还是语法错的。3. 语法分析器递归下降与LL(1)预测分析的实现3.1 为什么选递归下降而不是LR表驱动LR分析器能力强理论上能处理的文法更多但状态栈和ACTION/GOTO表对初学者就是黑匣子出了一次错很难从状态转移trace出原因。递归下降的劣势是左递归文法会死循环但教学实验的文法通常都改写成LL(1)了这个劣势基本不存在。这份资源用的是递归下降加一个Token预读lookahead。它的本质是自顶向下分析从起始符号开始按产生式展开每遇到一个终结符就和当前Token匹配。代码结构对应文法层次一眼能看出表达式优先级答辩时也容易讲清楚。3.2 文法、First集与Follow集语法分析器支持的文法是一个最简表达式文法优先级从低到高Expression - Term (( | -) Term)* Term - Factor ((* | /) Factor)* Factor - NUMBER | IDENTIFIER | ( Expression )*表示零次或多次循环这个写法本身就是消除左递归之后的LL(1)版本。手工算First集和Follow集结果如下非终结符FIRSTFOLLOWExpressionNUMBER, IDENTIFIER, ($, )TermNUMBER, IDENTIFIER, ($, ), , -FactorNUMBER, IDENTIFIER, ($, ), , -, *, /注意这里的$是输入结束符对应词法分析器返回的TOKEN_EOF。两个非终结符的Follow集有重叠所以分析表里多个产生式可以并存但同一格子没有冲突这个文法确实是LL(1)的。3.3 语法树构造与错误恢复Parser的头文件里定义了ASTNode用shared_ptr管理子树避免手动delete。节点只有left和right两个子节点这种二叉树结构对表达式文法够用#ifndef PARSER_H #define PARSER_H #include lexer.h #include memory #include string struct ASTNode { std::string type; std::string value; std::shared_ptrASTNode left; std::shared_ptrASTNode right; }; class Parser { public: explicit Parser(Lexer lexer); std::shared_ptrASTNode parse(); private: Lexer lexer; Token lookahead; void advance(); void match(const std::string value, const std::string hint); std::shared_ptrASTNode parseExpression(); std::shared_ptrASTNode parseTerm(); std::shared_ptrASTNode parseFactor(); [[noreturn]] void error(const std::string msg) const; }; #endiflookahead始终保存当前要匹配的Tokenadvance()从词法分析器拿下一个。match是唯一的消费入口值不匹配就抛错误抛错信息里带行列号。递归下降的核心在三个parse函数里它们互相调用的层次直接反映优先级#include parser.h #include iostream Parser::Parser(Lexer lex) : lexer(lex) { lookahead lexer.getNextToken(); } void Parser::advance() { lookahead lexer.getNextToken(); } void Parser::match(const std::string value, const std::string hint) { if (lookahead.value ! value) { error(期望 hint 实际是 lookahead.value 行 std::to_string(lookahead.line)); } advance(); } std::shared_ptrASTNode Parser::parse() { auto tree parseExpression(); if (lookahead.type ! TOKEN_EOF) { error(表达式结束后仍有未消费的Token); } return tree; } std::shared_ptrASTNode Parser::parseExpression() { auto node parseTerm(); while (lookahead.value || lookahead.value -) { auto op std::make_sharedASTNode(); op-type op; op-value lookahead.value; advance(); op-left node; op-right parseTerm(); node op; } return node; } std::shared_ptrASTNode Parser::parseTerm() { auto node parseFactor(); while (lookahead.value * || lookahead.value /) { auto op std::make_sharedASTNode(); op-type op; op-value lookahead.value; advance(); op-left node; op-right parseFactor(); node op; } return node; } std::shared_ptrASTNode Parser::parseFactor() { if (lookahead.type TOKEN_NUMBER || lookahead.type TOKEN_IDENTIFIER) { auto leaf std::make_sharedASTNode(); leaf-type (lookahead.type TOKEN_NUMBER) ? num : id; leaf-value lookahead.value; advance(); return leaf; } if (lookahead.value () { advance(); auto node parseExpression(); match(), 右括号); return node; } error(无法解析因子遇到 lookahead.value); }左结合性靠while循环实现。1 2 3进来时第一次parseTerm拿到1循环里构建(1, 2)第二次循环把新节点挂到原节点的right最终得到((1,2), 3)也就是(12)3。如果把循环改成直接递归调用parseExpression就会变成1(23)这是右结合加减法还看不出大问题遇到减号就会算出错误结果。错误恢复这里没有做复杂的同步集合而是直接终止报错。这个选择对课程设计是合理的——分析器不是编译器成品实验要求通常是“能识别合法输入并在非法输入上给出准确报错”而不是“跳过错误继续分析下一句”。如果你想支持多条语句的继续分析常见做法是维护一个syncSet遇到错误后不停advance()直到当前Token属于;或}等同步Token再回到上层循环。4. 把工程串起来主流程、VSCode编译与测试样例设计4.1 文件组织与依赖关系解压后的工程目录是我很喜欢的五文件结构头文件和源文件分离依赖方向是main.cpp依赖parser.hparser.cpp依赖lexer.h没有循环引用。整个工程就是标准的C项目不需要第三方库lexer.h Token定义、Lexer类声明 lexer.cpp getNextToken实现 parser.h ASTNode定义、Parser类声明 parser.cpp 递归下降解析器实现 main.cpp 入口读文件、驱动分析这种组织的直接好处是想单独测试词法分析器写一个只和Lexer对接的测试文件就行想换成LR分析器Parser类的公共接口不变词法那边完全不用动。4.2 主程序调用流程main.cpp负责三件事读入源文件、构造词法分析器、交给语法分析器。读文件我用二进制方式加ostringstream整体倒入而不是一行一行读省去处理跨行字符串的麻烦#include lexer.h #include parser.h #include fstream #include iostream #include sstream int main(int argc, char* argv[]) { if (argc 2) { std::cerr 用法: parser 源码文件 std::endl; return 1; } std::ifstream in(argv[1], std::ios::binary); if (!in) { std::cerr 无法打开文件: argv[1] std::endl; return 1; } std::ostringstream ss; ss in.rdbuf(); std::string source ss.str(); Lexer lexer(source); Parser parser(lexer); auto tree parser.parse(); std::cout 语法分析通过根节点类型: tree-type std::endl; return 0; }如果是在VSCode里开发配C/C环境时的关键在于tasks.json的编译参数要写全所有源文件。很多人只把main.cpp放进args结果g报一堆undefined reference就是这个原因{ version: 2.0.0, tasks: [ { label: build, type: shell, command: g, args: [ -stdc17, src/main.cpp, src/lexer.cpp, src/parser.cpp, -o, bin/parser ], options: { cwd: ${workspaceFolder} } } ] }-stdc17保证shared_ptr和[[noreturn]]这些特性在MSVC和GCC下行为一致。如果你在Windows上用MSVC编译器记得把代码页切到UTF-8或将源文件全部存成UTF-8无BOM否则中文注释会变成编译告警甚至乱码。4.3 测试样例怎么设计我建议至少准备三组测试文件合法简单表达式、合法复合表达式、非法表达式。合法复合用例测优先级和括号int a 10 20 * (3 - 1);预期是先算3-1再算20*2最后加10根节点是。非法用例故意漏掉右括号int a (1 2;运行后程序应该在;位置报“期望 右括号实际是 ;”。报错行列号和源文件里实际位置一致才算这个分析器合格。注意int a ...;这种带初始化语句的完整写法当前文法只处理等号右侧表达式左侧和声明部分由顶层代码处理。5. 避坑与常见问题解压后跑不起来的五个典型坑1. 中文注释让词法分析器卡死或乱码现象源码文件里有中文注释词法分析器输出乱码或者在isalpha(peek())上直接崩溃。原因char在Windows下默认有符号UTF-8中文首字节是负数传给isalpha、isalnum这类标准库函数时属于未定义行为。按字节读文件的方式不会自动跳过多字节字符。解决把源码文件统一存成UTF-8无BOM词法分析器显式处理注释。在getNextToken()开头加一段遇到/时检查peek(1)如果是/就跳到行尾如果是*就跳到*/跳的过程中用advance()推进不要碰isalpha。我每次做实验都强制自己先写注释跳过逻辑否则后面所有测试都白搭。2. 词法死循环分析器卡在同一个字符上现象程序不报错也不结束CPU占用拉满调试发现pos没有变化。原因某个分支只构造了Token没有调用advance()或者在peek() \0这个判断之前多了一次空闲的peek()调用没有对应的advance()。解决在getNextToken()里设一条铁律每个return分支前pos必然比进入函数时大。我一般会在函数末尾加一个调试断言打印旧pos和新pos跑一次哑数据哪个分支没推进马上暴露。另外运算符分支只advance()一次如果识别成双字符运算符必须连续调用两次advance()。3. 未知字符进了运算符分支状态机没有ERROR态现象输入#或这些文法语汇之外的字符程序不报错反而把它们当成运算符继续分析最后语法分析器报出莫名其妙的位置。原因手写状态机没有兜底分支未知字符被当成默认Token吞掉了。解决在getNextToken()里加一个TOKEN_ERROR类型遇到不在合法起始字符集合内的字符直接返回错误Token。主程序统计到TOKEN_ERROR或TOKEN_EOF之前出现过错误时退出码返回非0。这一步能挡住后面90%的排错时间。4. 减号右结合a-b-c被解析成a-(b-c)现象语法树dump出来10-3-2的树根是减号右子树还是减号节点。原因parseExpression写成递归调用而不是while循环。递归写法在每次遇到减号时递归调用parseExpression导致右结合。这是递归下降最常见的翻车点。解决按上面第3章的写法parseExpression里用while循环收集和-每次把已有节点挂到新op节点的left。验证方法很简单打印(10-3-2)的AST如果根节点的right不是减号节点说明左结合正确。从那以后我每次改完Parser都先跑一遍减法用例。5. lookahead预读的Token在报错时被吞掉现象错误信息指向的位置和真实错误隔了一行或者报错时已经跳过一个关键Token。原因match失败时先advance()再抛错误预读的Token被消费掉了错误处理里又尝试回退但Lexer没有提供pushback能力只能干瞪眼。解决match里的逻辑一定是先检查后推进。错误信息用当前lookahead的行列号拼出来不要再动游标。如果做了错误恢复跳过确保跳过的逻辑不会反复消费同一个Token。还有个小细节Windows下双击运行exe报缺少VCRUNTIME140.dll时别急着改代码这是没装VC Redistributable运行库和工程本身没关系。6. 进阶用法把语法树输出成四元式验证分析器正确性6.1 把AST打印成缩进树语法分析器跑通后我还建议做一步树结构可视化。一个简单的缩进打印就能看出结合性和优先级void dumpTree(std::shared_ptrASTNode node, int depth) { if (!node) return; for (int i 0; i depth; i) std::cout ; std::cout node-type node-value std::endl; dumpTree(node-left, depth 1); dumpTree(node-right, depth 1); }对10 20 * (3 - 1)执行后输出能清楚看到根是op 右子树是op *而*的右子树是op -。这比任何调试器都直观也是答辩时讲左结合最有力的证据。6.2 从AST生成四元式更进阶的验证方式是生成四元式因为它要求你正确遍历二叉树并分配临时变量。叶子节点直接返回自己的值op节点先递归左右子树再把结果拼成一条四元式// 返回该子树结果的临时变量名 std::string genIR(std::shared_ptrASTNode node, int temp) { if (!node) return ; if (node-type num || node-type id) { return node-value; } std::string left genIR(node-left, temp); std::string right genIR(node-right, temp); std::string t t std::to_string(temp); std::cout t left node-value right std::endl; return t; }temp就是临时变量计数器每生成一条四元式就自增一次。我习惯把四元式输出和人工手算的结果对拍10 20 * (3 - 1)应该得到三条先算t0 3 - 1再算t1 20 * t0最后t2 10 t1。如果顺序不对说明AST层级的构建有偏差往回查文法比查代码更快。从那以后我每次做完词法和语法分析器都强制自己走一遍“Token流dump → AST缩进树 → 四元式输出”三段对拍这个习惯帮我挡掉了好几次状态机回归的翻车——每次改动完哪怕只是加一个关键字也要全流程重跑一遍。希望帮到你。本文还有配套的精品资源点击获取
简介面向编译原理课程设计与自学的C词法分析器与语法分析器实现包适合计算机专业学生、对编译器运行机制感兴趣的开发者以及语言处理方向研究者。资源完整演示了从源代码到词法单元序列、再到抽象语法树的编译器前端流程包含有限自动机、上下文无关文法、递归下降/LL(1)解析等核心知识点。压缩包共9个文件约937KB其中2个cpp为源程序词法分析.cpp和语法分析.cpp分别对应两个分析器4个txt文件提供文法规则、源程序及token表输出便于对照验证另有2个exe可执行程序和1个README说明文档支持直接运行体验。目前已有736人学习下载适合需要课程设计参考或动手实践编译原理概念的学习者。通过阅读源码、查看token表与文法定义能更直观地理解分析器状态转换与语法树构建过程也可作为进一步扩展新型语法特性的起点。1. 编译原理词法分析器和语法分析器的C实现一份能直接跑通的工程编译原理的词法分析器Lexer和语法分析器Parser是C课程设计和考研复试里最常被要求现场写出来的两块。这份资源给的是一个不依赖Lex/Yacc、纯C写的小型编译器前端字符流进来经过词法分析变成Token流再经过递归下降的语法分析构建出语法树全程可以单步调试也方便你在上面继续加中间代码生成。它解决的不是“看懂定义”而是“真的跑通”——适合正在做编译原理实验、准备保研机试或者毕设里需要一个小型前端的人。接下来我把实现思路、参数设定和我实际踩过的坑拉一遍。2. 词法分析器怎么落地从状态转换图到Token流2.1 为什么是手写状态机而不是Lex生成很多教材花大篇幅讲正则表达式到NFA、NFA到DFA的子集构造这是理解自动机理论的必经路。但实际做课程设计时用Lex生成器反而限制你展示实现细节答辩时被追问“状态转移图怎么画的”容易答不实。我一般建议手写词法分析器先把每个Token类别的状态转移图画在纸上再直接编码成游标读取加判断的形式。这份资源走的就是手写路线好处是代码可控、错误定位直观。它把每个Token的识别逻辑收敛在getNextToken()一个入口里外部用不到任何生成器产物编译环境只要有一个标准C编译器就行。2.2 核心结构Token定义、符号表与游标模型词法分析器的高层设计分三块Token结构、符号表、游标推进器。先看Token定义和Lexer头文件#ifndef LEXER_H #define LEXER_H #include string #include vector enum TokenType { TOKEN_IDENTIFIER, TOKEN_NUMBER, TOKEN_KEYWORD, TOKEN_OPERATOR, TOKEN_STRING, TOKEN_EOF, TOKEN_ERROR }; struct Token { TokenType type; std::string value; int line; int column; }; class Lexer { public: explicit Lexer(const std::string source); Token getNextToken(); private: std::string src; size_t pos; int line; int column; char peek(size_t offset 0) const; void advance(); bool isKeyword(const std::string word) const; }; #endifToken里除了类型和值还记录行列号这是后面语法分析报错能定位到具体位置的根基。line从1开始column从1开始出错信息直接拼出来就行。词法分析器的主循环在getNextToken()里我用的是peek加advance的游标模型。peek(offset)只观察不移动advance()才真正推进并更新行号列号。这个模型比直接下标访问更不容易在双字符运算符上翻车#include lexer.h #include cctype #include unordered_set static const std::unordered_setstd::string keywords { int, float, if, else, while, return }; Lexer::Lexer(const std::string source) : src(source), pos(0), line(1), column(1) {} char Lexer::peek(size_t offset) const { size_t idx pos offset; if (idx src.size()) return \0; return src[idx]; } void Lexer::advance() { if (pos src.size()) { if (src[pos] \n) { line; column 1; } else { column; } pos; } } bool Lexer::isKeyword(const std::string word) const { return keywords.find(word) ! keywords.end(); } Token Lexer::getNextToken() { while (peek() || peek() \t || peek() \n) advance(); if (peek() \0) return {TOKEN_EOF, , line, column}; int startLine line, startCol column; if (isalpha(peek()) || peek() _) { std::string word; while (isalnum(peek()) || peek() _) { word.push_back(peek()); advance(); } if (isKeyword(word)) return {TOKEN_KEYWORD, word, startLine, startCol}; return {TOKEN_IDENTIFIER, word, startLine, startCol}; } if (isdigit(peek())) { std::string num; while (isdigit(peek())) { num.push_back(peek()); advance(); } if (peek() . isdigit(peek(1))) { num.push_back(.); advance(); while (isdigit(peek())) { num.push_back(peek()); advance(); } } return {TOKEN_NUMBER, num, startLine, startCol}; } std::string op(1, peek()); advance(); return {TOKEN_OPERATOR, op, startLine, startCol}; }先跳空白再判断结束这是个固定的顺序不能反过来——如果先判\0字符串末尾的空白和换行会直接让分析器漏掉真正的结束位置。关键字判定放在标识符识别之后先拼出完整词再查表避免把intx截成int加x两个Token。数字部分只处理了整数和小数没有做科学计数法。如果你的实验要求支持1e-5这种写法需要在isdigit循环之后加一个分支判断peek() e || peek() E并且后面必须跟数字或正负号加数字。运算符部分当前按单字符处理想支持、这类双字符运算符在return {TOKEN_OPERATOR, op, ...}之前加一个peek(1)的判断分支即可注意合并后要调用两次advance()。2.3 调试词法结果把Token流dump出来对拍写完词法分析器第一件事不是接语法分析器而是把Token流完整打印出来。我在主程序里挂了一个dump模式输出格式是行:列 type value一行一个Token1:1 KEYWORD int 1:5 IDENTIFIER a 1:7 OPERATOR 1:9 NUMBER 10 1:12 OPERATOR 1:14 NUMBER 20这个格式看着基础但对拍非常好用。我习惯把测试文件里的预期Token序列写进一个txt然后和程序输出做diff。词法分析器有没有把注释吃掉、字符串有没有截断、运算符有没有拆错diff一眼就出来。没有这一步后面语法分析报错时你根本分不清是词法错的还是语法错的。3. 语法分析器递归下降与LL(1)预测分析的实现3.1 为什么选递归下降而不是LR表驱动LR分析器能力强理论上能处理的文法更多但状态栈和ACTION/GOTO表对初学者就是黑匣子出了一次错很难从状态转移trace出原因。递归下降的劣势是左递归文法会死循环但教学实验的文法通常都改写成LL(1)了这个劣势基本不存在。这份资源用的是递归下降加一个Token预读lookahead。它的本质是自顶向下分析从起始符号开始按产生式展开每遇到一个终结符就和当前Token匹配。代码结构对应文法层次一眼能看出表达式优先级答辩时也容易讲清楚。3.2 文法、First集与Follow集语法分析器支持的文法是一个最简表达式文法优先级从低到高Expression - Term (( | -) Term)* Term - Factor ((* | /) Factor)* Factor - NUMBER | IDENTIFIER | ( Expression )*表示零次或多次循环这个写法本身就是消除左递归之后的LL(1)版本。手工算First集和Follow集结果如下非终结符FIRSTFOLLOWExpressionNUMBER, IDENTIFIER, ($, )TermNUMBER, IDENTIFIER, ($, ), , -FactorNUMBER, IDENTIFIER, ($, ), , -, *, /注意这里的$是输入结束符对应词法分析器返回的TOKEN_EOF。两个非终结符的Follow集有重叠所以分析表里多个产生式可以并存但同一格子没有冲突这个文法确实是LL(1)的。3.3 语法树构造与错误恢复Parser的头文件里定义了ASTNode用shared_ptr管理子树避免手动delete。节点只有left和right两个子节点这种二叉树结构对表达式文法够用#ifndef PARSER_H #define PARSER_H #include lexer.h #include memory #include string struct ASTNode { std::string type; std::string value; std::shared_ptrASTNode left; std::shared_ptrASTNode right; }; class Parser { public: explicit Parser(Lexer lexer); std::shared_ptrASTNode parse(); private: Lexer lexer; Token lookahead; void advance(); void match(const std::string value, const std::string hint); std::shared_ptrASTNode parseExpression(); std::shared_ptrASTNode parseTerm(); std::shared_ptrASTNode parseFactor(); [[noreturn]] void error(const std::string msg) const; }; #endiflookahead始终保存当前要匹配的Tokenadvance()从词法分析器拿下一个。match是唯一的消费入口值不匹配就抛错误抛错信息里带行列号。递归下降的核心在三个parse函数里它们互相调用的层次直接反映优先级#include parser.h #include iostream Parser::Parser(Lexer lex) : lexer(lex) { lookahead lexer.getNextToken(); } void Parser::advance() { lookahead lexer.getNextToken(); } void Parser::match(const std::string value, const std::string hint) { if (lookahead.value ! value) { error(期望 hint 实际是 lookahead.value 行 std::to_string(lookahead.line)); } advance(); } std::shared_ptrASTNode Parser::parse() { auto tree parseExpression(); if (lookahead.type ! TOKEN_EOF) { error(表达式结束后仍有未消费的Token); } return tree; } std::shared_ptrASTNode Parser::parseExpression() { auto node parseTerm(); while (lookahead.value || lookahead.value -) { auto op std::make_sharedASTNode(); op-type op; op-value lookahead.value; advance(); op-left node; op-right parseTerm(); node op; } return node; } std::shared_ptrASTNode Parser::parseTerm() { auto node parseFactor(); while (lookahead.value * || lookahead.value /) { auto op std::make_sharedASTNode(); op-type op; op-value lookahead.value; advance(); op-left node; op-right parseFactor(); node op; } return node; } std::shared_ptrASTNode Parser::parseFactor() { if (lookahead.type TOKEN_NUMBER || lookahead.type TOKEN_IDENTIFIER) { auto leaf std::make_sharedASTNode(); leaf-type (lookahead.type TOKEN_NUMBER) ? num : id; leaf-value lookahead.value; advance(); return leaf; } if (lookahead.value () { advance(); auto node parseExpression(); match(), 右括号); return node; } error(无法解析因子遇到 lookahead.value); }左结合性靠while循环实现。1 2 3进来时第一次parseTerm拿到1循环里构建(1, 2)第二次循环把新节点挂到原节点的right最终得到((1,2), 3)也就是(12)3。如果把循环改成直接递归调用parseExpression就会变成1(23)这是右结合加减法还看不出大问题遇到减号就会算出错误结果。错误恢复这里没有做复杂的同步集合而是直接终止报错。这个选择对课程设计是合理的——分析器不是编译器成品实验要求通常是“能识别合法输入并在非法输入上给出准确报错”而不是“跳过错误继续分析下一句”。如果你想支持多条语句的继续分析常见做法是维护一个syncSet遇到错误后不停advance()直到当前Token属于;或}等同步Token再回到上层循环。4. 把工程串起来主流程、VSCode编译与测试样例设计4.1 文件组织与依赖关系解压后的工程目录是我很喜欢的五文件结构头文件和源文件分离依赖方向是main.cpp依赖parser.hparser.cpp依赖lexer.h没有循环引用。整个工程就是标准的C项目不需要第三方库lexer.h Token定义、Lexer类声明 lexer.cpp getNextToken实现 parser.h ASTNode定义、Parser类声明 parser.cpp 递归下降解析器实现 main.cpp 入口读文件、驱动分析这种组织的直接好处是想单独测试词法分析器写一个只和Lexer对接的测试文件就行想换成LR分析器Parser类的公共接口不变词法那边完全不用动。4.2 主程序调用流程main.cpp负责三件事读入源文件、构造词法分析器、交给语法分析器。读文件我用二进制方式加ostringstream整体倒入而不是一行一行读省去处理跨行字符串的麻烦#include lexer.h #include parser.h #include fstream #include iostream #include sstream int main(int argc, char* argv[]) { if (argc 2) { std::cerr 用法: parser 源码文件 std::endl; return 1; } std::ifstream in(argv[1], std::ios::binary); if (!in) { std::cerr 无法打开文件: argv[1] std::endl; return 1; } std::ostringstream ss; ss in.rdbuf(); std::string source ss.str(); Lexer lexer(source); Parser parser(lexer); auto tree parser.parse(); std::cout 语法分析通过根节点类型: tree-type std::endl; return 0; }如果是在VSCode里开发配C/C环境时的关键在于tasks.json的编译参数要写全所有源文件。很多人只把main.cpp放进args结果g报一堆undefined reference就是这个原因{ version: 2.0.0, tasks: [ { label: build, type: shell, command: g, args: [ -stdc17, src/main.cpp, src/lexer.cpp, src/parser.cpp, -o, bin/parser ], options: { cwd: ${workspaceFolder} } } ] }-stdc17保证shared_ptr和[[noreturn]]这些特性在MSVC和GCC下行为一致。如果你在Windows上用MSVC编译器记得把代码页切到UTF-8或将源文件全部存成UTF-8无BOM否则中文注释会变成编译告警甚至乱码。4.3 测试样例怎么设计我建议至少准备三组测试文件合法简单表达式、合法复合表达式、非法表达式。合法复合用例测优先级和括号int a 10 20 * (3 - 1);预期是先算3-1再算20*2最后加10根节点是。非法用例故意漏掉右括号int a (1 2;运行后程序应该在;位置报“期望 右括号实际是 ;”。报错行列号和源文件里实际位置一致才算这个分析器合格。注意int a ...;这种带初始化语句的完整写法当前文法只处理等号右侧表达式左侧和声明部分由顶层代码处理。5. 避坑与常见问题解压后跑不起来的五个典型坑1. 中文注释让词法分析器卡死或乱码现象源码文件里有中文注释词法分析器输出乱码或者在isalpha(peek())上直接崩溃。原因char在Windows下默认有符号UTF-8中文首字节是负数传给isalpha、isalnum这类标准库函数时属于未定义行为。按字节读文件的方式不会自动跳过多字节字符。解决把源码文件统一存成UTF-8无BOM词法分析器显式处理注释。在getNextToken()开头加一段遇到/时检查peek(1)如果是/就跳到行尾如果是*就跳到*/跳的过程中用advance()推进不要碰isalpha。我每次做实验都强制自己先写注释跳过逻辑否则后面所有测试都白搭。2. 词法死循环分析器卡在同一个字符上现象程序不报错也不结束CPU占用拉满调试发现pos没有变化。原因某个分支只构造了Token没有调用advance()或者在peek() \0这个判断之前多了一次空闲的peek()调用没有对应的advance()。解决在getNextToken()里设一条铁律每个return分支前pos必然比进入函数时大。我一般会在函数末尾加一个调试断言打印旧pos和新pos跑一次哑数据哪个分支没推进马上暴露。另外运算符分支只advance()一次如果识别成双字符运算符必须连续调用两次advance()。3. 未知字符进了运算符分支状态机没有ERROR态现象输入#或这些文法语汇之外的字符程序不报错反而把它们当成运算符继续分析最后语法分析器报出莫名其妙的位置。原因手写状态机没有兜底分支未知字符被当成默认Token吞掉了。解决在getNextToken()里加一个TOKEN_ERROR类型遇到不在合法起始字符集合内的字符直接返回错误Token。主程序统计到TOKEN_ERROR或TOKEN_EOF之前出现过错误时退出码返回非0。这一步能挡住后面90%的排错时间。4. 减号右结合a-b-c被解析成a-(b-c)现象语法树dump出来10-3-2的树根是减号右子树还是减号节点。原因parseExpression写成递归调用而不是while循环。递归写法在每次遇到减号时递归调用parseExpression导致右结合。这是递归下降最常见的翻车点。解决按上面第3章的写法parseExpression里用while循环收集和-每次把已有节点挂到新op节点的left。验证方法很简单打印(10-3-2)的AST如果根节点的right不是减号节点说明左结合正确。从那以后我每次改完Parser都先跑一遍减法用例。5. lookahead预读的Token在报错时被吞掉现象错误信息指向的位置和真实错误隔了一行或者报错时已经跳过一个关键Token。原因match失败时先advance()再抛错误预读的Token被消费掉了错误处理里又尝试回退但Lexer没有提供pushback能力只能干瞪眼。解决match里的逻辑一定是先检查后推进。错误信息用当前lookahead的行列号拼出来不要再动游标。如果做了错误恢复跳过确保跳过的逻辑不会反复消费同一个Token。还有个小细节Windows下双击运行exe报缺少VCRUNTIME140.dll时别急着改代码这是没装VC Redistributable运行库和工程本身没关系。6. 进阶用法把语法树输出成四元式验证分析器正确性6.1 把AST打印成缩进树语法分析器跑通后我还建议做一步树结构可视化。一个简单的缩进打印就能看出结合性和优先级void dumpTree(std::shared_ptrASTNode node, int depth) { if (!node) return; for (int i 0; i depth; i) std::cout ; std::cout node-type node-value std::endl; dumpTree(node-left, depth 1); dumpTree(node-right, depth 1); }对10 20 * (3 - 1)执行后输出能清楚看到根是op 右子树是op *而*的右子树是op -。这比任何调试器都直观也是答辩时讲左结合最有力的证据。6.2 从AST生成四元式更进阶的验证方式是生成四元式因为它要求你正确遍历二叉树并分配临时变量。叶子节点直接返回自己的值op节点先递归左右子树再把结果拼成一条四元式// 返回该子树结果的临时变量名 std::string genIR(std::shared_ptrASTNode node, int temp) { if (!node) return ; if (node-type num || node-type id) { return node-value; } std::string left genIR(node-left, temp); std::string right genIR(node-right, temp); std::string t t std::to_string(temp); std::cout t left node-value right std::endl; return t; }temp就是临时变量计数器每生成一条四元式就自增一次。我习惯把四元式输出和人工手算的结果对拍10 20 * (3 - 1)应该得到三条先算t0 3 - 1再算t1 20 * t0最后t2 10 t1。如果顺序不对说明AST层级的构建有偏差往回查文法比查代码更快。从那以后我每次做完词法和语法分析器都强制自己走一遍“Token流dump → AST缩进树 → 四元式输出”三段对拍这个习惯帮我挡掉了好几次状态机回归的翻车——每次改动完哪怕只是加一个关键字也要全流程重跑一遍。希望帮到你。本文还有配套的精品资源点击获取
