企业官网建设流程全解析

简介：面向编译原理课程实验的学习者，这份文档围绕语法分析程序的设计与实现展开，可配合实验一所得单词序列完成语法检查与结构分析。内容以算术表达式简化子集为对象，给出 BNF 定义及 LL(1) 文法改写，讲解预测分析表的构造与使用，并附 C++ 实现的源程序框架，涉及分析栈、剩余串、产生式结构体以及 RIGHT/ERROR 输出等关键环节。文档还梳理实验目的、基本要求、流程图与数据结构考虑、词法与语法分析合并调试、正例与错例测试等，便于读者理解自上而下语法分析的完整链路，也可作为课程实验报告与程序调试的参考。资源包共 1 个 doc 文件，约 127KB，轻量便携，适合直接查阅与打印。已有 143 人学习，适合需要补足 LL(1) 分析表、递归下降或算符优先等分析方法实践的高校学生与自学者。

1. 从词法输出到语法判定：这套语法分析程序到底要交出什么

语法分析程序设计与实现这道题，很多人写完词法分析器就松懈了——扫描器能把i+i*i切成一串UCON, PL, UCON, MU, ID就觉得大功告成，真正卡住的是下一步：给这串单词一个结构上的说法。这个实验要的东西很具体：给定文法 G2[E]，读入上游扫描器吐出的单词序列，判断它是不是该文法的句子，是就输出 RIGHT 并逐行打印分析栈、剩余串和所用产生式；不是就输出 ERROR，同时把出错位置、当时的栈内容和缺失符号讲清楚。互联网上能搜到的同类代码大多把分析表写死在 main 里、错一个字符就整段退出，交上去能跑，答辩一问就露馅。这套方案适合正在做编译原理课设、需要一份能演示、能讲清推导过程、还能顺手接上实验一扫描器的完整实现。

2. 文法改造：从带左递归的 G2[E] 到可以查表的 LL(1)

2.1 为什么先做左递归消除，而不是直接写递归下降

题目给的原始文法是左递归的：

E → T | E+T | E-T T → F | T*F | T/F F → i | (E)

E → E+T这种形式，如果直接照抄成递归下降函数E() { E(); match('+'); T(); }，第一次调用就自己调自己，栈帧一路压到爆，程序直接崩。这是编译原理实验里最经典的一课：文法好看不等于能直接实现。消除直接左递归的标准做法是把A → Aα | β拆成两个非终结符：

A → βA' A' → αA' | ε

套到 E 和 T 上，再引入两个新非终结符 G（管加减）和 S（管乘除），得到改写后的 LL(1) 文法：

这里有个容易忽略的设计取舍：为什么选 LL(1)，而不是算符优先、SLR(1) 或 LR(1)。算符优先表要单独算优先关系，遇到一元负号和括号嵌套时优先关系容易冲突出错；SLR(1) 和 LR(1) 要做项目集规范族、构造 DFA，工作量比这个实验的定位大得多，一个课设周期内很难做扎实；递归下降写起来最直观，但左递归要手工消、错误定位全靠异常抛出，答辩时讲不清「第几步用了哪条产生式」。LL(1) 的产出是三张能手工推导、能当场合对的表——FIRST 集、FOLLOW 集、预测分析表，每一步分析都能打印出来，这对需要现场演示的实验来说是最优解。

改写之后还要确认一件事：新文法确实是 LL(1) 的。判定标准是对同一个非终结符的任意两条候选产生式 α、β，满足FIRST(α) ∩ FIRST(β) = ∅，并且如果 β 能推出 ε，还要满足FIRST(α) ∩ FOLLOW(A) = ∅。拿 G 来看，+TG的 FIRST 是{+}，-TG的 FIRST 是{-}，ε的 FIRST 是空集，三者互不相交；再看 S，*FS是{*}、/FS是{/}，也互不相交。这一步核过，后面填表才不会出现一格两个产生式的冲突。

2.2 提取左公因子与空产生式的书写约定

标准流程里消除左递归之后通常还要提取左公因子，但这份文法不需要。判断依据看 F：F → i和F → (E)，两个候选右部的首符号分别是i和(，交集为空，公共前缀长度为零，没有可提的东西。如果文法写成F → i | i(E)，那就必须提成F → i F'、F' → (E) | ε，否则查表时F遇到i不知道该选哪条。实验报告里把这段判断写出来，比只贴一张表更能说明你真的想过。

空产生式的书写是个小设计点。教材上写 ε，但代码里用单字符栈存符号，直接写希腊字母会带来编码和比较的麻烦。通常的做法是用^代替 ε，占一个 char 位，压栈时有特殊判断——遇到^就不压。原文代码里用的就是这个约定，g2.array[0]='^'、g2.length=1，把空产生式也当成一条长度为 1 的正常产生式来存，结构统一，只在压栈那一刻特判。

注意：^只能出现在产生式右部、且只能单独出现。如果哪条产生式写成S → ^FS，那不是 ε，是把^当成了一个普通终结符，查表时永远匹配不上，分析会卡死在这一格。

2.3 FIRST 与 FOLLOW 集：先手算再写进代码

很多人图省事，直接从网上抄一张分析表塞进程序，跑通了就交。这种做法的风险是：只要文法改一个符号，整张表就全错，而且你没法解释表里的每一项为什么在那儿。可靠的做法是先把 FIRST 和 FOLLOW 手推一遍，写在实验报告里，代码里的表只是这份手算结果的转录。

推导顺序建议按依赖关系走：先 FIRST，从最底层的 F 往上算，F 的 FIRST 是{i, (}，T → FS 的 FIRST 等于 FIRST(F)，E → TG 的 FIRST 等于 FIRST(T)，所以 E、T、F 三个的首符集完全一样。G 和 S 因为有 ε 产生式，FIRST 里要带上 ε。

FOLLOW 的推法反过来，从开始符号 E 往下传。E 是开始符号，先塞一个#；E → TG 说明 FOLLOW(G) 包含 FOLLOW(E)，所以 G 拿到#；G → +TG 说明 T 后面紧跟 G，FOLLOW(T) 包含 FIRST(G) 去掉 ε 的部分，即{+, -}，同时因为 G 能推出 ε，FOLLOW(T) 还要并入 FOLLOW(G)，于是 T 的 FOLLOW 变成{+, -, #}。用同样的传递关系往下推，S 从 T → FS 拿到 FOLLOW(T)，F 从 T → FS 和 S → *FS 拿到{*, /}再并上 FOLLOW(S)。

推完之后有一项自检特别好用：每一个非终结符的 FOLLOW 集大小应该只增不减，而且#必须出现在 E、G、T、S、F 全部五个里（因为整条文法的所有非终结符最终都可能走到串尾）。如果算完发现 F 的 FOLLOW 里没有#，那一定是某一步传递漏了。

3. 数据结构与分析表：把文法固化进一个 5×8 的二维表

3.1 终结符表、非终结符表与产生式结构体

LL(1) 分析程序的核心数据结构只有四个：终结符集合、非终结符集合、产生式数组、预测分析表。终结符集合决定了分析表的列，非终结符集合决定了行，两边顺序一旦定死就不能再动——这是后面所有查表逻辑的基准。

终结符按i + - * / ( ) #排，下标 0 到 7；非终结符按E G T S F排，下标 0 到 4。这里要注意一个反直觉的地方：非终结符的顺序不是按 E、T、F 的语法层级排，而是按改写后的产生式出现顺序 E、G、T、S、F。如果按E T F排，后面填表和查表用的行号就对不上，症状是程序能跑但判定结果和手推不一致，排查起来非常费时间。

产生式用结构体存，左部一个字符、右部一个字符数组、长度一个整数：

// 产生式：右部最多 3 个符号，'^' 表示 ε struct Prod { char lhs; // 左部非终结符，取值 E/G/T/S/F char rhs[4]; // 右部符号串，以 '\0' 结尾 int len; // 右部符号个数，ε 产生式记 1 }; // 10 条产生式，下标即编号，与分析表里的值一一对应 Prod P[10] = { {'E', "TG", 2}, // 0: E -> TG {'G', "+TG", 3}, // 1: G -> +TG {'G', "-TG", 3}, // 2: G -> -TG {'G', "^", 1}, // 3: G -> ε {'T', "FS", 2}, // 4: T -> FS {'S', "*FS", 3}, // 5: S -> *FS {'S', "/FS", 3}, // 6: S -> /FS {'S', "^", 1}, // 7: S -> ε {'F', "(E)", 3}, // 8: F -> (E) {'F', "i", 1} // 9: F -> i };

这样设计的直接好处是：分析表里只需要存产生式的编号（一个 int），打印时用P[id].lhs和P[id].rhs拼字符串，不用在每个表项里重复存一份右部。原文代码把type对象直接塞进C[10][10]，每个格子都是一个完整的结构体副本，内存浪费是小事，关键是填表代码变成了C[0][0]=e; C[1][1]=g;这种一个字母一个字母的赋值，改一条产生式要改好几处，非常容易错位。

3.2 预测分析表的填充规则与空项语义

分析表是 5 行 8 列的二维数组，行对应非终结符，列对应当前输入符号。填充规则来自 FIRST 和 FOLLOW：对产生式A → α，凡a ∈ FIRST(α)，就把M[A][a]填成这条产生式的编号；如果 α 能推出 ε，则凡b ∈ FOLLOW(A)，也把M[A][b]填成这条产生式。剩下没被覆盖的格子是空项，表示「此处无产生式可用」，也就是语法错误的位置。

// 行序 E G T S F，列序 i + - * / ( ) #，值 -1 表示空项 int M[5][8]; void initTable() { for (int i = 0; i < 5; ++i) for (int j = 0; j < 8; ++j) M[i][j] = -1; // 先全部置空 // E: FIRST(TG) = { i, ( } M[0][0] = 0; M[0][5] = 0; // G: 遇 + 走 1，遇 - 走 2；遇 ) 和 # 走 ε（FOLLOW(G) = { ), # }） M[1][1] = 1; M[1][2] = 2; M[1][6] = 3; M[1][7] = 3; // T: FIRST(FS) = { i, ( } M[2][0] = 4; M[2][5] = 4; // S: 遇 * 走 5，遇 / 走 6；遇 + - ) # 走 ε M[3][1] = 7; M[3][2] = 7; M[3][3] = 5; M[3][4] = 6; M[3][6] = 7; M[3][7] = 7; // F: 遇 i 走 9，遇 ( 走 8 M[4][0] = 9; M[4][5] = 8; }

对着这张表可以核对几个关键格子，验证理解是否正确。M[1][6]（G 遇到右括号）填 3，意思是「括号里加减链到此结束，用 ε 收尾」，这正是(i+i)能分析成功的原因。M[3][3]（S 遇到乘号）填 5 而不是 7，说明乘除链要继续延伸，不能提前收尾——如果这里错填成 ε，i+i*i会在第二个+之前就把 S 弹空，然后报出「期望 # 实际 *」这种完全对不上现象的错误。

提示：空项不要用 0 表示。产生式编号 0 是E → TG，用 0 当空项会导致「本该报错的地方反而展开了一条产生式」，程序不崩但结果全错，这类 bug 比崩溃更难查。

3.3 分析栈与剩余串：两个指针怎么配合

运行时的状态只有两个数组和两个指针。分析栈A从下标 0 往上长，top指向当前栈顶；剩余输入串B是一个已经归一化成终结符的字符数组，末尾补#，b指向当前待匹配字符。初始化时A[0]='#'、A[1]='E'、top=1，b=0。

栈里同时存终结符和非终结符，靠一张终结符表区分：拿弹出符号去i+-*/()#里找，找到就是终结符，走匹配分支；找不到就一定是非终结符，走查表分支。这个判断每轮循环都要做一次，所以必须写成函数或者每次循环开头重置标志位，不能依赖一个跨轮次的全局变量。

栈容量要留余量。最坏情况下，(((i)))这种深层嵌套加上多次展开，栈深会超过符号串长度的两倍。数组开 64 个字符够应付课设级别的测试用例，但如果要演示i+i*i/i-i*i+i这种长串，建议开到 128 并加一句越界断言，出错时能立刻定位而不是段错误。

4. 主控程序：一趟循环走完匹配与展开

4.1 初始化与主循环骨架

主循环的逻辑可以概括成一句话：弹出栈顶，是终结符就比对输入，是非终结符就查表展开，直到栈顶和输入同时到达#。整个过程是一趟线性扫描，没有回溯，这也是 LL(1) 相比回溯法的核心优势——每个位置该用哪条产生式，查表一次就定了。

char A[128]; // 分析栈 char B[128]; // 剩余串，已归一化为终结符并以 '#' 结尾 int top = 0, b = 0, len = strlen(B); A[top] = '#'; A[++top] = 'E'; // 初始栈内容：# E int step = 0; while (true) { // 每步打印：步骤号、分析栈、剩余串、所用产生式 printf("%-4d %-14s %-14s ", step++, A, B + b); char X = A[top--]; // 弹出栈顶符号 if (strchr("i+-*/()#", X) != NULL) { // 分支一：终结符 if (X == '#' && B[b] == '#') { // 双 # 相遇，接受 printf("acc\n"); break; } if (X == B[b]) { // 匹配成功，输入指针后移 printf("匹配 %c\n", X); ++b; continue; } printf("ERROR: 期望 %c，实际 %c\n", X, B[b]); break; } int m = row(X), n = col(B[b]); // 分支二：非终结符，查表 if (m < 0 || n < 0 || M[m][n] < 0) { printf("ERROR: 非终结符 %c 遇 %c 无产生式可用\n", X, B[b]); break; } const Prod& p = P[M[m][n]]; printf("%c -> %s\n", p.lhs, p.rhs); for (int k = p.len - 1; k >= 0; --k) // 逆序压栈 if (p.rhs[k] != '^') A[++top] = p.rhs[k]; // ε 不入栈 }

这段代码里有三个地方值得单独说清楚，因为它们是整份实现里最容易写错、也最容易被追问的地方。

第一个是A[top--]这个写法。它先取栈顶值赋给 X，再把 top 减一，等价于「弹出」。写成X = A[top]; top--;效果一样，但合在一起更紧凑。要注意的是弹出之后 top 指向的是新的栈顶，后面压栈时用A[++top]先加再赋值，两个操作正好对称。

第二个是逆序压栈。产生式右部+TG压栈后，栈里从下到上必须是G、T、+，也就是+在最顶上，下一轮才能先匹配+。所以循环变量k必须从p.len - 1递减到 0。如果写成正序，+TG压完是+在最底下、G在最顶上，下一轮直接去展开 G，分析顺序整个乱掉——症状是单符号输入i#能过，i+i#就报错，非常迷惑。

第三个是if (p.rhs[k] != '^')。空产生式G → ^压栈时，^会被跳过，栈里什么也不加，等价于「G 消失了」。如果漏掉这个判断，^会进入分析栈，下一轮弹出时既不匹配输入、又不在非终结符表里，程序直接报出「期望 ^ 实际 #」这种看不懂的错误。

4.2 终结符匹配与非终结符展开的分支边界

两个分支的判定依据是「弹出符号是否在终结符表里」，而不是「是否大写」。用大小写判断在本题能跑，因为非终结符恰好都是大写字母，但这是个坏习惯：一旦文法里出现id、num这类多字符终结符，或者把运算对象记成小写i以外的符号，判据立刻失效。正确做法是维护一张i+-*/()#的字符串，用strchr查。

匹配分支还有一个边界要处理：双#相遇必须放在「相等即匹配」之前判断。如果先判相等，#和#会被当成普通终结符匹配成功、指针后移，然后下一轮弹出栈里已经空了的A[top]，读到垃圾值。原文代码里的做法是先判x=='#'再exit(1)，效果上也是终止，但输出写的是acc!加强制退出，不够干净——正常接受应该让主循环自然结束，把收尾工作（比如释放输入、打印统计）留给循环外的代码。

非终结符展开分支要处理两种失败：符号不在非终结符表里（说明栈被污染了，通常是空产生式没跳过导致^入栈），以及查表得到空项（说明当前位置文法推不下去，是真正的语法错误）。这两种失败的信息要区分开，否则调试时分不清是自己的实现 bug 还是输入的用例就该报错。

4.3 接上词法分析：UCON、PL、ID 怎么变成 i、+、i

实验二的输入是实验一扫描器的输出，格式形如UCON, PL, UCON, MU, ID。语法分析器只认i + - * / ( ) #这八个终结符，所以中间要加一层归一化：无符号常数 UCON 和标识符 ID 都映射成i，加号 PL 映射成+，乘号 MU 映射成*，除号 DI 映射成/，左括号 LP、右括号 RP 各自对应，末尾补#。

# 把实验一输出的单词串归一化成文法终结符串 TOKEN_MAP = { "UCON": "i", "ID": "i", # 常数和变量都归为运算对象 i "PL": "+", "MI": "-", # 加、减 "MU": "*", "DI": "/", # 乘、除 "LP": "(", "RP": ")", # 左右括号 "EOF": "#" # 输入结束标记 } def normalize(token_line): out = [] for t in token_line.replace("，", ",").split(","): t = t.strip() if not t: continue if t not in TOKEN_MAP: raise ValueError(f"词法单元 {t} 无法映射到终结符") # 词法层错误 out.append(TOKEN_MAP[t]) out.append("#") return "".join(out)

这一层的作用不只是「翻译」。词法阶段的错误（比如出现@、非法数字12a）在这里就被拦下来，抛出明确异常，不会污染语法分析栈；归一化之后，语法分析器拿到的永远是干净的终结符串，匹配分支里不需要再考虑多字符 token 的比较问题。两个实验合起来构成完整前端，这也是题目要求「将词法、语法分析合在一起」的落点。

注意：归一化阶段不要偷偷「纠正」输入。比如遇到MI就自作主张补一个i，看似提高了通过率，实际上把错误输入变成了合法输入，测试用例里的错例全部失效。错例必须原样传下去，让语法分析器自己报错。

4.4 出错信息的三类划分

题目要求「不论对错，都应有明确的信息输出」，这句话在实现上意味着错误不能只打印一个 ERROR 了事。按出错位置分三类，每类的信息内容不同：

第一类是词法层错误，发生在归一化阶段，输出「第几个 token 无法映射」，此时语法分析还没开始。第二类是终结符不匹配，发生在匹配分支，输出「期望符号、实际符号、当前剩余串、当前栈内容」——这四项凑齐，基本能定位到是多了符号还是少了符号。第三类是查表得空项，发生在展开分支，输出「哪个非终结符遇到哪个输入符号推不下去」，这类错误通常对应「缺少运算对象」或「运算符连用」。

三类错误都应该在退出前把当前的分析栈和剩余串完整打印一遍。中途结果比错误信息本身更有价值，因为它是手推过程的标准答案，能和自己的推导逐行对照。

5. 避坑与排查：语法分析程序最容易翻车的五处

5.1 产生式抄错或挂错非终结符

现象：i+i*i#被判 ERROR，但手工按分析表推一遍明明是 RIGHT；或者分析步骤打印出来，第 3 步用的产生式和预期完全对不上。

原因：从教材或网络资料上抄产生式时，把消除左递归引入的中间非终结符搞混了。常见错法是把S → *FS写成F → -FS，或者把S → /FS挂到 F 上，还有的把 ε 产生式写成S → ^FS。原文的说明文档里就出现过F->-FS | /FS和S->^FS这样的笔误，直接照抄进代码就是灾难。

解决：把 10 条产生式单独列一张表，逐条和 FIRST 集对照——每条产生式右部的首符号必须落在左部非终结符的 FIRST 集里。F → -FS这条，F 的 FIRST 是{i, (}，根本没有-，一眼就能看出错。

5.2 ε 产生式被压进分析栈

现象：分析到i+i#的最后一步，栈顶弹出一个^，程序报「期望 ^ 实际 #」，或者 top 越界后读到乱码。

原因：空产生式G → ^的长度记为 1，压栈循环没有跳过^，把它当成普通符号压进去了。

解决：压栈时加一句if (p.rhs[k] != '^')，空产生式等价于「该非终结符凭空消失」。同时把「弹出符号既不是终结符也不在非终结符表里」这种情况显式判为内部错误，未来再出现类似污染能第一时间暴露。

5.3 逆序压栈写成了正序

现象：单符号输入i#能正确接受，带运算符的i+i#就报错，报错信息往往是「期望 G 实际 +」这类看着莫名其妙的内容。

原因：产生式右部从左到右压栈，导致最左符号沉到栈底，栈顶变成了最右符号。LL(1) 要求每轮处理最左符号，顺序一反，展开顺序全乱。

解决：循环写成for (int k = p.len - 1; k >= 0; --k)。验证办法很直接：对E → TG压栈后打印栈内容，从顶到底应该是T、G、#，如果看到G在顶上就是写反了。

5.4 分析表行列索引与符号表顺序不一致

现象：程序不崩、每步都能打印产生式，但某些合法串被判 ERROR，某些非法串反而过了。把打印的产生式和手推结果对比，发现第 2 步开始就分叉。

原因：填表时按E G T S F的顺序，查表时row()函数却按E T F G S的顺序返回行号，或者干脆在代码里写死M[1][3]这种魔数。两套顺序只要有一处对不上，整张表就错位。

解决：非终结符数组和填表行序共用同一个常量表，row()函数遍历这张表返回下标，绝不在业务代码里写数字。终结符同理。写完之后拿M[1][6]这种已知答案的格子做一次断言，等于给表加了个单元测试。

5.5 输入串未校验、指针越界

现象：输入里混进一个非法字符，程序不报错而是继续往下跑，最后输出一堆乱码；或者匹配完最后一个#后b继续自增，读到数组外的内存，段错误退出。

原因：读入阶段只判断了「是不是#结尾」，没有校验字符是否在终结符集合内；匹配成功后的++b没有做上界保护。

解决：读入时逐字符比对终结符表，非法字符立即报错退出，这一点原文代码是做到了的（if (ch!='i' && ch!='+' ...) exit(1)）；匹配分支里，++b之前加一句if (b >= len) break;之类的保护，让越界变成可控的错误提示而不是崩溃。

提示：这五条里有三条（5.2、5.3、5.5）只在特定输入下才触发，i#这种最小用例测不出来。测试集里必须包含i+i*i#、(i+i)*i#、i+i)#这三种，覆盖展开、嵌套和错误路径。

6. 验收与答辩：用测试用例把「能跑」变成「能证明」

验收环节最忌讳的是现场敲一个i+i*i#看着输出 RIGHT 就完事。评审关心的不是你跑通了一个用例，而是你能不能证明这套实现对「所有」输入都成立。我的做法是准备一张固定的测试表，正例、边界、错例各占一部分，每条都标注它考察的是哪条设计决策。

每条错例都要能说清「错在哪一步、当时栈里是什么、为什么这一格是空的」。比如i*#走到 F 遇#那一格，M[4][7] = -1，因为 F 的两条产生式首符集是{i, (}，#不在其中，也不在 FOLLOW(F) 里——这个解释比「程序报错了」有说服力得多。

答辩现场我一般只讲三件事，控制在五分钟内。第一件，为什么选 LL(1)：左递归必须消、表驱动可演示、错误可定位，一句话带过对比算符优先和 SLR 的取舍。第二件，三张表怎么来的：FIRST 从下往上推、FOLLOW 从上往下传、分析表由前两者交叉填出，顺手在白板上写FOLLOW(T) = {+, -, ), #}证明不是抄的。第三件，错误分几类、每类输出什么。剩下的时间留给现场跑测试表，让评委随便指一条错例，当场定位到分析表的具体格子。

有一套流程我后来每次做这类实验都强制走一遍：先手推三条用例写在纸上，再对着纸上的每一步去比对程序的打印输出，逐行对齐。哪一行对不上，问题一定在那一行对应的展开或匹配逻辑里，不用满代码找。这套笨办法救过我两次——一次是逆序压栈写反，一次是分析表行序错位，两次都是靠「纸上有、屏幕上没有」在十分钟内定位的。希望帮到你。

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