企业官网建设流程全解析

简介：一套面向编译原理课程核心实验的完整资源包，整合了词法分析器设计、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 类型与状态的对应关系，方便对照代码查错：

2.2.2 驱动循环与最长匹配

驱动循环的核心是查表。与很多教材写的不一样，这里不需要显式回退字符，因为遇到 -1 时前一个字符还没有被消费，直接跳出循环即可。

bool isKeyword(const std::string& s) { static const std::vector<std::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::map<std::string, std::set<char>>存储：

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 集合应该稳定成下面这样：

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); } }

冲突一旦出现，立刻在终端打印两个产生式的编号，并定位到具体非终结符和终结符。最常见的三类冲突及排查方法：

分析驱动用栈实现：栈底先放$，再放开始符号。每次比较栈顶符号和当前 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; } } vector<string> infixToPostfix(const string& expr) { vector<string> output; stack<char> 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 vector<string>& postfix) { stack<int> 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() { vector<string> 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才是第一个。减法和除法如果写反，结果会全部出错。实验里宁可抛异常，也不要返回一个魔法错误码，否则表达式一复杂你根本找不到根因。

优先级与结合性对照表如下：

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::set<LR1Item> closure(const std::set<LR1Item>& I) { std::set<LR1Item> 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 vector<Token>& tokens) { stack<int> 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输出，通常十分钟内就能定位到具体状态。

本文还有配套的精品资源，点击获取