企业官网建设流程全解析

简介：这份编译原理语法分析实验资料面向计算机专业学习者及需要完成课程实验的学生，围绕递归子程序法实现语法分析程序展开，可衔接已有词法分析结果，对文法定义的各类语法成分进行识别与输出。压缩包共2个文件，包含1份实验问题描述文档和1个C++源程序，整体约17KB，便于快速查看题目要求并对照实现。代码已在CG实验平台满分通过，已有6110人学习，具有较好的参考价值。读者可以从中了解testfile.txt到output.txt的输入输出组织、按单词顺序输出词法信息、在指定语法成分结束前另起一行输出<常量说明>等标记的处理方式，也能借鉴递归下降子程序的划分、预读控制与文法规则落地思路，适合用于实验复现、代码对照和查漏补缺。

1. 语法分析实验最怕“能跑但说不清”：这份 C++ 实现把中间结果都显示出来

编译原理的语法分析实验，多数人是先做出一版能过样例的代码：读 token、给出一个“对/错”，交完事。可一到验收被问“你的 FIRST 集怎么迭代出来的”“这个状态为什么选择归约而不是移进”，就卡住了。这份 C++ 版语法分析实验资源，把词法接口、递归下降、LL(1) 预测分析表、SLR(1) 的 ACTION/GOTO 表做成同一套文法上的四条可运行路径，栈、表、状态集全是显式数据结构，打印出来就能对着手推过程核验。适合正在赶课设的学生，也适合写过 parser 但没把 LR 表构造手推过一遍的工程师。下面按“先跑通、再改文法、最后看冲突”的顺序拆。

2. 从字符流到语法树：把词法接口和递归下降先接起来

不管后面上 LL(1) 还是 SLR(1)，第一件要确认的事只有一件：词法这层给出来的 Token 流，能不能被语法层直接消费。这一层没对齐，后面所有表都是白算。这一章先把 Scanner 和递归下降这条最短路径打通，跑出第一棵 AST，再去谈集合和表。

2.1 为什么把 Scanner 和 Parser 拆成两个类

整份代码的职责边界是四层：源串 → Token 流 → 语法结构 → AST。Scanner 只认字符，不认识任何非终结符；Parser 只认std::vector<Token>，不认识字符。这样拆的理由很实际——语法分析调试时，问题八成不在算法而在输入。如果 Parser 直接吃字符流，你没法构造一个“只有三个 Token”的输入去单测某条产生式；拆开之后，手写{Id, Plus, Id, End}就能把E -> T E'单独跑一遍。

各模块的输入输出大致是这样：

另一处选型是“递归下降 + 表驱动”双实现。递归下降的代码就是文法的直接镜像，改文法就要改代码，胜在可读、报错定位准；表驱动改文法只改数据文件，胜在能验证集合算得对不对。实验要求两套都写，本质是逼你把“文法”和“文法的执行”分开看。我第一次做这个实验时只写了递归下降，验收时被要求现场加一条产生式，改代码改到手忙脚乱，这个教训后来一直记着。

2.2 Token 结构与扫描器的最小实现

Token 里必须带词素原文和位置，否则报错时你只知道“第 7 个 token 不对”，不知道它在源文件哪一行——这是排错效率的分水岭。

// lexer.h #pragma once #include <cctype> #include <string> #include <vector> enum class TokKind { Id, Num, Plus, Minus, Star, Slash, LParen, RParen, End, Bad }; struct Token { TokKind kind; std::string text; // 词素原文，报错时直接回显 int line = 1, col = 1; // 供错误提示定位 }; class Lexer { public: explicit Lexer(std::string src) : src_(std::move(src)) {} std::vector<Token> scan(); private: char cur() const { return pos_ < src_.size() ? src_[pos_] : '\0'; } char ahead() const { return pos_ + 1 < src_.size() ? src_[pos_ + 1] : '\0'; } void advance(); std::string src_; size_t pos_ = 0; int line_ = 1, col_ = 1; };

主循环只做三件事：跳空白、按首字符分类、吐 Token。

// lexer.cpp std::vector<Token> Lexer::scan() { std::vector<Token> out; while (true) { while (cur() == ' ' || cur() == '\t' || cur() == '\r' || cur() == '\n') advance(); if (cur() == '\0') { out.push_back({TokKind::End, "$", line_, col_}); break; } int l = line_, c = col_; if (std::isalpha((unsigned char)cur()) || cur() == '_') { std::string s; while (std::isalnum((unsigned char)cur()) || cur() == '_') { s += cur(); advance(); } out.push_back({TokKind::Id, s, l, c}); // 关键字也先当 Id，交给 toSym 决定 } else if (std::isdigit((unsigned char)cur())) { std::string s; while (std::isdigit((unsigned char)cur())) { s += cur(); advance(); } out.push_back({TokKind::Num, s, l, c}); } else { switch (cur()) { case '+': out.push_back({TokKind::Plus, "+", l, c}); break; case '-': out.push_back({TokKind::Minus, "-", l, c}); break; case '*': out.push_back({TokKind::Star, "*", l, c}); break; case '/': out.push_back({TokKind::Slash, "/", l, c}); break; case '(': out.push_back({TokKind::LParen, "(", l, c}); break; case ')': out.push_back({TokKind::RParen, ")", l, c}); break; default: out.push_back({TokKind::Bad, std::string(1, cur()), l, c}); break; } advance(); } } return out; }

几个参数要留意。TokKind::End用一个不在文法里的"$"作词素，是为了让它天然对应 LR 表里的结束符，省掉一层映射。Bad不抛异常而是继续扫，好处是一次运行能报出所有非法字符，而不是改一个跑一次。toSym(const Token&)这个函数是把 Token 翻译成文法符号名的唯一入口，你在改文法时只需要动它一个地方：Id和Num都映射成id，End映射成$，其余原样返回。

2.3 消除左递归之后的递归下降骨架

表达式文法不能直接递归下降，E -> E + T会无限左递归，行为就是栈溢出（这个现象很有欺骗性，看起来像内存问题）。标准做法是消左递归：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id | num

代码就是这段文法的逐行翻译：

struct Node { std::string label; std::vector<std::unique_ptr<Node>> kids; }; class RdParser { public: explicit RdParser(std::vector<Token> t) : t_(std::move(t)) {} std::unique_ptr<Node> parse() { return E(); } private: const Token& peek() const { return t_[i_]; } bool accept(TokKind k) { if (peek().kind == k) { ++i_; return true; } return false; } void expect(TokKind k) { if (!accept(k)) throw std::runtime_error( "line " + std::to_string(peek().line) + ": unexpected '" + peek().text + "'"); } std::unique_ptr<Node> E(); // E -> T E' std::unique_ptr<Node> Ep(); // E' -> + T E' | ε std::unique_ptr<Node> T(); // T -> F T' std::unique_ptr<Node> Tp(); // T' -> * F T' | ε std::unique_ptr<Node> F(); // F -> ( E ) | id | num std::vector<Token> t_; size_t i_ = 0; }; std::unique_ptr<Node> RdParser::E() { auto n = std::make_unique<Node>(Node{"E", {}}); n->kids.push_back(T()); n->kids.push_back(Ep()); return n; } std::unique_ptr<Node> RdParser::Ep() { if (accept(TokKind::Plus)) { // 命中 FIRST(+ T E') auto n = std::make_unique<Node>(Node{"E'", {}}); n->kids.push_back(std::make_unique<Node>(Node{"+", {}})); n->kids.push_back(T()); n->kids.push_back(Ep()); return n; } return std::make_unique<Node>(Node{"E'->ε", {}}); // 等价于校验 peek ∈ FOLLOW(E') }

Ep()里那个空返回是整段代码最容易被质疑的地方。它不检查任何东西就返回 ε 节点，合法性实际上由调用方保证：能走到这一步，说明当前 Token 不在FIRST(+ T E')里。严谨一点的写法是在这里断言peek().kind属于{RParen, End}，也就是FOLLOW(E')。我在课设验收时被追问过一次“你凭什么认为这里可以返回空”，当时答不上来，后来所有 ε 分支都补了断言——多写一行，省掉一次答辩翻车。

2.4 编译与跑通第一条用例

g++ -std=c++17 -O2 -Wall -Wextra \ src/lexer.cpp src/rd_parser.cpp src/ll1_table.cpp src/slr_table.cpp src/main.cpp \ -o build/syn printf '1+2*(3-4)\n' | ./build/syn --mode rd --dump-ast

参数说明：--mode取rd/ll1/slr，切换三套分析器；--dump-ast递归打印树，缩进表示层级；另有--trace打印每一步规则应用或移进归约动作。用-Wall -Wextra是必须的，std::isalpha传char在部分平台上会触发未定义行为，这个警告能提前暴露问题。

期望输出的树根是E，左子树T -> F -> 1，右子树是E' -> + T E'里嵌的2*(3-4)。跑通之后不要急着改文法，先把--mode切到ll1，同一个输入再跑一遍——如果两边都接受，说明词法接口这一层已经对齐了，后面的工作才有意义。

3. LL(1) 预测分析表：FIRST/FOLLOW 算错，后面全白搭

递归下降靠人眼看 FIRST 决定走哪条分支，LL(1) 把这件事预先做成一张二维表。这一步的价值不在于多写一个分析器，而在于它会迫使你把 FIRST、FOLLOW、可空性三件事算到分毫不差——手推时最容易糊弄过去的正是这些地方。

3.1 文法的数据结构该怎么定

产生式用map<非终结符, vector<vector<string>>>存，右侧序列用vector<string>，终结符和非终结符统一用字符串标识，靠“是否出现在 map 的 key 里”区分。这套表示牺牲了一点性能，换来的是打印调试时能直接看到符号名，不用再翻译一遍编号。

using SymSet = std::set<std::string>; using RHS = std::vector<std::string>; using Grammar = std::map<std::string, std::vector<RHS>>; const std::string EPS = "ε"; // 空串用独立符号，不要用 ""

用""表示空串是个典型陷阱：vector<string>里出现空串，很多地方会把它当成“没有这个元素”处理，遍历时容易漏。显式给一个EPS，后面所有分支判断都写if (s == EPS) continue;，逻辑就干净了。

3.2 FIRST 与 FOLLOW 的不动点求解

两个集合都必须循环到不再变化为止。只扫一遍产生式是不够的——产生式 A 的 FIRST 依赖产生式 B，而 B 又可能排在 A 后面，但 A 的 FIRST 发生变化后，又可能反向影响 B。

void computeFirst(const Grammar& g, std::map<std::string, SymSet>& first) { for (auto& kv : g) first[kv.first] = {}; // 非终结符先置空 for (auto& kv : g) for (auto& r : kv.second) for (auto& X : r) if (!g.count(X)) first[X] = {X}; // 终结符的 FIRST 是自己 bool changed = true; while (changed) { changed = false; for (auto& kv : g) { for (auto& r : kv.second) { bool allNullable = true; for (auto& X : r) { size_t before = first[kv.first].size(); for (auto& s : first[X]) if (s != EPS) first[kv.first].insert(s); if (first[kv.first].size() != before) changed = true; if (!first[X].count(EPS)) { allNullable = false; break; } } if (allNullable && first[kv.first].insert(EPS).second) changed = true; } } } }

关键在allNullable这个标志：只有当右侧所有符号都可空，当前非终结符才可空。少写这一层判断，EPS就会沿着所有产生式扩散，最后整张预测表全是冲突。

FOLLOW 的结构类似，但传递方向相反，看的是“右侧某个非终结符后面跟什么”：

void computeFollow(const Grammar& g, const std::string& start, const std::map<std::string, SymSet>& first, std::map<std::string, SymSet>& follow) { for (auto& kv : g) follow[kv.first] = {}; follow[start].insert("$"); // 开始符号后面跟结束符 bool changed = true; while (changed) { changed = false; for (auto& kv : g) { for (auto& r : kv.second) { for (size_t i = 0; i < r.size(); ++i) { const std::string& X = r[i]; if (!g.count(X)) continue; // 终结符没有 FOLLOW SymSet firstOfRest; bool restNullable = true; for (size_t j = i + 1; j < r.size(); ++j) { for (auto& s : first.at(r[j])) if (s != EPS) firstOfRest.insert(s); if (!first.at(r[j]).count(EPS)) { restNullable = false; break; } } size_t before = follow[X].size(); for (auto& s : firstOfRest) follow[X].insert(s); if (restNullable && X != kv.first) // β 可空则 FOLLOW(A) 并入 for (auto& s : follow.at(kv.first)) follow[X].insert(s); if (follow[X].size() != before) changed = true; } } } } }

X != kv.first这个条件是为了避免自己往自己身上合并时边遍历边插入。逻辑上FOLLOW(A) ⊆ FOLLOW(A)恒成立，跳过它不损失任何信息，却能避开一类很隐蔽的迭代器问题。

3.3 预测分析表的填充与栈执行

表填充规则只有两条：对产生式A -> α，FIRST(α)里每个终结符对应填α；如果ε ∈ FIRST(α)，则对FOLLOW(A)里每个符号填α。

using Table = std::map<std::pair<std::string, std::string>, RHS>; bool buildLL1Table(const Grammar& g, const std::map<std::string, SymSet>& first, const std::map<std::string, SymSet>& follow, Table& M, std::vector<std::string>& conflicts) { auto firstOfSeq = [&](const RHS& r) { SymSet f; bool allNullable = true; for (auto& X : r) { for (auto& s : first.at(X)) if (s != EPS) f.insert(s); if (!first.at(X).count(EPS)) { allNullable = false; break; } } if (allNullable) f.insert(EPS); return f; }; for (auto& kv : g) { for (auto& r : kv.second) { SymSet f = firstOfSeq(r); for (auto& a : f) { if (a == EPS) continue; auto key = std::make_pair(kv.first, a); if (M.count(key) && M[key] != r) conflicts.push_back(kv.first + " / " + a); M[key] = r; } if (f.count(EPS)) for (auto& b : follow.at(kv.first)) { auto key = std::make_pair(kv.first, b); if (M.count(key) && M[key] != r) conflicts.push_back(kv.first + " / " + b); M[key] = r; } } } return conflicts.empty(); }

以第 2 章那套消完左递归的表达式文法为例，填出来的表长这样（空格表示查表失败，即报错）：

执行部分是显式栈。栈里放的是“还没匹配的符号”，栈顶在右边：

bool ll1Parse(const Table& M, const std::string& start, const std::vector<Token>& toks, std::vector<std::string>& trace) { std::vector<std::string> st{ "$", start }; size_t i = 0; while (!st.empty()) { std::string X = st.back(); std::string a = toSym(toks[i]); if (X == "$" && a == "$") return true; // 接受 auto it = M.find({X, a}); if (it == M.end()) { trace.push_back("error at " + a); return false; } RHS r = it->second; st.pop_back(); for (auto p = r.rbegin(); p != r.rend(); ++p) if (*p != EPS) st.push_back(*p); // 逆序压栈，跳过 ε trace.push_back(X + " -> " + join(r, " ")); if (!M.count({X, a}) || !isNonterm(X)) ++i; // 终结符匹配成功才推进输入 } return false; }

r.rbegin()逆序压栈这一句是最容易写反的地方，正序压进去，展开出来的符号顺序就整个颠倒。if (*p != EPS) st.push_back(*p)这个过滤也不能省，否则栈里会塞进一个永远匹配不上的"ε"符号，程序会在某个莫名其妙的时刻报错，而错误信息里显示的就是expect ε, got id这种让人一头雾水的内容。

3.4 冲突检测：文法不是 LL(1) 时怎么报

buildLL1Table返回conflicts非空就说明文法不是 LL(1)。这份实现不去强行消解冲突，而是把冲突位置原样打出来：A / a表示在非终结符 A 遇到终结符 a 时，有两条以上产生式都可用。这样做的好处是你能立刻定位到是哪条产生式写岔了——绝大多数冲突来自两处，要么公共左因子没提，要么ε产生式的 FIRST 判空写错。

公共左因子的典型例子是S -> if E then S | if E then S else S，两条产生式的 FIRST 交集是if。提取左因子变成S -> if E then S S'、S' -> else S | ε之后冲突消失。这一步在实验报告里一定要写，因为它是“为什么我的文法要改写成这样”的唯一合理解释。

4. SLR(1) 的 ACTION/GOTO 表：项目集规范族怎么用 C++ 存

LL(1) 走的是“看下一个符号决定展开哪条产生式”，LR 走的是“看已读入的内容和下一个符号决定移进还是归约”。前者要改文法，后者不用——这是 LR 最实在的优点，表达式文法的左递归和优先级可以原样保留。代价是状态构造复杂一个量级。

4.1 把“点”编码成（产生式编号，位置）

LR 项目就是一个产生式加一个点位置，不需要额外字段：

struct Prod { std::string lhs; RHS rhs; }; using Item = std::pair<int, int>; // {产生式编号, 点位置} using ItemSet = std::set<Item>; // 有序，便于判等与打印

用pair<int,int>而不是自定义结构体，是为了让std::set直接拿到字典序，状态判等时逐项比较即可，不用写比较函数。0 号产生式固定是S' -> S，这是 LR 分析器的增广文法约定，接受动作就挂在S' -> S ·这个项目上。

闭包运算要循环到不再新增项目，因为新加入的项目还会继续引出别的项目：

ItemSet closure(const std::vector<Prod>& P, ItemSet I) { bool changed = true; while (changed) { changed = false; std::vector<Item> snapshot(I.begin(), I.end()); // 先拷一份再遍历 for (const Item& it : snapshot) { const Prod& p = P[it.first]; if (it.second >= (int)p.rhs.size()) continue; // 归约项不产生闭包 const std::string& X = p.rhs[it.second]; if (!isNonterm(X)) continue; for (int k = 0; k < (int)P.size(); ++k) if (P[k].lhs == X && I.insert({k, 0}).second) changed = true; } } return I; }

先拷贝再遍历这一步是有意为之。虽然std::set插入不会让已有迭代器失效，但边遍历边插入会让循环次数变得不可预期，拷一份的成本远小于排查这种问题的成本。

4.2 规范族构造：用下标循环，别用范围 for

std::pair<std::vector<ItemSet>, std::map<std::pair<int, std::string>, int>> buildCanonical(const std::vector<Prod>& P) { std::vector<ItemSet> states; std::map<std::pair<int, std::string>, int> trans; auto add = [&](const ItemSet& s) -> int { for (int i = 0; i < (int)states.size(); ++i) if (states[i] == s) return i; states.push_back(s); return (int)states.size() - 1; }; add(closure(P, {{0, 0}})); for (size_t i = 0; i < states.size(); ++i) { // states 会增长，必须用下标 std::map<std::string, ItemSet> buckets; for (const Item& it : states[i]) { const Prod& p = P[it.first]; if (it.second < (int)p.rhs.size()) buckets[p.rhs[it.second]].insert({it.first, it.second + 1}); } for (auto& b : buckets) trans[{(int)i, b.first}] = add(closure(P, b.second)); } return {states, trans}; }

for (size_t i = 0; i < states.size(); ++i)这里不能用范围 for，因为循环体里add()会push_back新状态，容量一变迭代器就废了，表现是随机崩溃或者状态转移指向错误编号。这个错误我在两个不同项目里都见过，属于典型的内存问题。

4.3 ACTION/GOTO 表的编码与移进归约主循环

动作不用多态，一个字符加一个整数就够：

SLR(1) 和 LR(0) 的唯一区别在归约项的填表依据：LR(0) 对该行所有终结符都填归约，SLR(1) 只在FOLLOW(lhs)上填。就这一条，消掉了大量无谓冲突。

struct Action { char op; int arg; }; std::map<std::pair<int, std::string>, Action> action; std::map<std::pair<int, std::string>, int> goTo; // 1) 转移边分别落进 GOTO 和 ACTION for (auto& t : trans) { int s = t.first.first; const std::string& X = t.first.second; if (isNonterm(X)) goTo[{s, X}] = t.second; else action[{s, X}] = {'s', t.second}; } // 2) 归约项 for (int s = 0; s < (int)states.size(); ++s) for (const Item& it : states[s]) { const Prod& p = P[it.first]; if (it.second < (int)p.rhs.size()) continue; if (it.first == 0) { action[{s, "$"}] = {'a', 0}; continue; } for (auto& b : follow.at(p.lhs)) { auto key = std::make_pair(s, b); if (action.count(key) && action[key].op != 'r') conflicts.push_back("shift/reduce at state " + std::to_string(s)); action[key] = {'r', it.first}; } }

主循环同时维护两个栈：状态栈和属性栈（AST 节点）。两个栈必须严格同步，这是第 5 章会重点讲的一个坑。

bool lrParse(const std::vector<Prod>& P, /* action, goTo */ const std::vector<Token>& toks) { std::vector<int> st{0}; std::vector<std::unique_ptr<Node>> vals; size_t i = 0; while (true) { int s = st.back(); std::string a = toSym(toks[i]); auto it = action.find({s, a}); if (it == action.end()) return false; // 语法错误 const Action& act = it->second; if (act.op == 's') { st.push_back(act.arg); vals.push_back(std::make_unique<Node>(Node{toks[i].text, {}})); ++i; } else if (act.op == 'r') { const Prod& p = P[act.arg]; size_t n = p.rhs.size(); auto node = std::make_unique<Node>(Node{p.lhs, {}}); node->kids.assign(std::make_move_iterator(vals.end() - n), std::make_move_iterator(vals.end())); vals.erase(vals.end() - n, vals.end()); st.resize(st.size() - n); st.push_back(goTo.at({st.back(), p.lhs})); vals.push_back(std::move(node)); } else { return true; // accept } } }

归约时先assign再erase的顺序不能反，反了就是读已释放内存。std::make_move_iterator不能省，否则unique_ptr会被尝试拷贝，编译期就挂——这个报错信息很长，但本质就是“你在拷贝一个不可拷贝的类型”。

4.4 二义性与冲突：表达式文法的优先级怎么补

按上面的流程跑表达式文法E -> E + T | T、T -> T * F | F，多半会在某个状态上撞到 shift/reduce 冲突。原因是这套文法没写优先级和结合性，a + b * c和a * b + c在分析表里被同等对待。

两种处理方式，选哪种取决于实验要求。第一种是改写成无二义文法，把 `

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