SLR(1)语法分析器实战：从编译原理原理到自定义文法实现

简介这是基于Java实现的SLR(1)语法分析器实验源码包面向编译原理课程学习者与需要动手实践语法分析器构建的开发者。资源围绕自底向上的SLR(1)解析方法展开涵盖文法表示、消除左递归与左公因子、FOLLOW集构造、闭包与GO TO集计算以及分析表生成等关键步骤代码结构清晰适合对照理论逐步理解解析器实现全流程。压缩包共85个文件主体为76个Java源码文件另有6个XML配置、Idea项目文件及少量说明文本整体约40KB便于直接导入开发环境查看运行。已有521人参与学习内容完整且轻量可作为编译原理实验的参考实现或二次开发基础。通过阅读源码可直观掌握SLR(1)分析表的构建与移进归约流程为后续学习LR(1)、LALR等更复杂语法分析技术打下坚实基础。1. byyl SLR(1).zip 是什么编译原理课设里常见的语法分析器工程值得自己跑通byyl SLR(1).zip 这类压缩包在编译原理课程设计里出现频率相当高byyl 是「编译原理」的拼音缩写SLR(1) 是语法分析阶段最常被点名实现的自底向上分析方法所以这个 zip 里装的十有八九是一个完整的语法分析器工程——文法定义、LR(0) 项目集构造、ACTION/GOTO 分析表和驱动器。它要解决的是把一串 token 按文法规约成语法树的问题做完你会发现书上那一整章的分析表算法落到代码里其实没多少行。适合准备交编译原理课设、或者想搞清楚 LR 分析器内部机制的同学。别急着打开压缩包就找可执行文件先把原理和代码结构对齐后面替换自己的文法时才不会踩坑。2. SLR(1) 的分析原理LR(0) 项目集加 FOLLOW 集合一次看懂分析表从哪来2.1 为什么选 SLR(1)LR(0) 太弱、LR(1) 状态爆炸它是实践里的折中编译原理的语法分析阶段自底向上方法里最容易实现出成果的就是 LR(0) 和 SLR(1)。LR(0) 只看项目集内部状态就决定动作遇到移进-归约冲突基本只能靠人工干预实用性很有限而完整的 LR(1) 要为每个状态保存向前看符号状态数量经常成倍增长课设周期内写不完调试也更痛苦。SLR(1) 站在两者中间它仍然构造 LR(0) 项目集规范族只是归约时多查一步 FOLLOW 集合用「当前输入符号是否在产生式左部的 FOLLOW 里」来决定能不能归约。这个「多查一步」能消掉一批 LR(0) 解决不了的冲突代价很小代码量只多一个 FOLLOW 函数的量。多数常见文法——算术表达式、赋值语句、声明列表——对 SLR(1) 来说都够用所以它成了课设和教学的首选。理解它的工作过程你再去看 LALR(1) 或 LR(1) 的代码会发现只是在这套骨架上加东西。2.2 三步构造分析表从拓广文法、项目集规范族到 FIRST/FOLLOW 集合SLR(1) 分析表的构造可以拆成三个固定步骤每一步都对应代码里一个函数。第一步是拓广文法。给开始符号加一条增广产生式比如原开始符号是 E就加上E - E目的是让分析器能明确识别「整个输入串已经规约完成」的那一刻。没有这条产生式接受动作 acc 就没有落点。第二步是构造 LR(0) 项目集规范族。一个项目就是「产生式 圆点位置」比如E - E·T表示已经看见了 E正等着输入加号。closure 函数把圆点后面的非终结符对应的产生式全部展开goto 函数则模拟读入一个符号后圆点移动。从初始项目出发反复做 goto直到没有新状态就得到了规范族。第三步是计算 FIRST 和 FOLLOW。FOLLOW 集合是 SLR(1) 的核心当一个项目圆点已经到末尾形如T - F·不能直接归约要先看当前输入符号在不在 FOLLOW(T) 里。这个条件区分了 LR(0) 和 SLR(1)也是后面排查冲突时最先怀疑的地方。三步走完根据规则填 ACTION 表和 GOTO 表分析器就成型了。2.3 查表驱动的一趟分析状态栈加符号栈移进、归约、接受一个循环走完分析阶段比构造阶段更直白就是查表循环加两个栈。状态栈记录当前所在的状态编号符号栈记录已经移进或归约出的文法符号读头指向输入 token 流。每一步做的事可以用下面这段逻辑概括这也是几乎所有 LR 分析器驱动器的骨架# lr_driver.py —— 分析驱动器核心循环伪代码级 def parse(tokens, action_table, goto_table, productions): tokens list(tokens) [$] # 末尾补结束符 state_stack [0] # 初始状态 0 sym_stack [] # 符号栈初始为空 while True: state state_stack[-1] token tokens[0] # 1. 查 ACTION 表 action action_table.get((state, token)) if action is None: return False, 语法错误拒绝该输入 # 2. 移进状态入栈符号入栈读头前进 if action.startswith(s): state_stack.append(int(action[1:])) sym_stack.append(token) tokens.pop(0) # 3. 归约弹出 |rhs| 个状态和符号查 GOTO 表压入新状态 elif action.startswith(r): idx int(action[1:]) lhs, rhs productions[idx] for _ in rhs: state_stack.pop() sym_stack.pop() next_state goto_table[(state_stack[-1], lhs)] state_stack.append(next_state) sym_stack.append(lhs) # 4. 接受 elif action acc: return True, 输入串被接受这里的核心思想是移进就是「把当前输入压栈状态跟着走」归约就是「按产生式把栈顶一段符号换回左部同时状态跳回」。这个循环里没有递归、没有回溯每一步都是确定的查表操作所以 LR 系列分析器速度很快也适合手写。你用任何语言实现本质上都是在重复这个循环。3. 把 zip 工程跑起来一个最小 Python 版 SLR(1) 的完整实现与运行输出3.1 解压后的第一件事找入口文件和文法定义别急着双击运行拿到 zip 先解压然后用文本编辑器打开 README 或者看目录结构。这类课设工程的常规组织方式是一个源文件负责分析表构造和分析驱动一个文法文件描述产生式可能再配一个输入样例文件。入口文件命名常见的是slr1.py、main.c、parser.cpp文法文件通常叫grammar.txt之类。我一般先不看代码先打开文法文件确认它描述的是不是算术表达式文法再看入口文件里的数据结构——只要搞清楚「产生式怎么存、终结符怎么判、空串怎么写」三个问题后面替换成自己的文法就很顺。如果包里既有 C 版又有 Python 版优先用 Python 版调通。C 版通常牵扯内存管理和字符串分割排错成本高一截先跑通再回头读 C 代码会轻松很多。下面我直接给出一份最小但完整的 Python 实现逻辑和大多数课设源码一致你对照自己那份包就能找到对应函数。3.2 最小可跑的 SLR(1) 实现FIRST/FOLLOW 与 LR(0) 项目集先实现数据结构和两个集合计算这段代码是整个分析器的基础。# slr1_min.py —— 最小可跑的 SLR(1) 分析器第一部分 from collections import defaultdict # ---------- 1. 文法定义 ---------- # 产生式右部用 tuple 存空串写成空 tuple () productions [ (E, (E, , T)), (E, (T,)), (T, (T, *, F)), (T, (F,)), (F, ((, E, ))), (F, (id,)), ] start E # 终结符 右部出现且不在左部集合中的符号再加结束符 $ non_terms {lhs for lhs, _ in productions} terms {sym for _, rhs in productions for sym in rhs if sym not in non_terms} terms.add($) # 增广产生式S - S放在 all_prods 第 0 位 aug_prod (start , (start,)) all_prods [aug_prod] productions # ---------- 2. FIRST 集合不动点迭代 ---------- first defaultdict(set) for t in terms: first[t] {t} # 终结符的 FIRST 是自己 changed True while changed: changed False for lhs, rhs in all_prods: before set(first[lhs]) for sym in rhs: first[lhs] | first[sym] - {} if not in first[sym]: # 该符号不能推出空串停止 break else: first[lhs].add() # 整条右部都能推出空串 if len(first[lhs]) ! before: changed True # ---------- 3. FOLLOW 集合不动点迭代 ---------- follow defaultdict(set) follow[start].add($) changed True while changed: changed False for lhs, rhs in all_prods: for i, sym in enumerate(rhs): if sym not in non_terms: continue before set(follow[sym]) for nxt in rhs[i 1:]: follow[sym] | first[nxt] - {} if not in first[nxt]: break else: follow[sym] | follow[lhs] # 后面符号都能推空串 if len(follow[sym]) ! before: changed True这段代码有两个要点。第一FIRST 和 FOLLOW 都用不动点迭代用while changed反复扫描所有产生式直到集合不再变大。用单次循环或者递归实现容易漏掉 A 依赖 B、B 又依赖 A 的循环文法这里统一走迭代最稳。第二空串我用表示终结符集合要显式排除它否则空串会被当成一个普通终结符写进 ACTION 表后患无穷。项目集规范族的实现同样用不动点思想closure 不断把圆点后面的非终结符产生式加进来直到不再新增goto 先收集圆点移动后的项目再对结果做一次闭包。# ---------- 4. LR(0) 项目集规范族 ---------- def closure(items): items set(items) while True: new set(items) for pidx, dot in items: lhs, rhs all_prods[pidx] if dot len(rhs) and rhs[dot] in non_terms: for i, (l, _) in enumerate(all_prods): if l rhs[dot]: new.add((i, 0)) if new items: return frozenset(items) items new def goto(items, sym): moved set() for pidx, dot in items: lhs, rhs all_prods[pidx] if dot len(rhs) and rhs[dot] sym: moved.add((pidx, dot 1)) return closure(moved) # 从初始项目 (0, 0) 出发反复求 goto 直到状态数不再增加 C [closure({(0, 0)})] changed True while changed: changed False for items in list(C): for sym in terms | non_terms: nxt goto(items, sym) if nxt and nxt not in C: C.append(nxt) changed True注意状态集 C 的遍历顺序会影响状态编号但不影响分析结果。如果你要跟教材上的状态编号逐一对上就得把符号遍历顺序固定成字母序我平时调试时会加一行sorted(terms | non_terms, keystr)这样状态编号稳定对照书方便。3.3 分析表生成与驱动器用 idid*id 做一次完整实验拿到项目集规范族之后生成 ACTION/GOTO 表就是纯粹的规则翻译。遍历每个状态里的每个项目圆点后面是终结符就填移进动作圆点在末尾就根据 FOLLOW 集合填归约动作增广产生式的归约对应接受。# ---------- 5. 生成 ACTION/GOTO 分析表 ---------- ACTION {} GOTO {} conflicts [] for idx, items in enumerate(C): for pidx, dot in items: lhs, rhs all_prods[pidx] if dot len(rhs): # 圆点不在末尾 sym rhs[dot] if sym in terms: nxt C.index(goto(items, sym)) ACTION[(idx, sym)] s str(nxt) else: # 圆点在末尾归约 if pidx 0: # S - S 的归约就是接受 ACTION[(idx, $)] acc else: for t in follow[lhs]: if t : continue act r str(pidx) pre ACTION.get((idx, t)) if pre is not None and pre ! act: conflicts.append((idx, t, pre, act)) else: ACTION[(idx, t)] act for A in non_terms: nxt goto(items, A) if nxt: GOTO[(idx, A)] C.index(nxt) # ---------- 6. 分析驱动器 ---------- def parse(tokens): tokens list(tokens) [$] states [0] syms [] pos 0 trace [] while True: act ACTION.get((states[-1], tokens[pos])) if act is None: return False, trace trace.append((list(syms), list(tokens[pos:]), act)) if act acc: return True, trace if act.startswith(s): states.append(int(act[1:])) syms.append(tokens[pos]) pos 1 elif act.startswith(r): pidx int(act[1:]) lhs, rhs all_prods[pidx] for _ in rhs: states.pop() syms.pop() states.append(GOTO[(states[-1], lhs)]) syms.append(lhs) ok, trace parse(id id * id.split()) for syms, rest, act in trace: print(f符号栈{syms}, 剩余输入{rest}, 动作{act}) if conflicts: print(存在冲突, conflicts) else: print(分析表无冲突输入被接受 if ok else 拒绝)参数说明都写在代码里了重点看两个关键设计。一是项目用(产生式下标, 圆点位置)表示所有操作都是对这两个整数做处理比存字符串快也简单二是归约动作直接引用了第 3.2 节算出的follow[lhs]这就是 SLR(1) 和 LR(0) 本质差异所在。运行后你会看到类似这样的轨迹符号栈[], 剩余输入[id, , id, *, id, $], 动作s3 符号栈[id], 剩余输入[, id, *, id, $], 动作r4 符号栈[F], 剩余输入[, id, *, id, $], 动作r2 符号栈[T], 剩余输入[, id, *, id, $], 动作r1 ... 符号栈[E], 剩余输入[$], 动作acc状态编号可能和教材不同没关系看动作序列先移进 id归约成 F 再归约成 T遇到加号后继续读右边最后接受。这条轨迹就是规范归约序列的一种打印形式第 6 章我们会用它做验证。4. 换成你自己的文法改写 grammar.txt 的三个必调点与冲突处理4.1 文法描述格式第一行写开始符号每条产生式一行空串写成 ε把代码里的 productions 写死不是长久之计实际课设通常要求从文件读文法。我习惯的格式很简单第一行是开始符号之后每行一条产生式-左边是左部右边是符号序列符号之间用空格分开空串写成ε# grammar.txt —— 带一元负号的算术表达式文法 E E - E T E - T T - T * F T - F F - - F F - ( E ) F - id读取逻辑要注意两点跳过空行和#注释把右边的ε转成空 tuple否则闭包计算会把 ε 当成普通终结符。对应代码# load_grammar.py —— 从文本读取文法 def load_grammar(path): prods [] start None for raw in open(path, encodingutf-8): line raw.strip() if not line or line.startswith(#): continue if start is None: start line.split()[0] continue left, right line.split(-) syms tuple(right.strip().split()) if syms (ε,): syms () prods.append((left.strip(), syms)) return start, prods这段代码约定「第一个非注释行是开始符号」注释行可以放在文件任意位置方便你在每个产生式旁边标注含义。我实际用下来觉得这个格式比 JSON 或列表字面量更贴近书上的写法也方便复制粘贴老师的作业要求。4.2 改代码的三个必调点终结符集合、产生式编号、token 切分换文法后最容易翻车的是三处它们都在第 3.2 节的代码里。第一处是终结符集合。我的代码用non_terms和terms自动从产生式推导两处推导写的都是if sym not in non_terms顺序一旦反了、*这些符号会被漏掉分析表里缺项运行时直接报语法错误。第二处是产生式编号。r后面的数字是all_prods的下标增广产生式固定占第 0 位你新增产生式后归约动作的编号会自动跟着变一般不用手改但调试时看到r7这类编号要能立刻反应出它对应哪个文法行。第三处是 token 切分。上面示例用id id * id.split()按空格切分实际词法分析器输出的是不含空格的 token 流比如idid*id这时要先做词法切分import re def tokenize(s: str): return re.findall(r\b\w\b|[\-*/()], s) ok, trace parse(tokenize(idid*id))这里的正则含义是「优先匹配连续的单词字符否则匹配单个运算符或括号」。词法规则变复杂时这行要换成你自己词法分析器的输出但分析器内部完全不受影响LR 系列分析器对「上层怎么切词」不敏感。4.3 生成新分析表之前先跑一遍冲突检查换文法后第一件事不是拿输入串去试而是看冲突列表。第 3.3 节的代码里我留了一个conflicts列表生成分析表时如果某个(状态, 终结符)位置既要移进又要归约或出现两种不同归约就记录下来。SLR(1) 对这类冲突没有任何自动消解机制只能人工裁决。常见做法是让冲突处理策略可配置遇到 shift/reduce 冲突默认选移进这符合大多数语言的优先级直觉遇到 reduce/reduce 冲突选产生式编号较小的那个——也就是更早定义的产生式优先。修改建表循环里冲突分支的处理即可。但注意人工裁决能掩盖二义性却掩盖不了错误如果冲突大量出现先怀疑文法本身比如 if-else 悬挂、表达式优先级没分层、或者把ε写成了普通符号。5. SLR(1) 最常见踩坑空串、增广产生式、表索引错位等 5 条记录5.1 空串 ε 处理不当FIRST/FOLLOW 越算越空项目集闭包也缺项现象程序跑完打印出来的 FIRST 和 FOLLOW 全是空集或者项目集数量少得离谱分析表只有两三个状态。用A - B | ε这类文法时必现。原因空串没进 FIRST。第 3.2 节代码里是用表示 ε如果读取文法时把ε当成普通字符存进了 rhs那么first[ε]是空集 not in first[sym]的判断永远为真右部永远不会把空串贡献给左部推导链一断FOLLOW 跟着算不全。解决在加载文法时统一把表示空串的字符转成空 tuple()然后 FIRST 计算里保留if not in first[sym]这个分支。如果是从别的代码移植先打印所有产生式的右部确认没有(ε,)这种带元素的空串表示。5.2 增广产生式没进项目集acc 永远不出现程序死循环现象分析器对任何输入都跑到栈空或者直接越界trace 里从头到尾没有acc动作。原因建表时把增广产生式S - S漏掉了。没有它项目集族里就不存在S - S·这个接受项目ACTION 表里永远不会填acc驱动器到输入末尾只能返回「拒绝」。解决把all_prods [aug_prod] productions放在构造项目集之前初始项目固定用(0, 0)。这里有个连带注意点归约动作里的r编号和产生式列表下标绑定增广产生式必须占据下标 0否则括号匹配会错位。5.3 表索引错位把 GOTO 表当 ACTION 表用遇到非终结符就翻车现象分析过程看不出规律明明输入串是合法的却在移进几个符号后查表得到None提示语法错误。原因驱动器查表用了错误的键。ACTION 表的键是(状态, 终结符)GOTO 表的键是(状态, 非终结符)两者混用是课设里最高频的 bug。特别容易出现在归约动作之后刚归约出一个非终结符却拿这个非终结符去查 ACTION 表。解决驱动器归约后的状态转移必须查GOTO[(states[-1], lhs)]而不是ACTION。代码里把两个表分开存储就能在语法层面防止混用。如果你拿到的是 C 版本常见错误是把二维数组只开了一个下标传的是同一个枚举类型改法是把表声明成两个独立结构。5.4 FOLLOW 集合算不完整循环依赖的产生式被不动点算法跳过现象整个工程只有个别归约动作分析表稀疏得异常比如id后面该出现的移进动作没了。原因FOLLOW 计算用的是单次遍历。对A - B C、B - ε这类产生式如果先处理 B 后处理 AB 的 FOLLOW 已经决定要包含 A 的 FOLLOW但此时 A 的 FOLLOW 还没算出来单次遍历就漏了。这也是为什么第 3.2 节反复强调while changed不动点迭代。解决把 FIRST 和 FOLLOW 都写成直到集合不再变化的循环每次都要比较集合长度。排查时可以在迭代前后打印集合快照确认确实走到了收敛态。看到某个非终结符的 FOLLOW 始终没拿到$就检查它是否经多级非终结符间接连接到开始符号。5.5 悬挂 else 与移进/归约冲突该人工裁决时别手软现象文法里写了一条if E then S else S建表时报出 shift/reduce 冲突位置就在else这个终结符上。原因经典的悬挂 else 二义性。else既可以作为当前 if 语句的归约对象也可以作为外层 if 语句移进对象SLR(1) 在 FOLLOW(S) 里包含了 else所以冲突必然出现。解决按语言常识选择「移进优先」让 else 就近匹配最近的未闭合 if。在建表代码的冲突分支里遇到pre是归约动作、act是移进动作时保留移进即可。这里要记录一个经验二义性文法能用表构造出来但对初学者最安全的路是直接改写文法把 then 和 else 之间强制加一层匹配语句彻底消灭冲突来源。6. 验证 SLR(1) 分析器用规范归约序列复核再向 LALR(1) 迈半步6.1 对照规范归约序列验证分析过程书本上常讲「规范归约序列是移进归约分析的逆过程」实际验证时可以这样用对输入idid*id $先手工写出它的最右推导比如E ET ET*F ...再把推导倒过来看每一步应该是从右部归约到左部。你只需要在设计好的正确输入串上跑一遍分析器拿到第 3.3 节的 trace比对每一步的归约产生式是否和倒序推导一致。凡是中间出现「右部内容与符号栈栈顶不匹配」的步骤一定能在当步 trace 的符号栈里看出来。6.2 用冲突日志做调试而不是全靠 print我现在的习惯是建表时一定保留冲突输出运行前先看冲突列表运行后只看 trace 的最后几步。比逐个 print 状态栈高效。见到sN和rM同时出现在同一状态同一输入符号下先问自己这符号是否不该出现在产生式左部的 FOLLOW 里一半的课设冲突都是 FOLLOW 算宽了。再不行把项目集编号和项目内容打印出来人工核对教材例题的规范族。6.3 下一步改成 LALR(1)把项目集合并起来SLR(1) 跑通之后想往深处走最常见的方向是改成 LALR(1)。做法是构造完整 LR(1) 项目集然后把「核心项目相同」的状态合并成同心集合。合并后分析表体积和 SLR(1) 几乎一样但能处理一部分 SLR(1) 无法消解的冲突。注意合并后仍可能出现新的冲突那已经不是代码问题而是文法本身的问题。给课设答辩留一句「我对比了同一文法的 SLR(1) 和 LALR(1) 分析表规模」的结论效果比多写两百行重复代码好得多。我每拿到一个新的编译原理工程压缩包第一件事都是先把分析表打出来看冲突数再跑输入串——这个习惯替我挡掉了不少黑匣子式的翻车。希望帮到你。本文还有配套的精品资源点击获取