简介面向北京邮电大学编译原理课程实验一的词法分析器实现材料适合计算机专业学生及编译原理初学者用于课程实验对照与扫描器入门练习。内容围绕词法规则定义、输入字符流处理、分词逻辑、符号栈管理与错误处理等环节展开可帮助读者理解如何将源代码字符序列识别为标识符、关键字、常量与运算符等词素并为后续语法分析学习打基础。压缩包共4个文件包含2个txt说明与测试文本、1个h头文件和1个cpp源文件整体约10KB体量轻便便于阅读和在本机实验中编译调试。已有1000人学习下载可作为课程实验的参考实现与排错思路来源用来核对规则设计、测试用例组织和边界情况处理提升词法分析器实现的完整性与规范性。1. 编译原理实验一这次遇到的第一个问题往往不是算法本身编译原理课程实验一通常是整门课的第一道难关也最容易被低估。要求写一个词法分析器把源程序字符流切成一个个 Token输出形如(种别码, 词素)的序列听起来半小时能写完真跑起来问题全在细节里注释没跳过把后面半行代码吃掉了1.5e-3被切成三个 Token行号整体错开一行跟助教给的标准输出逐行对不上。这份某高校编译原理课程实验一的词法分析器工程包把源文件读取、规则匹配、最长匹配回溯、符号表登记、错误定位这几件事串成了一条完整链路代码是能直接make出可执行文件的那种不是伪代码。它适合两类人一类是刚接触编译原理、要交实验又不想只交个能跑的壳子另一类是实验一已经过了想把它当实验二语法分析的输入层继续用。2. 项目结构与技术选型三条实现路线怎么选拿到一个词法分析器工程先别急着看main。要看的是它把“规则”和“扫描”分没分开——这两件事混在一个函数里实验二加两条规则就得重写一遍这是很多人后期返工的根源。这份工程包的结构比较克制目录层级不深但边界划得清楚。2.1 目录骨架把“能交作业”和“能接着做实验二”分开展开压缩包之后的目录大致是这样lexer-lab/ ├── include/ │ ├── token.h # TokenType 枚举 Token 结构体 │ ├── lexer.h # Lexer 类声明next() / peek() / reset() │ └── symbol_table.h # 符号表接口 ├── src/ │ ├── main.cpp # 命令行入口读文件 → 循环取 Token → 打印 │ ├── lexer.cpp # 规则表 扫描主循环 注释跳过 │ ├── symbol_table.cpp # 哈希索引 线性存储 │ └── error.cpp # 错误收集与格式化输出 ├── tests/ │ ├── case01_basic.c │ ├── case02_number.c │ ├── case03_comment.c │ ├── case04_invalid.c │ └── expected/ # 每个用例对应的期望输出 ├── Makefile └── README.mdtoken.h单独拆出来是有讲究的。实验二做语法分析时Token是两边共用的数据结构如果它藏在lexer.cpp里语法分析器要么#include一个.cpp要么复制一份枚举——两种做法后面都会让你想给自己寄刀片。error.cpp独立也是同样的思路错误收集器在词法阶段只往里塞记录真正决定“遇错是继续还是退出”的是main这样调试时可以把错误全打出来而不是遇到第一个非法字符就exit(1)让你完全看不到后面还有多少问题。tests/expected/这个目录决定了这个工程是“作业”还是“项目”。有期望输出你改完规则表跑一条diff就知道有没有回归没有期望输出每次改完只能靠肉眼扫几百行早晚出错。2.2 三条实现路线正则表驱动、NFA→DFA、手写状态机课程实验一的实现方式基本逃不出这三种工程包里优先走的是第一条但另外两条的代码也留了痕迹因为实验报告里老师经常要求画出状态转换图。路线实现成本报告友好度运行速度适合场景std::regex表驱动低加规则只改一行中慢每个 Token 跑一遍全表规则少、以交作业为主正规式 → NFA → DFA高要写子集构造高能画图能写推导快查表 O(1)老师明确要求状态图手写状态机中数字和注释要单独写中最快后面还要接语法分析表驱动的好处是“规则即数据”加一个关键字就是往数组里多写一行改错成本极低坏处是std::regex在-O2下依然不快一万行的源文件能跑出秒级延迟虽然实验数据量根本到不了这个量级。真正正统的做法是子集构造把每条正规式先转成带 ε 边的 NFA再合成一个 DFA最后把 DFA 落成二维转移表。用 Python 写这段特别直观很多人的实验报告里贴的就是这一版def closure(states, nfa): 求 ε-闭包从 states 出发只走 ε 边能到达的全部状态 stack, seen list(states), set(states) while stack: s stack.pop() for t in nfa.eps.get(s, ()): # eps[s] 是 s 的 ε 后继集合 if t not in seen: seen.add(t) stack.append(t) return frozenset(seen) def move(states, ch, nfa): 从 states 出发吃掉一个字符 ch 后能到达的状态集合 return frozenset(t for s in states for t in nfa.trans.get((s, ch), ())) def subset_construction(nfa): start closure({nfa.start}, nfa) dfa_id, queue, trans {start: 0}, [start], {} while queue: cur queue.pop(0) for ch in nfa.alphabet: # 字母表 所有规则里出现过的字符 nxt closure(move(cur, ch, nfa), nfa) if not nxt: # 空集就是死状态直接丢掉 continue if nxt not in dfa_id: dfa_id[nxt] len(dfa_id) queue.append(nxt) trans[(dfa_id[cur], ch)] dfa_id[nxt] accept {dfa_id[s]: nfa.accept_of(s) for s in dfa_id if s nfa.accepts} return dfa_id, trans, accept三个函数的职责要分清closure只负责沿 ε 边扩散move只负责吃一个真实字符subset_construction做的是“把 DFA 的每个状态表示成 NFA 状态集合”这件事frozenset是让它能当字典键的关键——换成set会直接抛unhashable type。accept那一行判断的是“这个 DFA 状态包含任意一个 NFA 接受态”包含就算接受如果多条规则同时接受同一个状态集说明你的正规式有歧义得回去检查优先级而不是在这里随便挑一个。手写状态机则是工程实践里最常见的做法因为它不需要任何依赖调试时打个断点就能看到pos一步步往前挪。工程包里scanNumber()、scanIdentifier()、skipComment()这几个函数就是手写风格下面拆核心循环时会看到。2.3 构建与依赖一份 Makefile 说清编译单元工程包不带 CMake就是一个朴素的 Makefile好处是拿到手make一下就能跑不用装一堆工具CXX : g CXXFLAGS : -stdc17 -O2 -Wall -Wextra -Iinclude TARGET : lexer SRCS : src/main.cpp src/lexer.cpp src/symbol_table.cpp src/error.cpp OBJS : $(SRCS:.cpp.o) $(TARGET): $(OBJS) $(CXX) $(CXXFLAGS) -o $ $^ %.o: %.cpp $(CXX) $(CXXFLAGS) -c -o $ $ clean: rm -f $(OBJS) $(TARGET) test: $(TARGET) for f in tests/case*.c; do \ echo $$f; ./$(TARGET) $$f | head -5; \ done .PHONY: clean test-Iinclude是必须的否则src/*.cpp里的#include token.h找不到文件-Wall -Wextra建议留着词法分析器最容易出的问题是“比较有符号和无符号数”和“变量未初始化”这两个开关能当场抓住一半。test目标里用的是$$fMakefile 里$要写两遍才不会被自己吃掉这是新手最常见的一处翻车。如果你的环境是 Windows MinGW把g换成g.exe或者直接全量编译g -stdc17 -Iinclude src/*.cpp -o lexer.exe也能跑只是%那种模式规则在部分老版本 make 上不太灵。3. 核心模块拆解一个字符从进入程序到变成 Token这一章是整份工程里最值得逐行读的部分。词法分析器的逻辑量其实很小但它对“边界”的敏感度极高——差一个字符输出就全错而且错得很隐蔽。3.1 Token 定义先把词法单元的数据结构钉死// include/token.h #pragma once #include string enum class TokenType { // 关键字 KW_INT, KW_FLOAT, KW_IF, KW_ELSE, KW_WHILE, KW_RETURN, // 标识符与常量 ID, NUM_INT, NUM_FLOAT, // 运算符 OP_ASSIGN, OP_PLUS, OP_MINUS, OP_STAR, OP_SLASH, OP_LT, OP_LE, OP_GT, OP_GE, OP_EQ, OP_NE, // 界符 DELIM_LPAREN, DELIM_RPAREN, DELIM_LBRACE, DELIM_RBRACE, DELIM_SEMI, DELIM_COMMA, // 结束符与非法符号 END_OF_FILE, INVALID }; struct Token { TokenType type; // 种别 std::string lexeme; // 原始词素报错时原样回显 int line; // 行号从 1 开始 int col; // 列号从 1 开始按字符算不按字节算 int symIndex; // 在符号表中的下标非 ID 时为 -1 };lexeme和line/col这三个字段是很多作业版词法分析器省掉的省掉之后你会立刻吃到苦头报错信息只能写“非法字符”说不出是哪个字符、在哪一行调试时纯靠猜。symIndex是为实验二铺的路——语法分析阶段要做类型检查需要快速把同一个标识符的所有出现关联起来有下标就不必再拿字符串去哈希表里查一遍。用enum class而不是裸enum是为了避免KW_INT和某个整数常量在重载解析里混到一起这个坑不踩一次很难体会到。3.2 规则表关键字为什么必须排在标识符前面// src/lexer.cpp struct Rule { TokenType type; std::regex pattern; }; const std::vectorRule Lexer::rules() { // 顺序即优先级平局时排在前面的规则胜出 static const std::vectorRule kRules { // 关键字必须放在 ID 之前否则 int 会被 ID 抢先吃掉 {TokenType::KW_INT, std::regex(int)}, {TokenType::KW_FLOAT, std::regex(float)}, {TokenType::KW_IF, std::regex(if)}, {TokenType::KW_ELSE, std::regex(else)}, {TokenType::KW_WHILE, std::regex(while)}, {TokenType::KW_RETURN, std::regex(return)}, // 浮点写在整数之前1.5 才不会被切成 1 和 .5 {TokenType::NUM_FLOAT, std::regex((\\d\\.\\d*|\\.\\d)([eE][-]?\\d)?)}, {TokenType::NUM_INT, std::regex(\\d)}, {TokenType::ID, std::regex([A-Za-z_][A-Za-z0-9_]*)}, // 双字符运算符必须在单字符之前 {TokenType::OP_LE, std::regex()}, {TokenType::OP_GE, std::regex()}, {TokenType::OP_EQ, std::regex()}, {TokenType::OP_NE, std::regex(!)}, {TokenType::OP_LT, std::regex()}, {TokenType::OP_GT, std::regex()}, {TokenType::OP_ASSIGN, std::regex()}, {TokenType::OP_PLUS, std::regex(\\)}, {TokenType::OP_MINUS, std::regex(-)}, {TokenType::OP_STAR, std::regex(\\*)}, {TokenType::OP_SLASH, std::regex(/)}, {TokenType::DELIM_LPAREN, std::regex(\\()}, {TokenType::DELIM_RPAREN, std::regex(\\))}, {TokenType::DELIM_LBRACE, std::regex(\\{)}, {TokenType::DELIM_RBRACE, std::regex(\\})}, {TokenType::DELIM_SEMI, std::regex(;)}, {TokenType::DELIM_COMMA, std::regex(,)}, }; return kRules; }这份表里有三条约定每一条都对应一类经典错误。关键字排在ID前面是因为int和标识符的正规式都能匹配这三个字符长度相同靠的就是“平局取先出现者”。浮点排在整数前面同理。双字符运算符排在单字符前面是因为的前两个字符里单独也成立如果先匹配上并且长度相同就永远进不到那条规则。注意这里的关键字正规式没有写\b。写\b看起来更严谨但std::regex的默认 ECMAScript 语法在不同标准库实现上对\b的处理并不完全一致尤其是遇到中文注释、全角字符时容易出现“明明该匹配却不匹配”的玄学问题。正确做法是靠最长匹配来兜底intx会被ID以长度 4 胜出int则因为平局取关键字不需要词边界断言。3.3 扫描主循环最长匹配、回溯与位置推进// src/lexer.cpp Token Lexer::next() { skipBlankAndComment(); // 空白、// 行注释、/* */ 块注释 const size_t start pos_; const int startLine line_; const int startCol col_; if (pos_ src_.size()) return Token{TokenType::END_OF_FILE, , line_, col_, -1}; size_t bestLen 0; TokenType bestType TokenType::INVALID; for (const Rule r : rules()) { std::smatch m; auto first src_.cbegin() static_caststd::ptrdiff_t(pos_); // match_continuous必须从 pos_ 处开始匹配不接受跳过前缀的结果 if (std::regex_search(first, src_.cend(), m, r.pattern, std::regex_constants::match_continuous)) { if (m.length() bestLen) { // 严格大于平局保留先出现的规则 bestLen static_castsize_t(m.length()); bestType r.type; } } } if (bestLen 0) { // 一条规则都没命中吞一个字符报错 advance(1); return Token{TokenType::INVALID, src_.substr(start, 1), startLine, startCol, -1}; } std::string lexeme src_.substr(start, bestLen); advance(bestLen); // 同步更新 line_ / col_ / pos_ int idx -1; if (bestType TokenType::ID) idx symbols_.insert(lexeme, startLine); return Token{bestType, lexeme, startLine, startCol, idx}; }match_continuous这个标志是整段代码的命门。不加它regex_search会在整个剩余串里找第一个能匹配的位置于是源文件里出现一个的时候斜杠规则可能匹配到几十行之后的某个*/然后一次性吞掉中间所有代码——现象是“程序跑到某一行之后 Token 全没了”排查起来非常费时间。加上之后匹配起点被锁死在pos_行为才和正规式意义上的“从当前字符开始”一致。m.length() bestLen用的是严格大于这一点不能改成。会让后出现的规则覆盖先出现的关键字规则就白排了。这条最长匹配加大于号判断的逻辑等价于教科书里“最长匹配、优先规则”的表述只是换成了代码。advance()长这样它同时负责位置和行列号是整个工程里仅次于主循环的重要函数void Lexer::advance(size_t n) { for (size_t i 0; i n pos_ src_.size(); i) { char c src_[pos_]; if (c \n) { line_; col_ 1; } else if (c \t) { col_ 4; } // 制表宽度与实验要求对齐 else { col_; } pos_; } }把“推进”和“计数”绑在一个函数里是为了防止出现“pos_加了但col_忘了加”这种低级错误。所有位置变更都走这一个出口出问题时只需要看这一个函数。3.4 符号表与错误恢复让非法字符不打断整趟扫描符号表用的是哈希索引加线性存储两边各司其职// src/symbol_table.cpp int SymbolTable::insert(const std::string name, int line) { auto it index_.find(name); if (it ! index_.end()) { entries_[it-second].refCount; // 重复出现只计引用次数 return it-second; // 返回同一个下标保证输出稳定 } int id static_castint(entries_.size()); index_.emplace(name, id); entries_.push_back(Entry{name, line, 1}); return id; }线性数组保证输出顺序等于首次出现顺序这一点对拍标准输出很关键——用std::unordered_map直接遍历输出顺序是不确定的同一份代码跑两次结果都不一样diff永远过不去。哈希表只用来做 O(1) 判重。refCount现在看着没用实验二做“变量未使用检查”时它就是现成的数据。错误恢复走的是恐慌模式遇到INVALID就一直跳到下一个界符或空白为止把这段非法片段整体报出去而不是一个字符报一条。否则源文件里少一个引号你能收到三百条错误真正有用的第一条被淹在中间。错误记录里带行号、列号和原始词素error.cpp统一格式化成line 12, col 7: unexpected character #前后一致才好比对。4. 跑起来编译、用例与输出校验4.1 编译与最小可运行闭环# 进入工程目录 cd lexer-lab make clean make # 拿自带用例跑一遍 ./lexer tests/case01_basic.c正常的话你会看到一行行(KW_INT, int)、(ID, main)之类的输出。main.cpp的入口逻辑很简单读文件内容到std::string构造Lexer然后while循环调next()直到END_OF_FILE。想让它从标准输入读把文件读取那段换成std::istreambuf_iteratorchar就行调试时用管道喂输入比反复存文件快得多。注意读文件一定要用二进制模式std::ios::binary。文本模式在 Windows 上会把\r\n悄悄转成\n你在 Linux 上算出来的行号是对的拿到别人机器上就整体偏一位。4.2 测试用例怎么造正常、边界、非法三类工程包里的四个用例分别覆盖这四类场景自己加用例时也照这个思路来/* tests/case02_number.c —— 数字与注释的边界 */ int main() { int a 0; float b 1.5e-3; // 科学计数法指数带负号 float c .5; // 省略整数部分的浮点 /* 块注释跨行 第二行 */ if (a 10) b b 1; return 0; }这份用例里同时埋了几个问题0后面紧跟;检查整数规则会不会多吞字符1.5e-3检查浮点规则里指数部分写没写.5检查(\d\.\d*|\.\d)里那个|分支是否真的覆盖了前导小数点跨行块注释检查/* */的结束位置有没有把换行算进去。每一条都是我在批改别人的实验时真见过的错法。非法输入那份更值得花时间。塞一个#、一个没闭合的、一个单独出现的\看看程序是报错退出、死循环还是把剩下的代码全吞了。词法分析器的健壮性八成体现在这几行输入上。4.3 输出对齐用 diff 代替肉眼作业评分看的是跟你自己的期望输出对不对得上所以期望文件必须一起维护mkdir -p out fail0 for f in tests/case*.c; do name$(basename $f .c) ./lexer $f out/$name.txt 21 # -u 输出上下文出问题能直接看到是哪一行开始分叉 if ! diff -u tests/expected/$name.txt out/$name.txt out/$name.diff; then echo FAIL: $name (详见 out/$name.diff) fail1 fi done [ $fail -eq 0 ] echo ALL PASS这段脚本属于一次写好、后面一直受益的东西。改完规则表跑一遍绿了就说明没把老用例改坏。21别省错误信息通常走 stderr重定向掉之后diff永远是空的你会误以为全过了。提示期望文件第一次要人工核对后再保存别直接拿当前程序的输出当标准答案。曾经有人这么干然后把“所有关键字都识别成标识符”这个 bug 固化进了基线后面怎么改都是对的。5. 避坑与排查词法分析器最常见的五类出错情况5.1 切分错误关键字、浮点、注释现象一int、while这些词输出成(ID, int)但x还是(ID, x)。原因规则表里ID排在关键字前面且匹配长度相同平局时后出现的规则没能覆盖前面的。或者std::map按字母序存规则int和[A-Za-z_]谁先谁后完全不由你决定。解决规则用有序容器std::vector存关键字规则整体放在ID之前平局判断用严格大于号。改完跑一遍tests/case01看关键字是不是全绿。现象二1.5e-3输出成(NUM_FLOAT, 1.5)、(ID, e)、(OP_MINUS, -)、(NUM_INT, 3)四个 Token。原因浮点正规式只写了\d\.\d指数部分漏了或者写了[eE]但忘了后面的[-]?。解决把指数写成可选组([eE][-]?\d)?并且让浮点规则先于整数规则。补一条专门测指数的用例别只测1.5。现象三块注释之后整段代码消失或者程序卡死。原因/* ... */的跳过逻辑里没找到*/时pos_不前进while条件永远成立或者找结束标记时用src_.find(*/, pos_)返回npos后直接拿去做算术npos 2溢回 0把pos_送回文件开头。解决npos单独判断遇到未闭合注释就报一条错并把pos_推到文件末尾。行注释//同理要一直跳到\n或者文件结束。5.2 输出对不上行列号与符号表顺序现象四所有 Token 的行号都比期望少 1或者只有注释后面的行号错。原因行号从 0 开始算或者跳过注释时直接pos_往后挪没走advance()导致\n没被计数。\r\n换行也算一个坑\r会被当成一个普通字符让列号多 1。解决行号统一从 1 起所有位置变更强制走advance()skipBlankAndComment里遇到\r\n时把\r一起吞掉别让它进 Token 流。现象五同一份源文件跑两次符号表输出的顺序不一样。原因用std::unordered_map直接遍历输出迭代顺序取决于哈希桶布局和插入顺序无关。解决内部用unordered_map判重、用vector保序输出只走vector。这个改动一行代码能省掉一整晚的“为什么diff时好时坏”。5.3 环境与运行时问题现象六编译通过一跑就段错误。原因src_[pos_]越界。std::string::operator[]对pos size()是未定义行为不一定崩但读到的是\0会让某些规则意外匹配成功表现为“文件末尾多出莫名其妙的 Token”。解决所有访问前先判pos_ src_.size()或者统一用src_.at(pos_)换成抛异常让问题当场暴露。调试阶段用-fsanitizeaddress,undefined编译一次越界和未初始化基本一抓一个准g -stdc17 -g -fsanitizeaddress,undefined -Iinclude src/*.cpp -o lexer_asan ./lexer_asan tests/case04_invalid.c6. 二次开发把实验一扩成能跑完整前端的词法层6.1 加关键字和运算符只动两张表扩展点设计得很清楚加一个关键字TokenType加一项、kRules加一行、打印函数加一个case三处改完就生效不用碰扫描循环。加、-这种多字符运算符时只要记住把它放在单字符规则之前最长匹配会自动帮你选中更长的那个。唯一要小心的是别把-和-、的优先级写反写反了不报错只是永远匹配不到。6.2 给语法分析留 peek/consume 接口实验二要用它光有next()不够递归下降分析器经常需要向前看一个 Token// include/lexer.h 追加 class Lexer { public: Token next(); // 消费一个 Token const Token peek(size_t k 0); // 预读不消费 private: std::dequeToken lookahead_; // 预读缓冲 };peek的实现就是“缓冲不够就调一次next()补上然后返回下标k的元素”next()则先从缓冲里弹空了才真正扫描。这个缓冲层只有十几行但它把词法分析器和语法分析器彻底解耦了——语法分析器不需要知道源文件长什么样也不需要回退文件指针。6.3 验证方法差分测试加覆盖率改完之后怎么确认没改坏我是这么做的先跑tests/全量diff全绿再往下然后拿真实一点的源文件几百行的 C 片段跑一遍用-fsanitize版本再跑一遍确认没有越界最后看覆盖率gcov或者llvm-cov都行重点看advance()和skipBlankAndComment()的分支有没有被走到——这两个函数的分支覆盖率低于 90%说明你的用例里没有跨行注释、没有制表符、没有文件末尾无换行的情况而这三样恰恰是最容易出问题的地方。从我自己的教训来说最贵的不是写代码那两小时而是改完规则表之后不跑回归、直接交作业然后在提交前一晚发现浮点全错了。从那以后我每次动kRules都强制先make test再谈别的哪怕只加了一个。希望帮到你。本文还有配套的精品资源点击获取