尧图网页设计 
简介面向计算机专业课程设计与毕业设计场景这份北京化工大学编译原理大作业完整覆盖词法分析与语法分析两大核心模块实现了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 个 tokenLR0 在最朴素的版本里一概不看前瞻只要有归约机会就归约于是产生大量移进/归约冲突SLR1 引入全局 FOLLOW 集辅助判断LR1 则把前瞻符号传进每个项目内部精度最高但状态也最多。2.3 一个框架的三次增强从 LR0 到 SLR1 再到 LR1LR 家族的三个版本并不需要三套自动机构建代码。它们共用 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:i2] 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 LL1FIRST/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[i1:] 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/LR1LR 分析的核心是项目集族构建。项目格式用四元组表示(左部, 右部符号列表, 圆点位置, 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[dot1:] 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 - . Slookahead 固定为 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 → βAA → α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 测试用例设计覆盖正常、边界与错误恢复三组用例运行截图要想有说服力测试输入必须覆盖三层。只截一个12*3的成功运行图看不出任何边界能力。用例编号输入目的预期结果T01x 1 2 * 3;验证优先级归约序列中 * 先于 T02x (1 2) * 3;验证括号改变结合归约序列与 T01 不同T03x ;语法错误定位报错位置指向赋值号后T04x 1 ;错误恢复报错后继续分析到分号T05123abc词法边界定位到首个非法字符附近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。希望帮到你。本文还有配套的精品资源点击获取 编译原理大作业实战：从词法分析到LR1语法分析器全解析
简介面向计算机专业课程设计与毕业设计场景这份北京化工大学编译原理大作业完整覆盖词法分析与语法分析两大核心模块实现了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 个 tokenLR0 在最朴素的版本里一概不看前瞻只要有归约机会就归约于是产生大量移进/归约冲突SLR1 引入全局 FOLLOW 集辅助判断LR1 则把前瞻符号传进每个项目内部精度最高但状态也最多。2.3 一个框架的三次增强从 LR0 到 SLR1 再到 LR1LR 家族的三个版本并不需要三套自动机构建代码。它们共用 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:i2] 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 LL1FIRST/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[i1:] 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/LR1LR 分析的核心是项目集族构建。项目格式用四元组表示(左部, 右部符号列表, 圆点位置, 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[dot1:] 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 - . Slookahead 固定为 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 → βAA → α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 测试用例设计覆盖正常、边界与错误恢复三组用例运行截图要想有说服力测试输入必须覆盖三层。只截一个12*3的成功运行图看不出任何边界能力。用例编号输入目的预期结果T01x 1 2 * 3;验证优先级归约序列中 * 先于 T02x (1 2) * 3;验证括号改变结合归约序列与 T01 不同T03x ;语法错误定位报错位置指向赋值号后T04x 1 ;错误恢复报错后继续分析到分号T05123abc词法边界定位到首个非法字符附近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。希望帮到你。本文还有配套的精品资源点击获取