开头说到编译原理这门课算符优先分析算法应该是很多人在语法分析这一章第一次真正动手写代码的地方。当年我也是从“文法、推导、归约到底都是啥”的懵圈状态过来的到现在还能记得调试优先关系表时的那种抓狂感——明明照着书上的算法写的就是跑不出正确结果。这篇文章准备把我做算符优先分析算法C语言实现时的完整思路、数据结构设计、关键代码逻辑以及踩过的坑全部倒出来帮你把这个实验真正吃透不管是正在为课程设计发愁的同学还是想复习语法分析这块知识的开发者都应该能从里面拿到一些能直接用的东西。这篇内容不会只贴一段代码就完事。我会从算法本身在语法分析中的地位讲起把 FirstVT、LastVT、优先关系表、移进归约循环这几个核心环节一个一个拆开用 C 语言的具体实现把每个环节落到位。算符优先算法虽然不像 LR 分析那样通用但它对于表达式类文法来说足够直观而且代码量适中非常适合作入门级的语法分析实验理解了它你再看 SLR、LR 这些更复杂的分析算法时思路会顺很多。1. 算符优先分析到底在解决什么问题1.1 语法分析家族里的“偏科生”语法分析是编译器的第二个阶段输入是词法分析产出的 token 流输出是一棵语法树或者至少判断出“这个句子符不符合文法”。演算法大体分成两类自顶向下和自底向上。自顶向下就是从这里推导出去递归下降和 LL(1) 属于这一类自底向上的思路正好反过来从输入串逐步归约到文法的开始符号LR 和算符优先都属于这一类。算符优先分析在自底向上的家族里算是一个“偏科生”。它的偏科体现在它只关心终结符也就是实际出现在表达式里的运算符和括号之类的符号之间的优先关系不关心非终结符具体是怎么推导出来的。你拿到一个文法之后先不用构造完整的 LR 状态机只需要算出每对终结符之间到底是“移进优先”还是“归约优先”然后依据这些关系驱动分析过程。这种设计带来了两个直接好处。第一实现简单。一张二维优先关系表加一个栈就能完成大部分分析工作代码量远小于 SLR 或 LR 分析器的自动机构建部分。第二效率不差。算符优先分析跳过了许多无用的归约尝试直接通过优先关系定位句柄运行时的判断非常快。那它的限制也很明显。算符文法每个产生式右部不能出现相邻的非终结符只是一类很窄的文法子集不是所有上下文无关文法都能用。比如赋值语句、表达式、条件判断这类结构化比较强的语言成分没问题但遇到类型声明、继承关系这类文法算符优先就力不从心了。所以你在很多教材里看到算符优先分析都是拿表达式文法做例子这不是顺手选的而是这个算法本身就擅长处理“运算符夹着操作数”的结构。1.2 优先关系的直觉谁先谁后算符优先的核心思想其实一句话就能讲清楚在分析过程中当栈顶出现一个终结符 a而输入缓冲区头部是终结符 b 的时候我们需要决定是继续把 b 压入栈移进还是用栈顶的某个产生式进行归约。这个决定就依赖 a 和 b 之间的优先关系。如果 a 的优先级低于 b说明 b 后面的运算符应该先被处理这时候移进如果 a 超过了 b说明栈顶这一段的运算符可以先归约了这时就去栈里找句柄进行归约。这里必须单独提一下优先关系里的“等于”它不等于数学意义上的相等。a b 表示这两个终结符在文法中同时出现在某个产生式的相邻位置比如 E → E T 里 和 T或者说 T 推出的终结符之间的那种关系。它实际上说明这两个符号天然处于同一个表达式中归约时它们会一起被处理。很多初学者在这里踩坑把 理解成“用户定义的操作符相等”后面写代码就全乱了。研究这个算法的时候你会发现它的整个数据流非常规律文法 → FirstVT/LastVT 集合 → 优先关系表 → 分析栈。每个环节都是下一个环节的输入我后面整个 C 语言实现也会严格按照这条流水线来组织代码这样做的好处很明显——每一步都独立可测出了问题你能快速定位到是哪个环节算错了。1.3 实验目标跑通一个表达式文法我在课程实验里选择了一个经典的算术表达式文法来做 C 语言实现为了能验证括号和多重运算文法稍微做了一点增强E → E T E → T T → T * F T → F F → (E) F → i这里的 i 表示标识符或者整数常量。实际上算符优先实验最常见的做法是把 i 简化为一个终结符让整个分析过程不用去区分 identifier 和 number直接把输入读成以 i 为操作数的表达式串。比如输入 ii*i正确的分析结果应该是接受这个句子并且每一步归约都能套进上面的产生式里。我后面会基于这个例子展开讲。先记住这个文法后面说 FirstVT、LastVT、优先关系表构造的时候都会拿它来举例。2. 先把两个关键集合搞定FirstVT 和 LastVT2.1 集合定义别光背公式要看它到底收集了什么FirstVT(P) 的定义是从 P 出发经过一步或多步推导能够出现在句型的第一个位置上的终结符集合。这里有个容易混淆的点FirstVT 只看终结符非终结符会被跳过直到遇到终结符为止。举个例子文法里有 F → (E)那么从 F 出发一步推导得到 (E)这个字符串的第一个符号就是终结符 (所以 ( 属于 FirstVT(F)。如果推出来的第一个符号是非终结符就要继续看那个非终结符的 FirstVT把这些终结符也吸收进来。LastVT(P) 的定义对称从 P 出发经过一步或多步推导能够出现在句型最后一个位置上的终结符集合。F → (E) 里句型的最后一位是 E它本身是非终结符所以需要继续求 E 的 LastVT把 E 能推出的句型末尾终结符都收进来。比如 E 能推出 ET末尾是 T而 T 的 LastVT 里有 * 和 i所以 * 和 i 也会进入 F 的 LastVT。很多网上的代码为了省事直接把 FirstVT 和 LastVT 用最简单的规则硬算。这对小文法问题不大但对稍复杂的文法就很容易漏项。我建议不管实验要求多简单都按书上的迭代算法来实现自底向上逐层扫描产生式直到集合不再变化为止。2.2 数据结构设计集合用什么存C 语言里表示集合有好几种方式我的选择是用一个二维布尔数组来表示终结符集。具体做法是先给所有终结符和非终结符编个号从 0 开始。声明一个 int firstvt[非终结符数量][终结符数量]数组元素为 0 或 1。firstvt[下标][终结符编号] 1 表示该终结符属于该非终结符的 FirstVT 集合。为什么不用链表因为这里集合的运算无非是“并入某个终结符”和“判断某个终结符在不在”布尔数组这两项操作都是 O(1)而且排查问题时打印数组比遍历链表好看太多了。非终结符数量在实验文法里通常不超过 10 个终结符也不多开个 20x20 的数组足够用完全不存在空间问题。整个实现里你会反复用到“某个符号是不是终结符”这个判断。我建议在读取文法之后立刻构建一个终结符数组并给每个终结符分配唯一编号配一个 isTerminal[] 布尔数组。这样后面算优先表和处理分析栈的时候就顺手了。// 符号表数据结构定义 #define MAX_SYMBOL 32 #define MAX_PROD 20 typedef struct { char lhs; // 产生式左部 char rhs[8][MAX_SYMBOL]; // 产生式右部这里简化记录 int rhsCount; } Production;这里我只列了基础的数据结构思路真正实现时可以直接用二维字符数组保存产生式左部单独存一个字符右部按字符数组处理倒也直观。等后面代码量大了你会发现定义清晰的数据结构比任何算法技巧都管用。2.3 迭代求 FirstVT 的代码逻辑书上的迭代算法大致是若产生式形如 P → a...把 a 放入 FirstVT(P)。若产生式形如 P → Q a...把 a 放入 FirstVT(P)并且把 FirstVT(Q) 中的全部终结符加入 FirstVT(P)。重复扫描所有产生式直到所有集合都不再变化。第 1 条说的是直接从终结符开头的情况。第 2 条说的是左部非终结符开头但后面的终结符不能忽略同时还要继承左部那个非终结符的 FirstVT。这里有个细节第一次写很容易漏第 2 条里继承 FirstVT(Q) 的时候要循环处理因为 Q 的 FirstVT 可能是这一轮才刚被更新的。所以正确写法是用一个 flag 标记本轮是否有集合被修改如果有就再来一轮扫描直到完全没有变化才停止。用 C 语言实现这个迭代逻辑其实很直接外层 while(modified)内层遍历所有产生式对每个产生式检查右部第一个字符。如果是终结符直接置位如果是非终结符看右部第二个字符假设存在是否为终结符如果是则置位同时把该非终结符的整个 FirstVT 行拷贝过来。LastVT 的算法完全对称只需要把“开头”换成“结尾”“第一个”换成“最后一个”然后扫描产生式右部时从右往左看。写代码的时候可以复制 FirstVT 的函数再改方向但要小心别把边界条件改错尤其是右部只有一个字符的情况。3. 构造优先关系表三条规则走天下3.1 三条规则背后的逻辑有了 FirstVT 和 LastVT 之后构造优先关系表就变成机械操作了。对于每个产生式扫描它的右部把相邻符号包括终结符和非终结符混排之间的优先关系填进表里。规则汇总下来就三条规则一如果右部出现相邻的终结符 a 和 b那么 a b。 规则二如果右部出现 a Q 这种“终结符紧跟在非终结符后面”的形式那么对 Q 的 FirstVT 集合中的每一个终结符 b都有 a b。 规则三如果右部出现 Q a 这种“非终结符紧跟在终结符前面”的形式那么对 Q 的 LastVT 集合中的每一个终结符 b都有 b a。带括号的典型情况 F → (E)右部是 ( E )其中 ( 和 ) 都是终结符E 是非终结符。根据规则二( 要小于 E 的 FirstVT 中的所有终结符根据规则三E 的 LastVT 中的所有终结符都要大于 )。另外 ( 和 )本身不算相邻终结符因为中间夹了 E所以不会填 。规则一里的 专门处理 E → ET 这种产生式中 两边都是非终结符、没有相邻终结符但有别的产生式是 ET 这种形式时 T 推出的第一个终结符会和 产生关系那是由 FirstVT/LastVT 的传递收进来的。比如 T → F、F → (E) 这样的链 就可能会和 ( 产生 的关系。拿我前面的文法举例手工推一部分就能看到 和 * 的关系最后会得到 *因为规则二里 T 的 FirstVT 包含 *。这符合我们平时对运算优先级“乘比加优先”的直觉所以算符优先表本质上是把运算符优先级从文法中显式提取出来。3.2 优先表的存储二维数组也可以很优雅优先关系表本质上是一个二维矩阵行和列分别代表栈内终结符和输入终结符。三个格子存放三种标记我习惯用 -1 表示未定义、0 表示等于、1 表示小于、2 表示大于。#define REL_NONE -1 #define REL_EQ 0 #define REL_LT 1 #define REL_GT 2 int priorityTable[MAX_TERMINAL][MAX_TERMINAL];初始化全部填 -1之后每一条规则填进去的都是小范围的修改。注意一个产生式扫描完同一个表项可能被多条规则同时影响这时候就要求文法本身没有冲突——一个格子不能被同时填成两种不同关系。如果出现了说明这个文法不是算符优先文法程序应该报错退出。实践中我见过不少同学在这一步直接强覆盖等于是把文法冲突掩盖了后面分析阶段就会出现怪异的移进/归约现象。填表的实现也没什么花哨的遍历产生式右部的每个位置判断相邻符号的类型然后查对应非终结符的 FirstVT 或 LastVT 集合将集合里出现的每个终结符对应的表项置位。写的时候记得优先表的下标用的不是 ASCII 码而是终结符编号所以每次填表前要先做一次“终结符到编号”的映射查找。3.3 判断是不是算符优先文法把整张表填完之后扫描每个表项如果发现某个格子的值被不同的规则修改成不同的关系这个文法就不是算符优先文法。我实验时用的算术表达式文法天然满足要求但有的同学会自己换一个文法来测比如加了赋值语句的、加了单目负号的、或者有数组下标的文法这时候十有八九会遇到冲突。处理冲突有一个务实思路算符优先冲突并不一定等于文法真的歧义可能只是这个文法在“单目负号”这类语义上确实没法用算符优先生成干净的分析行为。比如单目负号和减法共用一个 - 符号谁先谁后不好决策这种文法需要特殊处理或者换用优先级驱动的 LR 变体。遇到这种情况不要硬改优先表先思考是不是文法本身就不适合算符优先分析。注意算符优先分析只适用于算符文法且必须在优先关系上有一致性。如果填表时发现冲突先回头检查文法是否真的算符文法有没有产生式右部出现相邻非终结符再考虑是不是运算符之间有歧义。4. 核心分析循环移进-归约的 C 语言实现4.1 栈结构与输入串组织分析过程使用一个栈来存放符号串栈里既可能有终结符也可能有非终结符。记得栈底要放一个 #输入串末尾也要加一个 ## 作为一个特殊的终结符参与优先关系比较。栈的数据结构直接用数组模拟最顺手#define MAX_STACK 128 typedef struct { char stack[MAX_STACK]; int top; // 栈顶指针指向当前栈顶元素 } AnalyzerStack;top 初始化为 0stack[0] 放 #。分析过程中栈里的非终结符同样占一个位置虽然它们不参与优先关系判断但它们必须参与句柄的匹配所以不能省略。栈的实际内容执行 push 操作时一次压入一个符号字符非常简单。输入串的处理建议一次性读入并用字符串保存缓冲区头指针不断向前移动。为了便于调试我给每个移动步骤都打印了栈内容和剩余输入这段输出在整个排错过程中非常有价值。4.2 终止条件的判断与归约条件分析循环的大致结构是取栈顶终结符 a。注意栈顶元素可能是非终结符这时候要向上查找到最近的一个终结符作为 a。取输入缓冲区的首个终结符 b也可能就是 # 或普通终结符。查找 priorityTable[a][b]。如果是 或 执行移进操作把 b以及它前面的所有字符这里其实是一次移进一个终结符压入栈。如果是 执行归约操作在栈中找到句柄并替换为某个产生式的左部非终结符。如果是 -1报错。归约的时候要找到句柄的边界。算符优先分析的特别之处是它不从栈顶向下滑而是先找栈中最近的一个终结符然后比较它和上一个终结符的优先关系直到出现 才确定句柄的头部。举一个具体的例子假设栈内容从底部到顶部是 # i i通过优先表查到 # 或 i 这样的关系时就知道该归约了。找到句柄之后把句柄对应的栈内容与所有产生式右部做匹配。如果匹配上就替换成左部符号。找不到匹配的产生式则报错。4.3 核心函数伪代码与实现要点下面这个函数是分析过程的主循环骨架void parse(AnalyzerStack *st, const char *input) { int pos 0; while (1) { char a getTopTerminal(st-stack, st-top); char b input[pos]; if (a # b #) { printf(Accept\n); break; } int rel getRelation(a, b); if (rel REL_LT || rel REL_EQ) { push(st, b); pos; } else if (rel REL_GT) { // 找到句柄执行归约 int start findHandle(st); reduce(st, start); } else { printf(Error at pos %d\n, pos); break; } } }getTopTerminal 要在“栈顶元素是非终结符”的情况下向上回退直到找到终结符。这个函数虽小但容易出错特别是刚归约完栈顶是非终结符时一定要循环退栈检查不能只查一层。findHandle 的逻辑是从栈顶往下扫描找到第一个终结符记下位置 topTerminalPos。然后从这个位置接着往下向栈底方向扫描终结符比较当前位置终结符和下一个更深的终结符之间的优先关系如果遇到 就停止句柄范围从这个 对应的更深的那个终结符的下一个位置到栈顶。reduce 操作是重头戏。找到句柄起止位置后把这一段字符串取出来去和所有产生式的右部比对。比对是顺序查找文法小没问题如果文法规模大了可以考虑建一个以右部字符串为键的哈希表加速匹配。不过我实验用的文法只有 6 条产生式线性扫描完全够用。归约成功后把句柄从栈中移除把产生式左部压入栈顶。注意压入后栈顶变成了非终结符下一轮循环的 getTopTerminal 会向上找终结符继续比较。这个过程要仔细对照教科书上“算符优先分析表”的示例流程跑一遍确保每一步的栈变化都和预期一致。提示移进操作压入的是当前输入符号 b但在一些实现中会一次性把输入串中连续符号都压入这不符合算法的标准过程。标准做法是每次移进一个终结符非终结符不会从输入直接产生只会因为归约而产生。5. 常见问题与排查技巧实录5.1 终结符的判断混乱导致优先表全错我在第一次写这个实验时把终结符和非终结符的判断写成了判断首字母大小写。教科书上的习惯是大写字母代表非终结符小写字母或特殊符号代表终结符但一旦文法里用 i 这种小写字母代表标识符用 E、T、F 代表非终结符时你的 isTerminal 函数就不能只靠大小写判断了。正确做法是在读取文法的时候收集所有出现在产生式左部的符号它们就是非终结符。其余在右部出现但不在左部出现的符号包括 、*、(、)、i、#就是终结符。不要把 i 误判成非终结符否则后面整个集合运算和分析都会错。调试方法很简单把终结符列表打印出来和预期比对。多写一个 debug 输出并不丢人反而是省时间的好习惯。5.2 表项越界和特殊符号 # 的处理在优先关系表里要占一个终结符位置它和所有终结符的关系需要提前手动设定。我记的设定是任何终结符和 # 与 # 和任何终结符只有在对应位置才可能相遇比如栈里出现 a # 这种情况通常提前在表里把 # 与其他所有符号的关系填成 即栈内终结符高于 # 时该归约就归约。不少同学忽略 # 在优先表里的初始化导致分析到最后一步突然报错。我的建议是在构建表的阶段就把 # 当作一个普通终结符参与编号但 # 不会出现在任何产生式右部只用在分析时作为边界标记。数组下标越界的问题也值得说。优先表的长宽要设成 MAX_TERMINAL × MAX_TERMINAL如果你直接拿 ASCII 码做下标遇到 ( 或 ) 这种字符没事但遇到中文或其它扩展字符就麻烦了。我见过极端情况是程序崩溃在查表那一刻就是因为越界后返回了一个内存垃圾。处理方式很原始所有访问优先表的地方必须经过编号映射函数绝不直接用字符值当索引。5.3 分析过程出现死循环怎么办死循环最常见的诱因是归约时不匹配任何产生式。比如句柄找得太大或太小导致栈里截取出来的符号串不是任何一个产生式的右部reduce 函数直接返回 -1而主循环在归约失败后没有跳出反而继续尝试归约就造成了死循环。另一个常见诱因是 findHandle 的边界判断写错。句柄的起点应该是优先关系 对应的那个终结符更深一位的符号但有人写成当前终结符本身导致每次归约掉的长度不对栈越归约越长。遇到死循环最好的排查方式不是加断点而是打印每一步的栈内容。你把循环次数上限设一个较大的值比如 1000 步超过就报错退出这样至少能定位是哪一步开始异常的。我在实际测试中遇到过一次典型的“栈只增不减”情况就是句柄识别错了归约时在栈顶没有真正消除元素。5.4 测试用例设计从简单到刁钻实验验收时老师一般会当场拿几个表达式来测我的经验是自己提前准备好一套分级测试用例。基础用例先测单操作数输入 i期望直接接受。这一步能验证终结符 i 和 # 的关系。接下来测 ii、ii、iii、i*(ii) 这种常规表达式。然后测嵌套括号 (i(i*i)) 这种更深的层级。最后测错误输入比如 i、(i)、i**i这些应该在你的程序中被正确拒绝。错误输入尤其重要因为很多同学的程序只能处理合法输入遇到非法输入要么崩溃要么死循环。我在实现里特意加了一个错误处理分支当出现未定义优先关系时输出一条明确错误信息并退出而不是继续循环。这才是分析器该有的表现也方便你检查自己优先表里有没有遗漏的关系。5.5 关于“单目负号”这个坑如果在文法里加上一条产生式 F → -F 或者 E → -E算符优先表很容易出现 - 和 - 之间的冲突。这个冲突本质上是因为单目负号和双目减号共用同一个终结符优先关系没法同时满足两者。很多版本的教材都直接回避单目负号的讨论我建议做实验时先不要贪多保持最基本的加法乘法文法就好。如果老师题目明确要求单目负号比较合适的处理思路是引入一个不同的终结符比如用 NEG 表示单目负号词法分析时区分场景这算是给算符优先分析“打补丁”。5.6 验证结果用动作序列对照课本每次接受一个句子后把归约动作序列记录下来比如“用 F→i 归约用 T→T*F 归约……”然后手工推演一遍看是否符合最左归约或者说符合算符优先分析的归约顺序。只有机器接受还不够要保证归约序列本身是正确的。我在测试中发现过一个有意思的现象程序接受了某个表达式但归约序列和手工推导不一致原因是 final Reduce 时用的是错误的产生式右部匹配——右部匹配的优先级顺序即先匹配长度更长的产生式还是更短的产生式如果不处理就容易出错误。解决办法是在 reduce 函数里对候选产生式先按右部长度降序排序优先匹配长句柄。这一点在标准 LR 分析里有明确规则算符优先分析里也应遵守避免短产生式误匹配。6. 从实验到真正的编译器前端6.1 算符优先分析成果能带给你什么做完这个实验你的收获不只是一份能交差的代码更重要的是你真的把自底向上分析的机制跑通了一遍。你会对“句柄”“移进”“归约”这些词建立起直觉栈里的符号不是简单的字符堆而是有结构层次的一层层“推导碎片”。以后再学 LR(1) 或者 LALR 的时候很多东西都能和这个实验对应起来。从代码能力上说你训练了“用模块化函数处理结构化数据”的基本功。FirstVT 集合、LastVT 集合、优先表这些模块是流水线式的任何一个环节出问题都能单独测试这种“为每个算法步骤建一个独立函数”的编程习惯比刷几道算法题划算得多。6.2 如果要把这个小项目扩展成真正的表达式解析器完成基础实验之后你可以试着做几个小扩展。第一把 i 替换成真实的数字常量和变量名也就是接入词法分析器让输入从“ii*i”变成真正的一串 token。第二增加单目运算符不过要注意处理方式。第三在归约动作中顺手构造语法树节点让每一步归约产生一个 AST 节点这样输出就不只是一句“接受”而是一棵可以后续做语义分析的语法树。第四个扩展方向是支持更多运算符并引入优先级表。算符优先分析的优势恰恰在于优先关系天然对应运算符优先级所以扩展开起来很顺手。比如增加比较运算符、逻辑运算符只需要在文法里增加产生式并检查新的优先表不冲突即可。6.3 写在代码之外的经验最后分享一个个人体会做编译原理实验最忌讳“对着代码发呆”。如果某一个功能怎么调都不对优先打开调试输出把每一个阶段的中间结果打印出来核对。算符优先分析这条链路上每个中间结果都是可以人工核验的FirstVT 集合对不对对着定义手算一遍优先表对不对对着三条规则扫描一遍分析过程对不对拿着教材的标准例题走一遍。还有个小技巧如果你的学校实验环境要求提交 .c 源文件并且老师可能会用不同的文法来测一定要把读入文法的部分写得灵活一点文法格式允许从文件读入或从标准输入读入不要把所有文法都硬编码在 main 函数里。这样不论老师怎么换测试文法你只要改输入文件就行。我当时就是吃了这个亏硬编码的文法在验收时被老师换了一个加赋值语句的文法结果只能现场改代码那种狼狈真的不想再来第二次。