简介面向编译原理课程 LL(1) 语法分析实验的完整资源包源自山东科技大学 2022 年编译原理实验题适合需要完成同类实验或复习自顶向下语法分析的本科生。资源内含可在 Code::Blocks 中直接运行的 C 语言实现与配套实验报告围绕题目给出的表达式文法E→TGG→TG|-TG|εT→FMM→*FM|/FM|εF→(E)|i完整演示了 FIRST 集合与 FOLLOW 集合的计算、预测分析表构造、空产生式处理以及表驱动 LL(1) 分析流程程序可对用户输入的任意符号串自动进行语法判断。报告内容详细对 8 条产生式逐一分析并给出实验原理、算法设计与运行结果展示能帮助读者快速理解 LL(1) 分析中关键冲突的解决思路对 FIRST 集、FOLLOW 集和预测分析表等核心概念也有直观代码示例支撑。资源以 ZIP 压缩包形式提供整体大小约 1.08MB解压后即可运行与对照学习。该资源已有 914 人浏览/学习在课程设计、实验报告撰写和考前回顾等场景下均有较强的参考价值。1. 为什么 22 年山科大的 LL1 实验能让一届届学生破防2022 年山东科技大学编译原理课程的语法分析实验点名要求用 LL1 分析法实现一个自顶向下的语法分析器。这个实验卡住的人不在少数倒不是算法本身多难而是教材上的 FIRST 集、FOLLOW 集和预测分析表这三座大山每一座都有大量“看似懂了、一写就废”的细节。LL1 分析法本质上是一种表驱动的预测分析靠一个分析栈、一张二维表和一个输入串指针就能判定一个文法能否被无回溯地识别。适合谁去做正在补编译原理实验学分的学生、复习自顶向下语法分析的考研党以及想快速复用一个手写递归下降替代方案的工程师。它解决的问题非常具体——给定一个文法如何机械地判断一个句子是否符合语法并给出完整的推导过程。2. 动手前先改造文法左递归与回溯LL1 的两大拦路虎2.1 不是所有文法都能直接进 LL1先分清哪些产生式是“毒药”LL1 分析法要求文法满足两个硬性条件无左递归、无回溯即同一非终结符的多个候选产生式不能有交集。很多学生拿到实验题目第一反应是把课本上的算术表达式文法直接搬进程序结果运行时报错或者分析栈越推越长。原因很简单教科书为了可读性给出的文法往往是左递归的比如常见的E → E T | T这种文法对 LL1 分析器来说是“毒药”。左递归为什么致命LL1 的分析过程是从开始符号出发不断用产生式右侧替换栈顶的非终结符。如果存在E → E T这样的产生式替换后栈顶依然是非终结符 E下一次又替换成 ET栈永远无法朝终结符方向收缩。这不是实现层面的 bug而是文法本身的结构注定了 LL1 算法跑不通。另一种毒药是候选产生式的 FIRST 集相交。比如S → if E then S | if E then S else S两个候选都以 if 开头分析器读到 if 时不知道该选哪条路这就叫“回溯”。LL1 的原则是绝不吃回头草所以这种文法必须在动手写代码前完成手术。2.2 消除左递归与提取左因子改写得留痕常见做法是分两步处理。第一步消除直接左递归方法是把A → A α | β改写为A → β A′和A′ → α A′ | ε。注意这个 ε 不是可有可无的它是递归出口稍后计算 FIRST 集和 FOLLOW 集时它都是关键角色。第二步是提取左因子把S → α β1 | α β2改成S → α S′、S′ → β1 | β2消掉同一前缀造成的分支歧义。这里有个实验报告里容易丢分的点改写过程不能只在草稿纸上演算要在代码注释里保留每一步的“病历”。比如# 原始文法存在直接左递归 # E - E T | E - T | T # T - T * F | T / F | F # F - ( E ) | id # # 消除直接左递归后 # E - T E # E - T E | - T E | ε # T - F T # T - * F T | / F T | ε # F - ( E ) | id这串注释不是写给老师看的是写给你自己调试用的。后面分析表哪里填错了回来看这个改写链能省半小时的定位时间。我还见过一种隐性翻车只消了E的左递归忘了T也有T → T * F这种直接左递归导致栈里 T 永远退不掉。检查这个坑的办法很简单把每个非终结符的所有产生式列出来凡是右侧第一个符号是自身的一律要改造。2.3 一个干净的算术表达式文法实验报告的标准素材完成改造后的文法是 LL1 分析实验最常用的素材我一般直接用上面这个算术表达式文法。终结符集合是{ , -, *, /, (, ), id }非终结符是{ E, E, T, T, F }开始符号是 E其中 id 可以替换成任意标识符或数字。这个文法的好处在于它刚好能演示 ε 产生式的作用E′ 和 T′ 都可能推导为空又能展示多层栈的展开过程输出分析步骤时非常有层次感。更重要的是它的预测分析表规模适中——5 个非终结符、7 个终结符手工表格只有三五行验证时算得过来。如果实验要求更复杂可以追加赋值语句、布尔表达式或者函数调用语法但核心步骤永远是这三板斧消除左递归、提取左因子、验证无二义。3. 硬算 FIRST 集与 FOLLOW 集表驱动的两个黑匣子3.1 FIRST 集的迭代规则与最小 Python 实现FIRST 集是预测分析表的行索引依据。定义不说了直接看计算规则对产生式X → Y1 Y2 ... Yn先把 FIRST(Y1) 里的所有非 ε 终结符放进 FIRST(X)如果 Y1 能推出 ε再继续看 Y2以此类推如果所有 Yi 都能推出 ε那么 ε 也进 FIRST(X)。对于终结符FIRST 就是它自身。这个计算用 Python 写非常顺手我实验时就用下面这个脚本快速验证手算的集合对不对# FIRST集迭代计算固定点算法直到所有集合不再变化 def compute_first(grammar, non_terminals, terminals): first {nt: set() for nt in non_terminals} for t in terminals: first[t] {t} changed True while changed: changed False for lhs, rhs_list in grammar.items(): for rhs in rhs_list: for symbol in rhs: before set(first[lhs]) if symbol in terminals: first[lhs].add(symbol) else: first[lhs] | (first[symbol] - {ε}) if ε not in first[symbol]: break else: first[lhs].add(ε) if first[lhs] ! before: changed True return first # 文法用字典表示key是非终结符value是候选产生式的符号元组列表 grammar { E: [(T, E)], E: [(, T, E), (-, T, E), (ε,)], T: [(F, T)], T: [(*, F, T), (/, F, T), (ε,)], F: [((, E, )), (id,)] } first compute_first(grammar, [E, E, T, T, F], [, -, *, /, (, ), id]) for nt, fs in first.items(): print(nt, sorted(fs))这段代码的关键在for...else结构当某个符号的 FIRST 集里不含 ε 时用break跳出内层循环不再往后看如果所有符号都含 ε那么else分支触发把 ε 加入左部。很多人手算时忘记这个“连环空推导”的传递性导致 FIRST 集少算一个终结符。固定点循环的最大好处是你不用在意迭代顺序反正最后一定会收敛——但注意如果某个非终结符的 FIRST 集存在间接左递归依赖这个循环可能会多跑几轮纯属正常。3.2 FOLLOW 集的 ε 连带规则最常见的丢分点FOLLOW 集比 FIRST 集更容易算错因为它的规则涉及“后面跟着什么”和“能不能推出空”的双重判断。规则背熟把#输入串结束符加入开始符号的 FOLLOW对A → α B β把 FIRST(β) 中除 ε 外的符号都加入 FOLLOW(B)如果 β 能推出 ε那么把 FOLLOW(A) 整体加入 FOLLOW(B)。实战中翻车最多的是第三条的传递性。比如算 FOLLOW(E′) 时产生式F → ( E )对 FOLLOW(E) 只增加了右括号但产生式E → T E′中TE′ 的 FIRST 不包含 ε所以这里没有连带可一旦文法里有A → B C且C → ε就会发生“隔着空产生式传 FOLLOW”的情况——FOLLOW(A)会被间接拷贝到FOLLOW(C)里。下面是 FOLLOW 集的参考实现依赖上一步的 FIRST 集合def compute_follow(grammar, non_terminals, terminals, first, start_symbol): follow {nt: set() for nt in non_terminals} follow[start_symbol].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 non_terminals: continue # 计算 rhs[i1:] 的 FIRST去掉ε塞进 FOLLOW[symbol] rest rhs[i1:] for rest_symbol in rest: if rest_symbol in terminals: follow[symbol].add(rest_symbol) break else: before len(follow[symbol]) follow[symbol] | (first[rest_symbol] - {ε}) if len(follow[symbol]) ! before: changed True if ε not in first[rest_symbol]: break else: # rest 全可为空把 FOLLOW[lhs] 并入 FOLLOW[symbol] before len(follow[symbol]) follow[symbol] | follow[lhs] if len(follow[symbol]) ! before: changed True return follow follow compute_follow(grammar, [E, E, T, T, F], [, -, *, /, (, ), id], first, E) for nt, fs in follow.items(): print(nt, sorted(fs))注意这里有个细节第 24 行的else挂在for rest_symbol in rest上含义是“rest 中每个符号的 FIRST 都含 ε”也就是 rest 整体可推出空此时必须把FOLLOW(lhs)传递给你当前处理的这个symbol。这种“隔空传染”的传递依赖是 FOLLOW 集和 FIRST 集计算中唯一的玄学难点一旦漏掉后面预测分析表必然少填若干项。3.3 把两个集合合并验证用可预测的边界串自测算出两个集合后别急着填表。先拿几个已知结果做交叉验证。以E′为例它的 FIRST 集应该是{ , -, ε }FOLLOW 集应该是{ #, ) }——因为 E′ 可能出现在输入串末尾firsh也可能出现在括号表达式内部( E )。F的 FOLLOW 集则是{ , -, *, /, ), # }正好覆盖了所有可能跟在因子后面的符号。如果脚本输出的结果和这个对不上优先检查文法字典里的产生式是不是写错了而不是急着质疑算法。一旦两个集合都算对了预测分析表的每个格子就有了明确依据。这个环节我习惯把脚本输出打印成键值对存好后面写 C 程序的表驱动代码时直接把这些数据抄进二维数组省得临时手算。4. 预测分析表与表驱动主循环从课本伪代码到可运行程序4.1 构造预测分析表 M[A, a] 的三个动作拿到 FIRST 集和 FOLLOW 集后预测分析表的填充逻辑只有三条规则。对每个产生式A → α先取 FIRST(α) 里的终结符 a在M[A, a]写入这个产生式如果 α 能推出 ε那么对 FOLLOW(A) 里的每个终结符 b包括 #在M[A, b]写入该产生式如果某个格子已经被填过说明文法不是 LL1必须回头改文法或检查集合计算。下表是我们这个算术表达式文法的预测分析表样式只截取部分关键格非终结符*()id#E——E→T E′—E→T E′—E′E′→T E′——E′→ε—E′→εT——T→F T′—T→F T′—T′T′→εT′→*F T′—T′→ε—T′→εF——F→(E)—F→id—注意 E′ 行在)和#下都是 ε 产生式这正是由 FOLLOW(E′) { #, ) }决定的。这个细节也是验证集合计算对不对的最直观窗口。表里所有空格代表“语法错误”——输入串走到这一步就该报错了。4.2 驱动主循环符号栈、输入串、动作记录的维护表驱动分析器的核心就是一个 while 循环循环不变式是栈里装着待匹配的符号序列从栈底到栈顶输入缓冲里装着剩下的终结符串末尾带 #。每次迭代看栈顶 X 和当前输入符号 a如果 X 是终结符或 #必须和 a 相同否则报错相同就弹出 X输入指针后移。如果 X 是非终结符查表M[X][a]取出产生式X → Y1Y2...Yk弹出 X把右部逆序压栈最后面的产生式符号最先被匹配。如果M[X][a]为空直接判定语法错误。我用 C 写实验主体时把符号编成整数常量表格存成二维数组。为了让实验报告能呈现完整的分析过程我还加了一个动作序列数组记录每一步做了什么操作#include stdio.h #include string.h #include ctype.h #define MAX_STACK 100 #define MAX_INPUT 100 // 符号编号0#, 1id, 2, 3-, 4*, 5/, 6(, 7), 8E, 9E, 10T, 11T, 12F // 预测分析表行为非终结符编号-8列为终结符编号 int table[5][8] { // # id - * / ( ) { 0, 8, 0, 0, 0, 0, 8, 0 }, // E { 9, 0, 10, 11, 0, 0, 0, 9 }, // E { 0, 12, 0, 0, 0, 0, 12, 0 }, // T { 0, 0, 13, 13, 14, 15, 0, 13 }, // T { 0, 16, 0, 0, 0, 0, 17, 0 }, // F }; // 产生式编号对照 // 8: E-T E 9: E-ε 10: E-T E 11: E--T E // 12: T-F T 13: T-ε 14: T-*F T 15: T-/F T // 16: F-id 17: F-( E ) int stack[MAX_STACK]; int top 0; char input[MAX_INPUT]; void push(int sym) { stack[top] sym; } int main() { // 输入串例子idid*id printf(输入文法句子id - * / 括号以#结束: ); scanf(%s, input); int len strlen(input); // 初始化栈底 #接着压入开始符号 E push(0); // # push(8); // E int ip 0; // 输入指针指向当前待匹配终结符 printf(步骤\t符号栈\t\t输入串\t\t动作\n); int step 1; while (1) { // 打印当前状态 printf(%d\t, step); for (int i top - 1; i 0; i--) { printf(%d, stack[i]); } printf(\t\t%s\n, input ip); int X stack[top - 1]; // 栈顶 int a input[ip] # ? 0 : 1; // 简化为id1其余终结符未细分 // 这里应完善把字符映射为终结符编号再查表 break; // 见下方说明 } return 0; }上面这份 C 代码在字符映射处做了省略因为完整映射会让篇幅翻倍。常见做法是写一个get_symbol(char c)函数把 # 映射为 0id 映射为 1 映射为 2以此类推然后用table[X - 8][a]查表。拿到产生式编号后先执行弹出再按右部长度逆序压栈。这个“逆序压栈”是新手最容易写反的地方先压右部最后一个符号最后压第一个才能保证栈顶是第一个待展开的符号。主循环的终止条件有两个一是栈顶和输入都是 #匹配成功二是某个格子查表为空报错并记录错误位置。实验报告里需要完整打印每一步的符号栈、剩余输入串、当前动作这样老师一眼就能看出你是真跑通了还是只做了个假输出。4.3 实验报告需要的过程数据分析栈每一步都留下证据很多学生写的实验报告只有最终一句话“匹配成功”这在编译原理实验里几乎等于没做。老师要看到的是对输入串idid*id分析器每一步栈里是什么、输入串还剩什么、查表命中了哪条产生式。建议在代码里把每个步骤输出成步骤 / 栈内容 / 输入串 / 动作四列能对应课本上的手工推导过程。另外至少测三个串合法的简单串id、多层嵌套(idid)*id、非法串idid——最后一个必须明确报错这样才证明错误处理分支是真的存在的。如果连非法输入都能“成功匹配”百分之百是查表逻辑有洞。我当初做这个实验时顺手把每一步的栈深度变化画了一条折线发现合法串的栈深度会先上升再下降非法串的栈深度则可能在中途卡死或越走越长。这个观察不一定写进报告但用来判断实现是否正确非常有效。5. LL1 实验的四个翻车点踩坑记录与前置排查5.1 翻车一左递归没有消干净栈在语法分析器里越推越长现象输入串明明是合法的idid程序跑了几百个步骤还没结束栈越来越大最后爆栈退出。原因你用了原始的E → ET每展开一次 E 就多压一层T E栈只增不减。解决回到文法改造环节确认所有非终结符都没有直接或间接左递归。排查技巧是在调试模式打印“栈顶符号在整个分析过程中出现的次数”如果某个非终结符被压栈超过输入串长度基本就是左递归残留。5.2 翻车二FOLLOW 集漏了 ε空产生式“断链”现象输入串id单独一个因子时分析到 T′ 后本应走 ε 产生式把 T′ 弹出程序却报“查表失败”。原因FOLLOW(T′) 里漏了#或右括号导致M[T′, #]是空格ε 产生式填不进去。拿到 FIRST 和 FOLLOW 后先打印出来和教材对比。FOLLOW(T′) 应当是{ , -, *, /, ), # }如果少了 #检查是不是算 FOLLOW(E′) 时忘了把 FOLLOW(E) 传递下去——因为F → ( E )让 FOLLOW(E) 有了)但 E′ 的 FOLLOW 依赖E → T E′的尾符号 E′ 可空进而把 FOLLOW(E) 拷给了 E′这个连锁反应最容易漏。5.3 翻车三程序只会打印“匹配成功”追溯性为零现象代码调通了输入输出都对但实验报告不知道写什么因为程序运行只有一句话。原因没有设计过程日志。解决在主循环里维护一个action变量记录每一步是“匹配终结符”“应用产生式 X→α”还是“接受完成”。打印格式参考 4.2 节的表格。如果已经写完了代码补丁思路也很简单在循环开头加一条printf把栈内容和剩余输入串打出来就行不用大改逻辑。5.4 翻车四文法看似 LL1一查冲突表立刻现原形现象手算预测分析表时发现某个格子有两种产生式程序里只能任选其一导致同一个输入串有时匹配成功有时失败。原因文法实际上不是 LL1可能是提取左因子不彻底。解决写一小段代码遍历所有非终结符对每个终结符检查M[A][a]是否被填了两次以上一旦冲突立刻输出冲突的产生式对。这个检测代码建议写在主程序开头每次运行时自动检查。课堂上的血泪经验是这种冲突绝大多数出现在“悬挂 else”类文法里——两个候选有相同公共前缀提取左因子时只提了一半。5.5 排查顺序先看文法再看表最后才怀疑代码遇到 Bug 不要上来就盯着 C 代码看半天。排查顺序应该是先人工判断文法是不是真的 LL1再验证 FIRST 集和 FOLLOW 集的脚本输出然后打印预测分析表看每个非终结符对应的列有没有空格异常。表格是对的但程序不对再查查表和栈操作逻辑。我见过有人调试三小时最后发现是产生式编号写反——右部逆序压栈时压成了正序纯属小失误但如果没有过程日志这种错非常难定位。6. 最后一步给分析表加 LL1 自检开关一晚肝完不返工6.1 把合法性自检写进主程序启动阶段在分析器启动时自动检查两点一是每个非终结符-终结符格子是否有冲突二是每个非终结符是否至少有一个可用的产生式。这个自检代码就十几行却能在你换测试文法时帮你挡住一大半低级错误。我习惯在 C 程序入口加一个validate_table()函数它遍历整个表发现table[i][j] ! 0 table[i][j] previous就报错退出避免带着错误的文法一路跑到底。有了这个开关后面换更复杂的文法做实验时不用每次手工核对整张表。6.2 用最小测试集说清“能跑”和“真对”自检通过后固定跑一组最小测试用例。必测id单个因子、idid*id运算符优先级、(idid)*id括号嵌套、idid预期报错、(id括号不匹配预期报错。前三个必须完整输出推导步骤后两个必须给出错误位置和预期符号集合。你的程序如果能做到这一点说明 LL1 分析表的每一行每一列都在正确工作——而不仅仅是碰巧能跑通一个样例。6.3 一句经验收尾做完这个实验最大的体会是LL1 分析法真正的难度不在写代码而在“把文法改造成 LL1 格式”和“把两个集合算对”这两个前置步骤上后者一旦出错后面的一切都是白费。我的习惯是任何时候先用脚本验证数据和集合再写主程序这就好比先量好尺寸再下料能省掉大半返工时间。希望帮到你。本文还有配套的精品资源点击获取