简介这是山东科技大学2022年编译原理课程实验的配套实现聚焦LL(1)语法分析法的完整落地。实验基于经典表达式文法含E→TG、T→FM及ε产生式覆盖FIRST集、FOLLOW集求解、预测分析表构造与驱动程序执行等环节代码可在Code::Blocks中直接运行适合编译原理学习者完成课设或理解自顶向下无回溯分析。资源以zip压缩包提供大小约1.08MB附带可直接运行的工程文件与完整实验报告用于梳理实验原理、设计思路、核心代码与测试结果。已有914人下载学习实用性经同类课程学习者验证。通过这份资料可获取从文法定义到分析表生成、再对ii*i等输入串执行分析的全套实现既可作为课程设计模板也能对照实验报告逐段理解算法细节加深对预测分析表构造、FIRST/FOLLOW集计算及错误处理等知识点的掌握。1. 编译原理实验里的 LL(1)这份山科大实验代码为什么值得直接跑每年的编译原理实验总有一批人卡在语法分析这一步。LL(1)分析法是自上而下预测分析的入门课但真到写代码时问题从来不在文法本身而在 First 集、Follow 集和那张要命的预测分析表上。这份 22 年山东科技大学编译原理实验的完整代码题目给的是一个已经消过左递归、提过左因子的表达式文法用 LL(1) 分析法对任意输入的符号串进行分析源码在 CodeBlocks 里直接能跑实验报告也齐全。对正在做同样实验、却被 C 语言实现细节卡住的人来说这份资源最大的价值不是让你抄而是让你对着跑通的结果看懂一张预测分析表是怎么从文法里长出来的。适合三类人被实验卡住的学生、想省掉调试时间直接看实现逻辑的人、以及准备复试面试想快速复习 LL(1) 完整流程的人。2. 先把文法看穿为什么这个表达式文法天生适合 LL(1)2.1 文法结构和 LL(1) 的匹配关系题目给出的是一个典型的表达式文法八个产生式覆盖了加减、乘除、括号和变量 iE - TG G - TG | -TG | ε T - FM M - *FM | /FM | ε F - (E) | i先说结论这个文法不需要任何改造就能直接做 LL(1) 分析。原因有三点。第一没有左递归E 的产生式右部开头是 TT 的开头是 FF 的开头是终结符 ( 或 i每个非终结符都不存在 “自己打头” 的情况所以不会死循环。第二公共左因子已经提取干净了G 的两个候选式分别以 和 - 开头M 的两个候选式分别以 * 和 / 开头F 的两个候选式分别以 ( 和 i 开头第一眼就能区分。第三ε 产生式都出现在 G 和 M 上它们是链的末尾节点Follow 集也算得干净。如果你是自己在做实验拿到其他文法时先别急着写代码。第一步永远是这样检查一遍有没有左递归、有没有公共左因子、ε 出现在哪几个非终结符上。这三件事决定了这个文法能不能用 LL(1)决定得越早后面写程序翻车的概率越低。2.2 First 集与 Follow 集的手算全过程LL(1) 分析的底层依赖就是 First 集和 Follow 集。手算一遍的价值在于你后面程序输出的表格对不对完全可以现在就用纸笔验证。First 集计算从产生式左部最底层的 F 开始推。F - (E) | i First(F) { (, i } T - FM First(T) First(F) { (, i } M - *FM | /FM | ε First(M) { *, /, ε } G - TG | -TG | ε First(G) { , -, ε } E - TG First(E) First(T) { (, i }计算 First 的核心规则是对一个产生式右部从左往右扫遇到终结符就收入集合并停止遇到非终结符就收入它的 First 集去掉 ε继续看下一个符号只有右侧所有符号都能推出 ε才把 ε 收入左部的 First。这里 F 不能推出 ε所以 T 的 First 和 F 完全一致不用再往下看。Follow 集计算Follow 的计算比 First 麻烦因为它要从 E 开始符号和产生式右部的位置关系两个方面推导。Follow(E) { $, ) } E 是开始符号所以有 $F - (E) 说明 ) 会跟在 E 后面 Follow(G) Follow(E) { $, ) } Follow(T) First(G) 去掉 ε union Follow(G) { , - } union { $, ) } { , -, $, ) } Follow(M) Follow(T) { , -, $, ) } Follow(F) First(M) 去掉 ε union Follow(T) { *, / } union { , -, $, ) } { *, /, , -, $, ) }计算 Follow 时有个规律值得记死谁后面跟了谁Follow 就往哪里传。M 出现在 T 的产生式右部末尾所以 Follow(M) 至少包含 Follow(T)F 后面跟着 M所以 First(M) 里的 * 和 / 都属于 Follow(F)而 M 可以推出 ε所以 Follow(T) 也得传给 Follow(F)。这里值得手写一遍因为程序里如果按照书上的算法直接翻译很容易漏掉 “右侧非终结符可空时向右传递 Follow” 这种传递关系。2.3 LL(1) 判定条件与常见误判判定一个文法是否 LL(1)对每个非终结符 A 的任意两个候选式 A→α 和 A→β两条规则必须同时满足规则一First(α) ∩ First(β) ∅ 规则二如果 α 或 β 可以推出 ε 则 First(另一个) ∩ Follow(A) ∅拿题目验证G 的两个候选式是 TG 和 εFirst(TG){}而 Follow(G){$,)}交集为空规则二成立。M 同理First(FM){}Follow(M){,-,$,)}不冲突。其余非终结符的候选式首符合法分集天然满足。这里要特别提醒一个常见的误判有人会把 First(G) 里的 ε 当作终结符参与求交集。ε 不属于任何终结符集合它在判定规则里的角色是 “触发器”不是成员。如果把 ε 写进 First(G) 的集合里去和 Follow(G) 求交集判断会全乱。3. 程序的骨架三张表加一个栈LL(1) 分析器的标准结构3.1 程序里的三张核心表拿到代码打开 .c 文件你首先会看到一堆全局数组。整个 LL(1) 分析程序本质上就是三张表加一个栈终结符表和非终结符表定义所有符号终结符里一定要含结束符 #。First 表与 Follow 表记录每个非终结符的集合填预测分析表时要用。预测分析表 table[M][N]行是非终结符列是终结符含 #单元格存产生式编号-1 表示出错。典型的数据结构定义长这样#define MAXN 100 char terminal[] {i, , -, *, /, (, ), #, \0}; char non_terminal[] {E, G, T, M, F, \0}; char first[5][10]; // 每个非终结符的First集合 char follow[5][10]; // 每个非终结符的Follow集合 int table[5][8]; // 预测分析表5行对应5个非终结符8列对应8个终结符 int stack[MAXN]; // 分析栈 int top;table 的行列映射不是随心所欲的它决定了后面查表代码的简洁程度。常见做法是提前写两个查下标函数遍历 non_terminal 和 terminal 数组返回符号对应的行号和列号。我在自己写的版本里会把下标查询单独封装因为主循环里查表次数太多每次都手写 for 循环既容易错又不方便改符号集合。3.2 分析栈、输入串、步骤表下推自动机的一次完整推导LL(1) 分析器的运行机制是一个下推自动机。初始化时栈底压入 #再压入开始符号 E。输入串以 # 结尾。每次循环看栈顶和输入串当前符号分三种情况栈顶是终结符则匹配输入栈顶是非终结符则查预测分析表拿到产生式并逆序压栈如果查不到就报错。拿输入串 ii*i# 手动走一遍全流程你会发现程序输出的那张步骤表就是这个过程步骤栈底→顶剩余输入动作1#Eii*i#E→TG2#GTii*i#T→FM3#GFMii*i#F→i4#GMi*i#匹配 i5#GTi*i#G→TG6#GT…匹配 继续处理后面部分完整推导会一直进行到栈里只剩 #输入也只剩 #分析成功。如果中途某一步栈顶非终结符查表得到 -1或者栈顶终结符和输入不匹配就直接判定输入串非法。这段推导手工走一遍后面测试程序输出时就能一眼看出哪一步错了。3.3 CodeBlocks 里从打开到跑起来这份代码是为 CodeBlocks 准备的打开方式没有什么玄机新建一个 Console 项目把 main.c 拖进去或者直接 File → Open 打开已有文件按 F9 构建并运行。程序运行时唯一要交互的地方是输入符号串。注意两点第一输入串要用 # 结尾比如 ii*i#第二不要加空格如果敲成 “i i * i #” 这种形式scanf 会在第一个空格处截断程序只拿到一个 i。常见的做法是在 main 函数入口加一句提示明确说明 “请输入以 # 结尾的表达式不要加空格”。读入用 scanf(%s, input) 就够输入串长度不会超过 100。4. 读懂核心代码First 计算、填表、主循环的执行逻辑4.1 First 集计算的循环不动点写法程序里 First 集不是只算一遍而是反复扫描所有产生式直到一轮扫描结束集合没有任何变化才停。这就是计算闭包的典型写法——不动点迭代。int changed 1; while (changed) { changed 0; for (int i 0; i prod_cnt; i) { if (add_first(prods[i].left, prods[i].right)) { changed 1; } } }add_first 函数负责根据一条产生式更新左部的 First 集返回 1 表示发生了新增。这个函数的内部逻辑是关键从左到右扫描右部符号第一个终结符直接加入遇到非终结符 X就把 First(X) 里除 ε 以外的符号全部加入如果 ε 不在 First(X) 里就停止扫描如果扫描完整个右部都能推出 ε左部的 First 也要加 ε。这个不动点循环有个非常隐蔽的问题如果 add_first 每次把已存在的符号又重复添加一遍changed 永远为 1程序就死循环了。所以 add_first 内部必须做实打实的 “集合添加”逻辑——先判断符号是否已经在集合里再决定是否新增。我自己调试时习惯在这个 while 循环的每轮末尾打印一遍所有 First 集肉眼看到集合两轮不再变化心里才踏实。4.2 预测分析表的填表规则预测分析表的填表规则说起来只有两句话对每个产生式 A→α把产生式编号填入 First(α) 中的每个终结符对应的列如果 α 能推出 ε再把编号填入 Follow(A) 中的每个终结符对应的列。for (int i 0; i prod_cnt; i) { char A prods[i].left; for (int j 0; j first_set_count; j) { char a first_symbols[i][j]; // First(α) 里的终结符 if (a ! ε) { table[row(A)][col(a)] i; } } if (can_derive_epsilon(prods[i].right)) { for (int j 0; j follow_count(row(A)); j) { char b follow[row(A)][j]; // Follow(A) 里的终结符 table[row(A)][col(b)] i; } } }填表时最容易犯错的位置是第二段循环。拿 G→ε 来说First(ε) 里没有任何终结符第一段循环什么都不做第二段循环要把该产生式填入 Follow(G) 的每一列也就是 $ 和 ) 对应的格子。如果你填表时漏了 # 列符号映射后面分析 ii# 时正好走到栈顶 G、输入 # 的情况一查表发现没有产生式就直接报错了。还有一点table 初始化时要把所有格子置为 -1不然读到未初始化的随机数分析结果全看运气。4.3 分析主循环三种情况的分流主循环是整个程序的发动机代码逻辑非常固定。一句话说清楚循环体里只看栈顶符号 X 和输入符号 a 的组合然后分三类处理。while (stack_top 0) { char X stack[stack_top]; char a input[input_pos]; if (X # a #) { // 栈空且输入读完成功 printf(Accept!\n); return 1; } if (is_terminal(X)) { // 栈顶是终结符 if (X a) { stack_pop(); input_pos; } else { printf(Error: terminal mismatch\n); return 0; } } else { // 栈顶是非终结符 int prod table[row(X)][col(a)]; if (prod 0) { printf(Error: no production\n); return 0; } stack_pop(); push_production(prod); // 逆序压栈 print_step(X, prods[prod], a); // 记录步骤 } }push_production 是逆序压栈产生式右部从左到右的符号从右往左依次压栈。比如 E→TG 弹出 E 后先压 G 再压 T压完栈顶是 T。为什么要逆序因为栈是后进先出为了让左部第一个符号最先被处理。这个细节如果写反了分析过程看起来就是另一条完全不同的推导了而且永远对不上输入串。另一个值得注意的细节是当产生式右部只有 ε 时push_production 里不应该压入任何东西。有些同学的代码会把 “ε” 字符串误当成符号压栈导致输入永远匹配不上这就是下一章要展开讲的坑。5. 避坑与常见问题排查LL(1) 实验翻车的五个现场5.1 查表返回 -1程序直接崩溃报段错误现象输入串 ii#程序跑到某一步突然跳出 Error或者干脆直接崩溃。有些人自己分析这串是完全合法的怎么程序不认原因预测分析表里$ 或 # 对应的列没有正确填入 ε 产生式。以 ii# 为例处理完 之后栈顶是 G输入串当前是 #。查表发现 table[G][#] -1程序认为语法错误。但你手写计算时 Follow(G) 明明包含 # 对应的 $填表循环却没执行到。解决检查 fill_table 的第二个循环确认产生式 G→ε 的编号被正确写入了 Follow(G) 中的所有列——包括 # 列。另外检查终结符数组里是否包含 ‘#’以及 col(‘#’) 是否返回了正确下标。常见的低级错误是把列号提前 return 成 0结果所有 ε 产生式全填到 i 那一列去了。5.2 ε 被当成终结符压进栈程序陷入死循环现象程序跑起来能匹配几个符号然后卡住不动或者疯狂输出步骤表停不下来任务管理器里 CPU 拉满。手动观察步骤表发现中间出现了一段重复的循环。原因push_production 在处理 ε 产生式时压入了表示 ε 的符号。这个 “ε” 既不是终结符也不是非终结符查表匹配永远失败程序就在栈顶反复弹出、压入同一个 ε 符号形成死循环。输入串永远等到一个永远不会出现的 ε 字符。解决产生式右部的 ε 应该用空表示处理方式只有一句话——弹出栈顶什么都不压也不读输入。我在代码里会用专门判断 if (prods[prod].right_len 0) 跳过压栈逻辑。检查你的代码里有没有把 “ε” 放进任何数组、任何字符串比较。符号集合里不应该有它。5.3 CodeBlocks 里中文注释乱码编译却通过了现象代码打开后注释全是乱码类似 “鏈嶅姟” 这种但按 F9 居然能编译运行。有些同学担心是文件损坏重新下载还是一样。原因源文件是 GBK 编码或 UTF-8 编码而 CodeBlocks 的编辑器默认编码不匹配。乱码出现在注释里不影响编译因为 C 编译器会把注释整体丢弃gcc 根本不解析注释内容。解决如果你觉得乱码碍眼可以在 CodeBlocks 菜单 Settings → Editor → General Settings 里把编码改成 UTF-8或者直接全选注释删掉重写。我不建议把源文件重新转码保存回 ANSI因为 Windows 下记事本另存 UTF-8 会带 BOM 头gcc 可能报 “stray ‘\357’ in program” 的错误反而把原本能跑的文件搞坏。能跑就别动乱码不影响实验报告。5.4 输入带空格scanf 截断导致分析结果永远是错的现象运行时提示输入字符串你按题目习惯输入了 “i i * i #” 这种带空格的形式结果程序只分析了 i 就报错或者整个程序直接按非法串处理。原因scanf(“%s”, input) 遇到空格、换行、Tab 都会截断读取所以它实际读到的只有一个 “i”。栈里的 E 匹配完 F→i 之后下一个符号是 但输入串已经是 # 了必然报错。这不是 LL(1) 的问题是 C 语言基础输入的问题。解决交互时输入不带空格的串ii*i# 这种格式就对了。如果在做实验时希望程序更健壮可以在读入之后写一个小循环把空格全部滤掉。我一般会加清除输入缓冲区的处理否则第二次 scanf 可能会读到残留的换行符。如果实验报告要求展示多种输入记住回车前检查一遍字符串里有没有空格。5.5 First 集循环永远不收敛程序死循环现象程序在初始化阶段也就是还没出现任何输入提示时就卡死或运行超时。用调试器打断发现线程停在 while(changed) 这个循环里。原因add_first 函数没有做重复判断就直接把符号塞进集合。比如遇到两个产生式都要往 T 的 First 里加 (每次扫描 changed 都会从 0 变 1循环永远无法收敛。这个 bug 的隐蔽之处在于文法产生式再多一点时情况更复杂重复可能体现在 “A 加了一个符号下一轮 B 又把它传给 A” 这种间接重复上。解决add_first 里先检查目标符号是否已在集合中不在才加入或者用整型布尔数组做集合标记而不是用字符串拼接。快速验证方法是把 while 循环最大迭代次数限制到 20 次超过就打印所有集合并中断——但这是排查手段最后还是要修好 add_first。从那以后我每次写 First 集不动点循环都习惯性把迭代计数变量打出来看一眼。6. 用六条输入串验证程序边界判断分析器是否可靠的最后一步程序能跑不代表正确代码里任何一处填表错误都可能让部分合法串被误判。我的习惯是准备一个测试集覆盖正常情况、嵌套括号、除法、连续运算符错误和缺少操作数错误这几类场景。输入串预期结果覆盖点ii*i#接受最基本的加减乘除混合i*(ii)#接受括号内嵌表达式i/i-i#接受左结合除法((i))#接受多层嵌套括号ii*#拒绝乘法后缺少操作数i**i#拒绝连续两个运算符跑完这六组数据对照程序输出的步骤表基本能判断分析器实现是否可靠。如果想验证更多可以再构造非法串 i(/i# 之类的好配合场景。提交实验报告时我用这六条串的截图老师没有追问过。验证之外还有一个更有价值的玩法故意改文法让程序冲突。你把 M→*FM|/FM 改成 M→*FM|*i再运行程序看它检测到的 First 集冲突。你会发现 First(*FM) 和 First(*i) 交集中都有 *程序在构造预测分析表时会往 table 同一格写了两个产生式。这一瞬间你会对 “文法不是 LL(1)” 有直观理解——它不是抽象概念就是预测分析表里那个格子装不下了。我用这套流程跑完这个实验后养成了一个习惯拿到别人的 LL(1) 代码先手算出 First 和 Follow再对照程序输出的表格最后故意喂一条错误输入确认程序不会死循环才敢提交。这一套走下来实验报告里的截图基本凑齐原理也顺便复习了一遍。希望帮到你。本文还有配套的精品资源点击获取