简介：这份资源面向高校计算机专业学生与编译原理课程设计者，提供一套基于C++实现的SNL语言编译器源码，覆盖词法分析、递归下降语法分析与LL1语法分析三大核心模块，适合需要完成课程设计或深入理解编译器前端流程的学习者。压缩包共36个文件，以9个h头文件与9个cpp源文件为主体，另有6个txt测试用例、4个xml配置、2个gif演示图及py、snl、pro、ui等辅助文件，整体约1.43MB，结构清晰便于按模块阅读。目前已有767人学习下载。源码中词法分析器负责识别关键字、标识符、常量与运算符并生成标记序列；递归下降分析为每个语法结构编写对应函数；LL1部分则涉及First集、Follow集计算与预测分析表构造，并配有图形界面展示分析过程。读者可借此对照理论完成从正则匹配到语法推导的完整实践，掌握左递归处理与错误恢复思路，为后续复杂编译器设计打下基础。
1. 从一份 SNL 编译器作业说起：词法、递归下降与 LL1 到底怎么串起来
很多人第一次拿到「编译原理课程设计」这个任务时，脑子里是分裂的：课本上讲的是 DFA、FIRST 集、FOLLOW 集、预测分析表，可真正要交的东西是一份能跑起来的 C++ 源码，输入一段 SNL 语言程序，输出词法单元序列、语法树或者报错位置。这两者之间的鸿沟，就是这篇笔记要填的东西。
SNL 是一门教学用的类 Pascal 小型语言，结构清晰、关键字少，非常适合拿来练手。整个任务通常拆成三块：词法分析负责把字符流切成 token；递归下降语法分析负责按文法手写下降函数、边匹配边建树；LL1 语法分析负责用预测分析表加显式栈做非递归推导。三块共用同一套 token 定义和文法，串起来才是一份完整的课程设计。适合正在做编译原理实验、被 FIRST/FOLLOW 集绕晕、或者想用 C++ 把理论落成代码的人。下面按「先立住理论、再动手复现」的顺序讲，每一步都给可抄的代码和参数。
2. SNL 词法分析器：从字符流到 token 序列的 C++ 实现
词法分析是整个编译器的入口，它的输出质量直接决定后面语法分析好不好写。SNL 的单词种类不多：关键字（program、var、procedure、begin、end、if、then、else、while、do、read、write、return 等）、标识符、整数常量、运算符和界符。核心思路是「最长匹配 + 预读一个字符」，用状态机把每类单词识别出来。
2.1 token 结构体与单词种别码设计
先定数据结构，这是后面所有模块的公共契约。种别码用枚举，token 里同时保留原始字符串和行号，行号是后面报错定位的关键，很多人一开始不存，后面排错时追悔莫及。
// token.h —— 词法单元定义，语法分析模块直接复用 enum TokenType { TOK_PROGRAM, TOK_PROCEDURE, TOK_VAR, TOK_BEGIN, TOK_END, TOK_IF, TOK_THEN, TOK_ELSE, TOK_WHILE, TOK_DO, TOK_READ, TOK_WRITE, TOK_RETURN, TOK_ID, // 标识符 TOK_INT, // 整数常量 TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_DIV, TOK_EQ, TOK_NEQ, TOK_LT, TOK_LE, TOK_GT, TOK_GE, TOK_ASSIGN, // := TOK_LPAREN, TOK_RPAREN, TOK_SEMI, TOK_COMMA, TOK_DOT, TOK_EOF, TOK_ERROR }; struct Token { TokenType type; std::string lexeme; // 原始单词，报错和建符号表都要用 int line; // 行号，从 1 开始 };种别码的设计原则是「一类一码」，不要把每个关键字都单独设一个枚举值再写一堆 if，那样代码会爆炸。关键字识别用一张静态 map 做查表，标识符先按规则读出来，再回查是不是关键字，这是最省事的做法。
2.2 关键字表与标识符、常量的识别逻辑
关键字表用std::unordered_map<std::string, TokenType>初始化一次即可。识别标识符时，只要首字符是字母，就持续读字母或数字，读到非字母数字为止，然后查表决定是关键字还是普通标识符。整数常量同理，连续读数字，注意溢出可以先不处理，课程设计范围内够用。
// lexer.cpp —— 核心扫描循环（节选） static const std::unordered_map<std::string, TokenType> keywords = { {"program", TOK_PROGRAM}, {"procedure", TOK_PROCEDURE}, {"var", TOK_VAR}, {"begin", TOK_BEGIN}, {"end", TOK_END}, {"if", TOK_IF}, {"then", TOK_THEN}, {"else", TOK_ELSE}, {"while", TOK_WHILE}, {"do", TOK_DO}, {"read", TOK_READ}, {"write", TOK_WRITE}, {"return", TOK_RETURN} }; Token Lexer::nextToken() { skipWhitespaceAndComment(); // 跳过空白和 { 注释 } if (pos >= src.size()) return {TOK_EOF, "", line}; char c = src[pos]; if (isalpha(c)) { // 标识符或关键字 std::string s; while (pos < src.size() && isalnum(src[pos])) s += src[pos++]; auto it = keywords.find(s); return {it != keywords.end() ? it->second : TOK_ID, s, line}; } if (isdigit(c)) { // 整数常量 std::string s; while (pos < src.size() && isdigit(src[pos])) s += src[pos++]; return {TOK_INT, s, line}; } // 运算符与界符：先处理双字符 := <= >= <>，再处理单字符 if (c == ':' && peek() == '=') { pos += 2; return {TOK_ASSIGN, ":=", line}; } if (c == '<' && peek() == '=') { pos += 2; return {TOK_LE, "<=", line}; } if (c == '>' && peek() == '=') { pos += 2; return {TOK_GE, ">=", line}; } if (c == '<' && peek() == '>') { pos += 2; return {TOK_NEQ, "<>", line}; } // ... 单字符分支略 pos++; return {TOK_ERROR, std::string(1, c), line}; }这里的关键参数是pos和line两个游标：pos是字符下标，line在遇到换行时自增。双字符运算符必须先判断，否则:=会被拆成:和=两个错误 token，这是新手最常翻的车。注释用{ }包裹，跳过时同样要维护行号，否则报错行号会整体偏移。
2.3 用测试用例验证词法输出
写完别急着接语法分析，先单独跑一遍词法，把 token 序列打出来核对。给一段最小 SNL 程序：
program p var x, y; begin x := 10; y := x + 1 end.期望输出里program是 TOK_PROGRAM，x是 TOK_ID，:=是 TOK_ASSIGN，10是 TOK_INT，最后.是 TOK_DOT。如果:=被拆开、或者行号对不上，就回到 2.2 检查双字符分支和换行处理。这一步过了，词法模块才算真正可用。
3. 递归下降语法分析：手写下降函数与语法树构建
递归下降是课程设计里最直观的语法分析方式：为文法里每个非终结符写一个函数，函数内部按产生式右部依次调用其他函数或匹配终结符。SNL 的文法没有左递归，天然适合递归下降，不用做消除左递归的改写，这是它比很多语言好写的地方。
3.1 消除左递归与提取公因子后的 SNL 文法
递归下降的前提是文法不能有左递归，也不能有需要大量回溯的公共前缀。SNL 的表达式文法通常写成：
expr -> term { (+|-) term } term -> factor { (*|/) factor } factor -> ID | INT | ( expr )这种「用循环处理左递归」的写法，等价于把expr -> expr + term | term改写成迭代形式，既避免了左递归，又不用建复杂的分析表。语句部分同理，stmt -> if ... | while ... | ID := expr | ...，每个分支靠当前 token 就能唯一确定，不需要回溯。
3.2 每个非终结符对应一个下降函数
下降函数的骨架是「看当前 token 决定走哪条产生式」。以语句和表达式为例：
// parser.cpp —— 递归下降核心函数 Token cur; // 当前 lookahead token void advance() { cur = lexer.nextToken(); } // expr -> term { (+|-) term } ExprNode* parseExpr() { ExprNode* node = parseTerm(); while (cur.type == TOK_PLUS || cur.type == TOK_MINUS) { TokenType op = cur.type; advance(); ExprNode* rhs = parseTerm(); node = new BinaryNode(op, node, rhs); // 建树 } return node; } // term -> factor { (*|/) factor } ExprNode* parseTerm() { ExprNode* node = parseFactor(); while (cur.type == TOK_STAR || cur.type == TOK_DIV) { TokenType op = cur.type; advance(); node = new BinaryNode(op, node, parseFactor()); } return node; } // factor -> ID | INT | ( expr ) ExprNode* parseFactor() { if (cur.type == TOK_ID) { auto n = new IdNode(cur.lexeme); advance(); return n; } if (cur.type == TOK_INT) { auto n = new IntNode(cur.lexeme); advance(); return n; } if (cur.type == TOK_LPAREN) { advance(); ExprNode* n = parseExpr(); expect(TOK_RPAREN); // 匹配右括号，不匹配就报错 return n; } error("factor 处期望 ID/INT/("); return nullptr; }advance()是唯一的 token 推进点，所有函数都通过它读下一个 token，这样 lookahead 永远只有一个，逻辑清晰。expect()负责匹配指定终结符，失败时打印行号和期望的 token 类型。建树用多态节点，BinaryNode、IdNode、IntNode各自实现求值或打印，后面想加语义分析直接扩展即可。
3.3 语法树节点设计与错误恢复
节点基类给一个虚函数print(int indent)，用来缩进打印树结构，方便肉眼验证。错误恢复上，递归下降最简单的策略是「恐慌模式」：遇到不匹配的 token 就报错，然后跳到下一个分号或end再继续，避免一个错误引发连锁报错。课程设计里能做到「报出第一处错误并给出行号」就已经合格，想加分再做多错误恢复。
struct Node { virtual ~Node() = default; virtual void print(int indent = 0) const = 0; }; struct BinaryNode : Node { TokenType op; Node* lhs; Node* rhs; void print(int indent) const override { std::cout << std::string(indent, ' ') << "Binary(" << op << ")\n"; lhs->print(indent + 2); rhs->print(indent + 2); } };参数上唯一要注意的是内存管理：课程设计里节点用new建、程序结束不释放也能跑，但想写得干净就用std::unique_ptr持有子节点，父节点只存裸指针观察。这个取舍看你对 C++ 的熟悉程度，不影响功能正确性。
4. LL1 语法分析：FIRST/FOLLOW 集与预测分析表落地
LL1 是课程设计里理论味最重的部分，也是考试和实验报告最爱考的地方。它的核心是：对文法每个非终结符求 FIRST 集和 FOLLOW 集，据此构造一张预测分析表，分析时用一个显式栈代替递归调用。相比递归下降，LL1 的好处是「非递归、可表格化」，坏处是文法必须无左递归、无公共前缀，且要能处理空产生式。
4.1 FIRST 集与 FOLLOW 集的手算与代码求解
FIRST(A) 是 A 能推导出的所有串的首终结符集合；FOLLOW(A) 是在某个句型中紧跟在 A 后面的终结符集合。手算规则课本讲得很细，代码求解用迭代到不动点的方式最稳：
// first_follow.cpp —— 迭代求 FIRST 集 // 反复扫描所有产生式，直到集合不再变化 bool changed = true; while (changed) { changed = false; for (auto& prod : productions) { std::string A = prod.lhs; auto& firstA = firstSet[A]; size_t before = firstA.size(); // X1 X2 ... Xn：把 FIRST(X1) 中非 ε 的加入 FIRST(A) for (auto& X : prod.rhs) { if (isTerminal(X)) { firstA.insert(X); break; } for (auto& t : firstSet[X]) if (t != "ε") firstA.insert(t); if (firstSet[X].count("ε") == 0) break; // X 不能推出 ε，停 if (&X == &prod.rhs.back()) firstA.insert("ε"); } if (firstA.size() != before) changed = true; } }FOLLOW 集规则三条：开始符号的 FOLLOW 含#；对A -> αBβ，把 FIRST(β) 非 ε 部分加入 FOLLOW(B)；若 β 能推出 ε，把 FOLLOW(A) 加入 FOLLOW(B)。同样用迭代到不动点实现。参数上要注意空串统一用字符串"ε"表示，别用空字符串，否则集合运算会出玄学问题。
4.2 预测分析表的构造与冲突处理
有了 FIRST 和 FOLLOW，对每条产生式A -> α：把 FIRST(α) 中每个终结符对应的表项M[A][t]填成这条产生式；若 α 能推出 ε，则把 FOLLOW(A) 中每个终结符对应的表项也填上。填表时如果发现某个格子已经有值，就是 LL1 冲突，说明文法不是 LL1 的，需要改写文法。
| 非终结符 | id | int | ( | ) | + | * | # |
|---|---|---|---|---|---|---|---|
| expr | expr->term... | expr->term... | expr->term... | ||||
| term | term->factor... | term->factor... | term->factor... | ||||
| factor | factor->id | factor->int | factor->(expr) |
表里空格代表出错。构造时用map<pair<string,string>, Production>存，查表 O(log n)，课程设计规模完全够用。
4.3 用显式栈跑一遍 LL1 分析流程
分析流程：栈初始压入#和开始符号，读入第一个 token；循环比较栈顶和当前 token，栈顶是非终结符就查表把产生式右部逆序压栈，是终结符就匹配并读下一个 token，直到栈空或出错。
// ll1_parser.cpp —— 显式栈驱动 std::stack<std::string> stk; stk.push("#"); stk.push(startSymbol); Token tok = lexer.nextToken(); while (!stk.empty()) { std::string top = stk.top(); if (isTerminal(top) || top == "#") { if (top == tokenName(tok)) { // 匹配成功 stk.pop(); if (top != "#") tok = lexer.nextToken(); } else { error("期望 " + top + " 实际 " + tokenName(tok)); break; } } else { // 非终结符，查表 auto key = std::make_pair(top, tokenName(tok)); if (!table.count(key)) { error("预测表无表项"); break; } stk.pop(); auto rhs = table[key].rhs; for (auto it = rhs.rbegin(); it != rhs.rend(); ++it) if (*it != "ε") stk.push(*it); // 逆序压栈 } }逆序压栈是这里最容易写错的地方：产生式右部term + expr要按expr、+、term的顺序压，才能保证栈顶先匹配term。空产生式不压栈，直接跳过。跑通后拿 2.3 那段 SNL 程序验证，输出应该是「匹配成功」而不是中途报错。
5. 避坑与排查：SNL 编译器实现里最容易翻车的 5 个点
这一章全是血泪经验，每一条都是实际写课程设计时大概率会撞上的。
现象一：:=被识别成两个 token，语法分析报「期望 ID 实际 :」。原因是词法里单字符分支先于双字符分支执行。解决：把所有双字符运算符（:=、<=、>=、<>）的判断放在单字符之前，用peek()预读下一个字符。
现象二：递归下降遇到if语句时无限递归或栈溢出。原因是语句函数里对if分支没有正确消费then、else关键字，导致 lookahead 卡住不动。解决：每个分支匹配完关键字后必须调用advance()，确保 token 一定前进；调试时在advance()里打印当前 token，一眼就能看出卡在哪。
现象三：FIRST 集求出来是空的或少了元素。原因是迭代终止条件写错，或者空产生式ε的处理漏了。解决：用「集合大小不再变化」作为终止条件，而不是固定循环次数；空串统一用"ε"字符串，检查每个产生式右部为空时是否正确加入ε。
现象四：LL1 预测分析表出现冲突，程序报「预测表无表项」。原因是文法本身不是 LL1 的，比如表达式有公共前缀或隐含左递归。解决：先确认文法已消除左递归、提取公因子；如果还冲突，说明该文法不适合 LL1，改用递归下降或 SLR，别硬凑。
现象五：报错行号总是差一行或指向文件末尾。原因是词法里跳过注释和空白时没有同步维护line变量，或者\r\n换行只处理了\n。解决：把行号自增统一放在「消费换行符」的地方，注释跳过函数里也要检查换行；读文件时用文本模式，避免\r残留。
6. 把三个模块串成一条流水线：验证方法与一个提效技巧
三个模块单独跑通只是及格线，真正要交的是「一份源码、一条命令、从输入到输出」。我一般会写一个main.cpp做驱动：读入.snl源文件，先跑词法把 token 存进vector，再让递归下降和 LL1 各自消费这份 token 序列，最后对比两者的分析结果是否一致。这个「双路对拍」是验证正确性最省事的办法——如果递归下降说语法正确、LL1 却报错，那一定是预测分析表或 FIRST/FOLLOW 算错了，反过来也一样。
// main.cpp —— 双路对拍驱动 int main(int argc, char** argv) { std::ifstream in(argv[1]); std::string src((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>()); // 路线一：递归下降 Lexer lex1(src); Parser rd(lex1); bool ok1 = rd.parseProgram(); // 路线二：LL1 Lexer lex2(src); LL1Parser ll1(lex2); bool ok2 = ll1.parse(); std::cout << "递归下降: " << (ok1 ? "通过" : "失败") << "\n"; std::cout << "LL1 : " << (ok2 ? "通过" : "失败") << "\n"; return (ok1 == ok2) ? 0 : 1; // 结果不一致返回非零，方便脚本判断 }参数上，argv[1]是源文件路径，返回码 0 表示两路一致、非零表示有分歧，这样可以直接挂到脚本里批量跑测试用例。测试集建议覆盖：空程序、只有声明没有语句、嵌套 if-while、表达式优先级（1+2*3应解析成1+(2*3)）、以及故意写错的语法（缺分号、括号不匹配），看两路是否都能报出同一行。
一个提效技巧：把 token 序列和语法树都支持「打印成文本」，然后用diff对比不同版本改动前后的输出。改文法或改词法时，只要 diff 没变化，就说明没引入回归。这个习惯让我在课程设计后期改一处、验一处，省了大量手工回归的时间。写编译器这种模块耦合紧的作业，最怕的就是改 A 崩 B，而可打印的中间表示就是你的后悔药。
最后说句实在的：SNL 这套东西麻雀虽小，词法、递归下降、LL1 三块正好覆盖编译前端的主干。把它写扎实，比抄一份能跑但看不懂的源码值钱得多。希望帮到你。
本文还有配套的精品资源，点击获取
