+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(fillegal 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))代码逻辑是每次从state0开始尽可能多地读入字符每经过一个可接受状态就记录位置最后取最长的可接受子串作为 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[i1:] 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 能推导出 epsilonFOLLOW[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 EE - 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[dot1:] lookahead) suffix rhs[dot1:] 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, dot1, 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 xxxstate yyy 没有移进/归约动作并终止分析。5. 三个实验联动时的调试顺序和验收常见坑5.1 先验证词法 token 流再验证语法分析把三个分析器拼起来时最常见的错误是语法分析器从输入文件中读到的 token 类型名和词法分析器输出的不完全一致。比如词法分析器把关键字也归为ID但 LL(1) 分析表里要求if单独是一个终结符。所以联动前应该先跑一个 only lexer 模式输出所有 token 序列确认没有(ID, int)混在(INT, int)里。有些实验包会提供一个verbose参数当被设置时打印每个 token 的细节在调试时先打开。5.2 画状态和分析树的关键指令如果你手头是被压缩包包裹的纯文本实验没有现成输出格式我一般会在代码里加上一条环境变量DEBUG1来打印中间结果。例如在 LL(1) 分析中打印每一步的栈和剩余输入DEBUG1 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, encodingutf-8-sig)试一次报错再换成gbk。5.4 快速生成测试用例的三条规则最后一招是构造测试集来覆盖边界。如果你要把三个分析器提交到课程平台或仓库至少准备三类输入第一类是只包含标识符和整数的表达式如a 1 2;用 LL(1) 验证最基础的产生式链第二类是多层括号嵌套如((a (b)))用来检查 LR(1) 状态栈是否会因括号深度增长而爆掉第三类是错误输入比如a * 1它应该被词法分析器报非法字符或被语法分析器报语法错误这两个结果只要有一个正常都能作为验收依据。最后把生成的 token 序列写入out_tokens.txt语法分析树以缩进形式写入tree.txt这两个文件的输出格式在验收时比终端打印更有说服力。本文还有配套的精品资源点击获取
简介这是编译原理课程设计实验的完整源码包提供词法分析器、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(fillegal 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))代码逻辑是每次从state0开始尽可能多地读入字符每经过一个可接受状态就记录位置最后取最长的可接受子串作为 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[i1:] 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 能推导出 epsilonFOLLOW[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 EE - 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[dot1:] lookahead) suffix rhs[dot1:] 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, dot1, 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 xxxstate yyy 没有移进/归约动作并终止分析。5. 三个实验联动时的调试顺序和验收常见坑5.1 先验证词法 token 流再验证语法分析把三个分析器拼起来时最常见的错误是语法分析器从输入文件中读到的 token 类型名和词法分析器输出的不完全一致。比如词法分析器把关键字也归为ID但 LL(1) 分析表里要求if单独是一个终结符。所以联动前应该先跑一个 only lexer 模式输出所有 token 序列确认没有(ID, int)混在(INT, int)里。有些实验包会提供一个verbose参数当被设置时打印每个 token 的细节在调试时先打开。5.2 画状态和分析树的关键指令如果你手头是被压缩包包裹的纯文本实验没有现成输出格式我一般会在代码里加上一条环境变量DEBUG1来打印中间结果。例如在 LL(1) 分析中打印每一步的栈和剩余输入DEBUG1 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, encodingutf-8-sig)试一次报错再换成gbk。5.4 快速生成测试用例的三条规则最后一招是构造测试集来覆盖边界。如果你要把三个分析器提交到课程平台或仓库至少准备三类输入第一类是只包含标识符和整数的表达式如a 1 2;用 LL(1) 验证最基础的产生式链第二类是多层括号嵌套如((a (b)))用来检查 LR(1) 状态栈是否会因括号深度增长而爆掉第三类是错误输入比如a * 1它应该被词法分析器报非法字符或被语法分析器报语法错误这两个结果只要有一个正常都能作为验收依据。最后把生成的 token 序列写入out_tokens.txt语法分析树以缩进形式写入tree.txt这两个文件的输出格式在验收时比终端打印更有说服力。本文还有配套的精品资源点击获取
