C++手写小型编译器课设：词法分析、递归下降与四元式生成

简介面向计算机专业本科生的编译原理课程设计与实验资料包覆盖从词法分析到汇编代码生成的完整实现包含词法分析、语法分析、中间代码生成及小型编译器设计等核心任务。内含词法分析器、LL(1)方法分析简单语句如ii*i、LR(0)与SLR(1)方法语法分析、四元式生成、汇编代码生成并附带一份小型编译器课程设计报告方便对照实验要求与报告撰写。压缩包共十四个文件包括四个cpp、三个c、三个h源程序三个txt文本一份doc课程设计报告整体仅557KB轻量易读。资源中还提供部分LL(1)文法和SLR(1)文法便于理解从文法定义、分析表构造到语法分析的全过程对掌握自顶向下与自底向上分析方法很有帮助。目前已有2349人学习适合正在进行编译原理课程设计、实验复习或需要完整代码范本的学生参考。1. 一个小型编译器课设仓库词法分析到实验报告一步到位编译原理课程设计这关每年都能劝退一批人文法推导背得明白但真要手写一个能识别int a 1 2 * 3;的小型编译器大多数人卡在第一步——词法分析里2*3到底该切成几个 Token浮点数和关键字怎么区分报错时行号为什么总是往后偏一行。这个资源围绕“从零手写一个最小可用的编译器”组织词法分析、语法分析、中间代码生成三大模块全部用 C 手工实现不依赖 flex/bison 这类生成器附带的实验报告和测试用例可以直接用于课程设计答辩。它的设计思路和国内多数教材的编译原理课设要求高度吻合适合作为二次开发的底子也适合抄骨架后替换成自己的文法。2. 项目总体设计从字符流到四元式的完整链路2.1 仓库布局与工程入口把源码包解压后目录结构很清爽没有把一堆 CMake 缓存和构建产物混进来。仓库按模块分离每个目录职责单一compiler-tiny/ ├── include/ │ ├── lexer.h # 词法分析器接口 │ ├── parser.h # 语法分析器接口 │ ├── ast.h # 抽象语法树节点定义 │ └── codegen.h # 四元式生成器接口 ├── src/ │ ├── main.cpp # 驱动入口串联各阶段 │ ├── lexer.cpp # 词法分析实现 │ ├── parser.cpp # 递归下降语法分析实现 │ ├── ast.cpp # AST 构建与打印 │ └── codegen.cpp # 四元式生成实现 ├── tests/ │ ├── case_01.txt # 简单赋值语句 │ ├── case_02.txt # 嵌套算术表达式 │ └── case_03.txt # 含变量的表达式 ├── docs/ │ ├── 实验报告模板.md │ └── 设计说明.md ├── Makefile └── README.md各模块的依赖方向是单向的main调lexer得到 Token 流再喂给parser生成 AST最后codegen遍历 AST 产出四元式。我在做课设时习惯把接口头文件和实现分开这样写测试的时候可以直接只链接lexer.o不用把语法分析一起编译进来排查问题快很多。编译入口是根目录的Makefile标准的make即可。目标产物只有一个可执行文件运行参数是源码文件路径输出在终端逐行打印 Token 序列和四元式列表这样验收时能把“中间过程”直接摆到老师面前。2.2 词法分析器的 Token 设计与状态划分词法分析器要处理的符号集合不大整数、标识符、关键字int、return、if、四则运算符、赋值号、括号和分号。头文件里定义的核心数据结构如下// include/lexer.h enum TokenType { TOK_IDENT, // 标识符 TOK_INT, // 整数字面量 TOK_KEYWORD, // 关键字 TOK_OP, // 运算符 - * / TOK_ASSIGN, // 赋值号 TOK_LPAREN, // ( TOK_RPAREN, // ) TOK_SEMI, // ; TOK_EOF // 结束标记 }; struct Token { TokenType type; std::string text; int line; // 行号从 1 开始 int col; // 列号从 1 开始 };line和col看着不起眼真正写报错提示时帮了大忙。词法分析器维护一个输入缓冲区和一个游标pos外层循环每次调用nextToken()就消费一段字符并返回一个 Token。判断依据是先扫字符类型数字开头进数字识别路径字母或下划线开头进标识符路径其余按单字符映射到运算符或分隔符。这个实现没有用状态表驱动直接基于分支扫描对小型文法语料完全够用。一个容易漏掉的点——空白和注释的过滤。我在这里加了个skipWhitespace()遇到空格、\t、\n就跳过并更新行号计数注释则要识别//到行尾。跳过逻辑里最需要注意的就是换行符必须递增line否则后续语法分析的报错行号全错。2.3 语法分析器用递归下降处理表达式文法语法分析是手写递归下降处理的文法简化成经典 EBNFprogram : statement_list statement : int IDENT expression ; expression : term (( | -) term)* term : factor ((* | /) factor)* factor : INTEGER | IDENT | ( expression )递归下降对初学者比较友好每个非终结符对应一个同名函数函数体内按产生式右侧的符号顺序调用其他非终结符函数或匹配终结符。解析1 2 * 3时函数调用栈会天然形成expression - term - factor的层级优先级通过层级体现——乘法在term层先被匹配所以它绑得更紧。为了避免左递归代码里全部换成了右递归或循环改写。比如expression内部先parseTerm()拿左操作数再循环判断下一个 Token 是不是或-是就继续取右操作数。每次结合运算时创建一个BinOpNode左右子节点挂好返回值给上层。AST 节点类型只保留三种数字节点、变量节点、二元运算节点。结构定义如下// include/ast.h struct ASTNode { enum NodeKind { NUM_NODE, IDENT_NODE, BINOP_NODE } kind; int intValue; // NUM_NODE 时的值 std::string name; // IDENT_NODE 时的名称 Token op; // BINOP_NODE 的运算符 ASTNode* left; ASTNode* right; };语法分析完成后整个源文件变成一棵 AST。codegen遍历这棵树生成四元式每一步运算产出一条(op, arg1, arg2, result)记录结果全部用临时变量t1、t2承接。2.4 驱动流程与输出设计main.cpp里的驱动流程不复杂但把各阶段串得很清楚// src/main.cpp 核心流程 int main(int argc, char* argv[]) { Lexer lexer(argv[1]); Parser parser(lexer); ASTNode* root parser.parseProgram(); std::cout Token 序列 std::endl; lexer.dumpTokens(); std::cout \nAST 结构 std::endl; root-dump(); CodeGen gen; std::cout \n四元式 std::endl; gen.generate(root); gen.dumpQuads(); return 0; }注意这里 Token 序列先被Parser消费了一遍再dumpTokens输出顺序上没问题因为词法分析的 Token 流是一次性全部产出并缓存的。这种做法比流式逐个读取的实现在调试时方便很多——你能同时看到输入、Token 列表和最终的语法树三个视图对照着定位。3. 核心代码走读手写词法分析与递归下降的落地细节3.1 词法分析分支跳转与数值识别词法分析器的主扫描函数是nextToken。这里贴出关键实现// src/lexer.cpp 核心扫描逻辑 Token Lexer::nextToken() { skipWhitespaceAndComments(); // 过滤空白与注释维护 line/col Token tok; tok.line currentLine; tok.col currentCol; char c peek(); if (c \0) { tok.type TOK_EOF; tok.text EOF; return tok; } if (isdigit(c)) { return readNumber(); // 识别连续数字并转 int } if (isalpha(c) || c _) { return readIdentifier(); // 标识符遇到关键字转为关键字类型 } advance(); tok.text std::string(1, c); switch (c) { case : tok.type TOK_OP; break; case -: tok.type TOK_OP; break; case *: tok.type TOK_OP; break; case /: tok.type TOK_OP; break; case : tok.type TOK_ASSIGN; break; case (: tok.type TOK_LPAREN; break; case ): tok.type TOK_RPAREN; break; case ;: tok.type TOK_SEMI; break; default: error(无法识别的字符); } return tok; }这段代码的核心思路是“按首字符决定扫描路径”。peek()只查看当前字符不移动游标advance()移动并更新行列号。“连续吞字符”这类操作在readNumber里更典型Token Lexer::readNumber() { Token tok; tok.line currentLine; tok.col currentCol; int value 0; while (isdigit(peek())) { value value * 10 (advance() - 0); // 边消费边累计 } tok.type TOK_INT; tok.text std::to_string(value); tok.intValue value; return tok; }这里的advance()返回被消费字符的 ASCII 码所以advance() - 0能直接拿到数值。readNumber没有处理负数——负号在语法层由上下文解决词法层只认正整数。实现里有个小细节遇到123abc这种输入目前会报错而不是只读123。我建议保持这个严格行为课设验收时这算“错误检测能力”的加分项。readIdentifier里除了收集字符还要查关键字表。源代码里维护一个std::unordered_setstd::string存{int, return}命中即把 Token 改成TOK_KEYWORD。这个查表动作很便宜别忘了在识别完标识符后做一次判断。3.2 语法分析递归下降函数的层次调用语法分析器核心是parseExpression和parseTerm的分层结构// src/parser.cpp 表达式与项 ASTNode* Parser::parseExpression() { ASTNode* left parseTerm(); while (lookahead.type TOK_OP (lookahead.text || lookahead.text -)) { Token op lookahead; advance(); ASTNode* right parseTerm(); left new BinOpNode(op, left, right); } return left; } ASTNode* Parser::parseTerm() { ASTNode* left parseFactor(); while (lookahead.type TOK_OP (lookahead.text * || lookahead.text /)) { Token op lookahead; advance(); ASTNode* right parseFactor(); left new BinOpNode(op, left, right); } return left; }这个写法就是“优先级爬升”的简化版。parseExpression遇到的第一个节点来自parseTermparseTerm又先拿parseFactor于是1 2 * 3的 AST 必然是把乘法节点挂在加法节点的右子树上。左结合通过循环实现——1 2 3第一次循环生成(12)节点第二次循环把它作为新左操作数接到3于是 AST 向左倾斜符合预期。parseFactor则处理三种情况ASTNode* Parser::parseFactor() { if (lookahead.type TOK_INT) { Token num lookahead; advance(); return new NumNode(num.intValue); } if (lookahead.type TOK_IDENT) { Token id lookahead; advance(); return new IdentNode(id.text); } if (lookahead.type TOK_LPAREN) { advance(); // 跳过 ( ASTNode* inner parseExpression(); match(TOK_RPAREN); // 必须匹配右括号 return inner; } error(语法错误意外的 Token lookahead.text); }match(TOK_RPAREN)这个动作很关键它先检查当前 Token 类型匹配才消费不匹配就调用error()并直接终止。语法错误的行号和列号在error()中从 Token 结构里取出这就是词法分析维护line/col的回报。3.3 四元式生成遍历 AST 边计算边生成四元式生成在codegen.cpp中实现采用后序遍历——先处理子树再处理当前节点// src/codegen.cpp 后序遍历生成四元式 std::string CodeGen::generateExpr(ASTNode* node) { if (node-kind ASTNode::NUM_NODE) { std::string t newTemp(); quads.push_back(Quad(, std::to_string(node-intValue), , t)); return t; } if (node-kind ASTNode::IDENT_NODE) { std::string t newTemp(); quads.push_back(Quad(, node-name, , t)); return t; } // BINOP先递归生成左右子节点的临时变量 std::string l generateExpr(node-left); std::string r generateExpr(node-right); std::string result newTemp(); quads.push_back(Quad(node-op.text, l, r, result)); return result; }newTemp()内部用一个计数器生成t1、t2……这类临时名。四元式结构体Quad是一个四元组(op, arg1, arg2, result)。对比一下2 * 3被翻译成(*, 2, 3, t1)1 t1翻译成(, 1, t1, t2)。这里的函数命名很直白每个表达式都产出一个保存结果的临时变量然后把临时变量的名字返回给上层继续参与运算。你可以把这个临时变量理解为寄存器分配的简化版本。如果课设要求再做一层优化后续可以在这个环节做常量折叠——发现arg1是常量且arg2是常量时直接算出结果不再生成四元式。这个思路我没有写进源码留作二次开发方向后面专门提。4. 避坑指北手写编译器时翻过的五个典型问题4.1 Token 行号错位语法报错全指向下一行现象输入文件里第 2 行出错报错信息却标在第 3 行接着第 4 行出错又标到第 5 行。原因skipWhitespace在遇到\n时没有让currentLine自增。词法分析器把换行符当作普通空白跳过却没有同步维护行列信息。第一个换行走失后后面所有行号整体偏加一。解决每次消费\n必须让行号加一、列号归零。代码写在一处char c advance(); if (c \n) { currentLine; currentCol 1; } else { currentCol; }修复后错误定位基本一测一个准。这也是为什么我强烈建议词法分析器优先把 Token 全部缓存下来再进语法分析——先看一批 Token行号对不对一目了然。4.2 递归下降直接套用左递归文法程序栈溢出现象解析1 2时没有任何输出程序直接 segment fault。原因一开始我照书把表达式写成expression - expression term然后在函数里写// 错误示例左递归导致无限调用 ASTNode* parseExpression() { ASTNode* left parseExpression(); // 永远不可能返回 // ...后续永远到不了 }每次调用parseExpression都先调自己形成无终止的递归链栈爆掉。解决把左递归文法改写成循环形式。经典改写是expression - term ( term)*代码就是用 while 循环反复读取运算符和操作数。注意不是简单把递归调用改成迭代就行而是要认清“左结合”由循环维持不是靠递归。改完之后123能正常生成左倾 AST挂载顺序正确。4.3 优先级写反2 3 * 4算成 20现象语法分析能通过但四元式生成的结果是(, 2, 3, t1)然后(*, t1, 4, t2)最后算出 20 而不是 14。原因parseExpression里直接解析成平级链表——两个操作数都走parseFactor没有经过parseTerm层级。乘法的优先级一旦和加法同级文法就退化成了从左到右的简单运算。解决严格按 EBNF 分层。expression调用termterm调用factor乘除法在低层先终结所以它绑得更紧。这个坑的排查方式很简单看 AST 树形结构根节点是还是*。如果2 3 * 4的根节点是说明乘法已经在右子树里先结合优先级正确。4.4 错误处理只报一处连续错误全部吞掉现象文件里有三个语法错误只输出第一处修掉后又会冒出后面两处。课设验收时被追问“为什么不能一次全部指出错误”。原因语法分析器遇到第一个错误就调用error()抛异常控制流中断剩余 Token 不再检查。这是最简单的设计但不是最友好的。解决做一个轻量错误恢复——在parseExpression的循环里遇到错误 Token 时记录错误并尝试同步到下一个;分号处再继续解析catch (const CompileError e) { errors.push_back(e.what()); while (lookahead.type ! TOK_SEMI lookahead.type ! TOK_EOF) { advance(); } if (lookahead.type TOK_SEMI) advance(); // 跳过当前语句 }这个“跳到下一个分号”的策略对短语句很有效能恢复且不容易产生级联干扰。实现成本不高报告里还能多写一节“错误恢复策略”。4.5 变量越界读没有语义检查就直接生成中间代码现象int a; b a 1;四元式生成了(, a, , t1)但b根本没声明过执行阶段直接读到垃圾值。原因词法和语法都通过语法树没问题但语义层没有检查未声明变量。codegen 阶段对IDENT_NODE无条件生成取值四元式没验证变量是否存在。解决在语法分析和 codegen 之间加一个简单的符号表检查。用std::unordered_mapstd::string, int记录已声明的变量类型遍历 AST 时遇到标识符节点先查表未声明就报错;遇到int声明语句则插入符号表。这个检查放在parser里收尾处做一次几十行就能实现能挡住一部分运行期才暴露的问题。5. 二次开发把玩具编译器扩成能用的课设作品5.1 扩展点一:增加printf输出语句给文法加一条print_statement : print expression ;词法层把print关键字加进关键字表语法分析多写一个parsePrintStatement生成四元式时产出(print, temp, , )。这样程序就有输出了测试用例能验证每条语句的真实结果课设演示时效果提升明显。5.2 扩展点二常量折叠与死代码删除codegen 的generateExpr里加一个检查左右子树都是NUM_NODE时直接算结果不再生成四元式。这条优化在一本教材的“中间代码优化”章节里是必提的例子写进实验报告能体现“不只是把功能调通”的理解。5.3 扩展点三把 Token 流导出为 JSON改动点集中在 Lexer加一个dumpToJson()方法把 Token 的 type、text、line、column 序列化为 JSON 数组。有了 JSON就能用脚本做回归测试把tests/目录下的每个用例跑一遍并与期望四元式做 diff。从那以后我每次改语法规则都会强制走一遍全量用例的回归对比看到旧四元式被新四元式替换时能立刻判断出影响面而不是靠肉眼盯语法树。这几个方向的改动量都不大最大的收益是让你真正理解“语法分析和语义分析该怎么分层”。这套 C 源码结构留好了扩展位希望帮到你。本文还有配套的精品资源点击获取