+LR(1)：编译原理实验链完整解析)
简介：这是编译原理课程设计实验的完整源码包，提供词法分析器、LL(1)语法分析器、LR(1)语法分析器三部分实现，适合正在学习编译原理或准备课程设计的高校学生参考。实验最初为词法分析器热身练习，支持匹配关键字、标记符、运算符、分界符、无符号数，并额外支持字符/字符串与行间注释，且配有图形界面。压缩包共52个文件，约6.88MB，主要包括4个cpp源文件、3个h头文件、10组in/out测试用例、5个pdf说明文档，以及makefile、html、gitignore等辅助文件，目录层次清晰，便于对照学习。目前已有1089人学习下载。读者可从中获得完整的实验源码、测试样例与文档，既能直接运行验证，也可参考其状态转换与递归下降或LL(1)/LR(1)表驱动分析的设计思路，对理解词法、语法分析流程及自拟实验很有帮助。
1. 三个分析器如何组成一条可验收的编译实验链
做编译原理实验时，拿到一个包含词法分析器、LL(1) 语法分析器、LR(1) 语法分析器的压缩包，第一反应往往是不知道从哪个文件开始读。常见情况是：实验要求先把源码字符串拆成 token，再用 LL(1) 或 LR(1) 方法判定语法是否符合文法，最后输出分析过程或语法树。这三个模块不是孤立的——词法分析器是语法分析器的输入前端，LL(1) 和 LR(1) 是同一套语法验证问题下的两种不同算法路线。适合这道题的人，是需要完成课程设计、准备编译原理实验验收，或想把手头残缺代码补全的读者。下面按"词法 -> LL(1) -> LR(1)"的顺序，讲清楚每一步的最小实现、核心参数设置和最常见的坑。
提示：实验包里的代码质量参差不齐，建议先跑通最小样例再读完整源码，否则容易被变量命名和状态表结构带偏。
2. 词法分析器：从正则描述到状态转移表的落地
2.1 为什么词法分析器通常用 DFA 而不是手写字符判定
词法分析器的任务是把源码字符串切成 token 序列，每个 token 包含类型和值。手工用 if-else 判断关键字、运算符、数字虽然能应付十几个样例，但遇到注释、字符串转义、浮点数就会失控。最稳妥的做法是先把词法规则写成正则表达式，再把正则转成 NFA，最后确定化为 DFA。实验包里的词法分析器如果自带一个token.txt或lexical_rules.txt，通常就是用状态转移表来实现 DFA。
状态转移表的一行代表一个状态，一列代表一个输入字符类别。常见的做法是把字符分成几类：字母、数字、运算符、分隔符、空白、其他。表中每个格子写的是"当前状态 + 当前字符类别 -> 下一状态 + 是否接受 + 接受时返回哪个 token 类型"。调试时最容易出错的是"最长匹配"：比如>=不能被拆成>和=，a123是一个标识符，不能先读a就结束。
2.2 用 Python 实现一个极简 DFA 词法分析器
下面这段代码是课程实验里常见的最小实现，直接把状态转移表写成字典，逐字符读入并根据当前状态查表。为方便演示，只处理标识符、整数、赋值号、加号、空格和换行。
def lexer(code): # 状态表: dict[(state, char_class)] = next_state trans = { (0, 'letter'): 1, # 标识符开头 (1, 'letter'): 1, (1, 'digit'): 1, (0, 'digit'): 2, # 整数开头 (2, 'digit'): 2, (0, '='): 3, (0, '+'): 4, } accept = {1: 'ID', 2: 'NUM', 3: 'ASSIGN', 4: 'PLUS'} tokens = [] i = 0 n = len(code) while i < n: c = code[i] # 跳过空白 if c.isspace(): i += 1 continue state = 0 start = i last_accept = -1 last_accept_pos = i while i < n: c = code[i] if c.isalpha(): cls = 'letter' elif c.isdigit(): cls = 'digit' elif c == '=': cls = '=' elif c == '+': cls = '+' else: cls = 'other' if (state, cls) not in trans: break state = trans[(state, cls)] i += 1 if state in accept: last_accept = state last_accept_pos = i if last_accept == -1: raise SyntaxError(f"illegal char at position {start}") token_text = code[start:last_accept_pos] tokens.append((accept[last_accept], token_text)) # 回退一个字符，处理最长匹配中非接受后缀 i = last_accept_pos return tokens print(lexer("a = b123 + 45"))代码逻辑是：每次从state=0开始，尽可能多地读入字符；每经过一个可接受状态就记录位置，最后取最长的可接受子串作为 token。last_accept_pos是核心，它解决了 "ab" 读完整后才被识别为 ID 的问题。参数上的关键点在于字符分类cls的划分，如果把=误分到字母类，状态表就会乱跳。初学时最容易漏的是"回退"：如果读入某个字符后不在表中，但之前已经有过可接受状态，就要把游标恢复到last_accept_pos，否则下一个 token 会从错误位置开始。
2.3 词法规则文件和错误恢复的位置
实验包里的词法分析器往往不只识别这几种 token，还需要支持字符串常量、多行注释等。这时候状态表里应该增加两个特殊状态：字符串状态和注释状态。字符串状态从遇到引号开始，直到遇到未转义的结束引号为止；注释状态从遇到/*开始，直到遇到*/为止。错误恢复的常见策略是：发现非法字符时记下位置，跳过该字符继续分析，而不是立刻抛出异常。在实验验收时，面试官或老师通常不看错误处理，只看能否正确输出 token 序列；但在自动化测试里，错误处理决定的鲁棒性会直接影响分数。
3. LL(1) 语法分析器：FIRST/FOLLOW 集和预测分析表的构造
3.1 LL(1) 名称里的三个"1"分别指什么
LL(1) 表示从左到右扫描输入串、产生最左推导、每一步只看一个输入符号。它和 LR 系列最大的区别是：LL 用文法产生式去匹配输入，而 LR 用移进-归约来反向推导。LL(1) 能分析的文法必须是无左递归、无公共左因子的。实验包里的 LL(1) 分析器如果带自动求 FIRST/FOLLOW 的代码，那算是一份较完整的实现；如果只是手工填好的预测分析表，你就需要自己验证表是否正确。
构造预测分析表 M 的方法是：对每个产生式 A -> alpha，对 FIRST(alpha) 中的每个终结符 a，把产生式填入 M[A][a]；如果 epsilon 在 FIRST(alpha) 里，则对 FOLLOW(A) 中的每个终结符 b（以及结束符 $），把产生式填入 M[A][b]。冲突的产生式会被填到同一个格子里，有冲突就说明文法不是 LL(1) 的，需要改写文法或用其他分析方法。
3.2 手写 FIRST/FOLLOW 计算函数
下面是一个通用的 FIRST/FOLLOW 求解代码，输入产生式列表和开始符号，输出两个字典。代码参考了实验报告里最常见的算法描述，并且做了集合的自动收敛。
from collections import defaultdict def compute_first_and_follow(productions, start_symbol): terminals = set() nonterminals = set() for lhs, rhs_list in productions.items(): nonterminals.add(lhs) for rhs in rhs_list: for symbol in rhs: if not symbol.isupper() and symbol != 'epsilon': terminals.add(symbol) FIRST = defaultdict(set) FOLLOW = defaultdict(set) FOLLOW[start_symbol].add('$') # 先处理直接能推出的终结符和 epsilon changed = True while changed: changed = False for lhs, rhs_list in productions.items(): for rhs in rhs_list: # FIRST 集传播 if rhs == ['epsilon']: if 'epsilon' not in FIRST[lhs]: FIRST[lhs].add('epsilon') changed = True continue for i, symbol in enumerate(rhs): if symbol in terminals: if symbol not in FIRST[lhs]: FIRST[lhs].add(symbol) changed = True break # 遇到终结符，此产生式后面符号不再贡献给 FIRST[lhs] else: before_len = len(FIRST[lhs]) FIRST[lhs] |= (FIRST[symbol] - {'epsilon'}) if len(FIRST[lhs]) != before_len: changed = True if 'epsilon' not in FIRST[symbol]: break else: # 所有符号都推导出 epsilon if 'epsilon' not in FIRST[lhs]: FIRST[lhs].add('epsilon') changed = True # FOLLOW 集传播 changed = True while changed: changed = False for lhs, rhs_list in productions.items(): for rhs in rhs_list: if rhs == ['epsilon']: continue for i, symbol in enumerate(rhs): if symbol not in nonterminals: continue # 看 A -> alpha B beta 中 beta 的 FIRST 集 beta = rhs[i+1:] if beta: beta_first = set() for s in beta: if s in terminals: beta_first.add(s) break else: beta_first |= FIRST[s] - {'epsilon'} if 'epsilon' not in FIRST[s]: break before = len(FOLLOW[symbol]) FOLLOW[symbol] |= beta_first - {'epsilon'} if len(FOLLOW[symbol]) != before: changed = True # 如果 beta 能推导出 epsilon，FOLLOW[lhs] 进 FOLLOW[symbol] if all(s in nonterminals and 'epsilon' in FIRST[s] for s in beta if s != 'epsilon') or not beta: before = len(FOLLOW[symbol]) FOLLOW[symbol] |= FOLLOW[lhs] if len(FOLLOW[symbol]) != before: changed = True else: before = len(FOLLOW[symbol]) FOLLOW[symbol] |= FOLLOW[lhs] if len(FOLLOW[symbol]) != before: changed = True return FIRST, FOLLOW productions = { 'E': [['T'], ['E', '+', 'T']], # 实际上包含左递归，仅作示例 }代码里的参数：productions的 value 是二维列表，每个元素是一条产生式的右侧符号列表。关键点是isfirst判断中用了symbol.isupper()来区分非终结符——如果你的文法用小写表示非终结符，这里的判断逻辑必须同步改。另一个容易忽略的是epsilon的传播方向：FIRST 集里是否包含epsilon取决于整个产生式右侧能否全部推导到空串。手动填预测分析表时，建议先打印出FIRST和FOLLOW，对着表逐格核对，不要盲信任课老师发的答案表——答案表里经常存在因打印排版导致的错位。
3.3 预测分析表的悬挂更新机制
LL(1) 分析器运行时有一个符号栈和一个输入缓冲区，初始化时栈里先放入$和开始符号。循环里只有当栈顶是终结符且等于当前输入时才弹栈；如果栈顶是非终结符，就查 M[stack_top][current_token] 得到产生式，然后把产生式右侧逆序压栈。实验报告中容易写错的是产生式右侧符号的压栈顺序：比如产生式 E -> T E'，压栈时要先压 E'，再压 T，这样弹栈时 T 才能被最先处理。
还要注意同步 token的处理。当表项为空时，主流做法是跳过当前输入 token；当栈顶终结符与输入不匹配时，弹栈。这个策略在错误恢复时很有效，但在验收时如果老师预期看到"非法输入"而不是跳过，就需要根据实验要求调整。
3.4 左递归消除和提取左因子是 LL(1) 实验的隐藏考点
大部分课程实验不会让你直接给定一个完美 LL(1) 文法，而是给出类似E -> E + T | T这样的左递归文法。这时你需要先手动改写成E -> T E'，E' -> + T E' | epsilon。很多同学直接在程序里输入原始文法，结果 FIRST 集陷入死循环。如果实验包里的代码已经提供了自动消除左递归的函数，那你要检查它是否处理了间接左递归（如 A -> B -> A）。常见的坑是：消除左递归后新增的E'被误写成非终结符E1，但词法分析器无法识别单引号，导致 LL(1) 分析器在解析产生式右侧时把E和'拆成两个 token。为了避免这个问题，建议在文法文件里统一使用大写字母加数字表示新增非终结符，比如E1,E2。在代码注释里说明这一点，既方便自己调试也方便验收老师理解。
4. LR(1) 语法分析器：活前缀与项集族的构造逻辑
4.1 LR(1) 和 SLR(1)/LALR(1) 的分界在哪
LR(1) 分析器比 LL(1) 更强大，它通过历史信息（状态栈）和向前看一个符号来决定是移进还是归约。在实验分包里，LR(1) 通常以.lalr或.table文件提供转换表。如果只给 LR(1) 这个词，大概率要求你构造 LR(1) 项集族，并且可能和 SLR(1) 做对比。SLR(1) 在归约时只用 FOLLOW 集来判断，而 LR(1) 用的是每个项特有的向前看符号集合，因此 LR(1) 能处理更多的文法。
构造 LR(1) 项目时，每个项包含四个部分：产生式左侧、产生式右侧中点的位置、向前看符号集合。比如E -> T . E' , {+, $}。初始项是S' -> . S , {$}。计算闭包时，如果当前项中圆点后跟的是非终结符 B，则把 B 的所有产生式加入项集，并且这些新项的向前看符号是FIRST(beta a)，其中 beta 是圆点后面的剩余符号串，a 是当前项的向前看符号。
4.2 用 Python 演示 LR(1) 项集族的增量构造
下面的代码实现了一个小型 LR(1) 自动机，它来自最常见的《编译原理》课程设计框架。为了可读性，只处理一个简单文法。
def closure(items, productions, first): items = set(items) queue = list(items) while queue: item = queue.pop() lhs, rhs, dot, lookahead = item if dot < len(rhs): B = rhs[dot] if B in productions: for prod_rhs in productions[B]: # 计算新项的 lookahead: FIRST(rhs[dot+1:] + lookahead) suffix = rhs[dot+1:] + list(lookahead) beta_first = set() for symbol in suffix: if symbol in first: beta_first |= first[symbol] - {'epsilon'} if 'epsilon' not in first[symbol]: break else: beta_first.add(symbol) break new_item = (B, tuple(prod_rhs), 0, tuple(sorted(beta_first))) if new_item not in items: items.add(new_item) queue.append(new_item) return items def goto(items, symbol, productions, first): moved = set() for lhs, rhs, dot, lookahead in items: if dot < len(rhs) and rhs[dot] == symbol: moved.add((lhs, rhs, dot+1, lookahead)) return closure(moved, productions, first) # 示例文法: S -> E, E -> E + T | T, T -> id productions = { 'S': [('E',)], 'E': [('E', '+', 'T'), ('T',)], 'T': [('id',)], } first = {'+': {'+'}, 'id': {'id'}, 'E': {'id'}, 'T': {'id'}} start_items = {('S\'', ('S',), 0, ('$',))} current = closure(start_items, productions, first) print("闭包后的初始项集:", current) next = goto(current, 'E', productions, first) print("读取 E 后的项集:", next)逻辑说明：closure函数维护一个队列，每当加入新项就继续寻找圆点后面的非终结符。这里的关键参数是lookahead，它被保存为一个元组，在goto中保持不变。构造 ACTION 和 GOTO 表时要对每个项集遍历所有符号：若圆点后是终结符，则 ACTION[state][terminal] = shift(下一状态)；若圆点后是非终结符，则 GOTO[state][nonterminal] = 下一状态；若圆点已经在产生式末尾，则对 lookahead 中的每个终结符填 reduce。
4.3 移进-归约冲突的判定和实验课的验收侧重
LR(1) 实验最常被考察的是冲突检测。如果某个状态中同时存在归约项E -> T . , {+, $}和移进项E -> T . + T , {$}，就出现 shift/reduce 冲突。这通常在表达式文法的E -> E + T . , {+}和E -> E + T . + T中体现。由于 LR(1) 的向前看集合已经足够精细，很多 SLR 状态中存在的冲突在 LR(1) 里会消失。实验要求如果只是"构造 LR(1) 分析表"，那你需要输出所有项集族和最终表；如果要求"实现 LR(1) 分析"，代码里的栈要保存状态序号和符号两层，归约时弹出等量状态。注意当归约产生式右侧长度为 n 时，弹栈后要读取新栈顶状态 s，然后查 GOTO[s][A] 并入栈。
在验收时，老师常问的一个问题是：LR(1) 和 LL(1) 在错误处理上的输出差异。LR(1) 对错误的定位更准确，因为它在栈里记录了之前看到的所有合法状态；但在实验代码里，如果不给 LR(1) 分析器写错误输出，它通常会在查表失败时抛出数组越界异常，这是不友好的行为。建议在 ACTION 表查不到 entry 时，输出 "syntax error at token 'xxx'，state 'yyy' 没有移进/归约动作"，并终止分析。
5. 三个实验联动时的调试顺序和验收常见坑
5.1 先验证词法 token 流，再验证语法分析
把三个分析器拼起来时，最常见的错误是语法分析器从输入文件中读到的 token 类型名和词法分析器输出的不完全一致。比如词法分析器把关键字也归为ID，但 LL(1) 分析表里要求if单独是一个终结符。所以联动前应该先跑一个 "only lexer" 模式，输出所有 token 序列，确认没有(ID, "int")混在(INT, "int")里。有些实验包会提供一个verbose参数，当被设置时打印每个 token 的细节，在调试时先打开。
5.2 画状态和分析树的关键指令
如果你手头是被压缩包包裹的纯文本实验，没有现成输出格式，我一般会在代码里加上一条环境变量DEBUG=1来打印中间结果。例如在 LL(1) 分析中打印每一步的栈和剩余输入：
DEBUG=1 python ll1_parser.py input.cmm在ll1_parser.py里，当os.environ.get("DEBUG") == "1"时，每执行一次查表动作就打印栈顶,当前token,选用产生式。用这个输出对照预测分析表逐行核对，往往能在十分钟内定位到 FIRST/FOLLOW 计算还是表填充的错误。LR(1) 分析器则打印每次移进和归约的状态栈长度、符号栈内容，比如shift to state 3, stack depth: 2。这个打印控制在关键循环里只输出一行，否则输出量会立刻淹没终端。
5.3 三个容易推翻结论的验收盲区
第一，空白字符在 LL(1)/LR(1) 中的处理。词法分析器通常跳过换行和空格，但如果你保留了换行作为 token，那 LL(1) 文法里必须加入LF终结符，否则读文件后第一行分析就会挂。第二，$结束符的传播。很多实验代码在分析前忘掉输入文件的末尾追加$或#，导致查表时取不出 token。第三，从.zip里解压出的源码如果是GBK编码，在 Python 3 里用默认 UTF-8 读取会出现UnicodeDecodeError。建议先统一用open(file, encoding='utf-8-sig')试一次，报错再换成gbk。
5.4 快速生成测试用例的三条规则
最后一招是构造测试集来覆盖边界。如果你要把三个分析器提交到课程平台或仓库，至少准备三类输入：第一类是只包含标识符和整数的表达式，如a = 1 + 2;，用 LL(1) 验证最基础的产生式链；第二类是多层括号嵌套，如((a + (b)))，用来检查 LR(1) 状态栈是否会因括号深度增长而爆掉；第三类是错误输入，比如a = * 1，它应该被词法分析器报非法字符或被语法分析器报语法错误，这两个结果只要有一个正常，都能作为验收依据。最后把生成的 token 序列写入out_tokens.txt，语法分析树以缩进形式写入tree.txt，这两个文件的输出格式在验收时比终端打印更有说服力。
本文还有配套的精品资源，点击获取
