编译原理实验C++实现：词法分析、语法分析与中间代码生成

简介面向杭电编译原理课程实验的配套源代码包覆盖词法分析、非确定到确定自动机的子集构造、递归下降分析与LL(1)语法分析四个核心模块适合正在学习编译器构造的学生对照实践。资源共11个文件其中C源文件与可执行程序各4个另有文本说明和SysY测试样例包体仅334KB轻量易读。已有1605人访问学习。通过阅读源码可掌握SysY语言词法分析器中八进制、十六进制常量的识别方法以及块注释与行注释两种格式的处理逻辑子集构造部分展示NFA到DFA的转换实现递归下降分析模块提供典型的递归子程序框架LL(1)部分则体现预测分析表驱动的解析过程。可执行文件便于直接运行验证测试输出文本有助于对比结果整体适合课内作业参考与考前复习。1. 编译原理实验源代码先把课程实验的边界说清楚再决定怎么写“编译原理实验 杭电 源代码 C”这个标题背后是一套用 C 写的编译原理课程实验代码覆盖词法分析、语法分析、语义分析与中间代码生成。杭电这类学校的编译原理课普遍把实验拆成三次上机加一次综合设计源码工程要能一个命令编译、三个模块顺序执行、最后输出可读的中间代码文件。我见过太多人从各种渠道拿到“完整源码”却跑不出老师给的测试点原因基本不是算法不会而是代码组织和边界处理出了问题。这篇笔记就按我做这类实验的路径来讲工程怎么搭、词法状态机怎么写、递归下降怎么保证不崩以及哪些地方最容易让测试点翻车。适合理工科正在赶实验的学生也适合毕业设计选了编译器方向、打算拿现成框架改一版的人。2. C 工程骨架源码阅读器、Token 定义与三个模块的分工2.1 目录怎么分头文件、实现、测试数据各归其位课程实验代码最忌讳把所有内容塞进一个 main.cpp。编译原理实验天然分三个阶段词法分析输出 Token 流语法分析消费 Token 流语义分析和中间代码生成挂在语法动作里。按阶段分目录后续查错会省很多时间。我一般用这样的结构compiler-lab/ ├── CMakeLists.txt # 用 CMake 组织构建 ├── include/ │ ├── source.hpp # 源码字符流读取器 │ ├── token.hpp # Token 类型与结构 │ ├── lexer.hpp # 词法分析器 │ ├── parser.hpp # 递归下降语法分析器 │ └── symtab.hpp # 符号表 ├── src/ │ ├── source.cpp │ ├── lexer.cpp │ ├── parser.cpp │ └── symtab.cpp ├── tests/ │ ├── case01_basic.txt # 最小测试用例 │ └── case02_expr.txt └── output/ ├── tokens.txt # 词法输出 └── quads.txt # 四元式输出这样划分的理由很直接词法分析器只依赖 source.hpp不碰语法分析的任何头文件语法分析器只消费 Token不关心 Token 是怎么扫描出来的。依赖单向流动哪个模块崩了直接看对应目录下的实现。CMakeLists 里只需要把 src 下的 cpp 全部编进来测试用例放在 tests 目录输出统一进 output 目录避免可执行文件和工作目录混在一起导致相对路径读不到文件。2.2 先写 SourceFile 而不是直接写 Lexer行号、列号与 unread 的现实理由很多课程实验代码把文件读进一个 string然后 Lexer 直接按下标取字符。这种做法在报错阶段会很难受语法分析报错要定位到第几行第几列如果字符串里没有行号索引就得每次从头数换行符。所以代码的第一步是写一个带行号、列号维护的源码读取器这是我做这类实验时第一个落地的东西。// src/source.cpp #include source.hpp #include fstream #include stdexcept bool SourceFile::open(const std::string path) { std::ifstream in(path, std::ios::binary); if (!in) return false; buffer_ std::string((std::istreambuf_iteratorchar(in)), std::istreambuf_iteratorchar()); pos_ 0; line_ 1; col_ 1; return true; } char SourceFile::next_char() { if (pos_ buffer_.size()) { return EOF; // 文件结束统一返回 EOF不抛异常 } char c buffer_[pos_]; if (c \n) { line_; // 只有在真正消费换行符时更新行号 col_ 1; } else { col_; } return c; } void SourceFile::unread_char() { if (pos_ 0) return; char c buffer_[--pos_]; if (c \n) { line_--; // 回退时同步恢复行号 col_ 1; } else if (col_ 1) { col_--; } }读取器只干三件事逐字符读取、记录当前位置、支持回退一个字符。回退功能在词法分析里几乎是刚需因为识别完一个标识符或数字后总会多读一个不属于当前 Token 的字符需要放回去。这里有个细节unread_char 必须同步回滚行号和列号否则回退到换行符前面的字符后行号会多算一行。我也见过直接在 next_char 里做行号累计、但 unread 不处理行号的做法报错信息错得莫名其妙排查起来非常折磨。2.3 用什么 C 版本C17 顺手老机房则退到 C98C 标准的选择直接影响代码写法。如果可以自由选择我建议直接用 C17理由有三个std::string_view做 Token 文本引用性能好且不拷贝结构化绑定让遍历符号表更清爽if constexpr没必要但在实验里可以用来处理泛型打印逻辑。但很多学校的实验机房还是老版本编译器甚至 Dev-C 5.x 默认走 C98这种情况就不要硬上 C17 特性否则编译报错一堆浪费一个晚上。# CMakeLists.txt 中指定标准两个版本都能跑 set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON)如果必须要兼容老环境代码里避开std::string_view统一用const std::string传参能不用auto就不用避免老编译器对类型推导的兼容性问题。有一点要提醒实验代码的目标不是写出多现代的 C而是稳定复现教材里的编译过程。清华版编译原理教材第三版是理论依据实验代码的每个模块几乎都能在教材里找到对应算法把教材里的数据结构翻译成 C 类比从零设计一套精妙的架构更稳妥。3. 词法分析器用一手状态机替代正则库才能对得上测试点3.1 Token 设计与类型枚举做完词法分析后面所有阶段都只认 Token词法分析器的输出是 Token 流Token 的结构决定了后面语法分析怎么写。课程实验里 Token 不需要很复杂核心字段就四个类型、文本、行号、列号。行号和列号必须保留语法分析报错、老师核对测试点都要用。// include/token.hpp #ifndef TOKEN_HPP #define TOKEN_HPP #include string enum class TokenType { IDENT, // 标识符 INTEGER, // 整型字面量比如 123 KEYWORD, // 保留字比如 int、if OP, // 运算符比如 - * / DELIM, // 界符比如 ; ( ) { } EOF_TOKEN // 文件结束标志 }; struct Token { TokenType type; std::string text; int line; int col; std::string type_name() const { switch (type) { case TokenType::IDENT: return IDENT; case TokenType::INTEGER: return INTEGER; case TokenType::KEYWORD: return KEYWORD; case TokenType::OP: return OP; case TokenType::DELIM: return DELIM; case TokenType::EOF_TOKEN: return EOF; } return UNKNOWN; } }; #endif把 KEYWORD 单独列出来而不是让词法分析直接返回 IDENT是因为语法分析阶段要频繁判断“当前 Token 是不是 if”“是不是 int”有了独立类型匹配函数可以少写一个字符串比较。这里的取舍是Token 文本直接拷贝一份 string 还是保存源码里的区间引用课程实验规模小直接拷贝就行不必用 string_view 做优化代码更直观。3.2 手工状态机扫描一个循环吃遍所有字符识别标识符和整型字面量是词法分析最核心的部分。常见做法是手写状态机不用正则库的原因是库的行为和老师期望的识别规则常有出入测试点一跑就暴露差别。核心扫描逻辑长这样// src/lexer.cpp bool Lexer::next(Token tok) { skip_whitespace_and_comments(); // 跳过空白与注释 int start_line reader_.line(); int start_col reader_.col(); char c reader_.next_char(); tok.line start_line; tok.col start_col; tok.text.clear(); if (c EOF) { tok.type TokenType::EOF_TOKEN; return false; } // 标识符或保留字字母或下划线开头 if (std::isalpha(static_castunsigned char(c)) || c _) { do { tok.text.push_back(c); c reader_.next_char(); } while (std::isalnum(static_castunsigned char(c)) || c _); reader_.unread_char(); // 多读的字符放回去 tok.type is_keyword(tok.text) ? TokenType::KEYWORD : TokenType::IDENT; return true; } // 整型字面量数字开头 if (std::isdigit(static_castunsigned char(c))) { do { tok.text.push_back(c); c reader_.next_char(); } while (std::isdigit(static_castunsigned char(c))); reader_.unread_char(); tok.type TokenType::INTEGER; return true; } // 运算符与界符走同一分支双字符运算符需要向前看一位 return scan_operator_or_delim(c, tok); }这段逻辑要做两件事识别 Token 并设置正确的行号和列号以及管理字符回退。注意标识符循环结束后那个 unread_char因为 while 条件里多读的字符不属于当前 Token必须放回缓冲区否则下一个 Token 会丢掉第一个字符。整型字面量同样处理。start_line 和 start_col 在扫描开始前记录Token 内部保存的是起始位置这对语法分析定位错误很有用。3.3 运算符与双字符运算符向前看一位就能避开匹配陷阱运算符里面最容易出问题的是双字符运算符和、和看起来相似语义完全不同。扫描到第一个字符后要向前看一个字符决定是单字符还是双字符 Token。我用一个分支函数处理// src/lexer.cpp bool Lexer::scan_operator_or_delim(char c, Token tok) { char next reader_.next_char(); bool is_double false; // 双字符运算符的候选组合 if ((c next ) || (c ! next ) || (c next ) || (c next ) || (c next ) || (c | next |)) { is_double true; } if (is_double) { tok.text.push_back(c); tok.text.push_back(next); tok.type TokenType::OP; return true; } // 单字符运算符或界符 if (next ! EOF) { reader_.unread_char(); // 不是双字符放回 next } tok.text.push_back(c); tok.type is_operator(c) ? TokenType::OP : TokenType::DELIM; return true; }这里有个边界情况很阴文件末尾只有一个next_char 返回 EOF此时不能直接 unread否则缓冲区下标会被改乱。我加了个next ! EOF判断EOF 不进入回退分支。测试点如果包含这类合法单字符运算符代码走正常的放回逻辑没有任何问题。4. 递归下降语法分析文法消除左递归、语义动作与符号表同步做4.1 消除左递归为什么直接按教材文法写会栈溢出递归下降分析器要求文法不含左递归。教材里表达式的经典文法E - E T | T直接翻译成函数会无限递归直到栈溢出。必须先把文法改写成等价的右递归或迭代形式。我最常给实验用的表达式文法如下expr - term { (|-) term } term - factor { (*|/) factor } factor - INTEGER | IDENT | ( expr )这个文法用花括号表示循环对应到递归下降代码里就是一个 while。它的巧妙之处在于优先级通过“层”体现expr 层处理加减term 层处理乘除factor 层处理括号和原子项。消除左递归后每个非终结符对应一个解析函数函数间互相调用形成下降路径输入串从左到右扫描一遍即可完成语法检查。// src/parser.cpp bool Parser::parse_expr() { if (!parse_term()) { return error(表达式缺少操作数, peek()); } while (match_op() || match_op(-)) { std::string op previous().text; // 记录当前运算符 if (!parse_term()) { return error(运算符后缺少操作数, peek()); } do_semantic_action(BINOP, op, temp_var()); // 生成四元式 } return true; } bool Parser::parse_term() { if (!parse_factor()) { return error(term 层无法解析, peek()); } while (match_op(*) || match_op(/)) { std::string op previous().text; if (!parse_factor()) { return error(运算符后缺少因子, peek()); } do_semantic_action(BINOP, op, temp_var()); } return true; } bool Parser::parse_factor() { if (match(TokenType::INTEGER) || match(TokenType::IDENT)) { return true; } if (match_op(()) { if (!parse_expr()) return false; if (!match_op())) { return error(缺少右括号, peek()); } return true; } return error(无法识别的因子, peek()); }每个函数的结构高度一致先判断当前 Token 是否是该层能处理的起始符号然后循环处理后续操作符。令牌匹配用 match 和 match_op 两个函数match 成功就消费 Token 并返回 true失败则不动 Token。这样一套实现下来错误恢复策略也简单在某个层解析失败就立即返回由上层决定是否终止还是尝试其他分支。递归下降代码的调试效率远高于查 LL(1) 分析表这也是这类实验普遍选择它的原因。4.2 四元式输出语义动作和语法分析同步做中间代码生成在课程实验里一般用四元式表示四元式的四个字段是操作符、左操作数、右操作数和结果。语法分析过程中每遇到一个运算符就调用一次语义动作生成一条四元式并写入文件。这样做的好处是语法分析结束后中间代码文件也有了不需要再遍历一遍语法树。// src/parser.cpp void Parser::do_semantic_action(const std::string op, const std::string arg1, const std::string arg2, const std::string result) { quads_.push_back({op, arg1, arg2, result}); } std::string Parser::temp_var() { return t std::to_string(temp_counter_); }对于a b * c这样输入语法分析生成的四元式序列一般是先处理 b * c 生成临时变量 t0再处理 a t0 生成 t1。这个结果和教材里的中间代码示例一致测试点核对的就是这种格式。四元式最好用定长结构体存储输出时按固定格式打印。每个临时变量用一个计数器生成保证名字不冲突。4.3 符号表实验规模不需要哈希表线性查找反而更方便符号表的实现选型常被过度设计。课程实验的源码文件一般只有几百行符号数量在几十到几百个之间用std::unordered_map反而会丢失符号的声明顺序而实验报告经常要求“按声明顺序输出符号表”。我一般用 vector 加线性查找// src/symtab.cpp int SymTab::lookup(const std::string name) { for (size_t i 0; i entries_.size(); i) { if (entries_[i].name name) { return static_castint(i); } } return -1; } int SymTab::insert(const std::string name, const std::string type) { // 如果已经存在返回原下标否则追加一条 int idx lookup(name); if (idx 0) return idx; entries_.push_back({name, type, /* line */ 0}); return static_castint(entries_.size() - 1); }线性查找的复杂度是 O(n)对实验规模来说完全够用。处理变量重复声明很直接插入前先查一遍已存在且同作用域就报语义错误否则正常追加。符号表行号字段在构造时记录后续查错可以直接引用到源码行。这里要跟写哈希表的同学说一句实验报告不需要你在复杂度上体现优越感稳定可复现的结果才是得分关键。5. 编译原理实验避坑记录死循环、错位行号与悬垂 else5.1 一跑测试点就卡死任务管理器里 CPU 拉满现象词法分析器处理含中文注释或非法字符的源码时程序完全无响应。原因扫描遇到不认识的字符代码没有消费它就直接返回外层循环反复调用 next 得到同一个非法字符形成死循环。解决在 Lexer 主循环里加一个 default 分支遇到任何类型都匹配不上的字符记录错误信息并强制读取下一个字符保证循环必然推进。// src/lexer.cpp // 默认分支非法字符强制消费避免死循环 { error_list_.push_back(无法识别的字符: std::string(1, c)); tok.type TokenType::IDENT; // 给一个无害的兜底类型 tok.text ERROR; return true; // 已经用掉一个字符下次必然前进 }这个 fix 的价值在于把“分析器遇到未知输入”从行为不确定变成行为确定。错误收集在 error_list_ 里最后统一输出不会漏报也不会卡死。我做实验时第一次遇到这种情况怀疑是自己的状态机逻辑错了排查了半天才发现是注释里的中文字符被逐字节读出来没有匹配分支。5.2 报错信息里行号永远是 1或者错位到完全对不上现象词法分析报错永远指向第一行语法分析报错位置离谱。原因大多数情况下是 unread_char 回退时没有恢复 line 和 col或者 token 行号在扫描过程中被后续字符更新覆盖了。解决在 Token 结构里line 和 col 在扫描开始前就固定记录后续无论读多少字符都不改动。我的代码里 start_line 和 start_col 用局部变量保存然后只赋值一次后续字符的读取完全不碰这两个变量。// src/lexer.cpp int start_line reader_.line(); int start_col reader_.col(); // 扫描过程中 reader_ 的 line / col 会变但 start_* 不会 tok.line start_line; tok.col start_col;如果你发现报错行号差一行多半是文件末尾多了一个换行符或者 windows 的 \r\n 被当成两个字符处理。在 open 阶段把 \r 过滤掉可以让行号统计只依赖 \n处理跨平台文件更可靠。5.3 悬垂 elseif 的匹配和你想要的不一样现象语法分析对if (a) if (b) c 1; else d 2;的处理else 跟了内层 if但语义分析阶段属性计算出来结果不对。原因递归下降天然最内层匹配else 总是结合最近的 if这是很多程序语言的设计选择符合 C 标准行为但如果你没在文法里显式定义考试题和实验报告里的解释要自洽。解决实验场景下明确采用最近匹配策略在代码注释里写清楚然后在报告里说明这是递归下降实现方式的自然行为不做特殊处理。// src/parser.cpp // 最内层匹配else 优先绑定最近的未匹配 if // 这是递归下降实现的自然语义无需额外栈结构 if (match(TokenType::KEYWORD, if)) { if (!parse_expr()) return false; if (!match_op())) return error(if 条件缺少右括号, peek()); if (!parse_statement()) return false; if (match(TokenType::KEYWORD, else)) { if (!parse_statement()) return false; } return true; }这段代码刻意没有做悬垂 else 修正是推荐做法。因为多数课程实验不要求 else 绑定规则可配置保持最内层匹配反而和 C 实际行为一致报错概率更低。5.4 123abc 被整体识别还是拆开识别测试点说了算现象输入int a 123abc;有的实现报词法错误有的实现拆分出123和abc还有的完全卡住。原因数字扫描结束后遇到字母不同的实验指导书要求不同。常见做法是拆开词法分析阶段不检查这种跨类别粘连交给语法分析去报错。解决数字扫描后多读的字母放回缓冲区让下一个 Token 从字母开始识别这样错误定位在语法分析阶段也更准确。// src/lexer.cpp // 数字后紧跟字母把字母放回去拆分处理 if (std::isalpha(static_castunsigned char(c))) { reader_.unread_char(); // 让字母成为下一个 Token 的开头 }但要注意有些测试点明确要求报“非法标识符”错误拆分会直接导致测试点判错。看清实验指导书再决定拿不定的情况在报告里写清楚你的处理方式一般不会被扣分。5.5 注释跨行导致 token 错乱现象/* 注释里包含换行符注释结束后 parser 报错位置偏移。原因跳过注释时直接把换行符丢弃但行号没有同步更新。解决在 skip_whitespace_and_comments 里遇到注释内容时逐字符读入并调用 reader_ 自己的 next_char让行号统计自然推进而不是用整行字符串处理。// src/lexer.cpp void Lexer::skip_whitespace_and_comments() { for (;;) { char c reader_.peek_char(); if (c || c \t || c \n || c \r) { reader_.next_char(); // 消费行号由 reader_ 维护 continue; } if (c / reader_.peek_next_char() /) { while (reader_.peek_char() ! \n reader_.peek_char() ! EOF) { reader_.next_char(); } continue; } if (c / reader_.peek_next_char() *) { reader_.next_char(); // 消费 / reader_.next_char(); // 消费 * while (true) { char ch reader_.next_char(); if (ch EOF) break; // 注释未闭合直接终止 if (ch * reader_.peek_char() /) { reader_.next_char(); break; } } continue; } break; } }块注释内部的所有换行都会经过 next_char 正常更新行号注释结束后行号是准确的。未闭合注释在 EOF 处自然终止不会造成死循环也能在错误报告里给出提示。6. 提交前的最后一道工序Token 转储、最小测试集与二分定位6.1 写一个 Token 转储工具肉眼对账词法分析器的调试手段里最直接的不是断点而是把 Token 流转储成文件一行一个 Token对照源代码逐行读。格式固定为“行号: 类型(文本)”这样一眼能看出遗漏、多余或者位置错位。// src/dump_tokens.cpp #include lexer.hpp #include iostream #include fstream int main(int argc, char* argv[]) { if (argc 3) { std::cerr 用法: dump_tokens 输入文件 输出文件\n; return 1; } SourceFile src; if (!src.open(argv[1])) { std::cerr 无法打开输入文件\n; return 1; } Lexer lexer(src); Token tok; std::ofstream out(argv[2]); while (lexer.next(tok)) { out tok.line : tok.type_name() ( tok.text )\n; } return 0; }转储文件的价值在于语法分析出错时直接打开 tokens.txt 看当前位置前后的 Token就能判断是词法阶段丢了字符还是语法阶段匹配逻辑写错。我每次改完词法分析器都先跑一遍 dump和手写期望对比对账通过才继续做语法分析。6.2 最小测试集五个用例覆盖 90% 的边界不需要准备几十个测试文件五个精心设计的用例比一大摞乱写的输入更有用。我的最小测试集是这样设计的case01_empty.txt 空文件期望词法输出 EOF不崩溃 case02_comments.txt // 单行注释 /* 跨行 注释 */ int a; case03_identifiers.txt int abc 10; int _tmp abc 20; case04_operators.txt a b c; d e f; g h i; case05_error.txt int 123abc; if (a ) b 1; else c 2;每个文件对应一类风险空文件验证初始化注释验证行号与跳过逻辑标识符验证下划线和关键字查表运算符验证双字符识别错误输入验证非法行为能报错不死循环。五个用例全部通过测试点大概率不会出大问题。如果某个用例行为怪异先用 dump 工具看 Token 流再定位到对应函数。6.3 二分定位把“全崩”变成“这条规则崩”最后一个技巧来自我自己的血泪经验语法分析全盘报错时不是检查整个 parser而是用“裁剪输入”的方式定位。把一个复杂测试用例按行注释掉一半如果错误消失说明问题在注释掉的那一半里保留问题一半继续注释掉一半几次下来就能定位到具体表达式。这套方法本质上和 git bisect 找回归是同一个思路但用在不支持版本回退的实验代码上更直接。我习惯在每次修改后跑一遍最小测试集确认没有引入新问题再继续加功能。给初学者的最后一个建议不要急着把所有模块一次写完。先跑通词法dump 出正确的 Token 流再写语法。每完成一层都落一次盘这样最后即使做不完语义分析前面两层的得分也保住了。文本输出用固定格式行号和列号对齐这是我在做这类实验时最值得的一个习惯。希望帮到你。本文还有配套的精品资源点击获取