企业官网建设流程全解析

算符优先分析这块，我在读本科的时候就被它绕晕过，后来工作后做表达式解析、简单脚本解释器，又把它捡起来重新啃了一遍，才算是真正吃透了。说实话，算符优先分析是自底向上分析法里最简单直观的一种，它不涉及复杂的状态机构造，也不用算LR(0)项目集族，核心就三个东西：FirstVT、LastVT和算符优先关系表。只要你把这三个东西搞明白，整个分析器的骨架就搭起来了，剩下的就是照着逻辑编码的体力活。

这篇文章我会按照我自己当初做课程设计时的完整思路，把算符优先分析从原理到代码一步一步讲透。里面包含完整的C语言实现，也包含我反复调试后总结的坑和心得。无论你是正在学编译原理、准备课程设计，还是工作中需要写一个简单的表达式求值器，这篇文章都能直接参考。

1. 整体设计与思路拆解

1.1 算符优先分析到底解决什么问题

先明确一下算符优先分析在整个编译前端的定位。词法分析把源程序切成一堆token，语法分析的任务就是根据文法规则，把这些token组装成一棵语法树。自底向上分析就是从输入串开始，不断找到当前句型的“句柄”或者“可归约串”，把它规约成产生式左部的非终结符，直到最后规约成起始符号。

算符优先分析是自底向上分析的一个特例，它重点关注终结符（也就是运算符、括号、标识符这类东西）之间的优先关系。这种方法的灵感其实很接近我们平时算表达式的习惯：先乘除后加减、括号优先级最高。算符优先分析就是把这种“优先级”的判断形式化，用一张二维表来记录任意两个相邻终结符之间是“低于”、“等于”还是“高于”的关系，然后凭借这张表指导栈顶应该继续移进还是开始规约。

它最大的好处是简单、效率高，适合处理表达式类文法，特别是算术表达式、布尔表达式这种运算符密集的语言结构。它的局限性也很明显：能处理的文法比较受限，必须满足算符优先文法的条件，而且它分析出来的往往不是一棵精确的语法树，而是一个“最左素短语”的归约序列，对语义规则的处理不如LR分析那么自然。

我在课程设计里选的文法就是经典的四则运算表达式文法：

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

这里i代表标识符或数字。这个文法很典型，它既包含了左递归和运算符优先级的信息，又是所有算符优先教材都会用的例子，用来说明算法最合适。

1.2 整个程序的功能划分和数据结构设计

写代码之前，我先把程序拆成了几个独立的部分，这样每一步的验证会非常清晰：

1. 输入文法和终结符、非终结符集合；
2. 构造每个非终结符的FirstVT和LastVT集合；
3. 生成算符优先关系表；
4. 用栈 + 优先关系表对输入串执行分析，输出移进/规约动作序列。

数据结构方面，我用了最直观的实现方式。文法产生式用一个结构体数组存储；终结符和非终结符用两个字符数组存；FirstVT和LastVT用二维布尔数组表示，每个非终结符对应一个数组，记录哪些终结符属于它的集合。算符优先关系表用二维矩阵，行和列都是终结符（加上#），每个单元格存放一个字符：<、=、>或者空。

我见过有人用哈希表来存终结符到索引的映射，但在这个场景下没必要，文法终结符最多十几个，线性扫描就足够了，代码可读性反而更好。这个设计思路也贯穿了整个程序：能不用复杂数据结构的地方，绝不用复杂的。

1.3 为什么我选择用C语言实现

选C语言是为了贴近编译原理课程本身的气质。算符优先分析本来就是对字符流做处理，C语言的字符数组、指针操作在这种场景下非常顺手，代码可以直接和文法的公式对应起来。另外，C语言没有太多语法糖，写出来的逻辑非常直白，读者如果拿着代码去对照算法流程，基本是一一对应的，这对理解算法本质很有帮助。

如果读者想用Python、Java也很容易移植，核心逻辑和数据结构关系不大，照抄思路就行。我代码里只用了标准库，没有任何平台相关的东西，任何带C编译器的环境都能直接跑起来。

2. 核心概念与原理深挖

2.1 终结符优先关系的定义

算符优先分析的核心是终结符之间的三种关系。假设a和b是两个终结符，它们的优先关系是这样定义的：

• 如果产生式中有形如...a b...或者...a V b...的右部（其中V是非终结符或为空），我们说 a 和 b 的优先级“相等”，记作 a = b；
• 如果有形如...a V...的右部，且 b 属于 FirstVT(V)，那说明 a 之后可以出现以 b 开头的终结符串，我们记作 a < b；
• 如果有形如...V b...的右部，且 a 属于 LastVT(V)，那说明 a 是某个非终结符派生串的最后一个终结符，记作 a > b。

这里要特别注意：这个“优先关系”并不是数学意义上的大小关系。“a < b”表示a的优先级低于b，也就是说，当分析栈栈顶是a、下一个输入符号是b的时候，应该做“移进”，让b先进栈，因为b的优先级更高，要先被处理。反过来“a > b”表示a的优先级高于b，栈顶的a以及它能形成的可归约串应该先被规约。这个逻辑和“乘除先于加减”的直觉是完全一致的。

等号关系是最容易理解错的。它不是表示两个算符的优先级相同，而是表示文法中这两个终结符可能直接相邻出现，或者中间只隔了一个非终结符。典型的例子是括号对(和)，在有产生式F -> ( E )的文法中，(=)是成立的，但我们绝不会说左括号和右括号的优先级相等。一切判定都必须回到文法产生式本身，不要凭直觉套“乘法优先于加法”这种经验，否则优先生成表会出大问题。

2.2 FirstVT和LastVT集合怎么算

FirstVT和LastVT贯穿整个算法，必须先把它们搞定。

FirstVT(P)的定义是：从P出发经过一步或多步推导，得到的句型中，最开头那个终结符的集合。更严谨地说：

• 若产生式P -> a...或P -> Q a...，则 a 属于 FirstVT(P)；
• 若产生式P -> Q...，则 FirstVT(Q) 中的元素全部属于 FirstVT(P)。

LastVT(P)的定义对称：从P出发推导得到的句型中，最末尾那个终结符的集合。

• 若产生式P -> ...a或P -> ...a Q，则 a 属于 LastVT(P)；
• 若产生式P -> ...Q，则 LastVT(Q) 中的元素全部属于 LastVT(P)。

理解这两个集合的关键是：它们是在回答“一个非终结符的内部，从两端看出去，能碰到哪些终结符”。FirstVT关心“开头”，LastVT关心“结尾”。

求法上，我推荐用“反复迭代直到不动点”的方式，就是初始化之后，不停地遍历所有产生式，把能推导出的终结符都塞进集合，直到某一次遍历后集合不再变化为止。这种算法容易实现、不容易出错，比用栈做深度优先遍历更直观。对于文法规模不大的场景，迭代次数根本不用担心性能问题。

这里强烈建议读者自己手工推一遍。找一张纸，写出所有产生式，先画出每个非终结符的FirstVT和LastVT的初始集合，然后一轮一轮地补充。你会发现这个过程跑两三遍就收敛了，而且对后面理解代码大有帮助。

2.3 从集合到算符优先关系表的建立

有了FirstVT和LastVT，建表就是按规则填空的过程。

对每一条产生式A -> X1 X2 ... Xn（Xi是终结符或非终结符），做如下检查：

• 如果Xi和Xi+1都是终结符，则 Xi = Xi+1；
• 如果Xi是终结符、Xi+1是非终结符，则对FirstVT(Xi+1)中的每个终结符a，设 Xi < a；
• 如果Xi是非终结符、Xi+1是终结符，则对LastVT(Xi)中的每个终结符a，设 a > Xi+1；
• 如果Xi是终结符、Xi+1是非终结符、Xi+2是终结符，则 Xi = Xi+2；
• 如果Xi是非终结符、Xi+1是终结符、Xi+2是非终结符，则对LastVT(Xi)中每个a，设 a > Xi+1，同时对FirstVT(Xi+2)中每个b，设 Xi+1 < b。

实现的时候只需要最后两条稍微细心一点，容易漏掉三符号组合的情况。

同时，还要给输入串的首尾加上#限定符，并规定# <所有首终结符，# >所有尾终结符，# = #。

做完这些，就得到一张二维表，表里每个格子的取值只有四种：<、=、>、空。如果某两个终结符之间出现既小于又大于的冲突，那这个文法就不是算符优先文法，不能直接用这个算法。这个冲突检查非常关键，实际写代码时也必须在建表过程中就检测出来，而不是等分析阶段才发现异常。

3. 完整代码实现与走查

3.1 程序的整体框架

先给一个总体的代码框架，后面我会逐段解释每个函数的实现思路。

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_PROD 100 #define MAX_SYM 100 #define MAX_TERM 20 typedef struct { char left; // 产生式左部非终结符 char right[10]; // 产生式右部字符串，如 "E+T" } Production; Production prods[MAX_PROD]; int prodCount = 0; char terminals[MAX_TERM]; // 终结符集合 int termCount = 0; char nonTerminals[MAX_SYM]; // 非终结符集合 int nonTermCount = 0; int firstVT[MAX_SYM][MAX_SYM]; // firstVT[非终结符索引][终结符索引] int lastVT[MAX_SYM][MAX_SYM]; // lastVT[非终结符索引][终结符索引] char priorityTable[MAX_TERM+1][MAX_TERM+1]; // 算符优先关系表，最后一个行/列是 # // 以下为函数声明 void parseGrammar(); void computeTerminalsAndNonTerminals(); void computeFirstVT(); void computeLastVT(); void buildPriorityTable(); int getTermIndex(char c); int getNonTermIndex(char c); void printFirstLastVT(); void printPriorityTable(); void analyzeExpression(char *expr); void showAnalysisSteps(char *expr);

这个结构把数据和逻辑彻底分开，后面扩展分析动作记录、语法树构建都方便。

3.2 文法读入与符号集合提取

首先需要读入文法。我当初做课程设计直接让用户在程序里输入产生式数量和各产生式，你也可以改成从文本文件读取，逻辑不变。下面是关键代码：

void parseGrammar() { printf("请输入产生式数量："); scanf("%d", &prodCount); getchar(); // 吸收换行符 for (int i = 0; i < prodCount; i++) { printf("请输入第 %d 条产生式（格式：左部->右部，如 E->E+T）：", i + 1); char buffer[50]; fgets(buffer, sizeof(buffer), stdin); buffer[strcspn(buffer, "\n")] = 0; // 去掉末尾换行 // 解析"->" size_t arrow = strstr(buffer, "->") - buffer; prods[i].left = buffer[0]; strcpy(prods[i].right, buffer + arrow + 2); } computeTerminalsAndNonTerminals(); }

这个解析方式比较原始，但足够用于课程设计。这里有个小细节，strcspn用来去掉fgets读到的换行符，很多人第一次写的时候会漏掉，导致后面所有符号提取都出错。

接着是终结符和非终结符的提取。规则很清晰：产生式左部一定是非终结符；右部中大写字母是非终结符，其他可打印字符（运算符、括号、i、#等）都是终结符。

void computeTerminalsAndNonTerminals() { termCount = 0; nonTermCount = 0; for (int i = 0; i < prodCount; i++) { char L = prods[i].left; if (!isInArray(nonTerminals, nonTermCount, L)) { nonTerminals[nonTermCount++] = L; } for (int j = 0; prods[i].right[j] != '\0'; j++) { char c = prods[i].right[j]; if (c >= 'A' && c <= 'Z') { if (!isInArray(nonTerminals, nonTermCount, c)) { nonTerminals[nonTermCount++] = c; } } else { if (!isInArray(terminals, termCount, c)) { terminals[termCount++] = c; } } } } // 加入结束符 # if (!isInArray(terminals, termCount, '#')) { terminals[termCount++] = '#'; } }

这里isInArray就是一个简单的线性查找辅助函数：

int isInArray(char *arr, int len, char c) { for (int i = 0; i < len; i++) { if (arr[i] == c) return 1; } return 0; }

我没有显式区分文法符号是终结符还是非终结符，而是统一用“大写字母=非终结符，其他=终结符”这个约定。这是编译原理里最常见的记号习惯，推荐大家沿用。

3.3 FirstVT与LastVT的迭代计算

FirstVT集合用firstVT[nonTermIndex][termIndex]来表示，取值为1表示该终结符属于对应非终结符的FirstVT。

初始化和迭代计算的完整函数：

void computeFirstVT() { memset(firstVT, 0, sizeof(firstVT)); // 初始化：显式出现在右部开头的终结符 for (int i = 0; i < prodCount; i++) { char L = prods[i].left; char firstChar = prods[i].right[0]; int Lidx = getNonTermIndex(L); if (firstChar >= 'A' && firstChar <= 'Z') { // 形如 P -> Q a ... / P -> Q ... // 这一轮不做直接的终结符添加，但需要把 L 和 Q 建立依赖关系 // 这里采用多次迭代的方式，不需要显式建依赖图 } else { int Tid = getTermIndex(firstChar); firstVT[Lidx][Tid] = 1; } // 形如 P -> Q a ... 中的 a 也属于FirstVT(P) if (firstChar >= 'A' && firstChar <= 'Z' && prods[i].right[1] != '\0') { char secondChar = prods[i].right[1]; if (!(secondChar >= 'A' && secondChar <= 'Z')) { int Lidx2 = getNonTermIndex(L); int Tid2 = getTermIndex(secondChar); firstVT[Lidx2][Tid2] = 1; } } } // 迭代直到不动点 int changed = 1; while (changed) { changed = 0; for (int i = 0; i < prodCount; i++) { char L = prods[i].left; char firstChar = prods[i].right[0]; int Lidx = getNonTermIndex(L); if (firstChar >= 'A' && firstChar <= 'Z') { // 若 P -> Q ...，则 FirstVT(Q) ⊆ FirstVT(P) int Qidx = getNonTermIndex(firstChar); for (int t = 0; t < termCount; t++) { if (firstVT[Qidx][t] && !firstVT[Lidx][t]) { firstVT[Lidx][t] = 1; changed = 1; } } } } } }

LastVT的求法完全对称，只不过要换成右部末尾的符号。

void computeLastVT() { memset(lastVT, 0, sizeof(lastVT)); for (int i = 0; i < prodCount; i++) { char L = prods[i].left; int len = strlen(prods[i].right); char lastChar = prods[i].right[len-1]; int Lidx = getNonTermIndex(L); if (!(lastChar >= 'A' && lastChar <= 'Z')) { int Tid = getTermIndex(lastChar); lastVT[Lidx][Tid] = 1; } // 形如 P -> ... a Q 中的 a 也属于 LastVT(P) if ((lastChar >= 'A' && lastChar <= 'Z') && len >= 2) { char secondLast = prods[i].right[len-2]; if (!(secondLast >= 'A' && secondLast <= 'Z')) { int Lidx2 = getNonTermIndex(L); int Tid2 = getTermIndex(secondLast); lastVT[Lidx2][Tid2] = 1; } } } int changed = 1; while (changed) { changed = 0; for (int i = 0; i < prodCount; i++) { char L = prods[i].left; int len = strlen(prods[i].right); char lastChar = prods[i].right[len-1]; int Lidx = getNonTermIndex(L); if (lastChar >= 'A' && lastChar <= 'Z') { int Qidx = getNonTermIndex(lastChar); for (int t = 0; t < termCount; t++) { if (lastVT[Qidx][t] && !lastVT[Lidx][t]) { lastVT[Lidx][t] = 1; changed = 1; } } } } } }

代码虽然有点长，但逻辑非常线性。每次迭代如果集合没有变化就停止，这就是经典的“不动点算法”。这里有个小优化：迭代没有必要超过非终结符个数+1次，因为每一轮至少新增一个元素（如果还有可能新增的话），但这属于锦上添花，不写也不会错。

3.4 算符优先关系表的构建

优先级表我用二维字符数组priorityTable，行和列都按terminals数组中的顺序排列，最后一列（或最后一行）是#。

建表前先把所有格子初始化为空字符：

void buildPriorityTable() { memset(priorityTable, 0, sizeof(priorityTable)); for (int i = 0; i < prodCount; i++) { char *right = prods[i].right; int len = strlen(right); for (int j = 0; j < len - 1; j++) { char a = right[j]; char b = right[j+1]; // 情形1：a b 都是终结符 if (!(a >= 'A' && a <= 'Z') && !(b >= 'A' && b <= 'Z')) { setRelation(a, b, '='); } // 情形2：a是终结符，b是非终结符 if (!(a >= 'A' && a <= 'Z') && (b >= 'A' && b <= 'Z')) { int bidx = getNonTermIndex(b); for (int t = 0; t < termCount; t++) { if (firstVT[bidx][t]) { setRelation(a, terminals[t], '<'); } } // 情形4：a 终结符，b 非终结符，c 终结符 => a = c if (j + 2 < len) { char c = right[j+2]; if (!(c >= 'A' && c <= 'Z')) { setRelation(a, c, '='); } } } // 情形3：a非终结符，b终结符 if ((a >= 'A' && a <= 'Z') && !(b >= 'A' && b <= 'Z')) { int aidx = getNonTermIndex(a); for (int t = 0; t < termCount; t++) { if (lastVT[aidx][t]) { setRelation(terminals[t], b, '>'); } } // 情形5：a非终结符，b终结符，c非终结符 if (j + 2 < len && (right[j+2] >= 'A' && right[j+2] <= 'Z')) { int cidx = getNonTermIndex(right[j+2]); for (int t = 0; t < termCount; t++) { if (lastVT[aidx][t]) { setRelation(terminals[t], b, '>'); } } for (int t = 0; t < termCount; t++) { if (firstVT[cidx][t]) { setRelation(b, terminals[t], '<'); } } } } } } buildSharpRelations(); checkConflicts(); }

setRelation和checkConflicts是关键辅助函数。setRelation负责写入关系并检查是否冲突：

void setRelation(char a, char b, char rel) { int ia = getTermIndex(a); int ib = getTermIndex(b); if (ia == -1 || ib == -1) { printf("错误：找不到终结符 %c 或 %c\n", a, b); return; } char old = priorityTable[ia][ib]; if (old == 0) { priorityTable[ia][ib] = rel; } else if (old != rel) { printf("冲突：%c 与 %c 之间同时存在 %c 和 %c 两种关系\n", a, b, old, rel); printf("文法不是算符优先文法！\n"); // 这里可以选择直接 exit(1) 或记录下来继续执行 } }

buildSharpRelations用来补充#的关系。要遍历所有终结符：

• 对所有终结符a（除了#），令# < a；
• 对所有终结符a（除了#），令a > #；
• 令# = #。

注意这两条规则不能漏，否则分析输入串的首尾时会出现“找不到关系”的错误。

void buildSharpRelations() { for (int t = 0; t < termCount; t++) { if (terminals[t] == '#') continue; setRelation('#', terminals[t], '<'); setRelation(terminals[t], '#', '>'); } setRelation('#', '#', '='); }

3.5 分析器主流程：移进-规约的循环

分析器主流程用两个数组模拟栈：一个是符号栈，存分析过程中出现的符号；一个是符号类型栈（终结符/非终结符）。真正的算符优先分析不依赖非终结符的具体值，因此栈里只需要保存终结符信息用于查表，但为了输出好看的步骤序列，我还是把非终结符也一起存了。

核心逻辑是这样：

void analyzeExpression(char *expr) { char stack[MAX_SYM]; char stackType[MAX_SYM]; // 'T' 终结符，'N' 非终结符 int top = 0; stack[top] = '#'; stackType[top] = 'T'; int ip = 0; // 输入指针 char input[MAX_SYM]; strcpy(input, expr); strcat(input, "#"); printf("%-20s %-20s %s\n", "步骤", "栈内容", "输入串"); printf("%-20s %-20s %s\n", "0", "#", input); int step = 1; while (1) { // 取栈顶终结符 a int k = top; while (stackType[k] != 'T') { k--; } char a = stack[k]; // 当前输入符号 b char b = input[ip]; // 查优先表 int ia = getTermIndex(a); int ib = getTermIndex(b); if (ia == -1 || ib == -1) { printf("输入串包含未定义符号，出错！\n"); return; } char rel = priorityTable[ia][ib]; if (rel == '<' || rel == '=') { // 移进 top++; stack[top] = b; stackType[top] = 'T'; ip++; printf("%-20d %-20s %s\n", step, stack, input + ip); step++; } else if (rel == '>') { // 规约：找到最左素短语的边界 // 从栈顶往下找，找到第一个使得 sj-1 < sj 的位置 int j = top; char sj = stack[j]; while (1) { // 找到左边第一个终结符 int jm = j - 1; while (jm >= 0 && stackType[jm] != 'T') { jm--; } if (jm < 0) { printf("规约错误：无法找到素短语左边界\n"); return; } char sjm = stack[jm]; int ijm = getTermIndex(sjm); int isj = getTermIndex(stack[j]); if (priorityTable[ijm][isj] == '<') { // 找到了左边界 break; } j = jm; } // 从 j 到 top 的内容是最左素短语，把它规约成一个非终结符 // 规约时，弹出从 j 到 top 的所有符号，压入一个非终结符 N top = j - 1; top++; stack[top] = 'N'; stackType[top] = 'N'; printf("%-20d %-20s %s\n", step, stack, input + ip); step++; } else { printf("错误：%c 与 %c 之间没有定义优先关系\n", a, b); return; } // 判断结束条件：栈中为 # N #，输入只剩 # if (stack[top] == 'N' && top >= 2 && stack[top-1] == '#' && stack[1] == 'N' && stack[0] == '#' && input[ip] == '#') { // 更准确的判断：栈内容恰好是 # N # printf("分析成功！\n"); return; } // 避免死循环 if (input[ip] == '#' && top == 0 && stack[top] == '#') { printf("分析失败！\n"); return; } } }

这里最需要小心的是找到“最左素短语”的循环。为什么是从栈顶往左找，找到第一个<关系就停？因为算符优先分析本质上时在“最右推导的逆过程”，而栈中终结符的关系从底到顶是“<、=、...、=、>”这样一个模式，<到>之间的内容恰好构成一个可规约串（也就是素短语）。这个循环从栈顶开始往下扫，遇到<就停，停下的位置就是素短语的左边界。

这段代码里还把规约后的非终结符统一标记为N，在真正的编译器中这里要用查产生式表，把匹配的产生式保存下来，以便后续构造语法树或翻译成中间代码。本文为了突出算符优先分析主流程，省掉了这个细节，但流程本身是完整的。

3.6 打印函数和辅助函数

为了让程序可用，我加了两个打印函数：一个打印FirstVT/LastVT集合，一个打印优先关系表。

void printFirstLastVT() { printf("\n=== FirstVT 集合 ===\n"); for (int i = 0; i < nonTermCount; i++) { printf("FirstVT(%c) = { ", nonTerminals[i]); for (int t = 0; t < termCount; t++) { if (firstVT[i][t]) { printf("%c ", terminals[t]); } } printf("}\n"); } printf("\n=== LastVT 集合 ===\n"); for (int i = 0; i < nonTermCount; i++) { printf("LastVT(%c) = { ", nonTerminals[i]); for (int t = 0; t < termCount; t++) { if (lastVT[i][t]) { printf("%c ", terminals[t]); } } printf("}\n"); } } void printPriorityTable() { printf("\n=== 算符优先关系表 ===\n"); printf(" "); for (int i = 0; i < termCount; i++) { printf("%4c", terminals[i]); } printf("\n"); for (int i = 0; i < termCount; i++) { printf("%4c", terminals[i]); for (int j = 0; j < termCount; j++) { if (priorityTable[i][j] == 0) { printf("%4c", ' '); } else { printf("%4c", priorityTable[i][j]); } } printf("\n"); } }

getTermIndex和getNonTermIndex就是线性查找，返回索引，找不到返回-1。

3.7 main函数的组织

main函数把前面的模块串起来，流程很清晰：

int main() { parseGrammar(); computeFirstVT(); computeLastVT(); printFirstLastVT(); buildPriorityTable(); printPriorityTable(); char expr[MAX_SYM]; printf("请输入待分析表达式（如 i+i*i#，注意不要带空格）："); scanf("%s", expr); analyzeExpression(expr); return 0; }

实际操作中，建议把分析过程封装成可以多次调用的函数，方便测试多个表达式。我的课程设计里加了一个简单的菜单循环，用户可以不停地输入表达式查看分析过程，不需要每次重启程序。这种小改进虽然没有技术难度，但演示效果会好很多。

4. 完整实例演示：从文法到分析结果

4.1 手工推导一遍 FirstVT 和 LastVT

为了验证程序的正确性，我先把上面的文法手工推一遍。文法如下：

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

终结符集合为{ +, -, *, /, (, ), i, # }，非终结符集合为{ E, T, F }。

先推FirstVT：

• 从E -> E+T可知，+属于FirstVT(E)（因为形如“E +”不匹配，但E -> E + T中右部第一个字符是E，第二个字符是+，非终结符后紧跟终结符，所以+属于FirstVT(E)）；
• 同理，E -> E-T使-属于FirstVT(E)；
• 从E -> T可知，FirstVT(T) ⊆ FirstVT(E)；
• 从T -> T*F可知，*属于FirstVT(T)；
• 从T -> T/F可知，/属于FirstVT(T)；
• 从T -> F可知，FirstVT(F) ⊆ FirstVT(T)；
• 从F -> (E)可知，(属于FirstVT(F)；
• 从F -> i可知，i属于FirstVT(F)。

所以初始一轮之后，FirstVT(F) ={ ( , i }，FirstVT(T) ={ *, / } ∪ FirstVT(F) = { *, /, (, i }，FirstVT(E) ={ +, - } ∪ FirstVT(T) = { +, -, *, /, (, i }。

再推LastVT：

• 从E -> E+T可知，+属于LastVT(E)吗？注意，右部最后一个字符是T，是E -> ... + T的形式，此时要看的是T的LastVT。但同一产生式的右部第二个字符是+、最后一个字符是T，属于“非终结符结尾、前面是终结符”的情形，因此+也属于LastVT(E)。同理-属于LastVT(E)。
• 从E -> T可知，LastVT(T) ⊆ LastVT(E)；
• 从T -> T*F可知，*属于LastVT(T)，且LastVT(F) ⊆ LastVT(T)；
• 从T -> T/F可知，/属于LastVT(T)；
• 从F -> (E)可知，)属于LastVT(F)；
• 从F -> i可知，i属于LastVT(F)。

所以LastVT(F) ={ ), i }，LastVT(T) ={ *, /, ), i }，LastVT(E) ={ +, -, *, /, ), i }。

这些结果和我们程序跑出来应该完全一致。读者可以拿这些值验证自己的手工计算。

4.2 手工建表并验证程序输出

按照之前描述的建表规则，我手工列出几个典型关系：

• 对于产生式E -> E+T：右部E、+、T三符号，+是终结符、后面是非终结符T，因此+ < FirstVT(T)，即+ < * 、+ < / 、+ < ( 、+ < i；同时LastVT(E) > +，即+, -, *, /, ), i > +。
• 对于产生式F -> (E)：右部(、E、)三符号，（ 是终结符）、E是非终结符、）是终结符，因此( = )；同时( < FirstVT(E)即( < + 、- 、* 、/ 、( 、i；以及LastVT(E) > )即+, -, *, /, ), i > )。

这些关系在分析表达式时会产生非常直观的效果。比如遇到i + i * i，当栈顶是i、输入是+时，查表发现i > +，于是先调i本身，生成N；接着栈顶终结符变成+，输入是i，查表发现+ < i，于是移进i……整个过程中，优先级高的乘除运算会先被归约，完全符合我们期望的运算顺序。

4.3 分析过程推演：i+i*i 的完整步骤

用这个文法分析i+i*i，手工推演步骤如下：

初始：栈#，输入i+i*i#。

1. 查表# < i，移进i，栈# i，输入+i*i#；
2. 查表i > +，规约i为N，栈# N，输入+i*i#；
3. 查表# < +（因为栈顶终结符是#，输入是+），移进+，栈# N +，输入i*i#；
4. 查表+ < i，移进i，栈# N + i，输入*i#；
5. 查表i > *，规约i为N，栈# N + N，输入*i#；
6. 查表+ < *，移进*，栈# N + N *，输入i#；
7. 查表* < i，移进i，栈# N + N * i，输入#；
8. 查表i > #，规约i为N，栈# N + N * N，输入#；
9. 查表* > #，规约N * N为N，栈# N + N，输入#；
10. 查表+ > #，规约N + N为N，栈# N，输入#；
11. 栈内容恰好是# N #，输入只剩#，分析成功。

这个序列在程序里会逐步打印出来。注意步骤9中，我们并没有严格按照“素短语是最左的”来命名，但算符优先分析的实际归约对象就是最左素短语，这个归约序列对应语法树的构建层级。你在运行程序时，如果输出和这个序列一致，说明实现是正确的基础版本。

5. 常见问题与调试技巧实录

5.1 我踩过的几个坑

第一个坑：fgets读到换行符，导致所有符号提取全部错位。这个问题看起来很低级，但非常容易踩。我第一次写完代码，运行后发现非终结符列表里多了一大堆奇怪的字符，排查了整整半小时才发现是换行符没有去掉。建议所有用fgets读字符串的程序，立刻跟一句buffer[strcspn(buffer, "\n")] = 0;，养成习惯。

第二个坑：算符优先关系表冲突检测没有放到建表过程中。一开始我只在建表完成后检查冲突，导致定位问题很困难。后来把冲突检查直接塞进setRelation里，一旦发现同一对终结符存在两种关系，立刻打印是哪两个终结符、哪两条产生式引发的冲突，调试效率提升了一个数量级。

第三个坑：#关系漏写。有一版代码忘了设置#和所有终结符的<、>关系，结果分析任何表达式都在第一步就报错。强烈建议建表完成后，先打印一次完整的关系表，对照教材手工检查几个关键位置，比如# < i、( = )、i > +，避免这种低级失误。

第四个坑：分析结束判断条件写错。最开始我用top == 0 && stack[top] == '#' && input[ip] == '#'作为成功条件，结果发现表达式分析到一半就误判成功。因为栈顶非终结符没参与判断，# N #的中间内容没有被检查。后来改成同时判断stack[top] == 'N'和栈中只有三个元素，才稳定下来。

5.2 调试时的小工具技巧

调试这类程序，最简单有效的方法是打印中间状态。我在每个关键函数（FirstVT计算、LastVT计算、建表、分析主循环）都加了可选的打印开关，用宏控制。比如：

#define DEBUG_FIRSTVT 1

调试阶段打开，验证函数输出正确后就关掉，避免刷屏。

分析主循环的打印我建议保留，因为这是课程设计演示的核心输出，评审老师一定会看。打印格式上，栈内容和输入串要对齐，步骤编号递增，这样看起来非常清晰。

另外有个很实用的技巧：准备一组边界测试用例。我每次改完代码都会测这组用例。

这些用例覆盖了基本路径和典型的错误路径，能有效检验分析器主循环对各种情况的处理。注意，算符优先分析器在语法错误检测上的能力有限，有些错误（比如缺右括号）可能不会在第一步就被发现，而是会在后面的规约或查表阶段暴露，这属于正常现象，不必惊慌。

5.3 后续扩展方向

算符优先分析器做出来后，往上扩展的方向很多。最简单的扩展是为规约动作关联语义规则，比如每规约出一个表达式，就执行一次相应的加减乘除计算，这样就把“分析器”升级成了一个“表达式计算器”。再进一步，可以在规约时构建语法树节点，为后续的中间代码生成做准备。

如果对算法本身有更高追求，可以研究一下如何从算符优先分析表自动构造一个有限自动机，或者把它和递归下降分析结合，形成一个混合型的语法分析方案。不过这些都是后话了，先把基础版本的流程跑通，再谈扩展。

我在做这个课程设计的时候，最大的体会是：编译原理的很多算法，看起来公式一大堆，但真正动手写代码之后，才发现核心逻辑就那么几行。关键是要理解“为什么要这么做”，而不是背住”怎么做”。算符优先分析本身就是把“人类的运算优先级直觉”形式化，你一旦体会到这一点，整个算法就不再是死板的规则集合，而是一个有逻辑脉络的体系。希望这篇文章能帮你顺利跨过这道坎。