语法分析器课设全解析：从FIRST/FOLLOW集到分析表驱动)
简介面向编译原理课程的Java版SLR(1)语法分析器实验源码包适合正在学习自底向上语法分析、需要完成实验或课程设计的学生。压缩包内共含85个文件其中76个Java源文件构成解析器主体辅以pom.xml等Maven配置、iml与xml工程文件整体仅40KB目录结构清晰便于直接导入IntelliJ IDEA运行。目前已有521人学习浏览。源码完整覆盖文法表示、消除左递归与左公因子、FOLLOW集与闭包计算、GO TO集合构造、分析表生成以及基于分析表的移进归约解析流程并在关键步骤中展示了如何用数据结构存储产生式、迭代扩张状态集合等实现细节。借助该源码读者可以在具体代码中对照编译原理教材的抽象概念理解每一个非终结符的驱动逻辑快速掌握SLR(1)分析表的构建方法与完整解析机制适合作为课程实验模板或算法复习参考。1. 编译原理课设最常打包出来的那个压缩包byyl SLR(1).zip 到底是干什么的一门编译原理课接近尾声的时候实验室里十有八九会流传一个命名风格极其统一的压缩包byyl SLR(1).zip。byyl 基本可以断定是“编译原理”的拼音缩写zip 里装的是一个 SLR(1) 语法分析器的完整工程。它解决的是编译原理课程里最硬的一块骨架给定一个文法自动计算出 FIRST 集、FOLLOW 集构造 LR(0) 项目集族最终生成 SLR(1) 分析表再用一张表驱动一个下推自动机完成句子的语法分析。这个项目适合两类人一类是正在赶课设、需要把教科书算法变成能交差代码的学生另一类是工作后需要快速补一个可用的语法分析器原型、手边又没有现成工具的开发者。不管哪一类拿到 zip 之后最关心的都是同一个问题这东西能不能在我自己机器上跑起来跑起来之后输出靠不靠得住。下面按我拆课设包的顺序把这条路完整走一遍。2. 先看包再跑通SLR(1) 项目压缩包的拆包顺序与三条主线2.1 解压后先分清三类文件再决定从哪个文件开始读一个典型的 SLR(1) 课设包解压之后你通常会同时看到三类东西说明文档、文法数据文件、源码文件。以我见过的课设包为例里面有 README 或者实验报告 PDF、一两个以 .txt 或 .in 结尾的文法文件以及一组源码文件常见课设包源码以 Python 或 C 为主也可能混着 Java。说明文档告诉你实验要求、验收点、输出格式文法文件是数据输入源码是整个工程的逻辑主体。unzip byyl\ SLR\(1\).zip -d byyl-slr1 cd byyl-slr1 find . -maxdepth 2 -type f | sort解压这一步看着简单实际有两个容易出错的地方。第一zip 包里的文件名如果带空格或括号直接 unzip 会把模式串拆开命令里对括号要转义否则 shell 会把它当成特殊符号处理。第二解压之后不要急着编译先看目录结构确认源码、数据、报告三个部分各在哪个位置很多课设包的组织方式是以一个主目录包所有内容但也有一些包是源码在根目录、数据在 data 子目录、报告在 doc 子目录里不先看清楚等 GPU 那套也好、环境变量也好全配完了才发现路径不对那就白费力气了。2.2 用一条命令行把最小文法跑起来运行参数与输出格式环境确认之后先不要直接上复杂文法。我的习惯是找一个只有四五条产生式的最小文法先试跑比如一个简单的表达式文法 E - E T | T, T - id。这个文法虽然简单但能覆盖移进、归约、接受三种基本动作足够验证整个链路是否通。python main.py --grammar tests/expr.in --input id id * id --trace --table-dump这条命令里隐藏着 SLR(1) 课设最常见的几种运行参数。--grammar 指定文法文件路径--input 是要分析的输入串多数课设包支持两种输入方式命令行直传和从文件读入后者的好处是输入串里有空格、换行时不易出错--trace 开启单步追踪输出也就是把分析栈、剩余输入、当前动作按行打印出来这是调试最重要的开关--table-dump 会把生成的 ACTION 表和 GOTO 表打印出来方便你对照教科书上的标准表。如果程序支持但 README 没写清楚参数直接看源码里的 argparse 或者参数解析部分比盲试参数来得快。跑这条命令时正确的输出应该是先打印文法和终结符/非终结符集合再打印分析表最后逐行打印分析过程并以“Accept”或“分析成功”结束。2.3 文法文件的书写约定产生式、终结符、空串与 # 号跑通了最小文法之后你才能真正理解一个文法文件长什么样。课设包里的文法文件一般就是纯文本每行一条产生式箭头用 - 表示左侧是单个非终结符右侧是符号串其中终结符通常是 id、、*、( 、) 这类 token非终结符用大写字母或者尖括号括起来。空串的表示方式各包不一最常用的是 EPS、null 或者直接留空这直接影响后面 FIRST 集和 FOLLOW 集的计算必须第一个确认。E - E T E - T T - T * F T - F F - ( E ) F - id这个文法文件有三个关键约定。第一开始符号取第一条产生式的左侧符号也就是 E很多实现不会单独配置开始符号而是默认第一条产生式左边就是开始符号。第二文件里不得出现 | 这种合并写法教科书里写 E - E T | T 是为了省纸程序里必须拆成两行否则读入器会把整个右侧当成一个符号串。第三结束符 #有的包写作 $由程序内部补全不需要也不能出现在文法文件里。如果你拿到一个包里面文法格式和上述不同那就以它的 README 为准但不管怎么变最终源码里都要归一化成“产生式编号、左部、右部列表”这种内部表示这一步是后续所有计算的前提。3. FIRST/FOLLOW/LR(0) 项目集族SLR(1) 分析器跑起来之前的三个地基3.1 为什么 SLR(1) 的核心不在查表而在集合和项目集很多学生拿到 SLR(1) 的工程后本能地先翻 driver 那个文件觉得分析表生成好了查表循环才是主角。实际上 SLR(1) 这个缩写已经把所有秘密写在名字里了S 代表 SimpleL 是 left-to-right 扫描R 代表 rightmost derivation 的逆过程括号里的 1 表示向前看一个终结符。LR(0) 项目集族构建了所有可能的分析状态而 SLR(1) 的特点在于归约动作不是靠项目集内部信息决定的而是看当前输入符号是否在对应非终结符的 FOLLOW 集里。这就意味着你不能跳过 FIRST 集和 FOLLOW 集直接写表生成函数因为 FOLLOW 集少算一个符号分析表里就会少一个归约项运行时报错或者静默接受错误句子就是必然的事。3.2 计算 FIRST 集不动点迭代与 ε 的显式表示计算 FIRST 集的标准做法是不动点迭代也就是反复扫描所有产生式直到所有集合不再变化为止。我见过不少学生自己手写的时候用递归结果递归进入循环产生式比如 A - B, B - A 的时候直接栈溢出所以稳妥的做法是用一个 while 循环配合 changed 标志位既直观又不会爆栈。def compute_first(grammar, terminals, nonterminals): first {nt: set() for nt in nonterminals} changed True while changed: changed False for lhs, rhs_list in grammar.items(): for rhs in rhs_list: before len(first[lhs]) for symbol in rhs: if symbol in terminals or symbol EPS: first[lhs].add(symbol) break else: first[lhs] | (first[symbol] - {EPS}) if EPS not in first[symbol]: break else: first[lhs].add(EPS) if len(first[lhs]) ! before: changed True return first这段代码看起来简单但有三个地方容易写错。第一个是当右部以终结符开头时直接把该终结符加入 FIRST 集并终止这条产生式的扫描第二个是当右部是非终结符时要把该非终结符 FIRST 集中除 EPS 之外的所有符号都加进来然后看这个非终结符的 FIRST 集里有没有 EPS有 EPS 才继续往后扫描下一个符号第三个是当整个右部所有符号都能推导出 EPS 时要把 EPS 加入左部的 FIRST 集。如果你用的文法文件里空串表示不是 EPS比如是空字符串代码里要把常量改成对应表示否则会出现明明应该有空串却算不出来的情况。3.3 计算 FOLLOW 集四个规则的顺序不能错FOLLOW 集的计算比 FIRST 集更依赖全局信息因为它用到的是产生式的右部结构而不只是单个符号的推导关系。FOLLOW 集初始要把 # 放入开始符号的 FOLLOW 集之后反复应用四个规则A - αBβ 时把 FIRST(β) 中除 EPS 外的所有符号加入 FOLLOW(B)β 能推导出 EPS 时把 FOLLOW(A) 加入 FOLLOW(B)B 是右部最后一个符号时也把 FOLLOW(A) 加入 FOLLOW(B)还有一条容易被忽略的当右部中 B 后面有多个符号时要逐个向后检查直到碰到一个 FIRST 集不含 EPS 的符号为止。def compute_follow(grammar, nonterminals, terminals, first): follow {nt: set() for nt in nonterminals} follow[nonterminals[0]].add(#) changed True while changed: changed False for lhs, rhs_list in grammar.items(): for rhs in rhs_list: for i, symbol in enumerate(rhs): if symbol not in nonterminals: continue before len(follow[symbol]) # 规则2把后面符号串的 FIRST 集不含 EPS加入 FOLLOW for j in range(i 1, len(rhs)): follow[symbol] | (first[rhs[j]] - {EPS}) if EPS not in first[rhs[j]]: break else: # 规则3后面符号串能推导出 EPS或者 B 是最后一个符号 follow[symbol] | follow[lhs] changed | (len(follow[symbol]) ! before) return follow这段代码里最精妙也最容易出错的是那个 for...else 结构如果后面的所有符号都含有 EPS或者 B 本身就是右部末尾循环正常结束会进入 else 分支把 FOLLOW(A) 并入 FOLLOW(B)。如果你把 else 写成了普通 continue或者忘记处理 B 是最后一个符号的情形FOLLOW 集就会偏小SLR(1) 分析表里的归约动作就会缺项。另一个工程上的细节是迭代终止条件的判空用 length 是否变化来判断是很可靠的因为集合里只加不减。3.4 closure 与 goto构造 LR(0) 项目集族有了 FIRST/FOLLOW 集之后SLR(1) 的地基还剩最后一块LR(0) 项目集族。所谓项目就是产生式右部带一个圆点标记比如 E - E . T圆点左边是已经分析过的部分右边是等待分析的部分。closure 函数负责把一个项目集补全如果某个项目圆点右边是非终结符 B那么所有以 B 为左部的产生式项目形态为 B - . α都要加入这个集合。goto 函数则负责把当前状态读入一个符号之后转移到的项目集算出来。def closure(items, grammar, nonterminals): result set(items) changed True while changed: changed False new_items set() for item in result: dot_pos item.index(.) next_sym item[dot_pos 1] if dot_pos 1 len(item) else None if next_sym in nonterminals and next_sym not in result: for rhs in grammar[next_sym]: new_items.add((next_sym, (.,) rhs)) if not new_items: break before len(result) result | new_items changed len(result) ! before return frozenset(result) def goto(items, symbol, grammar, nonterminals): moved set() for lhs, rhs in items: if len(rhs) 0 and rhs[0] symbol: moved.add((lhs, rhs[1:])) return closure(moved, grammar, nonterminals)这里有一个经常翻车的实现细节项目不要用字符串表示要用 (左部, 右部元组) 这样的元组结构圆点在右部元组里用特殊符号 . 显式占位。用字符串表示会遇到圆点到底算终结符还是分隔符的问题在计算 closure 的时候 next_sym 的取值会变得非常绕。另一个要点是 closure 过程用 while changed 循环而非递归因为文法的产生式之间可能存在间接递归递归做法在层数深的时候容易出现明明集合没变化还要反复展开的情况。当你把这条链路打通得到一组按状态编号排列的项目集且每个项目集到各符号的 goto 边都齐全时AR 表生成的准备工作才算真正结束。4. 从项目集到分析表ACTION/GOTO 生成与驱动循环的参数设定4.1 分析表的数据结构选择二维字典比嵌套数组更适合课设分析表本质上是“状态号 × 符号 → 动作”的映射动作有好几类移进、归约、接受、报错。数据结构的选择直接影响代码可读性和排错难度。C 课设里常见的是二维数组按状态和符号编号存但 Python 课设我更推荐用二维字典外层 key 是状态号内层 key 是符号value 是动作字符串。原因很简单课设文法规模小稀疏表用二维数组浪费大量空间而且很多格子本来就是空的输出对照表的时候还要过滤空值用 dict 直接打印出来就是可读的、只包含有动作的格子。4.2 生成 ACTION/GOTO 表把三种动作写进状态与符号的交叉点SLR(1) 分析表的生成规则一共就三条但每条都要和项目类型精确对应。对形如 A - α . a β 的项目其中 a 是终结符则在状态 i 与符号 a 的交叉格写入 s(j)j 是 goto(i, a) 指向的状态对形如 A - α . 的项目圆点在末尾即归约项目对每个终结符 a ∈ FOLLOW(A)在状态 i 与 a 的交叉格写入 r(k)k 是产生式编号如果某个归约项目的左部是开始符号且对应产生式是增广文法的第 0 条产生式那么状态 i 与 # 交叉格写入 acc。要注意的是扩展文法大多数课设包都会在内部加一条 S - S这条产生式不参与编号只是为了明确接受条件。def build_table(states, grammar, follow, terminals, nonterminals): action {i: {} for i in range(len(states))} goto_table {i: {} for i in range(len(states))} for i, items in enumerate(states): for lhs, rhs in items: if len(rhs) 0 or rhs[0] ! .: pass elif rhs[0] .: next_sym rhs[1] if len(rhs) 1 else None if next_sym in terminals: j get_state_index(goto(states[i], next_sym, grammar, nonterminals)) action[i][next_sym] fs{j} elif next_sym in nonterminals: j get_state_index(goto(states[i], next_sym, grammar, nonterminals)) goto_table[i][next_sym] j else: pass return action, goto_table这段代码只展示了动作写入的骨架真正完整的实现还要处理圆点在末尾的项目。归约项目写入时有一个关键点FOLLOW 集不能只当作一个集合要具体到终结符循环。我见过很多实现把归约动作直接写成遇到任何终结符都归约这就是把 SLR(1) 用成了简单的 LR(0)结果分析表里出现大量冲突。SLR(1) 之所以叫 SLR就是因为它用 FOLLOW 集做精确定位让归约只发生在合法才能归约的输入符号上这一个细节决定你的表里到底有没有冲突项。生成表之后我建议立刻打印出来和教科书上的标准表达式文法 SLR(1) 分析表对比如果 E 的那几行对不上一定是 FOLLOW 或项目集生成有偏差别急着往 driver 调。4.3 驱动循环与调试开关跟着单步输出核对每一步分析表生成之后driver 的写法和 LL(1) 预测分析器完全不同。SLR(1) 的 driver 维护一个状态栈和一个符号栈初始时状态栈压入 0符号栈压入 #。读入一个符号 a 后查 action[top][a]如果是 s(j)状态压栈、符号入栈、输入指针前进如果是 r(k)就按产生式 k 的右部长度弹出相同数量的状态和符号然后根据弹出后的栈顶状态和产生式左部查 goto 表把新状态压栈。如果是 acc 则分析成功。def parse(input_tokens, action, goto_table, grammar): stack [0] symbol_stack [#] ip 0 tokens input_tokens [#] while True: state stack[-1] a tokens[ip] act action[state].get(a) if act is None: raise SyntaxError(funexpected token {a} at position {ip}) if act.startswith(s): stack.append(int(act[1:])) symbol_stack.append(a) ip 1 elif act.startswith(r): lhs, rhs grammar[int(act[1:])] for _ in rhs: stack.pop() symbol_stack.pop() nxt goto_table[stack[-1]][lhs] stack.append(nxt) symbol_stack.append(lhs) elif act acc: return True驱动循环看起来人人会写但有几个细节决定成败。第一个是输入 token 序列末尾一定要补一个 # 否则查表查不到接受动作第二个是归约弹出时状态栈和符号栈要同步弹出我调试的时候见过有人只弹状态栈不弹符号栈结果符号栈越积越长最终栈里出现非终结符堆叠的诡异状态第三个是报错信息里要带上当前状态号和输入符号比如这是一个极其重要的调试参数它直接告诉你是哪一个状态的哪一个符号缺了动作比单纯打印“syntax error”有用十倍。如果你实现里加了 verbose 参数可以把每一步的状态栈、符号栈、输入位置逐行打出来这个输出格式照抄。5. SLR(1) 跑不通的五个高发坑现象、原因和排查顺序5.1 解压即报错 invalid zip archive: could not find eocd先说一个和语法分析算法完全无关但最高发的坑zip 文件本身损坏或者下载不完整。你在解压 SLR(1).zip 的时候如果看到invalid zip archive: could not find eocd这种报错基本上可以确定 zip 包的末尾被截断了。EOCD 是 End of Central Directory 的缩写zip 文件的结尾必须有这个结构找不到它说明文件不完整。解决办法是先看压缩包文件大小很多课设包才几十 KB如果下载下来是个几字节的网页或者空文件重新下载或者换一种下载方式。另外注意有些 Windows 机器上双击解压工具能打开但命令行 unzip 报错这通常是中文文件名编码问题不是文件损坏用 Python 的 zipfile 模块读一次就能区分。5.2 FOLLOW 集算了一个下午结果全是空集合现象是 FIRST 集正确但 FOLLOW 集所有非终结符都只包含一个 #或者干脆是空集。原因最常见的有两个第一是产生式读取时终结符集合没算全导致右部符号扫描时把终结符误判成未知符号跳过第二是 FOLLOW 集计算时忘记处理“非终结符是右部最后一个符号”这条规则或者把规则写成了只有后一个符号的 FIRST 不含 EPS 时才处理而没写 else 分支。解决方法是先在纸上用手算一遍简单文法的 FOLLOW 集然后把程序输出和手算逐项对比。我一般会在 compute_follow 里加一个 debug 开关每轮迭代后打印所有 FOLLOW 集的变化这样能直观看到第一轮之后哪些集合在增长哪些集合并进去就再也没动过。如果所有集合都不动但值全错多半是终结符集合定义错了检查一下终结符是不是包含了 EPS、非终结符是不是包含了一个不该存在的符号。5.3 分析表同一格出现两个动作移进/归约冲突的处理这是 SLR(1) 最经典的翻车现场build_table 之后发现 action[5][] 既写了 s7 又写了 r2。出现这种情况有两种可能一种是你把文法写成有歧义的了比如经典的悬空 else 文法或者表达式文法里没有给 * 和 规定优先级另一种是文法本身是 SLR(1) 处理不了的你的 FOLLOW 集没算错项目集也没错但这个文法需要 LALR(1) 或 LR(1) 才能处理。判别方法很直接先检查文法是否歧义最简单的是把表达式文法改成教科书上那个无歧义版本比如 E - E T | T, T - T * F | F, F - ( E ) | id如果改成无歧义版本冲突消失说明文法需要改写程序本身没问题如果改写后冲突还在说明这个文法的向前看信息在 FOLLOW 集里不够用属于 SLR(1) 能力边界问题需要换 LALR(1)。处理冲突的另一个工程手段是给终结符定义优先级和结合性很多 YACC/Bison 风格的工具就是靠这个消解移进归约冲突的但课设里不建议加这个复杂度直接换无歧义文法更省事。5.4 一跳 goto 就索引越界状态号映射的坑现象是分析过程走到某一步程序突然报 state index out of range 或者 KeyError。原因通常不是驱动循环写错而是项目集到状态号的映射表没建对。在生成项目集族的时候很多实现是把每个新的项目集追加到一个列表里同时用一个字典把项目集内容映射到状态号问题出在 frozenset 的哈希是基于元素顺序无关的同一个项目集元素相同但插入顺序不同哈希值是一样的但如果项目集内部用的是 list 而非 frozenset两个内容相同但顺序不同的项目集会被当成两个状态goto 表里查到的新状态号就指向了错误位置。解决方法是把所有项目集统一转成 frozenset 再哈希并且在查 goto 表的时候用 get 方法带一个哨兵返回值一旦发现查不到就打印当前状态和符号配合 4.3 的单步输出定位是哪一段转移出了问题。5.5 程序“正常结束”却没有任何输出acc 动作的位置不对这是最隐蔽的一个坑driver 循环正常退出返回 True但整条分析过程只做了一次归约或者根本没有动作输出看起来跑通了实际上什么都没验证。原因几乎都是接受条件写错了在 SLR(1) 里只有增广产生式 S - S 的归约项目对应的状态才能写 acc而且写 acc 的格子必须是 # 列。很多课设代码把每个产生式编号为 0 的开始符号归约项目都写成了 acc或者干脆对任何 FOLLOW 集合里的符号都接受。解决方法是检查你写的 build_table 部分确认只有左部为增广开始符号且圆点在末尾的项目写入 acc并且只写入 # 那一列。另一个容易被忽略的点是增广产生式占的编号如果你把 S - S 也编进了产生式列表那么归约 S - S 的动作不应该作为普通归约出现它只会印成 acc。6. 从课设到工具在 SLR(1) 上叠加的三个进阶改造6.1 给 driver 接一个真正的前端词法与错误恢复SLR(1) 分析器在课设里通常只接收一个 token 列表但你要把它变成一个能用的工具就得在前面加一个词法分析器把源代码字符串转成 token 流。这里有一个我踩过的坑词法分析器报错的行列号要带着位置信息传给语法分析器否则语法报错的时候只给一个 token 名用户根本不知道错在源文件的哪一行。更实用的是一个朴素的错误恢复策略当 driver 遇到非法 token 时不要直接崩掉而是输出错误信息和位置然后从输入流里跳过一批 token直到找到一个能继续分析的符号这个策略在错误恢复里叫 panic mode实现成本低对课程验证类场景够用。def parse_with_recovery(input_tokens, action, goto_table, grammar): stack [0] ip 0 sync_tokens {#, ;, }} while ip len(input_tokens): state stack[-1] a input_tokens[ip] act action[state].get(a) if act is None: print(ferror: unexpected {a} at token {ip}) while ip len(input_tokens) and input_tokens[ip] not in sync_tokens: ip 1 return False # 后面的移进/归约逻辑同普通 parse错误恢复的同步符号集合很值得再想一想。常见做法是把那些在语言里表示“一段结构结束”的 token 当作同步点比如分号、右花括号、右括号和结束符 #。恢复策略本身不用追求完美能报错、能解耦、不至于崩掉就是一个课设阶段合格的前端了。真到了做工业级工具的时候SLR(1) 本身就不太够用了这一步只是让实验看起来更像一个编译器前端。6.2 把分析过程可视化让状态栈的变化逐步可追调试 SLR(1) 的另一个高效技巧是把 trace 输出改成可视化形式每一行打印当前状态栈、符号栈、剩余输入以及这一步执行的动作。调试到第 5 章那种归约深度多的问题时人肉看栈输出还是费劲我一般会再写一个小函数把分析过程导出成 HTML 表格每一行对应一个状态颜色区分移进和归约。这个改造不需要动核心算法只在 driver 循环里收集日志开销极小但对上课验收非常加分。6.3 从 SLR(1) 到 LALR(1)值得花一天试试的下一步如果你把这套代码调通并且感觉 SLR(1) 的 FOLLOW 集太粗糙下一步就是 LALR(1)。LALR(1) 的核心是在 LR(0) 项目集上合并同心项目集把向前看信息从 FOLLOW 集细化成每个项目自己的展望符号冲突消解能力明显强不少。改造这条路线可以把现有代码里所有依赖 FOLLOW 的地方换成展望符号传播逻辑但工作量和 SLR(1) 完全不在一个量级属于典型的“看起来只是多一步实际上整套表生成都要重写”的工程。你想好要交作业就用 SLR(1)想继续往编译原理深处走再动 LALR别在截止前一天半路换算法那是血泪经验。我自己带过的一个课设里就吃过慢一步换算法的亏明明 SLR(1) 表在一个含十几个产生式的文法上是能跑的但项目汇报前非要改成 LALR 想显得更高级结果展望符号传播那一步有个 corner case 写错一直调试到验收前半小时。后来我的习惯就变成了课设阶段的 SLR(1) 输出先和手算表对一遍再跑输入样例确认基线正确后再谈扩展你如果也是赶工期的状态建议先照着这个流程把最小文法全流程跑通再决定要不要动 LALR 的念头。希望帮到你。本文还有配套的精品资源点击获取
