企业官网建设流程全解析

最近总能在课程群里看到类似问题：编译原理实验要求用 C 语言实现算符优先分析算法，优先关系表怎么建？栈顶该移进还是归约？代码怎么组织才不绕？说实话，这个算法在语法分析里不算难，但它把“优先关系表”和“移进-归约”两个概念叠在一起，很多同学学教材时能看懂，一到动手写代码就卡住。这篇文章按我自己做实验的路径来走，从为什么选算符优先、优先关系表怎么手算，到 C 语言里的栈和归约逻辑怎么设计，再到调试中容易踩的坑，完整过一遍。不管你是准备课程设计，还是单纯想把教材那章彻底吃透，应该都能用得上。

1. 算符优先分析到底在解决什么问题：为什么课程设计总选它

1.1 语法分析的两条路线：通用算法与专用简化

编译器前端里，语法分析器的任务是把词法分析得到的记号流，按照文法组织成语法结构。主流做法分两条线：一条是通用型的自顶向下或自底向上分析，比如 LL(1)、LR(1)，它们能处理一大类文法，但 LL(1) 对文法格式要求苛刻，LR(1) 的分析表又大又难手动构造；另一条是针对某类典型结构做专用简化，算符优先分析就属于这条线。

算符优先分析是自底向上的移进-归约分析，但它有一个非常独特的视角：整个分析过程只依赖终结符（也就是运算符号）之间的优先级关系来决定动作，非终结符在栈里只是个“占位符”。这在处理表达式类文法时特别有效。课程设计里最常见的表达式文法就是四则运算加括号，正好是算符优先分析的主场。

我个人的体会是：它之所以常被选来做课程实验，不是因为性能最好，而是因为代码量小、流程直观，能把“分析表”和“栈”这两个编译原理核心概念练到位。而且手写一遍之后，再看递归下降或者 LR 自动机，思路会清晰很多。

1.2 算符优先分析的关键：不管非终结符的“形状”

具体说说这个“不管形状”是什么意思。拿经典文法举例：

E -> E + T | T T -> T * F | F F -> ( E ) | i

如果按递归下降写，你得为 E、T、F 各写一个函数，分析i+i*i时函数调用层层嵌套；如果用 LR 分析，你要维护几十上百个状态。而算符优先分析只做一件事：比较当前栈顶最近的终结符和下一个输入符号之间的优先级，决定现在应该把输入符号压栈，还是把栈顶部的一段内容归约成一个非终结符。

这里有一个核心概念叫素短语。一个素短语是句型中的一个子串，它至少包含一个终结符，并且不再包含更小的素短语。算符优先分析每次归约的对象就是当前最左素短语。为什么它能做到？因为它提前建好了一张终结符之间的优先关系表，表格里记录着a < b、a = b、a > b或不存在关系，通过这张表就能在栈里切出素短语的边界。

换句话说，它把“句子结构”问题转化成了“运算符优先级”问题。这正是“算符优先”四个字的由来。也正因为它不看非终结符之间的复杂关系，所以对二义性文法非常敏感，这是后话。

1.3 与递归下降、LR 分析的一次直观对比

用一张表看三者区别会更直接：

算符优先的短板也很明显：它不能正确处理非终结符之间的结构关系，文法一旦不满足算符优先条件就无从下手。但正因为它“窄”，才更适合作为理解移进-归约机制的入口。

2. 从文法到优先关系表：FIRSTVT/LASTVT 的构建是本算法的地基

2.1 FIRSTVT 与 LASTVT：为什么需要这两个集合

优先关系表的构建不是拍脑袋，而是有标准流程。第一步先算 FIRSTVT 和 LASTVT。FIRSTVT(P) 表示非终结符 P 经过若干步推导后，可能出现在句首的终结符集合；LASTVT(P) 同理，是可能出现在句末的终结符集合。

教材里给了两条递归定义：对产生式A -> a...或A -> Ba...，a 属于 FIRSTVT(A)；对A -> B...，则 FIRSTVT(B) 里的终结符都属于 FIRSTVT(A)。LASTVT 对称：对A -> ...a或A -> ...aB，a 属于 LASTVT(A)；对A -> ...B，则 LASTVT(B) 里的终结符都属于 LASTVT(A)。注意这里 a 是终结符，B 是非终结符。

按这个规则，上面那个四则运算文法的集合很快能算出来。以 FIRSTVT 为例：F -> (E)让(进 FIRSTVT(F)，F -> i让i进 FIRSTVT(F)；T -> T*F说明*属于 FIRSTVT(T)，T -> F把 FIRSTVT(F) 并入 FIRSTVT(T)；E -> E+T说明+属于 FIRSTVT(E)，E -> T把 FIRSTVT(T) 并入 FIRSTVT(E)。最后得到：

FIRSTVT(F) = { (, i } FIRSTVT(T) = { *, (, i } FIRSTVT(E) = { +, *, (, i }

LASTVT 也类似：

LASTVT(F) = { ), i } LASTVT(T) = { *, ), i } LASTVT(E) = { +, *, ), i }

这些集合看着抽象，但用途很直接：我们想知道某个非终结符能“顶”出什么终结符来，才能在两个符号相遇时判断谁先处理。我第一次手算时漏了E -> T和T -> F这两条直接推导产生的集合传播，导致表和教材对不上。集合计算一定要把传递关系补全，不能只看产生式右部第一个符号。

2.2 三条规则手算优先关系表

有了 FIRSTVT 和 LASTVT，就可以按三条规则填表。设 a、b 是终结符，Q 是非终结符：

• 同一产生式右部出现...aQb...或...ab...，则a = b。
• 同一产生式右部出现...aQ...，则对 FIRSTVT(Q) 中的每一个终结符 b，a < b。
• 同一产生式右部出现...Qa...，则对 LASTVT(Q) 中的每一个终结符 b，b > a。

符号约定再强调一遍：a < b表示 a 的优先级严格低于 b，也就是遇到 a 和 b 相邻时，不能先处理 a，得等 b 先归约；a > b表示 a 高于 b，a 那一侧先归约。=通常出现在括号配对这类场景，表示两者绑在一起，比如( = )。

拿E -> E + T来套规则。右部是E + T，中间是+后跟非终结符 T，按第二条规则，+小于 FIRSTVT(T) 中的每个终结符，也就是+ < { *, (, i }。右部中E和+形成...Qa...，按第三条，LASTVT(E) 中的每个终结符>+，也就是{ +, *, ), i } > +。再比如F -> (E)，右部是( E )，按第一条，( = )；同时(后跟非终结符 E，所以( < FIRSTVT(E)；E 后跟)，所以LASTVT(E) > )。

把所有产生式都过一遍，就能得到一张 6 行 6 列的优先关系表。加上边界符号#后，约定#低于句子开头遇到的终结符，句子末尾的终结符高于#，且# = #。最终表如下：

这张表就是程序里那个二维数组的数据来源。我建议把表打印出来或者写成注释放在代码边上，调试时一眼就能对照。一旦分析出错，第一个要怀疑的就是表里某格填错了，而不是主循环写错。

2.3 用表验证文法是不是算符优先文法

优先表建好后，先别急着写代码，检查一遍是否有冲突。所谓冲突，是指同一对终结符之间同时出现了两种不同的关系，比如a < b和a > b，或者a = b和a < b。如果存在冲突，说明文法不是算符优先文法，后面的分析器没法可靠工作。

上面这张表里，除了空白表示无关系，每个格子只有一个值，说明这个四则运算文法是算符优先文法。做实验时经常遇到的情况是：自己随便改了一个文法，结果表里出现冲突，分析器有时对有时错。这时候不要硬调代码，而是回到文法本身，看看是不是产生了二义性。

3. 用 C 语言实现算符优先分析器：数据结构与主循环设计

3.1 数据结构：算符栈、终结符集合与优先关系表

C 语言实现全程不外乎数组和函数。我用字符数组模拟栈，栈顶下标是 top。终结符集合定义为数组，优先关系表定义成二维数组。这里顺序要和表的行列一致，查表时才不会乱：

#include <stdio.h> #include <string.h> #define STACK_SIZE 100 #define TERMINAL_NUM 6 // 顺序与优先级表行列一致 enum { HASH = 0, PLUS = 1, STAR = 2, LPAREN = 3, RPAREN = 4, ID = 5 }; char terminals[TERMINAL_NUM] = { '#', '+', '*', '(', ')', 'i' }; // 关系：0 表示小于，1 表示等于，2 表示大于，-1 表示无关系 int relation[TERMINAL_NUM][TERMINAL_NUM] = { // # + * ( ) i { 1, 0, 0, 0, -1, 0 }, // # { 2, 2, 0, 0, 2, 0 }, // + { 2, 2, 2, 0, 2, 0 }, // * { -1, 0, 0, 0, 1, 0 }, // ( { 2, 2, 2, -1, 2, -1 }, // ) { 2, 2, 2, -1, 2, -1 } // i };

这个二维数组和上一节的表是一一对应的。#在 C 语言里作为字符常量是普通字符，只是注意别把它和预处理指令混在一起，写在数组里没有任何问题。

3.2 核心函数：查找最顶终结符与最左素短语归约

栈里既有终结符又有非终结符，而移进-归约决策只看终结符，所以第一步要能从栈顶往下找到第一个终结符。这个函数很重要，很多新手直接取stack[top]，结果在栈顶刚被归约成非终结符时永远判断出错：

char stack[STACK_SIZE]; int top; int is_terminal(char ch) { for (int i = 0; i < TERMINAL_NUM; i++) { if (terminals[i] == ch) return 1; } return 0; } char top_terminal(void) { for (int i = top; i >= 0; i--) { if (is_terminal(stack[i])) return stack[i]; } return '\0'; } int get_relation(char a, char b) { int ia = -1, ib = -1; for (int i = 0; i < TERMINAL_NUM; i++) { if (terminals[i] == a) ia = i; if (terminals[i] == b) ib = i; } if (ia < 0 || ib < 0) return -1; return relation[ia][ib]; }

然后是找句柄。当 top_terminal 和输入符号的关系是大于时，说明栈顶素短语已经可以归约。归约范围从哪里开始？我的实现是从栈顶向下找句柄的最右终结符，然后继续向左扫描。扫描时维护一个变量 cur，表示当前句柄内最左边的终结符。每当遇到新的终结符 X，就比较 X 与 cur：如果 X 大于 cur 或 X 等于 cur，说明 X 还是句柄的一部分，更新 cur 为 X 继续向左；一旦遇到 X 小于 cur，说明 X 在句柄左边界之外，句柄起始位置就是 X 的下一个栈下标：

int find_handle(void) { int j = top; while (j >= 0 && !is_terminal(stack[j])) j--; // 句柄最右终结符 if (j < 0) return -1; int cur = j; j--; while (j >= 0) { if (!is_terminal(stack[j])) { j--; continue; } int rel = get_relation(stack[j], stack[cur]); if (rel == 2 || rel == 1) { // X > cur 或 X = cur：X 属于句柄 cur = j; j--; } else if (rel == 0) { // X < cur：X 在句柄左侧，句柄从 X+1 开始 return j + 1; } else { return -1; } } return 0; }

这里有个细节值得单独说：不能拿左边遇到的终结符固定去和句柄最右终结符比较。比如栈里是# ( N )，从右往左扫，遇到(时(和)是等于，还要继续左扫；再遇到#时，#和(是小于，这才判断出句柄是(N)。如果你一直拿#去和)比较，表里是空关系，程序直接报错。

3.3 主循环：移进-归约的完整流程与代码骨架

主循环就是教材算法的直接翻译。每次取栈中最上面的终结符 a 和当前输入符号 b，查表：

• 如果关系是小于或等于，把 b 压栈，读取下一个输入符号；
• 如果关系是大于，调用 find_handle 找到句柄并归约；
• 如果无关系，报语法错误。

void parse(const char *input) { const char *p = input; top = 0; stack[top] = '#'; while (1) { char a = top_terminal(); char b = *p; if (a == '#' && b == '#') { printf("accept\n"); return; } int rel = get_relation(a, b); if (rel == 0 || rel == 1) { // 小于或等于：移进 stack[++top] = b; p++; } else if (rel == 2) { // 大于：归约 int start = find_handle(); if (start < 0) { printf("syntax error near '%c'\n", b); return; } printf("reduce [%d, %d]\n", start, top); top = start - 1; stack[++top] = 'N'; // 统一归约为非终结符 N } else { printf("syntax error near '%c'\n", b); return; } } }

注意这里的归约动作是统一的：不管句柄内容是i、i+i、i*i还是(N)，都压入一个固定的非终结符N。单纯做语法识别这样足够了，因为算符优先分析不关心N到底是 E、T 还是 F。但如果你后面要做表达式求值或生成语法树，就必须在归约时记录句柄对应的产生式，这个我在后面展开。

跑一下i+i*i#，分析结果会是 accept。纸面上跟踪一遍，会比只看代码理解深得多：初始栈#，输入i，# < i移进；栈# i，输入+，i > +归约出N；栈# N，输入+，取最顶终结符是#，# < +移进；后面再处理i和*，整个流程非常顺。

4. 调试过程中我踩过的坑：边界、歧义与句柄误判

4.1 边界符号 # 的优先级：少写一行表就全乱套

第一个坑来自边界。很多教材直接说#小于所有可以出现在句首的终结符、大于所有可以出现在句尾的终结符，但表里具体怎么体现，很容易漏。比如#行、)列的关系，以及)行、#列的关系，一开始我为了方便全填了空关系，结果分析(i)#时，归约完括号内内容后栈是# ( N，输入)，( = )移进，栈变成# ( N )，输入#，此时 top_terminal 是)，查)行#列必须是大于才能触发归约。我填成空关系，程序直接报错。后来补上这一格才通过。

边界#的处理原则可以这样记：分析开始时#必须“让路”给输入串第一个终结符，所以#对其他能出现在句首的终结符是小于；分析结束时，栈里的终结符必须能“收尾”归约掉，所以它们对#是大于。任何在语法上不可能相邻的组合，比如#和)，填空关系没毛病，但不能把所有边界都填空关系。

这也是为什么我建议把表直接写在注释里。调试时对照表格，一秒就能看出是表的问题还是代码的问题。

4.2 单目负号与双目减号的二义性

第二个高发问题：想支持负数输入。表达式-3+5在词法上就是- 3 + 5，但算符优先分析器拿到的是一串终结符，它并不区分单目负号和减法。如果用现有文法，-只作为二元运算符出现在两个操作数之间，分析-3+5时第一个字符就是-，栈里#和-的关系查表，表里可能没有这项，直接报错。

常规做法是在词法阶段就把单目负号改造成另一个终结符，比如UMINUS，然后给文法加一条产生式F -> UMINUS F，并在优先关系表里给UMINUS安排最高优先级。这样做需要同步扩展 FIRSTVT、LASTVT 和表，看起来麻烦，但这是最干净的处理方式。如果你只是做个实验，最简单是暂时不支持负号，或者把负号跟数字粘在一起交给词法处理成负数常量，但这不是通用方案。

4.3 最左素短语范围判错：比较对象要动态更新

第三个坑确实比较容易混：find_handle 该从哪个位置开始？我看到不少同学的实现是从栈顶往下扫，遇到第一个终结符就认为句柄到头了，直接把那个终结符和它下面一段都归约。这样做对简单情况 ok，一到带括号或者连续运算就多归约或漏归约。

核心是记住：句柄的右边界是栈顶，句柄的最右终结符要从栈顶向下找第一个终结符；而句柄的左边界要用向左扫描的方式确定，扫描时比较的对象要动态更新成“当前句柄内最左边的终结符”，而不是一直拿句柄最右终结符当基准。我在 3.2 里给出的实现就是按这个逻辑写的，调试时加几行打印，把 start、top 输出来，很快就能看出问题。

为什么不能固定基准？因为素短语内部的终结符之间关系是大于或等于，一旦遇到小于，就说明已经越过句柄左边界。你要是拿“越界前的终结符”和“句柄最右终结符”比较，很可能表里是空关系或者错误关系。

4.4 词法层面的坑：多位数字、空白字符与标识符

最后一个坑是词法接口的问题。实验中为了省事，常用单个字符i代表任意标识符或数字，测试串也是i+i*i。可一旦你直接把真实输入像10 + 20喂给分析器，程序就会疯掉：字符1、0、空格都不在终结符表里，get_relation 返回 -1，直接报错。

正确做法是在喂给分析器之前做一次记号化：把多位整数读成一个i，把空白字符跳过，把+、*、(、)原样保留作为终结符。这一步不需要用 Lex 之类的工具，手写一个扫描函数就够。换句话说，算符优先分析器只管语法，词法分隔必须在它之前完成。这个接口设计上的认识，能让你后面接真实词法分析器时省很多事。

5. 从实验代码到真正的可用分析器：错误恢复与扩展方向

5.1 优先关系表为空时怎么办：错误检测与恢复

课程实验一般输入都是合法表达式，但如果你想把它做成一个真正的小型计算器前端，错误处理必须补上。最直观的做法：查表返回空关系时，打印出错位置并停止。但真实场景里，一个表达式可能有好几个错，停在一个错上返回，用户改完还得再跑一次，体验很差。

简单的错误恢复可以这样做：遇到空关系时，先放弃当前输入符号，输入指针往前加一，继续分析；同时记录错误次数，超过一定阈值就终止。这种叫 panic mode，优点是实现简单，缺点是可能误报后续一连串错误。稍微好一点的办法是往回弹栈，把栈顶元素弹出，直到重新找到能和当前输入符号建立关系的状态。对这个实验来说，我会建议先把“检测到无关系就报错并定位”做扎实，比盲目恢复更重要。

5.2 把判断语法正确升级为计算表达式的值

如果你不满足于只做语法识别，想顺便把表达式的值算出来，得在归约动作上加语义处理。思路是给每个栈元素多存一个值字段，结构体栈比两个平行数组更清晰：

typedef struct { char symbol; int value; } StackItem;

归约时，根据句柄的形式决定怎么算。比如句柄是N + N，归约时 value 等于左操作数加右操作数；句柄是N * N，value 等于左操作数乘右操作数；句柄是i，value 来自词法阶段给它的整数值；句柄是(N)，value 直接向上传递。这里有个好处：因为算符优先分析已经保证了归约顺序正确，所以语义动作不需要再判断优先级，直接在正确时机执行即可。这也是算符优先分析适合做计算器的原因。

需要提醒的是，如果归约时统一把句柄替换成固定N，你还需要额外记录“这个 N 到底是什么产生式归约出来的”，否则语义动作不知道该执行加法还是乘法。简单做法是在栈元素里加一个枚举字段，标记N_E、N_T、N_F之类的，或者不统一用N，而是按产生式归约成不同非终结符。由于算符优先分析对非终结符名称不敏感，这样做不会影响语法判断。

5.3 支持更多运算符和单目运算的扩展思路

扩展方向也顺着这条线走。想支持幂运算^，注意它的结合性是右结合，意味着同一个运算符连续出现时，左边那个的优先级要低于右边那个，所以优先表里^行^列应该填小于，这和+、*的大于正好相反。这是很容易搞错的地方，很多人直接照抄左结合运算符的关系，结果2^3^2算成了(2^3)^2。

想支持关系运算符、逻辑运算符，做法一样：扩展终结符集合，重算 FIRSTVT 和 LASTVT，填表，然后确认没有冲突。算符优先矩阵会越来越大，但代码本身不用改太多。想支持函数调用f(x)、数组下标a[i]，就要在文法里加入新的产生式，并处理逗号和方括号。算符优先分析在这些场景下依然能用，只是表会变得复杂，这也是为什么真实编译器通常偏向 LR 系算法。

说实话，算符优先分析不是什么高深算法，但它是编译原理课程里最适合自己动手写一遍的内容之一。我做完这个实验后最大的感受是：教材里那张优先表不是凭空来的，而是 FIRSTVT、LASTVT 加三条规则一步步推出来的，你把推演过程亲手走一遍，再去看任何一份网上的代码，都会觉得非常通透。如果你也在做类似的实验，建议别急着抄表或者复制代码，先手算一遍它，再对照着实现主循环，绝对比直接调通一个现成程序收获多得多。