语法分析器实现)
简介：这份资源面向高校计算机专业修读编译原理课程的学生与课程设计开发者，提供一套完整的C++实现方案，涵盖基于DFA的词法分析器与基于LALR(1)的语法分析器，帮助读者理解从记号序列到抽象语法树构建的完整流程，并掌握action与goto表、分析栈等核心机制。压缩包共17个文件，约2.48MB，包含3个cpp源文件、3个h头文件、6个txt测试与过程输出文件、2个md说明文档、1份docx与1份pdf课程设计报告，以及可直接运行的exe可执行文件，覆盖源码、文档与运行验证全环节。目前已有98人学习下载。读者可据此对照文法规则调试词法与语法分析流程，借助报告梳理设计思路，参考过程输出文件排查分析栈与状态转移问题，适合作为课程设计参考或编译原理实验的实践素材。
1. 从一份课设说起：DFA 词法 + LALR(1) 语法分析到底在做什么
很多人第一次接触编译原理课设，都是被那句“实现一个词法分析器和语法分析器”吓住的。真动手才发现，难点不在写代码，而在搞清楚 DFA 和 LALR(1) 这两套东西各自负责哪一段、边界在哪。词法分析器负责把字符流切成 token，DFA 是它最自然的实现模型；语法分析器负责把 token 流还原成语法树，LALR(1) 是自底向上分析里工程上最常用的一种。两者串起来，就是一个能跑通的最小编译器前端。
这套东西适合谁？正在做编译原理课设的本科生、想补编译基础的 C++ 开发者、以及需要给自研 DSL 写解析器的人。它不追求完整编译器后端，只把前端两个核心模块做扎实。下面按“先立住理论、再动手复现、最后讲坑”的顺序展开，代码用 C++ 写，环境用 VS Code 配 C/C++ 就能跑，不需要额外依赖。
2. DFA 词法分析器：从正则到状态转移表
2.1 为什么词法分析要用 DFA 而不是一堆 if-else
手写 if-else 也能切 token，但一旦关键字、标识符、数字、运算符混在一起，分支会爆炸，改一个规则要动一片代码。DFA 的好处是把“识别规则”和“识别逻辑”分开：规则用正则描述，逻辑就是一张状态转移表加一个循环。加一个关键字，只改表，不改代码。
从正则到 DFA 的标准路径是：正则表达式 → NFA（Thompson 构造）→ 子集构造 → DFA → 最小化。课设里通常不需要完整实现这条链，而是直接手写 DFA 的状态转移表，因为 C 语言子集的 token 种类有限，手写表反而更可控。常见做法是定义一个二维数组trans[state][char]，行是状态，列是输入字符，值是下一个状态，接受状态单独标记。
这里有个容易忽略的点：DFA 识别的是“最长匹配”。比如输入ifx，不能匹配到if就停，要继续读到ifx发现不是关键字，再回退成标识符。所以实现里必须记录“最后一次处于接受状态的位置”，这就是所谓的回溯点。
2.2 手写状态转移表：一个能跑的最小实现
下面这段代码实现了一个简化版 DFA 词法分析器，支持标识符、关键字、整数、单字符运算符。状态表用map存，方便扩展。
#include <iostream> #include <string> #include <map> #include <cctype> #include <vector> // 状态定义 enum State { S_START, S_ID, S_NUM, S_OP, S_ERR }; // 关键字表 const std::vector<std::string> keywords = {"if", "else", "while", "int", "return"}; struct Token { std::string type; std::string value; }; // DFA 转移函数：根据当前状态和字符返回下一状态 State transition(State s, char c) { switch (s) { case S_START: if (isalpha(c) || c == '_') return S_ID; if (isdigit(c)) return S_NUM; if (c == '+' || c == '-' || c == '*' || c == '/') return S_OP; return S_ERR; case S_ID: if (isalnum(c) || c == '_') return S_ID; return S_ERR; // 遇到非标识符字符，交给外层处理 case S_NUM: if (isdigit(c)) return S_NUM; return S_ERR; case S_OP: return S_ERR; // 单字符运算符，读一个就结束 default: return S_ERR; } } std::vector<Token> lex(const std::string& src) { std::vector<Token> tokens; size_t i = 0; while (i < src.size()) { if (isspace(src[i])) { i++; continue; } State cur = S_START; size_t start = i; size_t lastAccept = std::string::npos; State lastState = S_ERR; // 最长匹配循环 while (i < src.size()) { State next = transition(cur, src[i]); if (next == S_ERR) break; cur = next; i++; if (cur == S_ID || cur == S_NUM || cur == S_OP) { lastAccept = i; lastState = cur; } } if (lastAccept == std::string::npos) { std::cerr << "词法错误 at " << start << ": " << src[start] << std::endl; i = start + 1; continue; } std::string lexeme = src.substr(start, lastAccept - start); i = lastAccept; // 回退到最长匹配位置 if (lastState == S_ID) { bool isKw = false; for (auto& k : keywords) { if (lexeme == k) { tokens.push_back({"KEYWORD", lexeme}); isKw = true; break; } } if (!isKw) tokens.push_back({"ID", lexeme}); } else if (lastState == S_NUM) { tokens.push_back({"NUM", lexeme}); } else if (lastState == S_OP) { tokens.push_back({"OP", lexeme}); } } return tokens; } int main() { std::string src = "int main ifx 123 + return"; auto tokens = lex(src); for (auto& t : tokens) { std::cout << t.type << " : " << t.value << std::endl; } return 0; }这段代码的核心逻辑在lex函数里的最长匹配循环。lastAccept记录最后一次处于接受状态的位置，当transition返回S_ERR时跳出内层循环，然后回退到lastAccept。参数方面，keywords表决定哪些标识符被提升为关键字，transition函数里的字符判断决定状态走向。如果要做更完整的 C 语言子集，把S_OP扩展成多字符运算符（如==、<=）时，需要在transition里加中间状态，比如S_OP_EQ，读到=后再看下一个字符是不是=。
提示：
lastAccept初始化为npos，如果第一个字符就非法，直接报错并跳过，避免死循环。
2.3 符号表：词法阶段就要埋的伏笔
热词里有人搜“编译原理符号表”，这不是语法分析才需要的东西。词法阶段识别出标识符后，就应该往符号表里插一条记录，记录名字、类型（未知）、作用域。符号表可以用unordered_map<string, Symbol>实现，Symbol结构体里放type、scope、line。这样语法分析阶段做类型检查时，直接查表就行，不用重新扫一遍 token 流。
我一般会在词法分析器里加一个symtab成员，遇到ID类型的 token 就调用insert，如果已存在就更新行号。注意别把关键字也插进去，关键字是保留字，不是用户标识符。
3. LALR(1) 语法分析器：从文法到分析表
3.1 LALR(1) 和 LR(1)、SLR 的区别，以及为什么课设选它
LR 系列分析器分三种：SLR(1)、LR(1)、LALR(1)。SLR 只看 FOLLOW 集，冲突多；LR(1) 给每个项目带一个展望符，状态数爆炸；LALR(1) 把 LR(1) 中同心项目集合并，状态数和 SLR 差不多，但分析能力接近 LR(1)。课设选 LALR(1)，是因为它能在“状态数可接受”和“冲突少”之间取平衡，而且 C 语言子集的文法用 LALR(1) 基本不会产生移进-归约冲突。
构造 LALR(1) 分析表的完整流程是：拓广文法 → 构造 LR(1) 项目集族 → 合并同心项目集 → 构造 ACTION 和 GOTO 表。课设里如果手写，通常直接写文法然后跑一个生成器；如果自己实现，重点在项目集闭包的计算和展望符的传播。
这里有个关键概念：项目A → α·Bβ, a的展望符a来自 FIRST(βa)。闭包计算时，如果B → γ是产生式，就要把FIRST(βa)里的每个终结符作为B → ·γ的展望符。合并同心项目集时，把核心项目相同、展望符不同的项目集合并，展望符取并集。
3.2 用 C++ 实现项目集闭包与 GOTO 函数
下面这段代码实现了 LR(1) 项目集闭包和 GOTO 函数，是构造 LALR(1) 分析表的基础。文法用产生式数组表示，·用位置索引表示。
#include <iostream> #include <vector> #include <set> #include <map> #include <string> // 产生式：左部，右部，点位置 struct Item { int prod; // 产生式编号 int dot; // 点位置 std::set<std::string> lookahead; // 展望符 bool operator<(const Item& o) const { if (prod != o.prod) return prod < o.prod; return dot < o.dot; } }; // 文法产生式：左部 -> 右部 struct Production { std::string lhs; std::vector<std::string> rhs; }; std::vector<Production> grammar; std::map<std::string, std::set<std::string>> firstSets; // 计算 FIRST 集（简化版，假设已预处理） std::set<std::string> firstOfSequence(const std::vector<std::string>& seq, int start) { std::set<std::string> result; for (int i = start; i < seq.size(); i++) { const std::string& sym = seq[i]; if (firstSets.count(sym)) { result.insert(firstSets[sym].begin(), firstSets[sym].end()); if (!firstSets[sym].count("ε")) break; } else { result.insert(sym); // 终结符 break; } } return result; } // 闭包计算 std::set<Item> closure(std::set<Item> items) { bool changed = true; while (changed) { changed = false; std::set<Item> newItems = items; for (const auto& item : items) { const Production& p = grammar[item.prod]; if (item.dot >= p.rhs.size()) continue; std::string B = p.rhs[item.dot]; // 如果 B 是非终结符 for (int i = 0; i < grammar.size(); i++) { if (grammar[i].lhs != B) continue; // 计算 FIRST(βa) std::vector<std::string> beta(p.rhs.begin() + item.dot + 1, p.rhs.end()); std::set<std::string> firstBeta = firstOfSequence(beta, 0); std::set<std::string> newLookahead; if (firstBeta.count("ε") || beta.empty()) { newLookahead.insert(item.lookahead.begin(), item.lookahead.end()); } newLookahead.insert(firstBeta.begin(), firstBeta.end()); newLookahead.erase("ε"); Item newItem{i, 0, newLookahead}; // 检查是否已存在相同 prod 和 dot 的项 bool found = false; for (auto& it : newItems) { if (it.prod == newItem.prod && it.dot == newItem.dot) { size_t before = it.lookahead.size(); it.lookahead.insert(newLookahead.begin(), newLookahead.end()); if (it.lookahead.size() != before) changed = true; found = true; break; } } if (!found) { newItems.insert(newItem); changed = true; } } } items = newItems; } return items; } // GOTO 函数 std::set<Item> goTo(const std::set<Item>& items, const std::string& X) { std::set<Item> moved; for (const auto& item : items) { const Production& p = grammar[item.prod]; if (item.dot < p.rhs.size() && p.rhs[item.dot] == X) { moved.insert({item.prod, item.dot + 1, item.lookahead}); } } return closure(moved); }这段代码里，closure函数是核心。它遍历项目集，对每个点后面的非终结符B，计算FIRST(βa)，然后把B → ·γ加进去。注意newLookahead的处理：如果β能推导出空串，要把原项目的展望符也加进去。goTo函数把点向后移一位，再求闭包。参数方面，grammar是全局产生式表，firstSets需要提前算好。实际课设里，firstSets可以用一个单独的函数从文法生成，这里为了聚焦闭包逻辑省略了。
注意：合并同心项目集时，只合并核心项目（点不在最左的产生式）相同的项目集，展望符取并集。这一步做错，ACTION 表会多出很多不必要的归约项。
3.3 构造 ACTION 和 GOTO 表：移进-归约冲突怎么处理
有了项目集族和 GOTO 函数，构造分析表就顺了。对每个项目集I：
- 如果
A → α·aβ, b且a是终结符，ACTION[I, a] = 移进 goTo(I, a)； - 如果
A → α·, a，ACTION[I, a] = 归约 A → α； - 如果
S' → S·, $，ACTION[I, $] = 接受； - 对非终结符
A，GOTO[I, A] = goTo(I, A)。
冲突主要有两种：移进-归约冲突和归约-归约冲突。LALR(1) 里归约-归约冲突通常意味着文法有二义性，需要改写文法。移进-归约冲突最常见的是悬空 else 问题，标准解法是“移进优先”，因为移进相当于把 else 绑定到最近的 if。如果冲突解决不了，说明文法不是 LALR(1) 的，得换文法或换分析方式。
课设里我一般会写一个冲突检测函数，在填表时如果发现同一个格子被填了两次，就打印冲突类型和涉及的产生式，方便定位。别等到跑分析的时候才发现表是错的，那时候调试成本高得多。
4. 把两个分析器串起来：驱动代码与测试用例
4.1 主驱动流程：token 流怎么喂给 LALR(1)
词法分析器输出vector<Token>，语法分析器需要一个 token 流接口。常见做法是把Token转成终结符字符串，比如ID对应文法里的id，NUM对应num，关键字直接用小写。然后 LALR(1) 驱动器维护一个状态栈和一个符号栈，循环读 token，查 ACTION 表决定移进还是归约。
// 简化的 LALR(1) 驱动器 bool parse(const std::vector<Token>& tokens) { std::vector<int> stateStack = {0}; // 初始状态 std::vector<std::string> symbolStack; size_t pos = 0; while (true) { int state = stateStack.back(); std::string input = (pos < tokens.size()) ? tokens[pos].type : "$"; auto action = actionTable[state].find(input); if (action == actionTable[state].end()) { std::cerr << "语法错误 at token " << pos << ": " << input << std::endl; return false; } if (action->second.type == SHIFT) { stateStack.push_back(action->second.target); symbolStack.push_back(input); pos++; } else if (action->second.type == REDUCE) { int prod = action->second.target; int len = grammar[prod].rhs.size(); for (int i = 0; i < len; i++) { stateStack.pop_back(); symbolStack.pop_back(); } symbolStack.push_back(grammar[prod].lhs); int gotoState = gotoTable[stateStack.back()][grammar[prod].lhs]; stateStack.push_back(gotoState); } else if (action->second.type == ACCEPT) { return true; } } }驱动器的逻辑很直白：移进就把状态和目标压栈，归约就弹出对应长度的符号和状态，然后查 GOTO 表压入新状态。参数方面，actionTable是二维 map，action->second.type区分移进、归约、接受。注意归约后查 GOTO 用的是归约前栈顶的状态，不是归约后的，这个顺序别搞反。
4.2 测试用例设计：从简单表达式到嵌套语句
测试用例要覆盖三类：正常语句、边界情况、错误输入。正常语句比如int a = 1 + 2 * 3;，验证运算符优先级；边界情况比如空语句;、嵌套括号((a))；错误输入比如int = 3;，看报错位置对不对。
我一般会准备一个测试文件，每行一个用例，跑完打印“通过/失败”和错误位置。课设报告里附上测试结果，比空口说“实现了”有说服力得多。如果时间够，可以加一个简单的语法树打印功能，把归约过程可视化，调试时一眼就能看出哪步归约错了。
5. 避坑与排查：课设里最容易翻车的 5 个点
5.1 词法分析器死循环，token 流卡住
现象：程序跑起来不报错，但一直不结束，CPU 占用高。原因：最长匹配循环里，如果transition一直返回非S_ERR，但lastAccept没更新，i可能不前进。比如S_OP状态读到下一个字符还是运算符，transition返回S_ERR跳出，但如果lastAccept是npos，i只前进了一位，外层循环继续，又进入同样的状态。解决：在lastAccept为npos时，强制i = start + 1，并打印错误字符。
5.2 LALR(1) 分析表出现归约-归约冲突
现象：填表时同一个格子被两个不同的归约产生式占用。原因：文法有二义性，或者两个产生式的右部在某个状态下都能归约。解决：先检查文法是否有二义性，比如E → E + E | E * E这种没处理优先级的写法。改写文法，引入T和F分层。如果文法本身没问题，检查展望符计算是否正确，FIRST集有没有漏掉空串情况。
5.3 移进-归约冲突导致 else 绑定错误
现象：if (a) if (b) c; else d;解析成if (a) { if (b) c; else d; }，但期望是if (a) { if (b) c; } else d;。原因：LALR(1) 默认移进优先，把else移进内层if。解决：如果语言规范要求else绑定最近的if，移进优先就是对的，不用改。如果要求绑定外层，得改写文法，用matched和unmatched区分。
5.4 符号表作用域没处理，变量重复定义不报错
现象：同一个作用域里定义两个同名变量，程序不报错。原因：符号表只做了插入，没做重复检查。解决：在insert时先查当前作用域是否已存在同名符号，存在就报错。作用域用栈式结构管理，进入块时压入新作用域，退出时弹出。
5.5 VS Code 里 C++ 跳转失效，改代码全靠猜
现象：#include头文件能找到，但函数跳转和变量提示全没了。原因：VS Code 的 C/C++ 扩展没配好c_cpp_properties.json，或者compile_commands.json没生成。解决：在.vscode/c_cpp_properties.json里配好includePath和compilerPath，用 CMake 的话加-DCMAKE_EXPORT_COMPILE_COMMANDS=ON生成编译数据库。这个坑很常见，配好之后开发效率翻倍。
6. 进阶技巧：用表驱动 + 单元测试把课设做成可复用的前端
课设做完不是终点。如果想让这套代码真正能用在后续项目里，有两个方向值得投入：一是把 DFA 和 LALR(1) 的表生成过程自动化，二是给每个模块写单元测试。
表驱动自动化的意思是，词法规则用配置文件描述，语法产生式用 BNF 写，然后写一个生成器自动产出状态转移表和分析表。这样换一个语言子集，只改配置，不改代码。我一般会用一个简单的 JSON 或自定义格式存规则，生成器用 Python 写，产出的表用 C++ 数组或constexpr结构体嵌入。这样课设代码就从“一次性作业”变成了“可复用工具”。
单元测试方面，词法分析器测三类：正常 token、最长匹配、错误字符。语法分析器测四类：正常语句、优先级、嵌套、错误恢复。用 Catch2 或 Google Test 都行，VS Code 里配好测试任务，跑一次几秒钟。下面是一个 Catch2 的测试片段：
#define CATCH_CONFIG_MAIN #include <catch2/catch.hpp> TEST_CASE("Lexer longest match", "[lexer]") { auto tokens = lex("ifx 123"); REQUIRE(tokens.size() == 2); REQUIRE(tokens[0].type == "ID"); REQUIRE(tokens[0].value == "ifx"); REQUIRE(tokens[1].type == "NUM"); } TEST_CASE("Parser precedence", "[parser]") { auto tokens = lex("1 + 2 * 3"); REQUIRE(parse(tokens) == true); }测试用例不用多，覆盖关键路径就行。跑通之后，每次改文法或改状态表，先跑测试，绿了再继续。这个习惯能省下大量“改一处崩三处”的时间。
最后说个我自己的教训：第一次做课设时，我把词法和语法写在一个文件里，调试时根本分不清是 token 切错了还是分析表填错了。后来拆成两个独立模块，各自有测试，问题定位从半小时缩短到两分钟。如果你正在做这个课设，先把两个分析器的接口定清楚，再各自实现，别急着串起来。希望帮到你。
本文还有配套的精品资源，点击获取
