简介:面向计算机专业课程设计与毕业设计场景,这份北京化工大学编译原理大作业完整覆盖词法分析与语法分析两大核心模块,实现了LL1、LR0、SLR1、LR1及LALR1多种主流算法,适合需要参考编译前端完整实现思路的学生与开发者。资源包共56个文件,体积约1.21MB,以Python与Java源码为主,辅以XML工程配置、JS/CSS页面及Markdown说明文档,同时提供README与运行截图,便于快速掌握项目结构并二次扩展。已有164人学习使用,代码经测试运行成功,评审平均分达96.5分。内容上,词法分析提供控制台与动态交互页面两套实现,语法分析各算法独立成模块,附文档说明与运行截图,可对照学习或直接用于课设答辩,也可作为毕设初期立项演示。
1. 编译原理大作业为什么值得认真做:从词法分析到 LR1 一次补齐前端主干
期末前两周,检索“编译原理 词法分析 语法分析 LL1 LR1”的学生,多半只剩两个目标:拿到能跑的压缩包、交上不挂科。这里有个反直觉的结论:一套带源代码、文档说明和运行截图的大作业,比单纯一份源码更有复现价值,因为它逼着你把 LL1、LR0、SLR1、LR1 这四种语法分析方法的构建过程完整走一遍,恰好覆盖编译器前端的主干链路。对拿到这个压缩包的人来说,它解决的不仅是学分问题——面试时能画预测分析表、能讲清 LR 自动机怎么构建,靠的就是这一遍真动手。适合认真写作业的学生、要补编译原理基础的求职者,以及想快速把编译原理实验落地的开发人员。
2. 从预测表到 LR 自动机:LL1、LR0、SLR1、LR1 的差别只在两处
四种方法一起出现在大作业要求里,不是老师故意加量。它们共用同一套词法接口,却在语法分析阶段走向两条路:LL1 自顶向下展开产生式,LR 家族自底向上做移进和归约。把这一章读透,后面写代码就只是填表逻辑的区别。
2.1 词法分析在整条链路里的位置:token 流是所有分析器的唯一入口
词法分析器读入字符流,按词法规则切成 token 流。它是语法分析器的唯一数据源,输出格式直接决定下游代码的复杂度。这里的定位很明确:词法分析只负责“切词”,不负责判断“词拼在一起合不合法”,那是语法分析的事。对应清华大学出版社第三版教材第二章的内容,实操时就是一张状态转移图:把标识符、关键字、数字、运算符、分隔符分别映射到不同状态。
大作业里词法分析的常见做法有三种:手写状态机、用 flex 自动生成、用正则库辅助匹配。我的建议是手写状态机。文法规模小,状态转移表能画得出来,不会被工具生成的代码掩盖细节。更重要的是,手写状态机能让你在文档里画状态图,运行截图也能和状态图对应上,审核老师一眼就能看出你确实理解了 DFA。
词法分析器的对外接口通常是一个函数:输入整段源码,输出 token 列表,每个 token 是(类型,值)二元组,最后统一追加一个 EOF。这个 EOF 符号就是 LL1 里的结束符 $,也是 LR 表里的接受符号。很多项目在这一步就埋了坑,后面第 4 章会专门讲。
2.2 自顶向下与自底向上的分水岭:推导方向决定一切
LL1 是自顶向下:从开始符号出发,反复用产生式展开最左非终结符,直到输入串被完全推导出来。它需要向前看一个 token,决定当前用哪个产生式展开。这个“1”就体现在这里。
LR 家族是自底向上:从 token 流出发,把输入逐个压进分析栈,遇到右部匹配时就按产生式归约,直到栈里只剩开始符号。归约方向与 LL1 的推导方向正好相反。
这个方向差异直接带来一个关键结论:LL1 必须消除左递归,因为 E → E + T 这种产生式会让自顶向下推导永远展开不完;而 LR 天然处理左递归,同一套带左递归的文法在 LR 里完全正常。所以大作业里,LL1 和 LR 版本的文法文件不能直接共用,这是第一处需要区分的地方。
第二个差异在前瞻信息的处理方式上。LL1 的前瞻是固定的 1 个 token;LR0 在最朴素的版本里一概不看前瞻,只要有归约机会就归约,于是产生大量移进/归约冲突;SLR1 引入全局 FOLLOW 集辅助判断;LR1 则把前瞻符号传进每个项目内部,精度最高但状态也最多。
2.3 一个框架的三次增强:从 LR0 到 SLR1 再到 LR1
LR 家族的三个版本并不需要三套自动机构建代码。它们共用 CLOSURE 与 GOTO 两个核心函数,差别只集中在“归约动作何时合法”这一处。
LR0 的观点是:项目集中只要圆点到达产生式末尾,就无条件归约,不管下一个输入符号是什么。SLR1 的观点是:归约前看一眼当前输入符号,只有在它属于左部非终结符的 FOLLOW 集时才归约。LR1 更精细:每个项目在构建闭包时,就把合法的前瞻符号传播进来,归约时只认当前输入符号等于该项目自带的 lookahead 才动手。
所以代码层面可以只写一套 LR 自动机框架,再给归约判定留一个开关。先跑通 LR0,再加 FOLLOW,再传播 lookahead,这就是大作业推荐的演进路线,也是文档里最适合展示对比的地方。
| 方法 | 构建方向 | 前瞻信息来源 | 归约判定条件 | 常见问题 |
|---|---|---|---|---|
| LL1 | 自顶向下 | 当前输入 token | 查预测分析表 | 左递归、左公因子 |
| LR0 | 自底向上 | 无 | 圆点到达末尾即归约 | 大量冲突 |
| SLR1 | 自底向上 | 全局 FOLLOW 集 | 输入符号属于 FOLLOW(A) | FOLLOW 过宽造成假冲突 |
| LR1 | 自底向上 | 每个项目自带 lookahead | 输入符号等于该项目 lookahead | 状态数膨胀 |
这张表建议直接搬进文档说明里,它就是四种方法的浓缩答案。
3. 把核心模块跑通:词法分析、LL1 与 LR0/SLR1/LR1 的最小可运行实现
这一章按“词法 → LL1 → LR 自动机 → 三种表”的顺序给最小可运行实现。生产环境里这套东西通常用 C++ 或 Java 写,但教学场景用 Python 表达算法最直接,逻辑可以平移到任何语言。代码以教学清晰优先,数据结构用中文注释标清楚,方便你改成自己老师指定的语言。
3.1 词法分析:用一张状态转移逻辑识别标识符、数字与运算符
先写一个能跑的词法分析器。它处理 C 语言子集:标识符、关键字、整数、加减乘除、括号、赋值号和分号。
KEYWORDS = {"if", "else", "while", "int", "return"} END = "$" # 统一结束符,LL1 和 LR 共用 def is_digit(c): return "0" <= c <= "9" def is_id_start(c): return c.isalpha() or c == "_" def is_id_part(c): return c.isalpha() or c.isdigit() or c == "_" def tokenize(src: str) -> list: tokens = [] i, n = 0, len(src) while i < n: c = src[i] if c in " \t\n": # 空白直接跳过 i += 1 continue if is_id_start(c): # 标识符或关键字 start = i i += 1 while i < n and is_id_part(src[i]): i += 1 word = src[start:i] tokens.append(("KEYWORD" if word in KEYWORDS else "IDENT", word)) elif is_digit(c): # 整数 start = i i += 1 while i < n and is_digit(src[i]): i += 1 tokens.append(("INT", src[start:i])) elif c in "+-*/=();{},><": # 运算符与分隔符 two = src[i:i+2] if two in ("==", "!=", "<=", ">="): tokens.append(("OP", two)) i += 2 else: tokens.append(("OP", c)) i += 1 else: raise RuntimeError(f"无法识别的字符 {c},位置 {i}") tokens.append(("EOF", END)) return tokens这段代码把识别逻辑按状态分成三类:字母或下划线开头进入标识符分支,数字开头进入数字分支,运算符和分隔符单独处理。这里有一个必须注意的顺序问题:双字符运算符==、!=、<=、>=要放在单字符分支之前判断,否则==会被拆成两个=。
参数上,KEYWORDS集合随文法任意扩充,END常量被后面 LL1 和 LR 共用。如果老师要求错误恢复,不建议在这里直接抛异常,而是把错误信息记录进一个列表,继续往后扫,让语法分析阶段统一报错。
3.2 LL1:FIRST/FOLLOW 集与预测分析表的完整实现
LL1 表构建的核心是 FIRST 集和 FOLLOW 集。FIRST 集用不动点算法算,循环到没有新元素加入为止。
# grammar 格式:{"E": [["E", "+", "T"], ["T"]], ...} # epsilon 用字符串 "epsilon" 表示空串 def compute_first(grammar, nonterms): first = {nt: set() for nt in nonterms} changed = True while changed: changed = False for A, productions in grammar.items(): for body in productions: for symbol in body: if symbol not in nonterms: # 终结符直接加入 if symbol not in first[A]: first[A].add(symbol) changed = True break before = len(first[A]) first[A] |= (first[symbol] - {"epsilon"}) if "epsilon" not in first[symbol]: break if len(first[A]) != before: changed = True else: # body 所有符号都可能为空,epsilon 进 FIRST(A) if "epsilon" not in first[A]: first[A].add("epsilon") changed = True return first这个实现里最关键的是for...else结构:只有for循环完整跑完、没有被break打断时,才会执行else分支,此时说明产生式右部所有符号都可能推出空串,epsilon 才能进入 FIRST(A)。这个细节是新手最容易写错的地方。
FOLLOW 集在 FIRST 集基础上构建:
def compute_follow(grammar, first, start, nonterms): follow = {nt: set() for nt in nonterms} follow[start].add(END) # 开始符号的 FOLLOW 必须有结束符 changed = True while changed: changed = False for A, productions in grammar.items(): for body in productions: for i, B in enumerate(body): if B not in nonterms: continue old = set(follow[B]) rest = body[i+1:] if not rest: # B 在产生式末尾,FOLLOW(A) 并入 FOLLOW(B) follow[B] |= follow[A] else: for sym in rest: if sym in nonterms: follow[B] |= first[sym] - {"epsilon"} if "epsilon" not in first[sym]: break else: follow[B].add(sym) break else: # rest 全部可能为空,FOLLOW(A) 继续传播 follow[B] |= follow[A] if follow[B] != old: changed = True return follow注意 FOLLOW 集里永远不出现 epsilon,结束符统一用常量END表示,这里就是$或#。很多项目把$写死在 LL1 代码里、把#写死在 LR 代码里,两边接口一拼接就出问题,统一常量是治本做法。
有了 FIRST 和 FOLLOW,预测分析表就好填了:
def build_ll1_table(grammar, first, follow, nonterms, terms): table = {nt: {t: None for t in terms} for nt in nonterms} for A, productions in grammar.items(): for body in productions: deriv = set() # 该产生式能推导出的首个终结符集合 for sym in body: if sym in nonterms: deriv |= first[sym] - {"epsilon"} if "epsilon" not in first[sym]: break else: deriv.add(sym) break else: deriv.add("epsilon") for a in deriv - {"epsilon"}: assert table[A][a] is None, f"冲突:{A} -> {body}" table[A][a] = body if "epsilon" in deriv: for a in follow[A]: if a != "epsilon": assert table[A][a] is None, f"冲突:{A} -> {body}" table[A][a] = body return tableassert就是冲突检测。如果同一个表项被填两次,说明文法不是 LL(1) 文法,需要回去消除左递归或提取左公因子,而不是硬往下走。
3.3 LR 自动机的公共底座:CLOSURE 与 GOTO 一个实现吃遍 LR0/SLR1/LR1
LR 分析的核心是项目集族构建。项目格式用四元组表示:(左部, 右部符号列表, 圆点位置, lookahead),其中圆点位置是一个整数下标,表示已经扫描到右部第几个符号。
def first_of_string(symbols, first, nonterms): """对符号串求 FIRST 集,含 epsilon 传播""" result = set() for sym in symbols: if sym in nonterms: result |= first[sym] - {"epsilon"} if "epsilon" not in first[sym]: break else: result.add(sym) break else: result.add("epsilon") return resultfirst_of_string负责处理产生式右部圆点之后的符号串。闭包函数在展开非终结符时,需要用这个函数计算出新的前瞻符号:
def closure(items, grammar, first, nonterms): result = set(items) stack = list(result) while stack: left, right, dot, lookahead = stack.pop() if dot >= len(right): continue sym = right[dot] if sym in nonterms: # 求圆点之后符号串 beta 的 FIRST 集 beta = right[dot+1:] beta_first = first_of_string(beta, first, nonterms) if "epsilon" in beta_first: # beta 可能为空时,继承当前项目的 lookahead beta_first.remove("epsilon") beta_first.add(lookahead) for b in beta_first: new_item = (sym, [], 0, b) # 新项目:圆点在开头,lookahead 为 b if new_item not in result: result.add(new_item) stack.append(new_item) return frozenset(result)这里是 LR1 与 LR0 在实现上最本质的差异:当圆点后面的 beta 串可能为空时,新项目的 lookahead 必须继承当前项目的 lookahead,这叫 lookahead 传播。如果这里写错,LR1 分析表会漏掉合法归约,程序跑起来表现诡异。
GOTO 函数只需要把圆点移动一位,再做闭包:
def goto(item_set, symbol, grammar, first, nonterms): moved = set() for left, right, dot, lookahead in item_set: if dot < len(right) and right[dot] == symbol: moved.add((left, right, dot + 1, lookahead)) return closure(moved, grammar, first, nonterms)项目集族构建如下,注意用frozenset做集合元素,才能去重和求索引:
def build_lr1_collection(grammar, start, nonterms): # 增广文法:S' -> . S,lookahead 固定为 END initial = ("S'", [start], 0, END) C = [closure({initial}, grammar, first, nonterms)] transitions = {} # (状态编号, 符号) -> 目标状态编号 changed = True while changed: changed = False for i, item_set in enumerate(list(C)): # 收集当前状态里圆点右边的所有符号 symbols = {right[dot] for left, right, dot, _ in item_set if dot < len(right)} for symbol in symbols: nxt = goto(item_set, symbol, grammar, first, nonterms) if len(nxt) == 0: continue if nxt not in C: C.append(nxt) changed = True transitions[(i, symbol)] = C.index(nxt) return C, transitions这里用list(C)做快照,再配合changed外层循环继续扫描新加入的状态。这是处理“构建过程中集合不断增长”的可靠写法。transitions就是自动机的状态转移表,LLR0、SLR1、LR1 都复用这一份。
3.4 三张分析表的切换:只在归约判定处动手脚
有了自动机之后,ACTION 表是最后一步。三个版本的差异集中在归约分支的填写规则:
def build_action_table(C, transitions, grammar, follow, mode): action = {} for i, item_set in enumerate(C): for item in item_set: left, right, dot, lookahead = item if dot < len(right) and right[dot] not in nonterms: # 移进动作:状态跳转 action[(i, right[dot])] = ("shift", transitions[(i, right[dot])]) elif dot == len(right): # 归约/接受动作,三种模式的区别全部在这里 if left == "S'" and lookahead == END: action[(i, END)] = ("accept",) continue if mode == "LR0": # LR0:不看前瞻,对全部终结符填归约 for t in terms: action[(i, t)] = ("reduce", left, tuple(right)) elif mode == "SLR1": # SLR1:只对 FOLLOW(left) 里的终结符填归约 for t in follow[left]: if t != "epsilon": action[(i, t)] = ("reduce", left, tuple(right)) else: # LR1:只对当前项目自带的 lookahead 填归约 action[(i, lookahead)] = ("reduce", left, tuple(right)) return action这段代码直观展示了“一套框架三种表”的含义:移进逻辑完全一样,归约逻辑才是分歧点。LR0 在遇到归约项目时无脑填满所有终结符,SLR1 收窄到 FOLLOW 集,LR1 收窄到单个 lookahead。这也是为什么 LR1 状态数最多——每个项目都带着不同的前瞻符号,项目集自然膨胀。
代码里nonterms需要在函数外部传入,我这里为了可读性省略了参数列表中的nonterms。实际使用时记得补上,它是判断符号类型的依据。接受动作单独判断left == "S'",因为增广文法的归约意味着整个输入已经被归约成开始符号,这是 LR 分析的终止条件。
4. 大作业避坑指南:五个让项目翻车的常见问题
这一章全部来自我实际检查和辅导大作业时反复看到的问题。每一条都是“现象 → 原因 → 解决”的结构,照着自己代码里对应位置排查即可。
4.1 左递归没消除,LL1 预测分析表一列就翻车
现象:运行build_ll1_table时assert直接抛出冲突异常;如果没加断言,预测分析表里同一个入口被后写的产生式覆盖,分析时栈指针无限下探,最后栈溢出。
原因:文法里存在 E → E + T 这种左递归产生式。计算 FIRST 集时,FIRST(E) 的一部分来自 FIRST(T),而 E → E + T 的推导集合又把 + 带进了和 E → T 相同的位置,于是表项冲突。
解决:先消除左递归。把 A → Aα | β 改写成 A → βA',A' → αA' | ε。表达式文法的改写结果如下:
E -> T E' E' -> + T E' | epsilon T -> F T' T' -> * F T' | epsilon F -> ( E ) | id | num改完后重新计算 FIRST/FOLLOW。注意改写后的文法和原文法等价,但分析树的形状变了,后面做语义动作时要按新文法组装节点。
4.2 LR1 状态爆炸,文法稍大程序就卡死
现象:产生式超过 15 条后,项目集族从几十个涨到几百个,closure里的while stack循环反复迭代,程序肉眼可见地变慢。
原因:LR1 的 lookahead 传播是组合式膨胀。每个非终结符展开时,要把 FIRST(beta) 里的所有终结符都作为新项目的前瞻符号;项目之间又互相影响,闭包要好几轮才能稳定。状态数不是线性增长,而是按前瞻组合爆炸。
解决:先跑 LR0。如果 LR0 在某个状态没有冲突,就不要强行上 LR1。把模式开关留好,大作业里只需要展示“SLR1 报冲突而 LR1 不报”的一个小例子就足够说明 LR1 的价值。另外,闭包迭代用队列 +visited集合代替while changed全量扫描,能显著减少重复计算。真要在较大文法上跑 LR1,可以把项目集用整数编号缓存,避免frozenset反复哈希。
4.3 SLR1 的假冲突:FOLLOW 集太宽导致的归约错位
现象:SLR1 报告移进/归约冲突,但换成 LR1 之后冲突消失。我在检查作业时遇到的最典型案例是经典赋值文法:
S -> L = R | R L -> * R | id R -> L这个文法的 SLR1 自动机会在某个状态同时出现“看到 = 应该移进”和“R 归约到 L 后看到 = 应该归约”的矛盾判断,但实际输入上下文里 = 根本不可能出现在那个位置。
原因:SLR1 的归约条件用的是全局 FOLLOW 集,它把非终结符在所有可能出现位置的终结符都混在一起。FOLLOW 集是“可能”,不是“必然”,于是产生假冲突。
解决:最直接的办法是用 LR1 替代 SLR1 完成这个文法的分析。如果作业要求必须实现 SLR1,就把这个例子写进文档,说明这是 SLR1 的已知局限,并展示 LR1 的 lookahead 传播如何消除该冲突。这个例子本身就是文档的高价值素材。
4.4 结束符符号不统一:$ 和 # 各写各的
现象:词法分析返回的 EOF 是$,LL1 的 FOLLOW 初始化也是$,但 LR 驱动的接受动作却写成#。结果 LL1 分析正常,LR 分析一遇到输入结束就报“无法匹配任何动作”。
原因:教材里 LL 系列用$表示输入结束,LR 系列用#,两个习惯被分别抄进代码的不同文件,缺少统一常量。
解决:在项目根目录建constants.py,定义END = "$",词法分析、FIRST/FOLLOW、ACTION 表三处全部引用同一个常量。我的习惯是连关键字表、运算符表也放进这一份配置里,词法分析和语法分析共用,避免后续扩展文法时两边不同步。
4.5 运行截图和代码版本脱节
现象:文档里的 token 流截图和当前代码输出格式对不上,或者分析树用的文法还是旧版。这个问题在批改时最碍眼,因为它直接让人怀疑代码真实性。
原因:最后一天赶文档,截了几张历史输出图,代码之后又改过,但图没重跑。
解决:先定死测试输入,再跑程序,再截图,顺序不能反。每张截图文件名带测试用例编号,比如T01-lexer-normal.png、T02-ll1-table.png,文档里截图标题写同一编号。这样即使文档写到一半代码改了,也能立刻发现哪张图需要重截。
5. 文档说明与运行截图:让代码能被看懂的五条实战纪律
压缩包里的“文档说明”和“运行截图”不是装饰品,它们是评审老师判断“这代码是不是你写的”的第一证据链。这一章讲怎么把文档写成能复现、能加分的样子。
5.1 文法文件的设计:BNF 表示法与两种文法版本
大作业文档里必须放文法定义,程序里也要有一份机器可读的文法文件。书面文档用 BNF 表示法,程序内用数据结构表示,两者要一一对应。建议把 LL1 与 LR 的文法分开存放,因为 LL1 版被改写过了。
LR 版本保留左递归,直接描述语言结构:
S -> E E -> E + T | T T -> T * F | F F -> ( E ) | id | numLL1 版本消除左递归之后:
E -> T E' E' -> + T E' | epsilon T -> F T' T' -> * F T' | epsilon F -> ( E ) | id | num程序读入文法文件时,需要约定表达格式:->分隔左右部,|表示多个产生式,空白分隔符号,epsilon 显式写成epsilon。这个约定也要写进文档说明,否则老师没法复现你的构建过程。别忘了 LR 的增广文法 S' → S,它只在内存里构建,不写进文法文件。
5.2 测试用例设计:覆盖正常、边界与错误恢复三组用例
运行截图要想有说服力,测试输入必须覆盖三层。只截一个1+2*3的成功运行图,看不出任何边界能力。
| 用例编号 | 输入 | 目的 | 预期结果 |
|---|---|---|---|
| T01 | x = 1 + 2 * 3; | 验证优先级 | 归约序列中 * 先于 + |
| T02 | x = (1 + 2) * 3; | 验证括号改变结合 | 归约序列与 T01 不同 |
| T03 | x = ; | 语法错误定位 | 报错位置指向赋值号后 |
| T04 | x = 1 + ; | 错误恢复 | 报错后继续分析到分号 |
| T05 | 123abc | 词法边界 | 定位到首个非法字符附近 |
T01 和 T02 用来验证优先级处理是否正确;T03 和 T04 测试错误定位与恢复能力,这是大作业里最常见的加分项;T05 测试词法分析的边界。每个用例都要在文档里贴上 token 快照和关键动作序列,截图按 T01—T05 命名。这样老师拿到压缩包后,不需要自己构造输入就能复现全部截图。
5.3 README 的写作顺序:先让老师五分钟内跑起来
文档说明的第一页决定老师愿不愿意继续看。我见过的失败案例都是 README 一上来先讲算法原理,结果老师找不到运行入口,代码根本没跑起来就打了低分。正确的顺序是先讲怎么跑,再讲怎么测,最后贴截图。
# 编译原理大作业:词法分析与 LL1/LR0/SLR1/LR1 语法分析器 ## 运行环境 Python 3.10+,无第三方依赖 ## 运行方式 python main.py --file test/input.c --method ll1 python main.py --file test/input.c --method lr1 ## 输入输出格式 输入:C 语言子集源码 输出:token 流、分析表、归约序列、分析结果 ## 文件结构 src/lexer.py 词法分析 src/ll1.py LL1 表构建与分析 src/lr.py LR 自动机与三种分析表 docs/ 文档说明目录 shots/ 运行截图目录 ## 测试用例 见 test/ 目录,共 5 个用例,对应 shots/ 下的 T01—T05这段 README 骨架可以直接抄。它覆盖了评审老师最关心的四个问题:用什么跑、怎么跑、输入放哪、输出长什么样。至于算法原理,放正文文档里讲,不占用 README 的位置。
5.4 文档正文的章节划分:一个压缩包该有的完整结构
文档说明除了 README,还要有一份正文。我的建议是按四节组织:文法定义与两种版本说明、四种方法的分析表示例(不用全贴,每个方法一页即可)、测试用例与截图索引、局限与进一步的改进方向。
分析表示例是最容易出错的地方。贴表之前先确认表里的冲突情况和实际运行输出一致,尤其是 SLR1 与 LR1 对比的部分,这是整个项目的技术亮点,也是最容易被追问的地方。局限与改进方向里写两句“LR1 状态数膨胀可考虑 LALR1”这类话,能明显提升专业性。
6. 进阶方向:从表驱动分析器到小型编译器前端
这套大作业跑通之后,下一步是把它变成能用的前端。我有两个常用做法,一个用来验证正确性,一个用来扩展功能。
6.1 用 Yacc/Bison 做交叉验证
手动实现的 LR 分析器容易在小文法上自我感觉良好,遇到隐藏冲突浑然不觉。常见做法是把同一份文法同时喂给 Bison 和自己的程序,对比输出。执行bison -d -v grammar.y会生成y.output状态表,里面列出每个状态的移进、归约和冲突情况。把自己的 ACTION 表和它逐项对照:同一状态、同一终结符,动作不一致就查代码。Bison 报冲突而你的表没冲突,大概率是你漏判了;两边都冲突,再考虑换文法。注意这只是测试基准,不需要抄 Bison 的实现逻辑。
6.2 从识别器变成翻译器
在build_action_table的 reduce 分支里加一个语义动作:归约时把右部符号对应的 AST 节点从语义栈弹出,按产生式左部组装成新节点再压回去。分析栈管状态,语义栈管节点,两个栈同步 push 和 pop。这个小改动做完后,大作业就从“判断输入是否符合文法”升级成“能输出一棵分析树”,面试时可以现场演示。我当年在这个项目上栽过$和#不统一的跟头,也踩过 LR1 状态爆炸的坑,后来的习惯是先跑通 LR0,逐级往上加,绝不一步到位写 LR1。希望帮到你。
本文还有配套的精品资源,点击获取