企业官网建设流程全解析

简介：这是山东科技大学2022年编译原理课程实验的配套实现，聚焦LL(1)语法分析法的完整落地。实验基于经典表达式文法（含E→TG、T→FM及ε产生式），覆盖FIRST集、FOLLOW集求解、预测分析表构造与驱动程序执行等环节，代码可在Code::Blocks中直接运行，适合编译原理学习者完成课设或理解自顶向下无回溯分析。资源以zip压缩包提供，大小约1.08MB，附带可直接运行的工程文件与完整实验报告，用于梳理实验原理、设计思路、核心代码与测试结果。已有914人下载学习，实用性经同类课程学习者验证。通过这份资料可获取从文法定义到分析表生成、再对i+i*i等输入串执行分析的全套实现，既可作为课程设计模板，也能对照实验报告逐段理解算法细节，加深对预测分析表构造、FIRST/FOLLOW集计算及错误处理等知识点的掌握。

1. 编译原理实验里的 LL(1)：这份山科大实验代码为什么值得直接跑

每年的编译原理实验，总有一批人卡在语法分析这一步。LL(1)分析法是自上而下预测分析的入门课，但真到写代码时，问题从来不在文法本身，而在 First 集、Follow 集和那张要命的预测分析表上。这份 22 年山东科技大学编译原理实验的完整代码，题目给的是一个已经消过左递归、提过左因子的表达式文法，用 LL(1) 分析法对任意输入的符号串进行分析，源码在 CodeBlocks 里直接能跑，实验报告也齐全。对正在做同样实验、却被 C 语言实现细节卡住的人来说，这份资源最大的价值不是让你抄，而是让你对着跑通的结果，看懂一张预测分析表是怎么从文法里长出来的。适合三类人：被实验卡住的学生、想省掉调试时间直接看实现逻辑的人、以及准备复试面试想快速复习 LL(1) 完整流程的人。

2. 先把文法看穿：为什么这个表达式文法天生适合 LL(1)

2.1 文法结构和 LL(1) 的匹配关系

题目给出的是一个典型的表达式文法，八个产生式覆盖了加减、乘除、括号和变量 i：

E -> TG G -> +TG | -TG | ε T -> FM M -> *FM | /FM | ε F -> (E) | i

先说结论：这个文法不需要任何改造就能直接做 LL(1) 分析。原因有三点。第一，没有左递归，E 的产生式右部开头是 T，T 的开头是 F，F 的开头是终结符 ( 或 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。输入串以 # 结尾。每次循环看栈顶和输入串当前符号，分三种情况：栈顶是终结符则匹配输入；栈顶是非终结符则查预测分析表拿到产生式并逆序压栈；如果查不到就报错。

拿输入串 i+i*i# 手动走一遍全流程，你会发现程序输出的那张步骤表就是这个过程：

完整推导会一直进行到栈里只剩 #，输入也只剩 #，分析成功。如果中途某一步栈顶非终结符查表得到 -1，或者栈顶终结符和输入不匹配，就直接判定输入串非法。这段推导手工走一遍，后面测试程序输出时就能一眼看出哪一步错了。

3.3 CodeBlocks 里从打开到跑起来

这份代码是为 CodeBlocks 准备的，打开方式没有什么玄机：新建一个 Console 项目，把 main.c 拖进去，或者直接 File → Open 打开已有文件，按 F9 构建并运行。

程序运行时唯一要交互的地方是输入符号串。注意两点：第一，输入串要用 # 结尾，比如 i+i*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) 的每一列，也就是 $ 和 ) 对应的格子。如果你填表时漏了 # 列符号映射，后面分析 i+i# 时正好走到栈顶 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，程序直接崩溃报段错误

现象：输入串 i+i#，程序跑到某一步突然跳出 Error，或者干脆直接崩溃。有些人自己分析这串是完全合法的，怎么程序不认？

原因：预测分析表里，$ 或 # 对应的列没有正确填入 ε 产生式。以 i+i# 为例，处理完 + 之后栈顶是 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 语言基础输入的问题。

解决：交互时输入不带空格的串，i+i*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. 用六条输入串验证程序边界：判断分析器是否可靠的最后一步

程序能跑不代表正确，代码里任何一处填表错误都可能让部分合法串被误判。我的习惯是准备一个测试集，覆盖正常情况、嵌套括号、除法、连续运算符错误和缺少操作数错误这几类场景。

跑完这六组数据，对照程序输出的步骤表，基本能判断分析器实现是否可靠。如果想验证更多，可以再构造非法串 i(/i# 之类的好配合场景。提交实验报告时我用这六条串的截图，老师没有追问过。

验证之外还有一个更有价值的玩法：故意改文法让程序冲突。你把 M→*FM|/FM 改成 M→*FM|*i，再运行程序，看它检测到的 First 集冲突。你会发现 First(*FM) 和 First(*i) 交集中都有 *，程序在构造预测分析表时会往 table 同一格写了两个产生式。这一瞬间你会对 “文法不是 LL(1)” 有直观理解——它不是抽象概念，就是预测分析表里那个格子装不下了。

我用这套流程跑完这个实验后，养成了一个习惯：拿到别人的 LL(1) 代码，先手算出 First 和 Follow，再对照程序输出的表格，最后故意喂一条错误输入，确认程序不会死循环才敢提交。这一套走下来，实验报告里的截图基本凑齐，原理也顺便复习了一遍。希望帮到你。

本文还有配套的精品资源，点击获取