最近总能在课程群里看到类似问题编译原理实验要求用 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 各写一个函数分析ii*i时函数调用层层嵌套如果用 LR 分析你要维护几十上百个状态。而算符优先分析只做一件事比较当前栈顶最近的终结符和下一个输入符号之间的优先级决定现在应该把输入符号压栈还是把栈顶部的一段内容归约成一个非终结符。这里有一个核心概念叫素短语。一个素短语是句型中的一个子串它至少包含一个终结符并且不再包含更小的素短语。算符优先分析每次归约的对象就是当前最左素短语。为什么它能做到因为它提前建好了一张终结符之间的优先关系表表格里记录着a b、a b、a b或不存在关系通过这张表就能在栈里切出素短语的边界。换句话说它把“句子结构”问题转化成了“运算符优先级”问题。这正是“算符优先”四个字的由来。也正因为它不看非终结符之间的复杂关系所以对二义性文法非常敏感这是后话。1.3 与递归下降、LR 分析的一次直观对比用一张表看三者区别会更直接方法文法要求实现方式代码量错误处理典型场景递归下降LL(1) 或手工消除左递归每个产生式一个函数中直接栈显式可控手写小型语言前端LR(1)较宽工具自动分析状态机 分析表大强但表大难手写主流编译器生成工具算符优先算符优先文法优先表 算符栈小表空白处即错误表达式、小型计算器算符优先的短板也很明显它不能正确处理非终结符之间的结构关系文法一旦不满足算符优先条件就无从下手。但正因为它“窄”才更适合作为理解移进-归约机制的入口。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 - ...aBa 属于 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 - ET说明属于 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) 中的每一个终结符 ba b。同一产生式右部出现...Qa...则对 LASTVT(Q) 中的每一个终结符 bb a。符号约定再强调一遍a b表示 a 的优先级严格低于 b也就是遇到 a 和 b 相邻时不能先处理 a得等 b 先归约a b表示 a 高于 ba 那一侧先归约。通常出现在括号配对这类场景表示两者绑在一起比如( )。拿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 列的优先关系表。加上边界符号#后约定#低于句子开头遇到的终结符句子末尾的终结符高于#且# #。最终表如下#*()i#空*(空)空空i空空这张表就是程序里那个二维数组的数据来源。我建议把表打印出来或者写成注释放在代码边上调试时一眼就能对照。一旦分析出错第一个要怀疑的就是表里某格填错了而不是主循环写错。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 curX 属于句柄 cur j; j--; } else if (rel 0) { // X curX 在句柄左侧句柄从 X1 开始 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、ii、i*i还是(N)都压入一个固定的非终结符N。单纯做语法识别这样足够了因为算符优先分析不关心N到底是 E、T 还是 F。但如果你后面要做表达式求值或生成语法树就必须在归约时记录句柄对应的产生式这个我在后面展开。跑一下ii*i#分析结果会是 accept。纸面上跟踪一遍会比只看代码理解深得多初始栈#输入i# i移进栈# i输入i 归约出N栈# N输入取最顶终结符是## 移进后面再处理i和*整个流程非常顺。4. 调试过程中我踩过的坑边界、歧义与句柄误判4.1 边界符号 # 的优先级少写一行表就全乱套第一个坑来自边界。很多教材直接说#小于所有可以出现在句首的终结符、大于所有可以出现在句尾的终结符但表里具体怎么体现很容易漏。比如#行、)列的关系以及)行、#列的关系一开始我为了方便全填了空关系结果分析(i)#时归约完括号内内容后栈是# ( N输入)( )移进栈变成# ( N )输入#此时 top_terminal 是)查)行#列必须是大于才能触发归约。我填成空关系程序直接报错。后来补上这一格才通过。边界#的处理原则可以这样记分析开始时#必须“让路”给输入串第一个终结符所以#对其他能出现在句首的终结符是小于分析结束时栈里的终结符必须能“收尾”归约掉所以它们对#是大于。任何在语法上不可能相邻的组合比如#和)填空关系没毛病但不能把所有边界都填空关系。这也是为什么我建议把表直接写在注释里。调试时对照表格一秒就能看出是表的问题还是代码的问题。4.2 单目负号与双目减号的二义性第二个高发问题想支持负数输入。表达式-35在词法上就是- 3 5但算符优先分析器拿到的是一串终结符它并不区分单目负号和减法。如果用现有文法-只作为二元运算符出现在两个操作数之间分析-35时第一个字符就是-栈里#和-的关系查表表里可能没有这项直接报错。常规做法是在词法阶段就把单目负号改造成另一个终结符比如UMINUS然后给文法加一条产生式F - UMINUS F并在优先关系表里给UMINUS安排最高优先级。这样做需要同步扩展 FIRSTVT、LASTVT 和表看起来麻烦但这是最干净的处理方式。如果你只是做个实验最简单是暂时不支持负号或者把负号跟数字粘在一起交给词法处理成负数常量但这不是通用方案。4.3 最左素短语范围判错比较对象要动态更新第三个坑确实比较容易混find_handle 该从哪个位置开始我看到不少同学的实现是从栈顶往下扫遇到第一个终结符就认为句柄到头了直接把那个终结符和它下面一段都归约。这样做对简单情况 ok一到带括号或者连续运算就多归约或漏归约。核心是记住句柄的右边界是栈顶句柄的最右终结符要从栈顶向下找第一个终结符而句柄的左边界要用向左扫描的方式确定扫描时比较的对象要动态更新成“当前句柄内最左边的终结符”而不是一直拿句柄最右终结符当基准。我在 3.2 里给出的实现就是按这个逻辑写的调试时加几行打印把 start、top 输出来很快就能看出问题。为什么不能固定基准因为素短语内部的终结符之间关系是大于或等于一旦遇到小于就说明已经越过句柄左边界。你要是拿“越界前的终结符”和“句柄最右终结符”比较很可能表里是空关系或者错误关系。4.4 词法层面的坑多位数字、空白字符与标识符最后一个坑是词法接口的问题。实验中为了省事常用单个字符i代表任意标识符或数字测试串也是ii*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 * Nvalue 等于左操作数乘右操作数句柄是ivalue 来自词法阶段给它的整数值句柄是(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 加三条规则一步步推出来的你把推演过程亲手走一遍再去看任何一份网上的代码都会觉得非常通透。如果你也在做类似的实验建议别急着抄表或者复制代码先手算一遍它再对照着实现主循环绝对比直接调通一个现成程序收获多得多。
C语言实现算符优先分析：优先关系表构建与移进归约算法详解
最近总能在课程群里看到类似问题编译原理实验要求用 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 各写一个函数分析ii*i时函数调用层层嵌套如果用 LR 分析你要维护几十上百个状态。而算符优先分析只做一件事比较当前栈顶最近的终结符和下一个输入符号之间的优先级决定现在应该把输入符号压栈还是把栈顶部的一段内容归约成一个非终结符。这里有一个核心概念叫素短语。一个素短语是句型中的一个子串它至少包含一个终结符并且不再包含更小的素短语。算符优先分析每次归约的对象就是当前最左素短语。为什么它能做到因为它提前建好了一张终结符之间的优先关系表表格里记录着a b、a b、a b或不存在关系通过这张表就能在栈里切出素短语的边界。换句话说它把“句子结构”问题转化成了“运算符优先级”问题。这正是“算符优先”四个字的由来。也正因为它不看非终结符之间的复杂关系所以对二义性文法非常敏感这是后话。1.3 与递归下降、LR 分析的一次直观对比用一张表看三者区别会更直接方法文法要求实现方式代码量错误处理典型场景递归下降LL(1) 或手工消除左递归每个产生式一个函数中直接栈显式可控手写小型语言前端LR(1)较宽工具自动分析状态机 分析表大强但表大难手写主流编译器生成工具算符优先算符优先文法优先表 算符栈小表空白处即错误表达式、小型计算器算符优先的短板也很明显它不能正确处理非终结符之间的结构关系文法一旦不满足算符优先条件就无从下手。但正因为它“窄”才更适合作为理解移进-归约机制的入口。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 - ...aBa 属于 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 - ET说明属于 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) 中的每一个终结符 ba b。同一产生式右部出现...Qa...则对 LASTVT(Q) 中的每一个终结符 bb a。符号约定再强调一遍a b表示 a 的优先级严格低于 b也就是遇到 a 和 b 相邻时不能先处理 a得等 b 先归约a b表示 a 高于 ba 那一侧先归约。通常出现在括号配对这类场景表示两者绑在一起比如( )。拿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 列的优先关系表。加上边界符号#后约定#低于句子开头遇到的终结符句子末尾的终结符高于#且# #。最终表如下#*()i#空*(空)空空i空空这张表就是程序里那个二维数组的数据来源。我建议把表打印出来或者写成注释放在代码边上调试时一眼就能对照。一旦分析出错第一个要怀疑的就是表里某格填错了而不是主循环写错。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 curX 属于句柄 cur j; j--; } else if (rel 0) { // X curX 在句柄左侧句柄从 X1 开始 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、ii、i*i还是(N)都压入一个固定的非终结符N。单纯做语法识别这样足够了因为算符优先分析不关心N到底是 E、T 还是 F。但如果你后面要做表达式求值或生成语法树就必须在归约时记录句柄对应的产生式这个我在后面展开。跑一下ii*i#分析结果会是 accept。纸面上跟踪一遍会比只看代码理解深得多初始栈#输入i# i移进栈# i输入i 归约出N栈# N输入取最顶终结符是## 移进后面再处理i和*整个流程非常顺。4. 调试过程中我踩过的坑边界、歧义与句柄误判4.1 边界符号 # 的优先级少写一行表就全乱套第一个坑来自边界。很多教材直接说#小于所有可以出现在句首的终结符、大于所有可以出现在句尾的终结符但表里具体怎么体现很容易漏。比如#行、)列的关系以及)行、#列的关系一开始我为了方便全填了空关系结果分析(i)#时归约完括号内内容后栈是# ( N输入)( )移进栈变成# ( N )输入#此时 top_terminal 是)查)行#列必须是大于才能触发归约。我填成空关系程序直接报错。后来补上这一格才通过。边界#的处理原则可以这样记分析开始时#必须“让路”给输入串第一个终结符所以#对其他能出现在句首的终结符是小于分析结束时栈里的终结符必须能“收尾”归约掉所以它们对#是大于。任何在语法上不可能相邻的组合比如#和)填空关系没毛病但不能把所有边界都填空关系。这也是为什么我建议把表直接写在注释里。调试时对照表格一秒就能看出是表的问题还是代码的问题。4.2 单目负号与双目减号的二义性第二个高发问题想支持负数输入。表达式-35在词法上就是- 3 5但算符优先分析器拿到的是一串终结符它并不区分单目负号和减法。如果用现有文法-只作为二元运算符出现在两个操作数之间分析-35时第一个字符就是-栈里#和-的关系查表表里可能没有这项直接报错。常规做法是在词法阶段就把单目负号改造成另一个终结符比如UMINUS然后给文法加一条产生式F - UMINUS F并在优先关系表里给UMINUS安排最高优先级。这样做需要同步扩展 FIRSTVT、LASTVT 和表看起来麻烦但这是最干净的处理方式。如果你只是做个实验最简单是暂时不支持负号或者把负号跟数字粘在一起交给词法处理成负数常量但这不是通用方案。4.3 最左素短语范围判错比较对象要动态更新第三个坑确实比较容易混find_handle 该从哪个位置开始我看到不少同学的实现是从栈顶往下扫遇到第一个终结符就认为句柄到头了直接把那个终结符和它下面一段都归约。这样做对简单情况 ok一到带括号或者连续运算就多归约或漏归约。核心是记住句柄的右边界是栈顶句柄的最右终结符要从栈顶向下找第一个终结符而句柄的左边界要用向左扫描的方式确定扫描时比较的对象要动态更新成“当前句柄内最左边的终结符”而不是一直拿句柄最右终结符当基准。我在 3.2 里给出的实现就是按这个逻辑写的调试时加几行打印把 start、top 输出来很快就能看出问题。为什么不能固定基准因为素短语内部的终结符之间关系是大于或等于一旦遇到小于就说明已经越过句柄左边界。你要是拿“越界前的终结符”和“句柄最右终结符”比较很可能表里是空关系或者错误关系。4.4 词法层面的坑多位数字、空白字符与标识符最后一个坑是词法接口的问题。实验中为了省事常用单个字符i代表任意标识符或数字测试串也是ii*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 * Nvalue 等于左操作数乘右操作数句柄是ivalue 来自词法阶段给它的整数值句柄是(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 加三条规则一步步推出来的你把推演过程亲手走一遍再去看任何一份网上的代码都会觉得非常通透。如果你也在做类似的实验建议别急着抄表或者复制代码先手算一遍它再对照着实现主循环绝对比直接调通一个现成程序收获多得多。
