手写LALR(1)语法分析器：从BNF到可调试action表

简介：本资源是一份面向高校计算机专业本科生的编译原理课程设计实践材料，完整实现基于DFA的词法分析器与基于LALR(1)的语法分析器，覆盖编译前端核心环节，助力理解词法识别、状态转换、分析表构造及自底向上语法分析全过程。压缩包共17个文件，含3个C++源文件（.cpp）、3个头文件（.h）构成可编译主体，6个文本文件（.txt）提供测试样例、分析过程日志与文法定义，另有PDF与DOCX双格式课程设计报告、README说明文档及已编译的Windows可执行文件（.exe），整体大小2.48MB，结构清晰、开箱即用。已有98人学习下载，资源附带详细使用说明与分析过程截图，涵盖action/goto表生成、分析栈动态演进等关键教学难点，便于对照理论复现实验、调试验证算法逻辑，并支撑课程报告撰写与答辩准备。

1. 这不是玩具项目：一个能跑通真实 C++ 源码的 LALR(1) 语法分析器，连while (i < 10) { i++; }都能推导出完整分析栈

你手头那份《编译原理》课设报告里写的“实现了 LALR(1) 分析器”，大概率只是画了张 goto 表草图、手算几个状态转移——但这个compiler-master.zip不是。它真能把LexicalAnalysisSourceProgram.txt里一行int a = b + 3 * (c - 1);切成INT ID ASSIGN ID PLUS NUM MUL LPAREN ID MINUS NUM RPAREN SEMI这串 token，再用实打实的 LALR(1) action/goto 表驱动分析栈，一步步 shift-reduce 出一棵带节点编号的语法树，最后输出SyntaxAnalysisProcess.txt里那种带时间戳、栈顶符号、动作类型（shift/reduce/accept）和归约产生式的完整执行日志。它不依赖 LLVM 或 ANTLR，纯 C++ 手写状态机与分析表构造逻辑；可执行文件Compiler.exe双击就能跑，不需要配环境、不报vcruntime140.dll缺失——因为所有依赖已静态链接进去了。适合三类人：刚学完龙书第 4 章想验证自己理解是否正确的本科生；被课设 deadline 追着跑、需要可运行参考实现的工科生；还有想快速拆解 LALR(1) 表生成逻辑、避开 yacc/bison 黑匣子的嵌入式开发者。它不教你怎么写 parser generator，但它把 parser generator 的核心输出——那张让人头皮发麻的 action 表——变成了一段你能单步调试、改参数、看内存变化的 C++ 代码。

2. 从源码结构到核心流程：为什么选 DFA + LALR(1)，而不是正则+递归下降？

2.1 源码目录即设计蓝图：六个关键文件如何分工协作

整个compiler-master的源码结构不是随意堆砌，而是严格对应编译前端流水线：

• LexicalAnalysis.h/.cpp：DFA 实现层。不是用 regex 库匹配字符串，而是用二维跳转表dfa_table[state][char]做状态迁移。字符集预处理为0-9、a-z、A-Z、+-*/等 12 类，每个状态对应一个enum TokenType（如KEYWORD_INT,IDENTIFIER,NUMBER），最终输出vector<Token>。
• SyntaxAnalysis.h/.cpp：LALR(1) 核心。不调用任何外部 parser generator，所有 action/goto 表在initTables()中硬编码生成。文法定义在SyntaxAnalysisGrammar.txt里（BNF 格式），程序读取后自动计算 FIRST/FOLLOW 集、构造 LR(0) 项集族、合并冲突项生成 LALR(1) 表——这部分代码就是龙书算法 4.7 节的 C++ 翻译。
• main.cpp：胶水层。按顺序调用LexicalAnalysis::analyze()→SyntaxAnalysis::parse()，把词法结果喂给语法分析器，并将SyntaxAnalysisProcess.txt的每行日志映射到控制台输出。
• header.h：全局定义。包含Token结构体（type,value,line_num）、Production结构体（lhs,rhs,length）、以及MAX_STATES/MAX_SYMBOLS等硬编码尺寸——这是你后续调大文法规模时第一个要改的地方。
• Compiler.exe：已编译产物。由 Visual Studio 2019 x64 工具链生成，静态链接/MT，无需安装 VC++ Redistributable（这点直接干掉 80% 的新手运行失败场景）。

提示：SyntaxAnalysisGrammar.txt是你修改文法的唯一入口。它不是示例，而是实际参与编译的输入——initTables()函数会逐行解析它，生成action_table[256][128]和goto_table[256][64]。别试图手动改表，改文法再重跑Compiler.exe。

2.2 DFA 词法分析器：状态跳转表比正则引擎更可控

DFA 的实现藏在LexicalAnalysis.cpp的getNextToken()函数里。它不走std::regex，而是用查表法：

// LexicalAnalysis.cpp 第 87 行起 int currentState = 0; while (pos < input.length()) { char c = input[pos]; int charClass = getCharClass(c); // 将字符映射到 0~11 的类别索引 int nextState = dfa_table[currentState][charClass]; if (nextState == -1) break; // 无转移，当前 token 结束 currentState = nextState; pos++; } // 检查 currentState 是否为接受态（accepting state） if (isAcceptingState(currentState)) { return Token(tokenTypeMap[currentState], lexeme, lineNum); }

关键点在于dfa_table是一个int[32][12]的二维数组（32 个状态 × 12 类字符），每个元素存的是下一个状态编号。比如状态 0 读到字母a（class=1）跳到状态 1，状态 1 读到字母继续留在状态 1，直到遇到空白符或运算符才跳出循环。这种设计的好处是：

• 性能确定：O(n) 时间复杂度，无回溯；
• 边界清晰：getCharClass()函数明确定义了哪些字符属于同一类（如所有数字0-9→ class=2），避免 ASCII 码直连导致的漏判；
• 调试友好：你在 VS 调试器里直接看currentState和charClass，就能验证 DFA 是否按预期跳转。

LexicalAnalysisSourceProgram.txt里的测试用例（如if (x > 0) { y = x * 2; }）会被切成 13 个 token，每个 token 的line_num字段精确到行号——这靠input[pos] == '\n'时lineNum++实现，不是粗暴的strtok。

2.3 LALR(1) 语法分析器：action/goto 表不是魔法，是可读的 C++ 数组

SyntaxAnalysis.cpp的parse()函数是整套系统最硬核的部分。它维护两个栈：stateStack（存状态编号）和symbolStack（存文法符号）。核心循环如下：

// SyntaxAnalysis.cpp 第 142 行起 while (true) { int currentState = stateStack.back(); int lookahead = nextToken.type; // 当前前瞻符号 int action = action_table[currentState][lookahead]; if (action > 0) { // Shift stateStack.push_back(action); symbolStack.push_back(nextToken); nextToken = lexer.getNextToken(); } else if (action < 0) { // Reduce int productionIndex = -action - 1; // action=-3 表示用第 2 条产生式归约 Production prod = productions[productionIndex]; // 弹出 prod.rhs.size() 个状态和符号 for (int i = 0; i < prod.rhs.size(); i++) { stateStack.pop_back(); symbolStack.pop_back(); } // 归约后新状态 = goto_table[ stateStack.back() ][ prod.lhs ] int newState = goto_table[stateStack.back()][prod.lhs]; stateStack.push_back(newState); symbolStack.push_back(Token(prod.lhs, "", 0)); // 归约后的非终结符 logReduce(prod, symbolStack.size()); // 写入 SyntaxAnalysisProcess.txt } else if (action == 0) { // Accept logAccept(); return true; } else { // Error logError(currentState, lookahead); return false; } }

注意三点：

1. action_table是short[256][128]，负数表示 reduce，0 表示 accept，正数表示 shift 到那个状态；
2. goto_table是short[256][64]，只对非终结符查表，终结符查action_table；
3. productions[]数组按SyntaxAnalysisGrammar.txt顺序存储，productionIndex直接对应文法编号（从 0 开始）。

这意味着：你改SyntaxAnalysisGrammar.txt第 5 行，productions[4]就变；你调大MAX_PRODUCTIONS，productions[]数组就扩容——没有黑盒，全是裸指针和数组下标。

3. 文法定义与表生成：手写 BNF 如何变成可执行的 action 表？

3.1SyntaxAnalysisGrammar.txt的格式约束与扩展方法

该文件采用简化 BNF，每行一条产生式，格式为：
<非终结符> -> <符号1> <符号2> ... | <符号A> <符号B> ...
例如：

<program> -> <stmt_list> <stmt_list> -> <stmt> <stmt_list> | ε <stmt> -> <assign_stmt> | <if_stmt> | <while_stmt> <assign_stmt> -> ID ASSIGN <expr> SEMI <expr> -> <term> <expr_tail> <expr_tail> -> PLUS <term> <expr_tail> | MINUS <term> <expr_tail> | ε <term> -> <factor> <term_tail> <term_tail> -> MUL <factor> <term_tail> | DIV <factor> <term_tail> | ε <factor> -> LPAREN <expr> RPAREN | ID | NUMBER

必须遵守的三条铁律：

• 所有终结符（ID,ASSIGN,SEMI等）必须与LexicalAnalysis.h中TokenType枚举值完全一致；
• ε表示空产生式，不能写成epsilon或lambda；
• 左递归必须显式消除（如<expr> -> <expr> PLUS <term>会崩，必须改写为<expr> -> <term> <expr_tail>）。

要添加for循环支持？只需在文件末尾加两行：

<stmt> -> <for_stmt> <for_stmt> -> FOR LPAREN <assign_stmt> SEMI <expr> SEMI <assign_stmt> RPAREN <stmt>

然后重新编译Compiler.exe——initTables()会自动重算 FIRST/FOLLOW 集、构造新项集族、合并冲突生成新表。不需要手算 goto 表，但你要确保新文法是 LALR(1) 可分析的（无移进-归约或归约-归约冲突）。

3.2initTables()函数：LALR(1) 表生成的四步硬编码流程

SyntaxAnalysis.cpp中的initTables()是整个项目的“编译器之编译器”。它分四步构建 action/goto 表：

1. LR(0) 项集族构造：从拓广文法S' -> .S开始，用闭包（closure）和转移（goto）操作生成所有项集。代码中ItemSet类封装了vector<Item>和set<Item>去重逻辑；
2. FIRST/FOLLOW 集计算：computeFirst()递归遍历产生式右部，computeFollow()根据产生式左部和右部位置传播 FOLLOW 集；
3. LALR(1) 合并：对所有具有相同核心（core）的 LR(0) 项集，合并它们的展望符（lookahead）集合。这是 LALR 与 LR(1) 的本质区别——代码里用map<vector<Item>, set<int>> coreToLookaheads实现；
4. action/goto 表填充：遍历每个项集，对每个终结符a，若存在A -> α.aβ且a ∈ FOLLOW(A)，则填reduce；若存在A -> α.aβ且goto(I, a) = J，则填shift J；对非终结符A，填goto_table[I][A] = J。

注意：MAX_STATES默认为 256，MAX_SYMBOLS为 64。如果你的文法超过 256 个状态（比如加了函数声明、数组、指针等复杂语法），initTables()会触发assert(stateCount < MAX_STATES)失败。此时必须改header.h并重新编译——这不是 bug，是设计者给你留的安全阀。

3.3SyntaxAnalysisProcess.txt日志：读懂每一行背后的栈操作

该文件是分析过程的“行车记录仪”。典型一行如下：
[12:34:56] StateStack: [0,3,5] SymbolStack: [#,id,=] Action: shift 7 Lookahead: num

解读：

• [12:34:56]：毫秒级时间戳，便于定位卡顿点；
• StateStack: [0,3,5]：当前分析栈状态，对应action_table[5][num]查表；
• SymbolStack: [#,id,=]：符号栈内容，#是栈底哨兵；
• Action: shift 7：执行 shift，压入状态 7；
• Lookahead: num：当前前瞻符号是NUMBER类型。

如果是归约：
[12:34:57] Reduce using rule 3: <term> -> <factor>
表示用第 3 条产生式（索引从 0 开始）归约，弹出<factor>对应的符号和状态，再查goto_table[当前栈顶状态][<term>]得到新状态。

这个日志不是装饰品——当你发现accept没出现时，直接搜Error关键字，看哪一行action == -2（即查表得 -2），再反查action_table[状态号][符号号]就知道冲突在哪。

4. 避坑指南：五个让课设答辩翻车的致命细节（附血泪排查路径）

4.1 现象：Compiler.exe双击闪退，命令行运行显示Failed to open file: LexicalAnalysisSourceProgram.txt

原因：程序默认从当前工作目录读取*.txt文件，而非 exe 所在目录。Windows 资源管理器双击时，工作目录是桌面或文档夹，不是compiler-master文件夹。
解决：

• 方法一（推荐）：用 CMD 进入compiler-master目录再运行：

  cd D:\download\compiler-master Compiler.exe

• 方法二：修改main.cpp第 22 行，把ifstream路径改成绝对路径：

  ifstream lexFile("D:/download/compiler-master/LexicalAnalysisSourceProgram.txt");

• 方法三：在compiler-master文件夹内新建快捷方式，右键 → 属性 → “起始位置” 填D:\download\compiler-master。

4.2 现象：词法分析输出LexicalAnalysis.txt里ID全是乱码（如ID: ??），但NUMBER正常

原因：LexicalAnalysis.cpp第 65 行lexeme += c;在处理中文标识符时，char c是 UTF-8 多字节编码的第一个字节，导致lexeme存了半个汉字。
解决：

• 方案一（保守）：禁止中文标识符，在getCharClass()中把0x80-0xFF字节全归为INVALID类；
• 方案二（进阶）：改用std::wstring和wifstream，但需同步修改Token.value为wstring，并重载所有<<输出——课设不建议，超纲；
• 方案三（实用）：用 VS 的“高级保存选项”把LexicalAnalysisSourceProgram.txt另存为 ANSI 编码（GBK），char就能正确读取中文。

4.3 现象：SyntaxAnalysisProcess.txt卡在StateStack: [0,3]不动，最后报Error at state 3, lookahead SEMI

原因：action_table[3][SEMI] == 0（未定义动作），说明文法在状态 3 遇到SEMI时既不能 shift 也不能 reduce，即存在移进-归约冲突。常见于if-else悬空 else 问题。
排查：

• 打开SyntaxAnalysisGrammar.txt，找所有含SEMI的产生式；
• 检查if_stmt是否定义为<if_stmt> -> IF LPAREN <expr> RPAREN <stmt> ELSE <stmt>（无歧义）；
• 若定义为<if_stmt> -> IF LPAREN <expr> RPAREN <stmt>（无 else），则SEMI后必须跟else，否则冲突；
• 临时注释掉if相关产生式，看能否通过——能则确认是if文法问题。

4.4 现象：Compiler.exe运行时报Access violation reading location 0x00000000，调试器停在action_table[currentState][lookahead]

原因：currentState或lookahead超出数组边界。currentState最大为MAX_STATES-1（255），lookahead最大为MAX_TOKEN_TYPES-1（127）。但nextToken.type可能是UNKNOWN（值为 128）或未初始化的垃圾值。
解决：

• 在parse()循环开头加断言：

  assert(currentState >= 0 && currentState < MAX_STATES); assert(lookahead >= 0 && lookahead < MAX_TOKEN_TYPES);

• 在LexicalAnalysis::getNextToken()末尾强制token.type = UNKNOWN，避免未赋值；
• 检查TokenType枚举值是否连续（UNKNOWN=0, ID=1, NUMBER=2,...），中间不能有空洞。

4.5 现象：课程设计报告.docx里的 action 表和Compiler.exe实际输出的SyntaxAnalysisProcess.txt对不上

原因：报告是静态截图，而Compiler.exe运行时根据SyntaxAnalysisGrammar.txt动态生成表。你改了文法却没更新报告。
解决：

• 用Compiler.exe生成新日志后，运行tools/gen_table_report.py（需自行编写，读取action_table数组并输出 Markdown 表格）；
• 或手动复制SyntaxAnalysisProcess.txt开头的Action Table:部分（如有），粘贴到报告里；
• 终极方案：在initTables()末尾加ofstream tableFile("action_table_dump.txt");，把action_table[i][j]全部 dump 出来，作为报告附件。

5. 进阶技巧：用 GDB 单步调试 LALR(1) 分析栈，定位文法冲突根源

5.1 编译带调试信息的版本：绕过 VS 的“一键编译”陷阱

Compiler.exe是 Release 版，无法调试。你需要用 MinGW-w64 生成带 DWARF 符号的可执行文件：

# 假设你已安装 MinGW-w64（推荐 x86_64-10.2.0-release-posix-seh-rt_v7-rev1） g++ -g -O0 -static-libgcc -static-libstdc++ \ main.cpp LexicalAnalysis.cpp SyntaxAnalysis.cpp \ -o Compiler_debug.exe

关键参数说明：

• -g：生成调试符号，GDB 才能显示变量名和源码行；
• -O0：关闭优化，否则stateStack.back()可能被优化成寄存器，GDB 看不到；
• -static-libgcc -static-libstdc++：静态链接，避免目标机缺libstdc++-6.dll；
• 不要用-std=c++17：原代码用 C++11 特性（auto,nullptr），高版本可能触发constexpr报错。

编译后，用file Compiler_debug.exe确认输出含debug_info字段，再用gdb ./Compiler_debug.exe启动。

5.2 GDB 调试实战：三步锁定归约冲突点

假设SyntaxAnalysisSourceProgram.txt输入a = b + ;（故意缺右操作数），你想知道为什么在+后报错：

gdb ./Compiler_debug.exe (gdb) break SyntaxAnalysis.cpp:145 # 在 action_table 查表行打断点 (gdb) run # 程序停在 while 循环第一行 (gdb) display/i $rip # 显示当前汇编 (gdb) display stateStack # 自动打印 stateStack 内容 (gdb) display symbolStack # 自动打印 symbolStack 内容 (gdb) display nextToken.type # 显示前瞻符号 (gdb) c # 继续运行 # 当停在 '+' 时，nextToken.type = PLUS (值为 10) (gdb) p action_table[stateStack.back()][10] # 打印 action_table[当前状态][PLUS] $1 = 0 # 返回 0，说明此处未定义动作 (gdb) p stateStack.back() # 查看当前状态号 $2 = 12 # 状态 12 (gdb) p productions # 查看所有产生式 # 发现状态 12 的 goto 表中，PLUS 对应列全为 0 → 确认是文法缺陷

此时你知道：状态 12 下+既不能 shift（无转移），也不能 reduce（无产生式以+结尾），必须修改文法——比如给<expr_tail>加一条| ε，让+后可为空。

5.3 用 Python 快速验证文法 LALR(1) 性：避免手算 200 行表

手算 LALR(1) 表太耗时。写个 Python 脚本读取SyntaxAnalysisGrammar.txt，调用lark-parser库做验证：

# validate_grammar.py from lark import Lark grammar = """ ?start: stmt_list stmt_list: stmt stmt_list | stmt: assign_stmt | if_stmt assign_stmt: "id" "=" expr ";" expr: term expr_tail expr_tail: "+" term expr_tail | "-" term expr_tail | term: factor term_tail term_tail: "*" factor term_tail | "/" factor term_tail | factor: "(" expr ")" | "id" | "num" """ try: parser = Lark(grammar, parser='lalr') print("✅ 文法是 LALR(1) 可分析的") except Exception as e: print("❌ 冲突 detected:", str(e))

运行python validate_grammar.py，如果输出✅，说明你的文法无冲突；如果报Shift-Reduce conflict，脚本会明确指出哪条产生式导致冲突——比看Compiler.exe的Error日志快 10 倍。

5.4 修改header.h的黄金参数：让小课设变大项目

原项目为教学精简，MAX_STATES=256限制了文法规模。要支持 C 语言子集（含函数、结构体、指针），需调整：

改完后，必须重新编译所有.cpp文件（g++ -g ...），因为header.h被所有源文件#include，宏定义改变会导致数组尺寸重算。编译后用size Compiler_debug.exe对比：增加 1MB 是正常的，超过 5MB 说明表过大，需检查文法是否冗余。

从那以后我每次改SyntaxAnalysisGrammar.txt，都强制走一遍validate_grammar.py+gdb单步 +Compiler_debug.exe日志比对三步流程——哪怕只是加一个分号，也要确认action_table真的变了。这习惯救了我三次答辩前夜的崩溃。希望帮到你。

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