企业官网建设流程全解析

简介：面向编译原理课程实验的这份文档，聚焦语法分析程序的设计与实现，适合正在完成词法、语法分析实验的高校学生与自学者对照参考。压缩包内仅1个doc文件，约127KB，篇幅集中，便于查阅和打印，目前已有143人学习下载。文档以算术表达式简化子集为分析对象，给出BNF定义、LL(1)文法改写、预测分析表构造，并提供基于C++的源程序片段，涉及分析栈、剩余串、终结符与非终结符等数据结构，以及产生式结构体、分析表填充、RIGHT/ERROR判定和中间结果输出等内容。读者可据此理解从单词序列到语法结构检查的实验脉络，结合符合语法规则的语句与若干错例调试程序，也可为实验报告整理和课堂验收提供参考。

1. 语法分析：为什么写完了 LL(1) 分析器，还是说不清它在干什么

互联网上能搜到大量语法分析实验的成品源码，抄下来跑通几个测试串，十分钟就够。但真遇到输入报错，多数人说不清是文法写错了、分析表填错了，还是栈操作错了。反直觉的地方在于：这类分析器的本体不是那两三百行 C++，而是那张 5 行 8 列的二维表，代码只是围着它转的查表循环。表对了，循环只有十几行的逻辑；表错了，代码写得再漂亮也只会输出 ERROR。搞懂表怎么来的、栈怎么动的，才算真正写过一遍语法分析。

2. 左递归消除：E → E+T 为什么不能直接喂给自顶向下分析

算术表达式的 BNF 写出来天然是左递归的：E → E+T | E-T | T。人看着舒服，因为加法和减法本来就是从左往右结合。但这份文法如果原样交给自顶向下分析，程序在第一秒就会失控。原因不在代码，在文法本身的形状。

2.1 左递归让下降程序在栈上原地打转

递归下降是最贴近直觉的实现方式：每个非终结符写一个函数，函数体照着产生式右部依次调用。如果照抄E → E+T，得到的函数第一句就是调用自己：

# 左递归版文法的递归下降实现：错误示范 def E(): E() # E -> E + T 的第一件事，就是再进一次 E match('+') T()

这段代码没有任何出口条件，调用栈会一直增长到崩掉。换成分析栈的视角更好理解：栈顶是 E，查表得到产生式 E → E+T，把右部逆序压栈，栈顶又变成 E，下一轮继续查表还是 E → E+T。栈的深度只增不减，输入指针一步都没往前走。

这暴露了自顶向下分析的一条硬约束：每展开一步，必须消耗掉至少一个输入符号，或者让待展开的符号变少。左递归违反了这个单调性。算符优先和 LR 系列不受影响，因为它们是从下往上归约，栈里攒的是已经读完的部分，不存在「展开自己」这一步。选 LL(1) 就等于接受了这个限制。

2.2 改写文法：把递归挪到右边，拆出 G 和 S 两个尾巴

通用改写规则只有一条：A → Aα | β改成A → βA'、A' → αA' | ε，其中 α 是那串重复的后缀，β 是不以 A 开头的入口。套到加减法上，α 是+T或-T，β 是T，于是：

E → T G G → + T G | - T G | ε

乘除同理，把T → T*F | T/F | F改写为T → F S、S → * F S | / F S | ε。因式那一层本来就右递归，括号和原子符号不需要动。

这里有个容易忽略的设计点：为什么拆成两条链 G 和 S，而不是合并成一条？因为它们对应不同的优先级。文法里的层级关系直接就是优先级的编码——F 在最深层，处理括号和原子，绑定最紧；T 包着 F，处理乘除；E 包着 T，处理加减。i+i*i能被正确解析成i+(i*i)，靠的不是分析器聪明，而是i*i在文法结构上更早就被 F、S 这两层收进了 T 里。

原文档「问题分析」那一段把产生式和 G/S 的编号挤在了一起，F->-TG g1、S->^FS这类错位看着挺唬人，其实是表格排版塌了。真正可信的是源码里那几行结构体赋值：e.origin='E'、e.array="TG"、g1.origin='G'、g1.array="-TG"。读这类实验材料，永远以最终能编译的代码为准，别信被 Word 表格揉过的文字。

2.3 改写前后语言一样，但语法树的形状变了

改写保证的是产生的句子集合不变，不保证推导树一样。左递归E → E+T生成长在左边的树，a-b-c自然归成(a-b)-c；右递归的G → -TG生成长在右边的树，同一串会归成a-(b-c)。对加法无所谓，对减法就是实打实的语义错。

这是自顶向下分析器的血泪经验：文法改写会悄悄改掉结合性。实际操作里没人回去改文法，都在语义动作里补：处理G → -TG时不直接做减法，而是把 T 的值取负，再交给累加器加上去。这样右递归的树形照样算出左结合的数值。类似的还有左公因子提取（A → ab | ac改成A → aA'、A' → b | c），它同样不改变语言，但会把判断推迟到下一层。只要记住「改写只保语言、不保结构」，后面配语义动作时就知道该在哪补。

3. FIRST / FOLLOW 与预测分析表：那张 5×8 的表是怎么算出来的

分析表是这类程序的核心，但它的每一格都不是猜出来的，都是从两个集合推出来的。搞清楚这两个集合，等于搞清楚了分析器「凭什么知道下一步用哪条产生式」。

3.1 FIRST：一个非终结符能打头的所有终结符

FIRST(A) 的定义是：从 A 出发推导，能出现在最左边的那些终结符的集合；如果 A 能推出空串，ε 也算进去。它回答的问题是「看到当前输入符号是 a，能不能确定该展开 A」。

算法本身是不动点迭代，因为一个非终结符的 FIRST 依赖它右部第一个符号的 FIRST，链条可能很长。手算也行，规则就三条：终结符的 FIRST 是它自己；A → X Y Z从 X 开始看，X 的 FIRST 去掉 ε 全部并进来，如果 X 能推出 ε 就继续看 Y，一路并到某个不能推出 ε 的符号为止；全串都能推出 ε 才给 A 加 ε。

对这份文法算一遍：

看结果就能读出结构：E 和 T 的 FIRST 完全一样，因为它们都靠 F 打头；G 和 S 都含 ε，因为它们是改写时引入的可空尾巴。这份文法没有左公因子问题，如果 E 的右部同时有T G和T H两条，FIRST 就撞了，必须先提公因子。

3.2 FOLLOW：ε 产生式该填到哪一列

只有 FIRST 填不满整张表。像G → ε这种产生式右部是空的，FIRST 里只有 ε，可表格的列是输入符号，总不能填到 ε 那一列。这时候看的是 FOLLOW(G)：G 后面可能紧跟哪些终结符，就在那些列上填G → ε。

FOLLOW 的计算规则也是三条：给开始符号的 FOLLOW 加#；对A → αBβ，把 FIRST(β) 去掉 ε 并入 FOLLOW(B)；如果 β 能推出 ε（或 β 本来就是空），把 FOLLOW(A) 整个并入 FOLLOW(B)。同样要迭代到收敛。

FOLLOW(E) = { ), # } FOLLOW(G) = FOLLOW(E) = { ), # } // E → TG 中 G 在末尾 FOLLOW(T) = FIRST(G)\{ε} ∪ FOLLOW(E) = { +, -, ), # } FOLLOW(S) = FOLLOW(T) = { +, -, ), # } // T → FS 中 S 在末尾 FOLLOW(F) = FIRST(S)\{ε} ∪ FOLLOW(T) = { *, /, +, -, ), # }

注意 FOLLOW 里完全没有(和i。这两个符号只可能出现在表达式的开头，不会紧跟在任何非终结符后面。表里 E 行和 T 行只在(、i两列有内容，就是这个原因。

3.3 用源码的 C[5][8] 反推填表，顺便验证有没有冲突

填表规则两条，写死就够用：对每条A → α，把该产生式填进所有FIRST(α)对应的列；如果 α 能推出 ε，再把A → ε填进所有FOLLOW(A)对应的列。如果同一格被填两次，且两条产生式不同，就是冲突，这份文法不是 LL(1)。

源程序里v1的顺序是i + - * / ( ) #，索引 0 到 7；v2的顺序是E G T S F，索引 0 到 4。按这个行列排出来的表是这样的：

跟源码里C[0][0]=e; C[0][5]=e;C[1][1]=g; C[1][2]=g1; C[1][6]=g2; C[1][7]=g2;一路对下来，能逐格吻合。这种「自己算一遍再跟代码比」的验证方式，比盯着代码读十遍有效得多，任何一格对不上，立刻能定位是 FIRST 算错了还是下标映射错了。

不想手算的话，用几十行脚本就能把这两张集合并出来，思路就是反复扫描产生式直到集合不再变化：

# FIRST / FOLLOW 的不动点计算，规模小，直接暴力迭代到收敛 GRAMMAR = { 'E': [['T', 'G']], 'G': [['+', 'T', 'G'], ['-', 'T', 'G'], []], 'T': [['F', 'S']], 'S': [['*', 'F', 'S'], ['/', 'F', 'S'], []], 'F': [['(', 'E', ')'], ['i']], } TERM = {'i', '+', '-', '*', '/', '(', ')', '#'} def first_sets(): first = {A: set() for A in GRAMMAR} changed = True while changed: # 集合单调增长，必然收敛 changed = False for A, prods in GRAMMAR.items(): for rhs in prods: if not rhs: # 空产生式：FIRST 里放 ε if 'ε' not in first[A]: first[A].add('ε'); changed = True continue for sym in rhs: # 从左往右扫，遇到不能推空的就断 add = {sym} if sym in TERM else (first[sym] - {'ε'}) if not add <= first[A]: first[A] |= add; changed = True if sym in TERM or 'ε' not in first[sym]: break else: if 'ε' not in first[A]: first[A].add('ε'); changed = True return first def follow_sets(first): follow = {A: set() for A in GRAMMAR} follow['E'].add('#') # 开始符号后面跟结束符 changed = True while changed: changed = False for A, prods in GRAMMAR.items(): for rhs in prods: for i, sym in enumerate(rhs): if sym not in GRAMMAR: continue tail = rhs[i + 1:] add, nullable = set(), True for t in tail: # 看紧跟其后的符号能不能推空 add |= ({t} if t in TERM else first[t] - {'ε'}) if t in TERM or 'ε' not in first[t]: nullable = False; break if nullable: add |= follow[A] if not add <= follow[sym]: follow[sym] |= add; changed = True return follow

first_sets里那个for ... else是有意写的：循环正常跑完（没被 break）说明右部所有符号都能推出空，才给左部加 ε。follow_sets里nullable标记的作用是判断 β 是否能整体推空，能的话要继承左部的 FOLLOW。两段都用while changed而不是扫一遍，是因为 FIRST 和 FOLLOW 之间存在互相依赖，一轮扫描推不完，得迭代到集合不再增长为止——这是所有数据流类算法的共同写法，和后面要讲的查表循环是同一种思路。

4. 表驱动主循环：分析栈、剩余串和三个下标的真实分工

拿到表之后，剩下的代码其实很薄。整份源程序里真正干活的就三段：压栈初始化、取栈顶查表、按结果分支。把这三段拆开看，能看清每个变量的职责，也能看出哪些地方最容易写错。

4.1 栈顶是终结符还是非终结符，两条路径完全不同

主循环每轮只做一件事：弹出栈顶符号x，看它是什么。如果是终结符，就去和当前输入符号ch比，相等就同时前进（输入指针b加一，ch换成下一个字符），不等就是语法错误；如果是非终结符，就拿x和ch去查表，查出产生式后把右部压栈。

这两个分支的对称性很强：终结符负责「消耗输入」，非终结符负责「展开」。输入串一共有 l 个符号，每个符号被消耗一次，整棵树展开的步数是有限的，所以循环必然终止。判断终结符的方式是查v1数组，这份源码用了一次线性扫描加flag标记：

x = A[top--]; // 弹出栈顶 int flag = 0; for (j = 0; j <= 7; j++) // 在终结符表 v1 里找 if (x == v1[j]) { flag = 1; break; } if (flag == 1) { // 分支一：栈顶是终结符 if (x == '#') { cout << "acc!"; break; } // 栈和输入同时到底 if (x == ch) { print(); print1(); cout << "匹配"; ch = B[++b]; } else { print(); print1(); cout << "出错"; exit(1); } } else { // 分支二：栈顶是非终结符 int m = row_of(x), n = col_of(ch); type cha = C[m][n]; if (cha.origin != 'N') { // 'N' 是「表项为空」的哨兵 print(); print1(); cout << cha.origin << "->" << cha.array; for (j = cha.length - 1; j >= 0; j--) A[++top] = cha.array[j]; if (A[top] == '^') top--; // 空产生式不留在栈上 } else { print(); print1(); cout << "出错"; break; } }

参数含义值得逐个过一遍：A是分析栈，栈底永远是最先压进去的#，栈顶指针是top；B是剩余输入串，存的是从扫描器拿到的符号序列，尾部补#；b是当前读到的位置，ch是B[b]的缓存，之所以缓存而不是每次都取B[b]，是因为查表时要用当前符号做列下标，取一次存起来比反复解引用清楚。C[m][n]的m来自非终结符在v2里的位置，n来自当前输入符号在v1里的位置，两个映射表就是这张二维数组的行列坐标。

源码用cha.origin != 'N'判断表项是否为空，靠的是初始化阶段把整张表填成origin='N'。这个约定的好处是省掉一个bool数组，坏处是初始化漏掉一格就会变成「随机行为」——后面避坑那节会细说。

4.2 逆序入栈：为什么循环要从 length-1 压到 0

for (j = cha.length - 1; j >= 0; j--) A[++top] = cha.array[j];这一行是整份代码里最容易写反的地方，写反了程序还能跑，只是分析过程全错。

原因在于栈的语义：栈顶在数组末尾（top是最大下标），下一次弹出的一定是A[top]。产生式右部是按从左到右的顺序写进array的，要让最左边的符号先被处理，它就必须最后压、待在栈顶。以E → TG为例，array = ['T','G']，逆序压入先是 G 再是 T，栈变成# G T（top 指向 T），下一轮弹出 T，正好是最左符号。如果正序压，栈变成# T G，弹出 G，直接把整个推导顺序打乱了——G 是尾巴上的符号，它该在 T 处理完之后才轮到。

把栈画成竖着的就能对上：压栈顺序和弹出顺序互逆，所以入栈必须反向。LR 分析器里归约后压入左部符号，原理相同但不涉及逆序，因为只压一个符号。很多人在 LR 上和 LL 上套用同一套记忆，就会在这里翻车。

4.3 空产生式与打印对齐：两个不显眼但必须处理的细节

源码用字符'^'表示 ε，g2.array[0]='^'、length=1。压栈之后判断一句if (A[top] == '^') top--;把它弹掉。逻辑上没错，因为空产生式不产生任何符号，不该在栈里占位置。但如果漏了这句，下一轮弹出的就是'^'，它既不在v1也不在v2里，程序会走到「既不是终结符也不是非终结符」的灰色地带，轻则死循环，重则在row_of里越界。

打印函数print()和print1()是给分析过程留痕迹用的。print()从栈底打到栈顶，print1()先输出若干个空格把「剩余字符」列对齐，再输出B[b..l]。这种对齐打印在实验报告里很加分，因为每一步的分析栈、剩余串、所用产生式排成三列，一眼能看出推导是不是走在正轨上。

有一个细节要留意：源码里print()的循环写的是for (a = 0; a <= top + 1; a++)，而栈的有效范围是A[0..top]，所以每行会多打一个未初始化的字符。不致命，但会让人误以为栈里有个莫名其妙的东西。改成a <= top就干净了。这类「看着能跑、数据其实多一格」的问题，是读别人的实验代码时最常见的噪声来源。

5. 常见问题排查：分析器报 ERROR 之外的几种翻车

分析器跑不通，很少是 LL(1) 理论没学懂，绝大多数是接口、下标、初始化这三类琐碎问题。下面几条都是这类实现里反复出现的，每条按现象、原因、解决写，对照改就行。

5.1 输入与词法接口的坑

现象一：输入1+2立刻提示「输入串中有非法字符」并退出，连分析过程都不打印。

原因：源程序里合法字符只有i、+、-、*、/、(、)、#八个，而且判定用的是单字符比较。前面词法分析那一步输出的是UCON,PL,UCON,MU,ID这类二元式内码，中间还夹着逗号和类别码，直接把整串喂进来，第一个字符U就不在v1里。这条实验要求「将词法、语法分析合在一起」，正是为了逼你把两段的接口对齐。

解决：在两者之间加一个映射层，把词法单元序列翻译成终结符序列——常数和标识符统一输出i，运算符原样输出，末尾补#。映射表单独放一张，别塞进分析循环里。如果坚持用内码驱动，那就得把v1换成内码集合，同时把ch的数据类型从char升成string，代码里所有单字符比较要一起改，改动面比加映射层大得多。

现象二：分析过程打印的「剩余字符」列整体错位，最后会多出一个乱码字符。

原因：读入循环用B[j] = ch; j++;一路存到#为止，退出时j已经指向#的下一位，而l = j又把这个越界下标当成「剩余串长度」。print1()里for (j = b; j <= l; j++) cout << B[j];用<=比较，于是每次都多输出一格未初始化的B[l]。更麻烦的是这里的循环变量和全局的j是同一个，函数里改完，外面的读入下标也跟着变，属于典型的「变量复用埋雷」。

解决：长度记成l = j - 1，或者把打印循环条件改成j < l；同时把print1()内部的循环变量声明成本地变量，不要复用全局下标。更彻底的做法是给输入串单独一个结构体，长度、当前指针、缓冲区一起封装，谁也别想偷偷改别人的状态。

5.2 栈与预测表的坑

现象三：分析到第几步时栈顶出现'^'，之后要么原地打转，要么直接崩溃。

原因：空产生式压栈后没弹掉。G → ε、S → ε这两条在分析i+i#这类串时会频繁命中，'^'一旦留在栈上，下一轮它既查不到终结符表也查不到非终结符表，row_of('^')会返回一个越界下标，C[m][n]越界读出来的还是随机值。

解决：压栈之后立刻判断并弹栈，if (top >= 0 && A[top] == '^') top--;。更好的做法是根本不让'^'进栈——压栈前先看length是不是 1 且内容为'^'，是就整段跳过。后者能避免把「哨兵字符」和「真实符号」混在同一套比较逻辑里。

现象四：同一份输入跑两遍，结果不一样，有时 acc 有时出错。

原因：预测表没初始化全。源码里用双层循环把C[m][n].origin全填成'N'，m到 4、n到 7，范围是对的。但只要把非终结符或终结符多加一个（比如想支持%运算），循环上界没跟着改，新增的那一行或一列就是未定义内容，恰好不等于'N'就被当成有效产生式执行，于是「有时能过、有时乱跳」。这类问题最像玄学，因为同一个编译产物两次运行结果都可能不同。

解决：初始化别手写下标上界，用sizeof(v1)/sizeof(v1[0])算列数，或者干脆用memset(C, 'N', sizeof(C))一把梭——前提是origin是第一个成员且结构体没有指针。然后在查表处加一句断言，m、n落在合法范围内才继续。

现象五：单独测i+i全对，一测(i+i)*i就报错，且错误位置很靠前。

原因：F 行的(列没填。C[4][5]=f这一格对应的正是F → (E)，漏掉它，一遇到左括号就查表得空。另一种同源问题是v2的顺序和填表时的行号对不上：v2 = {'E','G','T','S','F'}就要求C[0]是 E 行、C[2]是 T 行，如果填表时按E,T,F,G,S的顺序写，整个表就错位了，但编译期完全看不出来。

解决：把整张表打印出来人眼对一遍，比单步调试快十倍。表打印可以写在程序启动阶段，用v1、v2做行列标题，一眼就能看出哪行哪列是空的。这一步花两分钟，能省掉一小时的断点。

6. 从 LL(1) 到 LR：这套代码真正值钱的地方是「表从哪来」

把这几种方法摆在一起看，选型其实是个很朴素的权衡。递归下降写起来最像人话，每个非终结符一个函数，但左递归、回溯、公共前缀三座山压着，稍微复杂的语言就写不下去；算符优先表小、实现简单，可它对文法有额外要求，而且错误定位往往只能告诉你「这里不对」，说不出期望什么；LL(1) 表驱动，表小、循环短、错误位置精确到符号，代价是文法必须先改造，改造过程还会顺手改掉结合性；LR(1) 描述能力强，左递归照写不误，但状态表规模大得多，手工构造基本不现实，得靠工具生成。

真正值得记住的是这三种分析器的表在形式上同构。LL(1) 的预测分析表是「栈顶非终结符 × 当前输入符号 → 一条产生式」，LR 的 ACTION/GOTO 表是「栈顶状态 × 当前输入符号 → 移进或归约」，本质都是把「下一步该干什么」从代码里搬到数据里。代码退化成一台通用引擎，换语言只需要换表，不用改循环。这份实验代码只有一百多行，但它演示的正是这个分工：type结构体描述产生式，C[5][8]描述决策，主循环只负责查和执行。

想验证自己是不是真看懂了，有个简单办法：改动文法里一条产生式，比如把F → i扩成F → i | i [ E ]（加个下标语法），然后重算 FIRST/FOLLOW，重新填表，看会不会在某一行撞出冲突。会撞，说明这个扩展不是 LL(1) 的，得先提公因子；不会撞，说明你的集合法则用对了。这个过程比背十遍定义都管用，因为它把「文法」和「表」之间的因果链完整走了一遍。

再说个取舍：这份实现把词法分析和语法分析合在了一起，输入直接按字符读，省掉了两个模块之间的接口设计。这在实验规模下是聪明的做法，能在一份代码里看到端到端的完整链路；但真做编译器，这两层必须切开，因为词法要处理注释、空白、关键字识别这些和语法无关的事，混在一起会让主循环膨胀成几百行，错误处理也没法分层。看清楚「实验里为什么可以合、工程里为什么必须分」，本身就是这道题想训练的判断力。

从那以后我每次碰分析器，不管是自己写还是读别人的，第一件事都是把预测表或状态表原样打印出来贴在屏幕上，先对着输入串手动走三步，确认行列映射和栈操作都对，再去读那段循环。这个习惯救过我很多次，因为出问题的地方九成在表里，不在代码里。希望帮到你。

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