编译原理实验通关：词法分析、LL(1)、逆波兰式与LR(1)的C++实现

简介一套面向编译原理课程核心实验的完整资源包整合了词法分析器设计、LL(1)分析法、逆波兰式的生成与计算、LR(1)分析法四个重点模块。资源以C源码和配套文档为主体适合计算机专业本科生课后实践、课程设计或考研复习时对照学习。包体共35个文件4个cpp为各实验的程序实现9个docx为实验报告与详细说明11个txt和5个md存放测试数据、使用指南与项目介绍压缩包整体仅789KB结构清晰、按实验分目录整理便于逐个模块查阅调试。目前该资源已有149人浏览学习内容紧凑实用。通过这份资料学习者既能运行词法分析器和语法分析器的完整代码也可借助文档理解预测分析表构建、逆波兰式转换与计算、LR(1)自动机构造等核心原理在动手修改和调试中系统巩固编译原理知识。1. 编译原理实验的四个关卡代码与理论如何对齐编译原理实验通常是四连击先写词法分析器再写 LL(1) 预测分析接着用逆波兰式做中间代码计算最后上 LR(1) 分析器。每关单独做都不难难的是代码和理论对不上——FIRST/FOLLOW 集合手算全对程序里的预测分析表却是一张硬编码数组改一个产生式就要重写一遍。我在整理这份 C 实验代码时刻意把每个实验拆成「文法定义、表构造、驱动循环」三层无论是应对期末考试选择题还是课程设计验收都能很快定位问题。源码包里的experiment_1到experiment_4分别对应这四个部分每个目录都有 demo 和 readme适合两类人期末突击想用可运行代码反推理论的学生以及想快速把大学算法工程化的工程师。这里按实验顺序往下拆重点讲代码怎么落位。2. 词法分析器设计Token 分类与状态转移表的实现2.1 为什么实验里应该用状态转移表词法分析器的常见错误是从主流程开始写拿到一个字符if判断是不是数字else if判断是不是字母。这样写十个 Token 类型还能撑住一旦加入、、/* 注释 */分支会指数膨胀。更合理的做法是先定 DFA 状态再把「状态 × 字符类别」映射成一张二维表。代码里实际驱动的就是一个坐标查表动作当前状态是行当前字符所属类别是列表里存下一个状态-1 表示无路可走。状态转移表把逻辑变成数据之后可维护性高很多。改一条识别规则只需要改表项不需要改动驱动循环。比如要支持科学计数法1e-3传统 if-else 要加一大段状态变量用 DFA 只需要新增两个状态和几行表项。这对课设验收时临时加需求非常有用。2.2 一个最小可跑的 C 词法分析器2.2.1 Token 和状态表定义先定义 Token 类型和对应状态。为了不过度膨胀只保留标识符、整数、运算符、界符、保留字和 EOF 六类。DFA[row][col]里 row 是当前状态col 是字符类别表值 -1 表示当前词素应该结束。#include string #include vector #include cstring enum TokenType { TK_ID, // 标识符 TK_NUM, // 整数常量 TK_KEYWORD, // 保留字 int/if/else/while/return TK_OP, // 运算符 - * / ! TK_SEP, // 界符 ; , ( ) { } TK_EOF // 输入结束 }; struct Token { TokenType type; std::string lexeme; int line; int column; }; // 字符类别0 字母/下划线1 数字2 运算符3 界符4 空白 int charClass(char ch) { if (isalpha(ch) || ch _) return 0; if (isdigit(ch)) return 1; if (strchr(-*/!, ch)) return 2; if (strchr(;,(){}[], ch)) return 3; return 4; } // 状态含义0 START, 1 IN_ID, 2 IN_NUM, 3 IN_OP, 4 IN_SEP int DFA[5][5] { {1, 2, 3, 4, 0}, // START空白回到 START {1, 1, -1, -1, -1}, // IN_ID字母或数字继续 {-1, 2, -1, -1, -1},// IN_NUM数字继续 {-1, -1, 3, 0, 0}, // IN_OP连续运算符继续 {-1, -1, -1, -1, -1}// IN_SEP单字符界符立即结束 };DFA[3][3]的值是 0表示运算符后面遇到界符时运算符词素结束界符留给下一次调用。DFA[4][4]全部为 -1说明界符是单字符读入一个界符后必须在下一个字符处停下。表里的空白字符类别只有在 START 状态才会被忽略如果出现在标识符或数字中间会直接截断当前词素这符合词法分析的「最长匹配」原则。下面的表给出 Token 类型与状态的对应关系方便对照代码查错Token 类型进入状态示例TK_IDIN_IDcount, _tmpTK_NUMIN_NUM123, 004TK_OPIN_OP, , -TK_SEPIN_SEP;, (, {TK_KEYWORD从 TK_ID 中区分int, if, return2.2.2 驱动循环与最长匹配驱动循环的核心是查表。与很多教材写的不一样这里不需要显式回退字符因为遇到 -1 时前一个字符还没有被消费直接跳出循环即可。bool isKeyword(const std::string s) { static const std::vectorstd::string kw {int, if, else, while, return}; for (const auto k : kw) if (k s) return true; return false; } Token nextToken(const std::string src, size_t pos, int line) { int state 0; std::string lexeme; Token tok; while (true) { if (pos src.size()) { if (lexeme.empty()) return {TK_EOF, $, line, 0}; break; } char ch src[pos]; int nxt DFA[state][charClass(ch)]; if (nxt -1 || (nxt 0 state ! 0)) break; lexeme ch; state nxt; pos; } if (lexeme.empty()) { // 完全无法识别的字符打印错误后跳过 tok {TK_EOF, std::string(1, src[pos]), line, 0}; pos; return tok; } if (state 1) tok.type isKeyword(lexeme) ? TK_KEYWORD : TK_ID; else if (state 2) tok.type TK_NUM; else if (state 3) tok.type TK_OP; else if (state 4) tok.type TK_SEP; else tok.type TK_EOF; tok.lexeme lexeme; tok.line line; return tok; }这里的关键是nxt 0 state ! 0这个条件。它处理的是 START 状态本身START 在遇到空白时表值是 0但如果你正在 IN_ID 状态下一个字符是运算符且表值也是 0说明当前标识符已经读完必须结束。lexeme.empty()分支用来兜底未知字符否则遇到这类字符会死循环。调用nextToken前要把整个源文件读入std::string而不是从文件流里逐字符读。原因是状态转移过程中经常需要「看一个字符再决定是否接受」一次性读内存后所有操作都是数组下标移动速度更快也方便打印出错的上下文。行号line可以在一个简单的循环里维护每当读入\n就加一。2.3 我踩过的坑和参数调整建议多字符运算符要靠在 IN_OP 状态里「能合并就合并」实现。状态表里DFA[3][2] 3因此后面再遇到会继续留在 IN_OP形成但遇到;时表值是 0就会输出把;留给下一轮。如果实验需要支持注释别在驱动循环里做字符串匹配正确做法是再加两个状态遇到/后如果下一个字符是*进入 IN_COMMENT在 IN_COMMENT 里遇到*/才回到 START。数字后面不能跟字母比如12abc应该报错。可以在 IN_NUM 状态遇到字母时把当前 Token 标记成 error并输出位置信息。很多词法分析的考题选择题都在考这类边界的判别。界符表里千万不要设置跟随字符否则会把连续的两个界符合并成一个错误 Token。界符永远单字符遇到就输出。3. LL(1) 分析法FIRST、FOLLOW 集合与预测表生成3.1 先把文法变得能让预测分析表没有冲突LL(1) 分析法是自顶向下、最左推导的分析方法每一步根据当前栈顶符号和当前输入符号通过预测分析表唯一确定下一步动作。它要求文法没有左递归且任意非终结符的候选产生式之间不能有重叠的 FIRST 集合。因此代码的第一步不是算表而是重写文法。直接左递归E - E T | T要改成E - T E、E - T E | ε间接左递归要通过代入消除。提取左公因子针对的是if (E) S | if (E) S else S这类改写后加一个新非终结符。很多初学者跳过这步直接拿原始文法算 FIRST/FOLLOW结果预测表全是冲突。实验里正确的做法是把改写后的文法保存成内部结构左部、右部产生式数组并给每个符号编号后面算集合和填表都依赖这个编号。3.2 FIRST 与 FOLLOW 的固定点迭代实现3.2.1 用 while 循环算 FIRST 而不是递归递归求 FIRST 在写法上很简单但遇到间接左递归或产生式之间互相依赖时会栈溢出或算不全。稳妥方案是用循环不断把新的终结符插入集合直到某一轮没有变化。下面代码用std::mapstd::string, std::setchar存储bool changed true; while (changed) { changed false; for (const auto prod : grammar) { const std::string A prod.left; const std::string alpha prod.right; size_t i 0; while (i alpha.size()) { char X alpha[i]; if (isTerminal(X)) { if (firstSets[A].insert(X).second) changed true; break; } // X 是非终结符把 FIRST(X) 除 ε 之外加入 FIRST(A) for (char t : firstSets[X]) { if (t ! EPSILON firstSets[A].insert(t).second) changed true; } // 如果 X 不能推出 ε直接停止向后传播 if (firstSets[X].find(EPSILON) firstSets[X].end()) break; i; } // 产生式右部所有符号都可空A 才能推出 ε if (i alpha.size()) { if (firstSets[A].insert(EPSILON).second) changed true; } } }这段代码有两个关键点一是「X 可空才继续向右看」二是「处理到右部末尾时把 ε 加入 FIRST(A)」。如果这两个条件写错FIRST 集合会多算或少算预测表自然错。EPSILON可以用\0表示关键是不要和真正的输入符号冲突isTerminal判断标准是符号集合不要用 ASCII 范围判断。以经典表达式文法为例经过这样的迭代后FIRST 集合应该稳定成下面这样非终结符FIRSTE{ (, id }E{ , ε }T{ (, id }T{ *, ε }F{ (, id }3.2.2 FOLLOW 集的生成规则与实现FOLLOW 的计算依赖 FIRST并且使用一样的固定点迭代。对每个产生式A - αBβ把FIRST(β)除 ε 之外加入FOLLOW(B)如果β可以推导出 ε则把FOLLOW(A)加入FOLLOW(B)。代码里最麻烦的是「β 可空」这个判断while (changed) { changed false; for (const auto prod : grammar) { for (size_t i 0; i prod.right.size(); i) { char B prod.right[i]; if (!isNonTerminal(B)) continue; size_t j i 1; bool suffixCanBeEmpty true; while (j prod.right.size()) { char C prod.right[j]; if (isTerminal(C)) { if (followSets[B].insert(C).second) changed true; suffixCanBeEmpty false; break; } else { for (char t : firstSets[C]) { if (t ! EPSILON followSets[B].insert(t).second) changed true; } if (firstSets[C].count(EPSILON) 0) { suffixCanBeEmpty false; break; } j; } } if (suffixCanBeEmpty || j prod.right.size()) { for (char t : followSets[A]) { if (followSets[B].insert(t).second) changed true; } } } } if (followSets[startSymbol].insert($).second) changed true; }followSets[startSymbol]必须放入$这是很多实验代码遗漏的地方。如果漏了分析id id * id这种完整输入时可能会在文件结束符上报错。另外注意suffixCanBeEmpty的初始化如果 B 后面没有符号它保持 true这样才满足「β 为空时复制 FOLLOW(A)」。3.3 预测分析表填表与冲突检测有了 FIRST 和 FOLLOW填表就是标准算法对产生式A - α遍历FIRST(α)中的终结符 a在M[A][a]填入该产生式如果 α 可空则对FOLLOW(A)中的每个 b 也填入。代码里做一层包装让填表时能记录冲突bool addToTable(char A, char terminal, int prodIndex) { int slot table[A][terminal]; if (slot ! -1 slot ! prodIndex) return false; // 冲突 slot prodIndex; return true; } for (const auto prod : grammar) { auto firstAlpha getFirstOfString(prod.right); for (char a : firstAlpha) { if (a ! EPSILON) addToTable(prod.left, a, prod.index); } if (firstAlpha.count(EPSILON)) { for (char b : followSets[prod.left]) addToTable(prod.left, b, prod.index); } }冲突一旦出现立刻在终端打印两个产生式的编号并定位到具体非终结符和终结符。最常见的三类冲突及排查方法冲突表现原因修复方法M[A,a]同时有两个产生式待选两个右部 FIRST 集合有交集提取左公因子M[A,a]同时来自 FIRST 和 FOLLOW某个右部可空且 FIRST/FOLLOW 重叠检查文法是否真的 LL(1)分析栈顶是 A输入是 a但表项为 -1FOLLOW 集合缺少$或 ε检查空产生式处理边界分析驱动用栈实现栈底先放$再放开始符号。每次比较栈顶符号和当前 Token相等就弹出并前进不相等就根据table[stackTop][currentToken]的产生式把产生式右部逆序压入栈。这样输出的产生式序列正好对应最左推导可以直接和课本上的推导过程对拍。如果用的是从experiment_2里拷来的文法结构体记得先确认getFirstOfString能处理空右部很多 bug 都来自这个函数没有考虑ε。提示用 while 循环求 FIRST/FOLLOW 时第一次执行前必须把所有集合清空。如果复用了上一次运行的数据表项会残留出现莫名其妙的冲突。4. 逆波兰式的生成及计算中缀转后缀与栈式求值4.1 调度场算法比表达式树更贴合实验逆波兰式又被称为后缀表达式运算符跟在操作数后面括号消失运算顺序完全由顺序决定。实验里要求「生成及计算」所以要把两个功能分开先由中缀表达式转换后缀再对后缀做栈式求值。常见做法是用调度场算法shunting yard它只依赖运算符的优先级和结合性不用额外构造语法树。为什么不直接用表达式树表达式树也能生成后缀但需要先构造二叉树还要考虑内存释放和节点类型。调度场算法一边扫描一边输出代码更短也更贴合课程里讲的「栈在编译中的应用」。优先级比较时左结合运算符同级别要弹出右结合运算符同级别不弹这是整个算法唯一的难点。4.2 转换和求值的完整代码4.2.1 中缀转后缀实现#include stack #include vector #include string #include cctype #include iostream using std::string; using std::vector; using std::stack; int opPriority(char op) { switch (op) { case : case -: return 1; case *: case /: return 2; case ^: return 3; default: return 0; } } vectorstring infixToPostfix(const string expr) { vectorstring output; stackchar ops; size_t i 0; while (i expr.size()) { if (isdigit(expr[i]) || isalpha(expr[i])) { string item; while (i expr.size() (isalnum(expr[i]) || expr[i] .)) { item expr[i]; } output.push_back(item); } else if (expr[i] () { ops.push(expr[i]); } else if (expr[i] )) { while (!ops.empty() ops.top() ! () { output.push_back(string(1, ops.top())); ops.pop(); } if (!ops.empty()) ops.pop(); i; } else if (isspace(expr[i])) { i; } else { while (!ops.empty() opPriority(ops.top()) opPriority(expr[i])) { // ^ 是右结合遇到同优先级不弹出 if (expr[i] ^ opPriority(ops.top()) opPriority(expr[i])) break; output.push_back(string(1, ops.top())); ops.pop(); } ops.push(expr[i]); } } while (!ops.empty()) { if (ops.top() () return {}; // 括号不匹配 output.push_back(string(1, ops.top())); ops.pop(); } return output; }操作数直接输出运算符入栈前把所有栈顶优先级更高的运算符弹出。左括号具有最高优先级但不能被直接比较所以用单独分支处理。^是右结合与栈顶同优先级时不弹这样2^3^2会得到2 3 2 ^ ^而不是先算2^3。返回值是空 vector 时调用方必须检查否则后续求值会崩溃。4.2.2 后缀表达式求值实现int evaluatePostfix(const vectorstring postfix) { stackint values; for (const string token : postfix) { if (isdigit(token[0])) { values.push(std::stoi(token)); } else { int right values.top(); values.pop(); int left values.top(); values.pop(); switch (token[0]) { case : values.push(left right); break; case -: values.push(left - right); break; case *: values.push(left * right); break; case /: if (right 0) throw std::runtime_error(division by zero); values.push(left / right); break; default: throw std::runtime_error(unknown operator); } } } return values.top(); } int main() { vectorstring post infixToPostfix(3 4 * (2 - 1)); if (post.empty()) { std::cerr bad expression\n; return 1; } for (const auto s : post) std::cout s ; std::cout \n evaluatePostfix(post) \n; return 0; }输出是3 4 2 1 - * 再求值得7。注意弹出顺序先出的right是第二个操作数后出的left才是第一个。减法和除法如果写反结果会全部出错。实验里宁可抛异常也不要返回一个魔法错误码否则表达式一复杂你根本找不到根因。优先级与结合性对照表如下运算符优先级结合性示例转换 -1左ab-c-a b c -* /2左ab*c-a b c * ^3右2^3^2-2 3 2 ^ ^( )--(ab)*c-a b c *4.3 负号、除零和调用方要做的检查负号判断如果-出现在表达式开头、左括号后面或者紧跟一个运算符它应当被当作一元负号。简单做法是把它改写成0 - x更严谨的写法是增加一元运算符标记让求值阶段在弹栈前压入0。空表达式infixToPostfix返回空 vector 时直接报错不要进入求值函数。Token 边界数字后面跟字母比如12abc是词法错误逆波兰模块只应当拿到合法 Token 流。括号不匹配转换完成后栈里还残留(return {}会把问题暴露在调用层不要在求值时才报段错误。5. LR(1) 分析法从项目集到 ACTION/GOTO 表驱动5.1 LR(1) 和 LL(1) 的差异决定代码结构LR(1) 是自底向上的分析方法分析时维护的是状态栈而不是非终结符栈。每个状态对应一个项目集项目里包含圆点位置和前看符号。正因为如此LR(1) 可以处理左递归文法表达式文法E - E T | T不需要改写直接构造项目集即可。实验里把 LL(1) 和 LR(1) 放在一起可以直观感受到两种表驱动的差异LL(1) 表是非终结符 × 终结符LR(1) 表是状态 × 符号动作分为移进、规约、接受、报错。5.2 项目集规范族与驱动表的核心逻辑LR(1) 表由项目集规范族生成核心是closure和goto。闭包运算的伪码如下struct LR1Item { int prodIndex; // 产生式编号 int dot; // 圆点位置 char lookahead; // 前看符号 }; std::setLR1Item closure(const std::setLR1Item I) { std::setLR1Item J I; bool changed true; while (changed) { changed false; for (auto item : J) { if (item.dot production[item.prodIndex].right.size()) continue; char B production[item.prodIndex].right[item.dot]; if (!isNonTerminal(B)) continue; // 计算 B 后面符号串的 FIRST连上当前 lookahead auto betaA production[item.prodIndex].right.substr(item.dot 1) item.lookahead; auto firstBetaA getFirstOfString(betaA); for (auto prodB : productionsByLeft[B]) { for (char a : firstBetaA) { LR1Item n {prodB.index, 0, a}; if (J.insert(n).second) changed true; } } } } return J; }这里最容易出错的地方是betaA的构造它必须把当前项目的lookahead也拼到圆点后面的符号串末尾。因为如果β可以推出 ε那么原来的lookahead会直接传递到新加入的项目。很多实现把FIRST直接写成FOLLOW或者忘记连接lookahead导致 LR(1) 自动机比 LR(0) 还粗规约动作自然错。得到项目集和转移关系后ACTION/GOTO 表可以按规则填充对每个状态遇到终结符查 goto 得到移进目标遇到项目[A - α·, a]在ACTION[state][a]填规约遇到[S - S·, $]填接受。驱动代码是典型的表驱动循环bool lrParse(const vectorToken tokens) { stackint stateStack; stateStack.push(0); int idx 0; while (true) { int s stateStack.top(); int sym tokenToSymbol(tokens[idx]); Action act table[s][sym]; if (act.type Action::SHIFT) { stateStack.push(act.value); idx; } else if (act.type Action::REDUCE) { const Production p productions[act.value]; for (size_t i 0; i p.right.size(); i) stateStack.pop(); int top stateStack.top(); stateStack.push(table[top][nonTerminalToSymbol(p.left)].value); } else if (act.type Action::ACCEPT) { return true; } else { return false; } } }规约时弹出右部长度个状态再根据当前栈顶状态和左部非终结符查 GOTO 表压入新状态。这个步骤和 LL(1) 的「逆序压产生式右部」完全不同很多同学第一次写时会忘记规约后要重新查一次 GOTO 表导致状态栈失衡。调试时可以用--debug-table把每次查询的(state, symbol)和动作打出来对照手算表一行行核。5.3 用 LL(1) 结果对拍 LR(1) 规约序列最实用的验证技巧是用同一份表达式分别跑 LL(1) 和 LR(1) 分析器。LL(1) 会输出产生式展开序列LR(1) 会输出规约序列两者最终生成的语法树应该完全一致。以id id * id为例LL(1) 会输出类似于E - T E、T - F T、F - id的序列LR(1) 会输出F - id、T - F T、E - T E等规约动作。把两个序列反向对齐如果圆括号位置匹配不上说明至少有一张表是错的。可以给实验程序加一个命令式入口./exp_engine --mode ll1 --expr a b * c --parse-seq ./exp_engine --mode lr1 --expr a b * c --parse-seq对比输出时先看第一个规约动作。LL(1) 从开始符号往下展开LR(1) 从输入符号向上归约所以最底层的id - F应该先出现。另一个常见问题是 LR(1) 项目集编号不一致导致 ACTION/GOTO 表错位做实验时最好把项目集编号固定写入文件每次构造前先打印一遍状态转移表免得改了一处产生式后表全部错位。真正卡住的时候回到课本那一章找一张完整文法的 LR(1) 分析表一行行对代码里的debug-table输出通常十分钟内就能定位到具体状态。本文还有配套的精品资源点击获取