算符优先分析法是我当年学编译原理时觉得最“像一个正常人”的语法分析方法。因为你看表达式i i * i不需要先画什么推导树、算一堆 FIRST、FOLLOW脑子里天然就知道先算乘法再算加法——算符优先分析法干的事就是把这套“人脑直觉”形式化变成一张表和一套移进-归约规则喂给程序去执行。如果你正在被自下而上的语法分析搞到头大或者做实验课“算符优先分析表生成”做到怀疑人生又或者准备面试时被问“算符优先分析和 LR 有什么区别”那这篇内容应该能帮你把第 5 章这块硬骨头啃下来。我会把优先关系、FIRSTVT/LASTVT、素短语这些概念用完整的手工推导和代码思路串起来最后再聊聊我实际踩过的坑。1. 自下而上分析的全局视图优先分析法处在哪个位置1.1 从“移进-归约”到“最右推导的逆过程”自下而上分析的核心思想是从输入串出发不断把右部匹配的符号串“归约”成非终结符最终归约到文法的开始符号。这个过程在形式上是最右推导的逆过程——也就是说如果语法树存在那么自下而上分析就是沿着最右推导的路径倒着走回起点。为了描述每一步该归约哪个符号串教材里引入了“句柄”这个概念。句柄本质上是某个产生式的右部同时它出现在当前句型的最左位置归约它就能和最右推导一一对应。你可以把句柄想象成“拆积木时最上面那块松动的积木”每次只拆最可能拆的那一块。LR 分析器就是沿着这条严格路径走的每次归约的必然是真句柄属于规范归约。但这里有一个很实际的问题对于表达式文法我们真的需要每次都精确定位句柄吗其实不需要。人用手算表达式时不会每一步都去检查“这是不是最右推导的逆过程”而是只看运算符之间的优先级*比高所以先算i * i括号优先级最高所以先算括号内的内容。算符优先分析法就是抓住了这种“运算符优先级”的本质把分析过程从“识别句柄”简化为“比较相邻终结符的优先关系”实现起来比 LR 简单一个量级。1.2 为什么单独给“算符优先”开一条路线在自下而上分析的众多方法里算符优先分析Operator Precedence Parsing是一个很特别的存在。它不像 LR 那样对文法有非常一般性的要求而是专门面向“运算符语言”设计的最典型的就是算术表达式、布尔表达式、赋值语句这类文法。它最大的优点是分析表中不出现非终结符终结符之间的优先关系才是主角。这意味着分析时不用关心栈里的非终结符具体是什么名字只需要盯着终结符比较优先级然后决定是移进还是归约。对于表达式文法来说这种简化非常自然而且实现起来的空间开销和时间开销都远小于同等级的 LR 分析表。代价是什么呢代价就是它牺牲了一部分能力。算符优先分析归约的未必是句柄而是“最左素短语”因此它不属于规范归约。如果文法比较复杂或者两个终结符之间的优先关系出现冲突这个方法就会失效。所以在学习时我建议大家把算符优先分析看成“LR 的简化特例”而不是独立的万能方法这样理解它的能力和边界都会清晰很多。2. 三种优先关系与 FIRSTVT、LASTVT 的核心定义2.1 “小于、等于、大于”到底在比什么算符优先分析定义了三对终结符之间的二元关系符号分别是、教材里常用 ≐ 表示、。注意这里的“小于、等于、大于”不是数值比较而是“优先级关系”的抽象如果a b意思是终结符a的优先级低于终结符b那么在实际分析中当栈顶出现a而当前输入符是b时应该优先处理b代表的运算也就是先把b移进栈。举个例子在经典表达式文法里 *表示加号的优先级低于乘号。处理i i * i时栈顶终结符是当前输入是*因为 *所以把*移进栈而不是急着把左边的部分归约。这直观对应了“先乘除后加减”。a ≐ b表示两者优先级相等通常出现在“括号配对”或者“同一个运算符连续出现但结合性需要特殊处理”的场景。比如(和)之间有( ≐ )表示遇到右括号时可以把括号内的内容整体归约。a b则表示栈顶终结符优先级更高该做归约了。三种关系合在一起构成了分析程序的决策依据比较栈顶终结符和当前输入符若或≐则移进若则归约。2.2 FIRSTVT 和 LASTVT 的递归计算规则构造优先关系表之前必须先算出每个非终结符的 FIRSTVT 集合和 LASTVT 集合。FIRSTVT(A) 的定义是从 A 出发经过一步或多步推导得到的句型中“最左边可能出现的终结符集合”。它和 FIRST 集合的区别在于FIRSTVT 只关心第一个符号是终结符的情况如果第一个符号是非终结符则继续追踪这个非终结符的 FIRSTVT直到遇到终结符为止。计算规则可以归纳为两条基础规则和一条迭代规则如果产生式形如A → a...或A → B a...那么终结符a属于 FIRSTVT(A)。如果产生式形如A → B...且b ∈ FIRSTVT(B)那么b也属于 FIRSTVT(A)。用大白话说第一条规则找“直接以终结符开头”的候选式第二条规则负责把左部非终结符打头的候选式继续传递下去。LASTVT(A) 的定义完全对称从 A 出发推导出的句型中“最右边可能出现的终结符集合”。计算规则也对称如果产生式形如A → ...a或A → ...aB那么终结符a属于 LASTVT(A)。如果产生式形如A → ...B且b ∈ LASTVT(B)那么b也属于 LASTVT(A)。实际手工推导时建议大家从最底层的非终结符往上推。因为底层非终结符的候选式最简单FIRSTVT/LASTVT 一眼就能看出来往上层层传递时才不容易漏项。2.3 优先关系表的三条构造规则有了 FIRSTVT 和 LASTVT就可以构造优先关系表了。对文法中每条产生式逐一检查应用下面三条规则若产生式右部出现...a b...或...a B b...a、b为终结符B为非终结符则a ≐ b。这条规则本质是终结符紧挨着终结符或者被一个非终结符隔开的两个终结符它们在语法结构上处于同一层所以优先级相等。若产生式右部出现...a B...a是终结符B是非终结符则对 FIRSTVT(B) 中的每个终结符b都有a b。意思是终结符a后面跟了一个非终结符B那么B能推导出的所有“开头终结符”优先级都比a高处理时要先处理b。若产生式右部出现...B a...a是终结符B是非终结符则对 LASTVT(B) 中的每个终结符b都有b a。意思是非终结符B后面直接跟终结符a那么B能推导出的所有“结尾终结符”优先级都比a高处理时先归约B的部分。这三条规则一定要对照着具体产生式去理解光背很容易弄混方向。我见过很多同学把第 2 条和第 3 条搞反最后表里全是错的。有个笨但有效的记忆法看产生式右部终结符在前、非终结符在后那就是“前面低、后面高”记非终结符在前、终结符在后那就是“前面高、后面低”记两个终结符之间要么直接挨着要么隔了一个非终结符那就是“相等”记≐。3. 完整实例经典表达式文法全流程演算3.1 选用文法与目标说明为了把上面的规则落到实地我们用一个几乎所有教材都会用的经典表达式文法E → E T | T T → T * F | F F → ( E ) | i这里E表示表达式T表示项F表示因子终结符集合是{, *, (, ), i}非终结符集合是{E, T, F}开始符号是E。注意这个文法没有把减法和除法放进来是为了让推导过程更清爽实际扩展时思路完全一样。我们的目标是通过手工推导得到完整的算符优先关系表然后用这个表去分析输入串i i * i看它如何一步步完成归约。整个流程走完你对优先分析法的理解会从“背规则”变成“会推规则”。3.2 FIRSTVT 和 LASTVT 完整推导先从最底层的F开始。F的产生式是F → ( E ) | i。第一条基础规则遇到F → i右部直接以终结符i开头所以i ∈ FIRSTVT(F)遇到F → ( E )右部也直接以终结符(开头所以(也属于FIRSTVT(F)。因此FIRSTVT(F) { (, i }再看 LASTVT(F)。产生式F → i右部以终结符i结尾所以i ∈ LASTVT(F)产生式F → ( E )右部以终结符)结尾所以) ∈ LASTVT(F)。因此LASTVT(F) { ), i }接着推T。T的产生式是T → T * F | F。先看 FIRSTVT产生式T → F右部以非终结符开头所以FIRSTVT(F)中的所有元素都要传给T即(, i进入FIRSTVT(T)。产生式T → T * F右部以非终结符T开头没有直接以终结符开头的候选式但注意右部第二个符号是终结符*虽然它不是右部开头但在 FIRSTVT 的定义里A → B a...中的a也是 FIRSTVT(A) 的成员。这里的T → T * F正好就是A → B a...的形式A是TB是Ta是*。所以* ∈ FIRSTVT(T)。综合起来FIRSTVT(T) { *, (, i }LASTVT(T)产生式T → F右部以非终结符结尾LASTVT(F)中的), i都进入LASTVT(T)。产生式T → T * F右部以非终结符F结尾所以LASTVT(F)继续传给T同时它符合A → ...aB的形式a是*所以*也属于LASTVT(T)。综合LASTVT(T) { *, ), i }最后推E。E → E T | T。FIRSTVT(E)E → T把 FIRSTVT(T) 全部传过来即*, (, iE → E T符合A → B a...a是所以 ∈ FIRSTVT(E)。因此FIRSTVT(E) { , *, (, i }LASTVT(E)E → T把 LASTVT(T) 全部传过来即*, ), iE → E T符合A → ...aBa是所以 ∈ LASTVT(E)。因此LASTVT(E) { , *, ), i }这就是整个推导过程。检查一下有没有漏项E的 FIRSTVT 里面没有)E的 LASTVT 里面没有(都是符合预期的。3.3 优先关系表的生成过程有了 FIRSTVT/LASTVT逐条产生式套三条规则。先看F → ( E )。右部是( E )符合...aB b...的模式其中a是(B是Eb是)所以规则 1 给出( ≐ )。同时这个产生式还包含...aB...的模式(后跟E所以规则 2 给出对 FIRSTVT(E) 中的每个终结符b有( b。FIRSTVT(E) 是{, *, (, i}也就是说( ( * ( ( ( i再看F → i没有成对的终结符没有产生任何优先关系这符合直觉单个因子本身就是最基础的操作数不需要额外定义优先级。看T → T * F。右部是T * F符合...B a...和...aB...同时出现的模式。先处理aB部分*后跟非终结符F规则 2 给出* FIRSTVT(F)而 FIRSTVT(F) 是{(, i}所以* ( * i再处理Ba部分非终结符T后跟*规则 3 给出 LASTVT(T) 中的每个终结符b有b *。LASTVT(T) 是{*, ), i}所以* * ) * i *看T → F右部只有单个非终结符不产生任何优先关系。看E → E T。右部是E T。规则 2 处理后跟T FIRSTVT(T)而 FIRSTVT(T) 是{*, (, i}所以 * ( i规则 3 处理E后跟LASTVT(E) 中的每个终结符b有b 。LASTVT(E) 是{, *, ), i}所以 * ) i 看E → T右部单个非终结符不产生优先关系。最后处理边界符号#。分析开始前栈底和输入串末尾都有#它不属于文法终结符但参与分析。习惯上定义# FIRSTVT(E) LASTVT(E) # # ≐ #也就是# 、# *、# (、# i以及 #、* #、) #、i #还有# ≐ #。把这些关系汇总到一张 6×6 的表格里行表示栈顶终结符列表示当前输入终结符结果如下优先关系*()i#空*(≐空)空空i空空#空≐表中的“空”表示这一对终结符之间没有定义优先关系一旦分析过程中需要比较它们就说明输入串有语法错误。比如i i在正常表达式中是非法的表中i行i列没有关系程序会在这里报错这是合理行为。3.4 用优先关系表分析输入串i i * i有了表分析过程就变成机械操作了。用一个栈存放文法符号开始时栈底放#输入串末尾也放#。每次比较栈顶终结符a和当前输入符b若a b或a ≐ b把b移进栈若a b则找栈顶最左素短语进行归约若没有定义关系报错。下面分析i i * i我列出关键步骤。为了可读性非终结符统一归约为N因为算符优先分析在归约时并不关心非终结符的具体名字只知道“这里归约出了一个非终结符”就够了。第一步栈是#输入是i i * i #。查表#和i# i移进i栈变成# i输入变成 i * i #。现在栈顶终结符是i当前输入符是查表i 所以归约。把栈顶的i归约为N栈变成# N。第二步栈顶终结符是#当前输入符是查表# 移进栈变成# N 输入变成i * i #。接着比较栈顶终结符和输入符i i移进i栈变成# N i输入变成* i #。第三步比较栈顶终结符i和当前输入符*查表i *所以归约i为N栈变成# N N。继续比较栈顶终结符和输入符* *移进*栈变成# N N *输入变成i #。再比较*和i* i移进i栈变成# N N * i输入变成#。第四步比较栈顶终结符i和输入符#i #归约i为N栈变成# N N * N。此时栈顶终结符是*输入符是#查表* #继续归约。把N * N归约为N栈变成# N N。再比较栈顶终结符和输入符# #继续归约把N N归约为N栈变成# N。最后比较栈顶终结符#和输入符## ≐ #分析成功结束。观察整个流程可以发现算符优先分析在第二步到第三步之间实际上先归约了右边i * i中的因子再归约整个乘积最后才处理加法完全符合“先乘除后加减”的运算顺序。这就是这个方法名字里“优先”两个字的真正含义——它不需要像 LR 那样严格寻找句柄只需要按照优先关系决定“什么时候算、什么时候往后看”。4. 素短语、最左素短语与文法合法性判定4.1 素短语到底是个什么东西既然算符优先分析归约的不是句柄那它每次归约的到底是什么答案是“最左素短语”。素短语的定义是至少包含一个终结符并且除自身之外不再包含任何更小的素短语的短语。字面描述比较绕我换个说法。在一个句型中有些子串是一个产生式的右部这些子串叫“短语”。句柄是其中最左边那个。素短语则额外要求这个子串内部不能套着另一个可以归约的短语而且它必须包含至少一个终结符否则就退化成了只有非终结符的归约无法用优先关系驱动。还是看i i * i的句型N N * i。在这个句型里N * i是一个素短语因为它包含终结符*和i并且内部不再有可以归约的短语。N N * i整体虽然也能匹配某个产生式的右部但它内部包含N * i这个更小的可归约子串所以它不是素短语。在每一步归约中算符优先分析选择的是“最左边”的那个素短语这就是“最左素短语”。这个定义直接关系到归约动作的正确性。分析程序在决定归约时不能随便归约一个能匹配产生式的子串而必须找最左素短语。实现时通常采用“从栈顶向下扫描找到第一个终结符优先级低于前一个终结符的位置”这个位置到栈顶之间的子串就是要归约的素短语。你如果自己写分析器这部分的代码逻辑值得单独测。4.2 算符优先文法的三个判定条件并不是任何文法都能用算符优先分析法用之前需要先判断文法是不是“算符优先文法”。教材里的判定条件主要有三条文法中不能有形如A → ...BC...的产生式右部也就是说两个非终结符不能相邻出现。理由很明显算符优先关系只定义在终结符之间如果两个非终结符贴在一起中间没有终结符作为“锚点”就无法用优先关系驱动分析。对任意两个终结符a、b它们之间至多只有一种优先关系成立。如果同时出现了a b和a b或者既≐又就说明文法有歧义优先关系表不唯一分析程序不知道该移进还是归约。没有二义性的基本要求文法本身必须是二义性文法之外的非二义性文法。这三条条件里第二条在实际做题时最容易踩坑。比如有的同学推导和的优先关系时发现从E → E T得到 但内心又觉得“同一个运算符应该相等”于是擅自写成 ≐ 结果构造出的表和标准答案对不上。其实在左结合文法里同级运算符之间是而不是≐因为左结合意味着右边的运算符要“等左边的算完再算”所以栈顶的运算符优先级更高。判断的时候一定要跟着规则走不要凭直觉改结果。4.3 优先函数节省一张表的工程化手段优先关系表虽然直观但存储空间是终结符个数的平方。对嵌入式环境这种资源敏感的场景可以把表压缩成两个一维数组栈内优先函数f和输入优先函数g让优先关系的比较变成整数比较。定义是a b当且仅当f(a) g(b)a ≐ b当且仅当f(a) g(b)a b当且仅当f(a) g(b)。构造优先函数的方法有迭代法和关系图法。关系图法的思路是把每个终结符a拆成两个节点一个代表f(a)一个代表g(a)根据优先关系连边a b从f(a)连向g(b)a b从g(b)连向f(a)a ≐ b则同时连两条边。然后对每个节点求最长路径长度作为其优先函数值。有环说明不存在优先函数。但优先函数有个致命弱点它把“无优先关系”和“优先级相等”混为一谈。原来的表中i和i之间无定义转为优先函数后可能被解释为相等导致错误输入无法及时报错。所以实际工程里如果要用优先函数必须额外在文法层面保证“凡是表中无定义的位置运行时一定不会出现”。这一点在做实验时容易被忽略面试被问到优先函数时也常常作为加分点。5. 程序化实现把分析表生成和分析过程写成代码5.1 数据结构怎么设计最顺手如果你正在写“算符优先分析表生成”实验第一步不是急着写算法而是把数据结构设计好。我自己的习惯是终结符集合用一维数组存#放在最后一位FIRSTVT 和 LASTVT 用二维布尔矩阵表示行是非终结符列是终结符值为true表示该终结符属于对应非终结符的集合优先关系表用二维字符数组存储取值 、、、四种。用布尔矩阵而不是set的好处是后续迭代计算非常直观直接遍历矩阵找true而不需要做集合求并、判断元素是否存在等操作。对于学习级代码这种“空间换逻辑”的思路能少掉很多头发。5.2 FIRSTVT/LASTVT 迭代求解的核心代码逻辑FIRSTVT 和 LASTVT 的计算可以统一用“迭代到不再变化”的方式实现。以 FIRSTVT 为例初始时遍历所有产生式找到满足A → a...或A → B a...的候选式把终结符a标记进 FIRSTVT(A)。然后不断遍历产生式只要遇到A → B...且 FIRSTVT(B) 中有新的终结符就把这些终结符也加入 FIRSTVT(A)直到所有集合都不再增长。这里给一段思路性的 Python 伪代码def compute_firstvt(grammar, non_terminals, terminals): firstvt {nt: set() for nt in non_terminals} changed True while changed: changed False for lhs, rhs_list in grammar.items(): for rhs in rhs_list: # 规则: A - a... 或 A - B a... if rhs[0] in terminals: if rhs[0] not in firstvt[lhs]: firstvt[lhs].add(rhs[0]) changed True elif len(rhs) 2 and rhs[0] in non_terminals and rhs[1] in terminals: if rhs[1] not in firstvt[lhs]: firstvt[lhs].add(rhs[1]) changed True # 规则: A - B... if rhs[0] in non_terminals: for b in firstvt[rhs[0]]: if b not in firstvt[lhs]: firstvt[lhs].add(b) changed True return firstvtLASTVT 的代码完全对称只是把“开头”换成“结尾”把...aB和...B a的判断条件换一下。写代码时最容易出 bug 的地方是产生式右部的边界条件len(rhs) 2判断一定要写否则当右部只有一个非终结符时会越界。这个坑我在第一次写的时候踩过报错还不是报在明显的地方是算出来的集合莫名其妙少符号排查了很久才发现是越界访问。5.3 分析驱动主程序的实现要点分析驱动主程序是另一个重要模块。核心逻辑就是维护一个栈不断比较栈顶终结符和当前输入符执行移进或归约。栈里面会混合存放非终结符和终结符但比较优先级时要从栈顶往下找“最近的那个终结符”跳过非终结符。伪代码大概是这样的def analyze(tokens, precedence_table, terminals): stack [#] tokens.append(#) ip 0 while True: # 找到栈顶最近的终结符 top_terminal next(t for t in reversed(stack) if t in terminals) cur tokens[ip] rel precedence_table[top_terminal][cur] if rel : raise SyntaxError(非法终结符组合) if rel or rel : stack.append(cur) ip 1 elif rel : # 找最左素短语并归约 # 从栈顶往下扫描, 找到第一个 的位置 # 中间的子串整体归约为非终结符 do_reduce(stack) if stack [#] and cur #: break归约时不需要真的查产生式决定用哪个非终结符替换因为算符优先分析不关心非终结符名字直接把素短语替换成统一的N就行。这也是写实验代码时最省事的地方。如果后续要做语法树那在归约时需要记录“这个素短语对应文法的哪个产生式”再在栈里压入对应的左部非终结符。实际上如果实验要求是“生成优先关系表并分析句子”我建议把表生成和分析驱动分成两个独立文件来写。表生成部分专心处理 FIRSTVT、LASTVT 和优先关系分析驱动部分只依赖二维表结果这样两边独立测试出错了也容易定位。6. 手工推导与实验中出现的高频问题6.1 FIRSTVT/LASTVT 计算时的常见漏项我批过不少同学的作业FIRSTVT 和 LASTVT 计算中最常见的错误就三种。第一种是漏掉形如A → B a...这种产生式右部“第二个位置”的终结符。很多人记得A → a...规则却忘了B a...这种非终结符后面紧跟终结符的情况也要加入集合。比如E → E T里属于 FIRSTVT(E) 不是因为它出现在右部开头而是因为它出现在第一个非终结符E后面。第二种是迭代传递时只传了一层。比如文法有三层产生式E → T、T → F、F → i如果遍历一遍就结束很可能只算出 FIRSTVT(T) 包含i忘了继续传给 FIRSTVT(E)。解决办法就是前面代码里的while changed循环一直循环到没有任何变化为止。手工算的时候可以用“标记已传递”的方法每轮只检查新增元素不然很容易漏。第三种是把#当作普通终结符参与 FIRSTVT/LASTVT 计算。#只是分析时的界符不属于文法符号计算 FIRSTVT/LASTVT 时不应该包含它。有同学在初始时把#放进去结果优先关系表里多出一堆莫名其妙的行和列分析时又对不上号。6.2 优先关系表出现冲突怎么处理如果算出的优先关系表中同一对终结符既出现了又出现了或者既≐又那基本可以断定文法不是算符优先文法。遇到这种情况不要试着“手工改表”而要回到文法层面解决。最常见的处理手段是改写文法。比如原本有产生式E → E E | E * E | (E) | i这个文法有二义性i i * i可以有两种不同的语法树导致和*的优先关系无法唯一确定。解决办法就是把它分层拆成我们前面用的E → E T | T、T → T * F | F这种形式让优先级通过文法层级天然体现。拆完之后再算优先关系表冲突就消失了。还有一种情况是左结合和右结合混用导致的问题。比如要支持赋值运算的右结合直接写E → id E | ...会引入 还是 的疑问。多数教材的处理方式是把右结合的运算单独用一层产生式表示或者在算优先函数时特殊处理。考试和面试里最常见的考法就是给你一个二义性文法让你判断它“是否是算符优先文法”并说明理由答案的核心就落在“两个终结符之间存在不止一种优先关系”这一点上。6.3 面试常问的几个“为什么”面试官问到优先分析法时通常不是考你会不会构造表而是考你对概念边界的理解。以下几个问题是我多次遇到的也是我觉得最值得提前想清楚答案的。问算符优先分析和 LR 分析的核心区别是什么答LR 分析是规范归约每次归约的必然是最右推导的逆过程对应的句柄算符优先分析只比较终结符之间的优先关系归约的是最左素短语不是规范归约。LR 分析能力强、适用范围广但分析表和状态机构建复杂算符优先分析表小、实现简单适合表达式类文法但无法处理非算符优先文法。问为什么算符优先分析归约时不关心非终结符的具体名字答因为优先关系只定义在终结符之间非终结符既不参与比较也不影响移进归约决策。归约时只需要把素短语替换成一个非终结符并继续分析语法树的构建是后续语义动作的事。问句柄和素短语有什么区别答句柄是规范归约中每一步要归约的短语它一定是短语且是最左的素短语是至少含一个终结符且内部不再含更小短语的短语。对算符优先分析来说最左素短语是归约对象但它不一定是句柄。一个经典反例是简单优先分析法中句柄和素短语可能不一致的情况不过在算符优先分析的适用范围里最左素短语已经足够完成语法识别。6.4 实验课测试用例选择经验最后分享一点实验课的实际经验。写完算符优先分析器之后不要只测i i * i这种教科书用例一定要准备几组边界测试。我建议至少要测四类一是正常优先级测试比如i i * i、(i i) * i验证乘除优先和括号处理二是连续运算测试比如i i i验证同级左结合的处理三是嵌套括号测试比如i * (i (i i))验证多层括号场景四是错误输入测试比如i 、()、i i、i * * i预期行为是程序能够报告语法错误而不是陷入死循环或者数组越界。尤其要注意i i这种错误输入。由于表中i和i没有优先关系分析器比较栈顶符号和当前输入符时应该立刻报错。如果程序在这种输入下发散大概率是“无优先关系”被当成了或处理检查一下比较逻辑里是否严格判断了空格字符。在实际写代码过程中我的体会是算符优先分析适合用“先把表打出来、再手工验证几条路径”的方式调试。建一个很小的文法打印 FIRSTVT、LASTVT 和优先关系表对照教材答案核对确认无误后再去跑分析程序。比起直接调一个庞大的分析器这样分阶段验证能省下大量排查时间。优先分析法虽然不如 LR 强大但它的简洁性至今仍是处理表达式文法的有效工具也是理解更复杂自下而上分析算法的重要一步。 算符优先分析法是我当年学编译原理时觉得最“像一个正常人”的语法分析方法。因为你看表达式i i * i不需要先画什么推导树、算一堆 FIRST、FOLLOW脑子里天然就知道先算乘法再算加法——算符优先分析法干的事就是把这套“人脑直觉”形式化变成一张表和一套移进-归约规则喂给程序去执行。如果你正在被自下而上的语法分析搞到头大或者做实验课“算符优先分析表生成”做到怀疑人生又或者准备面试时被问“算符优先分析和 LR 有什么区别”那这篇内容应该能帮你把第 5 章这块硬骨头啃下来。我会把优先关系、FIRSTVT/LASTVT、素短语这些概念用完整的手工推导和代码思路串起来最后再聊聊我实际踩过的坑。1. 自下而上分析的全局视图优先分析法处在哪个位置1.1 从“移进-归约”到“最右推导的逆过程”自下而上分析的核心思想是从输入串出发不断把右部匹配的符号串“归约”成非终结符最终归约到文法的开始符号。这个过程在形式上是最右推导的逆过程——也就是说如果语法树存在那么自下而上分析就是沿着最右推导的路径倒着走回起点。为了描述每一步该归约哪个符号串教材里引入了“句柄”这个概念。句柄本质上是某个产生式的右部同时它出现在当前句型的最左位置归约它就能和最右推导一一对应。你可以把句柄想象成“拆积木时最上面那块松动的积木”每次只拆最可能拆的那一块。LR 分析器就是沿着这条严格路径走的每次归约的必然是真句柄属于规范归约。但这里有一个很实际的问题对于表达式文法我们真的需要每次都精确定位句柄吗其实不需要。人用手算表达式时不会每一步都去检查“这是不是最右推导的逆过程”而是只看运算符之间的优先级*比高所以先算i * i括号优先级最高所以先算括号内的内容。算符优先分析法就是抓住了这种“运算符优先级”的本质把分析过程从“识别句柄”简化为“比较相邻终结符的优先关系”实现起来比 LR 简单一个量级。1.2 为什么单独给“算符优先”开一条路线在自下而上分析的众多方法里算符优先分析Operator Precedence Parsing是一个很特别的存在。它不像 LR 那样对文法有非常一般性的要求而是专门面向“运算符语言”设计的最典型的就是算术表达式、布尔表达式、赋值语句这类文法。它最大的优点是分析表中不出现非终结符终结符之间的优先关系才是主角。这意味着分析时不用关心栈里的非终结符具体是什么名字只需要盯着终结符比较优先级然后决定是移进还是归约。对于表达式文法来说这种简化非常自然而且实现起来的空间开销和时间开销都远小于同等级的 LR 分析表。代价是什么呢代价就是它牺牲了一部分能力。算符优先分析归约的未必是句柄而是“最左素短语”因此它不属于规范归约。如果文法比较复杂或者两个终结符之间的优先关系出现冲突这个方法就会失效。所以在学习时我建议大家把算符优先分析看成“LR 的简化特例”而不是独立的万能方法这样理解它的能力和边界都会清晰很多。2. 三种优先关系与 FIRSTVT、LASTVT 的核心定义2.1 “小于、等于、大于”到底在比什么算符优先分析定义了三对终结符之间的二元关系符号分别是、教材里常用 ≐ 表示、。注意这里的“小于、等于、大于”不是数值比较而是“优先级关系”的抽象如果a b意思是终结符a的优先级低于终结符b那么在实际分析中当栈顶出现a而当前输入符是b时应该优先处理b代表的运算也就是先把b移进栈。举个例子在经典表达式文法里 *表示加号的优先级低于乘号。处理i i * i时栈顶终结符是当前输入是*因为 *所以把*移进栈而不是急着把左边的部分归约。这直观对应了“先乘除后加减”。a ≐ b表示两者优先级相等通常出现在“括号配对”或者“同一个运算符连续出现但结合性需要特殊处理”的场景。比如(和)之间有( ≐ )表示遇到右括号时可以把括号内的内容整体归约。a b则表示栈顶终结符优先级更高该做归约了。三种关系合在一起构成了分析程序的决策依据比较栈顶终结符和当前输入符若或≐则移进若则归约。2.2 FIRSTVT 和 LASTVT 的递归计算规则构造优先关系表之前必须先算出每个非终结符的 FIRSTVT 集合和 LASTVT 集合。FIRSTVT(A) 的定义是从 A 出发经过一步或多步推导得到的句型中“最左边可能出现的终结符集合”。它和 FIRST 集合的区别在于FIRSTVT 只关心第一个符号是终结符的情况如果第一个符号是非终结符则继续追踪这个非终结符的 FIRSTVT直到遇到终结符为止。计算规则可以归纳为两条基础规则和一条迭代规则如果产生式形如A → a...或A → B a...那么终结符a属于 FIRSTVT(A)。如果产生式形如A → B...且b ∈ FIRSTVT(B)那么b也属于 FIRSTVT(A)。用大白话说第一条规则找“直接以终结符开头”的候选式第二条规则负责把左部非终结符打头的候选式继续传递下去。LASTVT(A) 的定义完全对称从 A 出发推导出的句型中“最右边可能出现的终结符集合”。计算规则也对称如果产生式形如A → ...a或A → ...aB那么终结符a属于 LASTVT(A)。如果产生式形如A → ...B且b ∈ LASTVT(B)那么b也属于 LASTVT(A)。实际手工推导时建议大家从最底层的非终结符往上推。因为底层非终结符的候选式最简单FIRSTVT/LASTVT 一眼就能看出来往上层层传递时才不容易漏项。2.3 优先关系表的三条构造规则有了 FIRSTVT 和 LASTVT就可以构造优先关系表了。对文法中每条产生式逐一检查应用下面三条规则若产生式右部出现...a b...或...a B b...a、b为终结符B为非终结符则a ≐ b。这条规则本质是终结符紧挨着终结符或者被一个非终结符隔开的两个终结符它们在语法结构上处于同一层所以优先级相等。若产生式右部出现...a B...a是终结符B是非终结符则对 FIRSTVT(B) 中的每个终结符b都有a b。意思是终结符a后面跟了一个非终结符B那么B能推导出的所有“开头终结符”优先级都比a高处理时要先处理b。若产生式右部出现...B a...a是终结符B是非终结符则对 LASTVT(B) 中的每个终结符b都有b a。意思是非终结符B后面直接跟终结符a那么B能推导出的所有“结尾终结符”优先级都比a高处理时先归约B的部分。这三条规则一定要对照着具体产生式去理解光背很容易弄混方向。我见过很多同学把第 2 条和第 3 条搞反最后表里全是错的。有个笨但有效的记忆法看产生式右部终结符在前、非终结符在后那就是“前面低、后面高”记非终结符在前、终结符在后那就是“前面高、后面低”记两个终结符之间要么直接挨着要么隔了一个非终结符那就是“相等”记≐。3. 完整实例经典表达式文法全流程演算3.1 选用文法与目标说明为了把上面的规则落到实地我们用一个几乎所有教材都会用的经典表达式文法E → E T | T T → T * F | F F → ( E ) | i这里E表示表达式T表示项F表示因子终结符集合是{, *, (, ), i}非终结符集合是{E, T, F}开始符号是E。注意这个文法没有把减法和除法放进来是为了让推导过程更清爽实际扩展时思路完全一样。我们的目标是通过手工推导得到完整的算符优先关系表然后用这个表去分析输入串i i * i看它如何一步步完成归约。整个流程走完你对优先分析法的理解会从“背规则”变成“会推规则”。3.2 FIRSTVT 和 LASTVT 完整推导先从最底层的F开始。F的产生式是F → ( E ) | i。第一条基础规则遇到F → i右部直接以终结符i开头所以i ∈ FIRSTVT(F)遇到F → ( E )右部也直接以终结符(开头所以(也属于FIRSTVT(F)。因此FIRSTVT(F) { (, i }再看 LASTVT(F)。产生式F → i右部以终结符i结尾所以i ∈ LASTVT(F)产生式F → ( E )右部以终结符)结尾所以) ∈ LASTVT(F)。因此LASTVT(F) { ), i }接着推T。T的产生式是T → T * F | F。先看 FIRSTVT产生式T → F右部以非终结符开头所以FIRSTVT(F)中的所有元素都要传给T即(, i进入FIRSTVT(T)。产生式T → T * F右部以非终结符T开头没有直接以终结符开头的候选式但注意右部第二个符号是终结符*虽然它不是右部开头但在 FIRSTVT 的定义里A → B a...中的a也是 FIRSTVT(A) 的成员。这里的T → T * F正好就是A → B a...的形式A是TB是Ta是*。所以* ∈ FIRSTVT(T)。综合起来FIRSTVT(T) { *, (, i }LASTVT(T)产生式T → F右部以非终结符结尾LASTVT(F)中的), i都进入LASTVT(T)。产生式T → T * F右部以非终结符F结尾所以LASTVT(F)继续传给T同时它符合A → ...aB的形式a是*所以*也属于LASTVT(T)。综合LASTVT(T) { *, ), i }最后推E。E → E T | T。FIRSTVT(E)E → T把 FIRSTVT(T) 全部传过来即*, (, iE → E T符合A → B a...a是所以 ∈ FIRSTVT(E)。因此FIRSTVT(E) { , *, (, i }LASTVT(E)E → T把 LASTVT(T) 全部传过来即*, ), iE → E T符合A → ...aBa是所以 ∈ LASTVT(E)。因此LASTVT(E) { , *, ), i }这就是整个推导过程。检查一下有没有漏项E的 FIRSTVT 里面没有)E的 LASTVT 里面没有(都是符合预期的。3.3 优先关系表的生成过程有了 FIRSTVT/LASTVT逐条产生式套三条规则。先看F → ( E )。右部是( E )符合...aB b...的模式其中a是(B是Eb是)所以规则 1 给出( ≐ )。同时这个产生式还包含...aB...的模式(后跟E所以规则 2 给出对 FIRSTVT(E) 中的每个终结符b有( b。FIRSTVT(E) 是{, *, (, i}也就是说( ( * ( ( ( i再看F → i没有成对的终结符没有产生任何优先关系这符合直觉单个因子本身就是最基础的操作数不需要额外定义优先级。看T → T * F。右部是T * F符合...B a...和...aB...同时出现的模式。先处理aB部分*后跟非终结符F规则 2 给出* FIRSTVT(F)而 FIRSTVT(F) 是{(, i}所以* ( * i再处理Ba部分非终结符T后跟*规则 3 给出 LASTVT(T) 中的每个终结符b有b *。LASTVT(T) 是{*, ), i}所以* * ) * i *看T → F右部只有单个非终结符不产生任何优先关系。看E → E T。右部是E T。规则 2 处理后跟T FIRSTVT(T)而 FIRSTVT(T) 是{*, (, i}所以 * ( i规则 3 处理E后跟LASTVT(E) 中的每个终结符b有b 。LASTVT(E) 是{, *, ), i}所以 * ) i 看E → T右部单个非终结符不产生优先关系。最后处理边界符号#。分析开始前栈底和输入串末尾都有#它不属于文法终结符但参与分析。习惯上定义# FIRSTVT(E) LASTVT(E) # # ≐ #也就是# 、# *、# (、# i以及 #、* #、) #、i #还有# ≐ #。把这些关系汇总到一张 6×6 的表格里行表示栈顶终结符列表示当前输入终结符结果如下优先关系*()i#空*(≐空)空空i空空#空≐表中的“空”表示这一对终结符之间没有定义优先关系一旦分析过程中需要比较它们就说明输入串有语法错误。比如i i在正常表达式中是非法的表中i行i列没有关系程序会在这里报错这是合理行为。3.4 用优先关系表分析输入串i i * i有了表分析过程就变成机械操作了。用一个栈存放文法符号开始时栈底放#输入串末尾也放#。每次比较栈顶终结符a和当前输入符b若a b或a ≐ b把b移进栈若a b则找栈顶最左素短语进行归约若没有定义关系报错。下面分析i i * i我列出关键步骤。为了可读性非终结符统一归约为N因为算符优先分析在归约时并不关心非终结符的具体名字只知道“这里归约出了一个非终结符”就够了。第一步栈是#输入是i i * i #。查表#和i# i移进i栈变成# i输入变成 i * i #。现在栈顶终结符是i当前输入符是查表i 所以归约。把栈顶的i归约为N栈变成# N。第二步栈顶终结符是#当前输入符是查表# 移进栈变成# N 输入变成i * i #。接着比较栈顶终结符和输入符i i移进i栈变成# N i输入变成* i #。第三步比较栈顶终结符i和当前输入符*查表i *所以归约i为N栈变成# N N。继续比较栈顶终结符和输入符* *移进*栈变成# N N *输入变成i #。再比较*和i* i移进i栈变成# N N * i输入变成#。第四步比较栈顶终结符i和输入符#i #归约i为N栈变成# N N * N。此时栈顶终结符是*输入符是#查表* #继续归约。把N * N归约为N栈变成# N N。再比较栈顶终结符和输入符# #继续归约把N N归约为N栈变成# N。最后比较栈顶终结符#和输入符## ≐ #分析成功结束。观察整个流程可以发现算符优先分析在第二步到第三步之间实际上先归约了右边i * i中的因子再归约整个乘积最后才处理加法完全符合“先乘除后加减”的运算顺序。这就是这个方法名字里“优先”两个字的真正含义——它不需要像 LR 那样严格寻找句柄只需要按照优先关系决定“什么时候算、什么时候往后看”。4. 素短语、最左素短语与文法合法性判定4.1 素短语到底是个什么东西既然算符优先分析归约的不是句柄那它每次归约的到底是什么答案是“最左素短语”。素短语的定义是至少包含一个终结符并且除自身之外不再包含任何更小的素短语的短语。字面描述比较绕我换个说法。在一个句型中有些子串是一个产生式的右部这些子串叫“短语”。句柄是其中最左边那个。素短语则额外要求这个子串内部不能套着另一个可以归约的短语而且它必须包含至少一个终结符否则就退化成了只有非终结符的归约无法用优先关系驱动。还是看i i * i的句型N N * i。在这个句型里N * i是一个素短语因为它包含终结符*和i并且内部不再有可以归约的短语。N N * i整体虽然也能匹配某个产生式的右部但它内部包含N * i这个更小的可归约子串所以它不是素短语。在每一步归约中算符优先分析选择的是“最左边”的那个素短语这就是“最左素短语”。这个定义直接关系到归约动作的正确性。分析程序在决定归约时不能随便归约一个能匹配产生式的子串而必须找最左素短语。实现时通常采用“从栈顶向下扫描找到第一个终结符优先级低于前一个终结符的位置”这个位置到栈顶之间的子串就是要归约的素短语。你如果自己写分析器这部分的代码逻辑值得单独测。4.2 算符优先文法的三个判定条件并不是任何文法都能用算符优先分析法用之前需要先判断文法是不是“算符优先文法”。教材里的判定条件主要有三条文法中不能有形如A → ...BC...的产生式右部也就是说两个非终结符不能相邻出现。理由很明显算符优先关系只定义在终结符之间如果两个非终结符贴在一起中间没有终结符作为“锚点”就无法用优先关系驱动分析。对任意两个终结符a、b它们之间至多只有一种优先关系成立。如果同时出现了a b和a b或者既≐又就说明文法有歧义优先关系表不唯一分析程序不知道该移进还是归约。没有二义性的基本要求文法本身必须是二义性文法之外的非二义性文法。这三条条件里第二条在实际做题时最容易踩坑。比如有的同学推导和的优先关系时发现从E → E T得到 但内心又觉得“同一个运算符应该相等”于是擅自写成 ≐ 结果构造出的表和标准答案对不上。其实在左结合文法里同级运算符之间是而不是≐因为左结合意味着右边的运算符要“等左边的算完再算”所以栈顶的运算符优先级更高。判断的时候一定要跟着规则走不要凭直觉改结果。4.3 优先函数节省一张表的工程化手段优先关系表虽然直观但存储空间是终结符个数的平方。对嵌入式环境这种资源敏感的场景可以把表压缩成两个一维数组栈内优先函数f和输入优先函数g让优先关系的比较变成整数比较。定义是a b当且仅当f(a) g(b)a ≐ b当且仅当f(a) g(b)a b当且仅当f(a) g(b)。构造优先函数的方法有迭代法和关系图法。关系图法的思路是把每个终结符a拆成两个节点一个代表f(a)一个代表g(a)根据优先关系连边a b从f(a)连向g(b)a b从g(b)连向f(a)a ≐ b则同时连两条边。然后对每个节点求最长路径长度作为其优先函数值。有环说明不存在优先函数。但优先函数有个致命弱点它把“无优先关系”和“优先级相等”混为一谈。原来的表中i和i之间无定义转为优先函数后可能被解释为相等导致错误输入无法及时报错。所以实际工程里如果要用优先函数必须额外在文法层面保证“凡是表中无定义的位置运行时一定不会出现”。这一点在做实验时容易被忽略面试被问到优先函数时也常常作为加分点。5. 程序化实现把分析表生成和分析过程写成代码5.1 数据结构怎么设计最顺手如果你正在写“算符优先分析表生成”实验第一步不是急着写算法而是把数据结构设计好。我自己的习惯是终结符集合用一维数组存#放在最后一位FIRSTVT 和 LASTVT 用二维布尔矩阵表示行是非终结符列是终结符值为true表示该终结符属于对应非终结符的集合优先关系表用二维字符数组存储取值 、、、四种。用布尔矩阵而不是set的好处是后续迭代计算非常直观直接遍历矩阵找true而不需要做集合求并、判断元素是否存在等操作。对于学习级代码这种“空间换逻辑”的思路能少掉很多头发。5.2 FIRSTVT/LASTVT 迭代求解的核心代码逻辑FIRSTVT 和 LASTVT 的计算可以统一用“迭代到不再变化”的方式实现。以 FIRSTVT 为例初始时遍历所有产生式找到满足A → a...或A → B a...的候选式把终结符a标记进 FIRSTVT(A)。然后不断遍历产生式只要遇到A → B...且 FIRSTVT(B) 中有新的终结符就把这些终结符也加入 FIRSTVT(A)直到所有集合都不再增长。这里给一段思路性的 Python 伪代码def compute_firstvt(grammar, non_terminals, terminals): firstvt {nt: set() for nt in non_terminals} changed True while changed: changed False for lhs, rhs_list in grammar.items(): for rhs in rhs_list: # 规则: A - a... 或 A - B a... if rhs[0] in terminals: if rhs[0] not in firstvt[lhs]: firstvt[lhs].add(rhs[0]) changed True elif len(rhs) 2 and rhs[0] in non_terminals and rhs[1] in terminals: if rhs[1] not in firstvt[lhs]: firstvt[lhs].add(rhs[1]) changed True # 规则: A - B... if rhs[0] in non_terminals: for b in firstvt[rhs[0]]: if b not in firstvt[lhs]: firstvt[lhs].add(b) changed True return firstvtLASTVT 的代码完全对称只是把“开头”换成“结尾”把...aB和...B a的判断条件换一下。写代码时最容易出 bug 的地方是产生式右部的边界条件len(rhs) 2判断一定要写否则当右部只有一个非终结符时会越界。这个坑我在第一次写的时候踩过报错还不是报在明显的地方是算出来的集合莫名其妙少符号排查了很久才发现是越界访问。5.3 分析驱动主程序的实现要点分析驱动主程序是另一个重要模块。核心逻辑就是维护一个栈不断比较栈顶终结符和当前输入符执行移进或归约。栈里面会混合存放非终结符和终结符但比较优先级时要从栈顶往下找“最近的那个终结符”跳过非终结符。伪代码大概是这样的def analyze(tokens, precedence_table, terminals): stack [#] tokens.append(#) ip 0 while True: # 找到栈顶最近的终结符 top_terminal next(t for t in reversed(stack) if t in terminals) cur tokens[ip] rel precedence_table[top_terminal][cur] if rel : raise SyntaxError(非法终结符组合) if rel or rel : stack.append(cur) ip 1 elif rel : # 找最左素短语并归约 # 从栈顶往下扫描, 找到第一个 的位置 # 中间的子串整体归约为非终结符 do_reduce(stack) if stack [#] and cur #: break归约时不需要真的查产生式决定用哪个非终结符替换因为算符优先分析不关心非终结符名字直接把素短语替换成统一的N就行。这也是写实验代码时最省事的地方。如果后续要做语法树那在归约时需要记录“这个素短语对应文法的哪个产生式”再在栈里压入对应的左部非终结符。实际上如果实验要求是“生成优先关系表并分析句子”我建议把表生成和分析驱动分成两个独立文件来写。表生成部分专心处理 FIRSTVT、LASTVT 和优先关系分析驱动部分只依赖二维表结果这样两边独立测试出错了也容易定位。6. 手工推导与实验中出现的高频问题6.1 FIRSTVT/LASTVT 计算时的常见漏项我批过不少同学的作业FIRSTVT 和 LASTVT 计算中最常见的错误就三种。第一种是漏掉形如A → B a...这种产生式右部“第二个位置”的终结符。很多人记得A → a...规则却忘了B a...这种非终结符后面紧跟终结符的情况也要加入集合。比如E → E T里属于 FIRSTVT(E) 不是因为它出现在右部开头而是因为它出现在第一个非终结符E后面。第二种是迭代传递时只传了一层。比如文法有三层产生式E → T、T → F、F → i如果遍历一遍就结束很可能只算出 FIRSTVT(T) 包含i忘了继续传给 FIRSTVT(E)。解决办法就是前面代码里的while changed循环一直循环到没有任何变化为止。手工算的时候可以用“标记已传递”的方法每轮只检查新增元素不然很容易漏。第三种是把#当作普通终结符参与 FIRSTVT/LASTVT 计算。#只是分析时的界符不属于文法符号计算 FIRSTVT/LASTVT 时不应该包含它。有同学在初始时把#放进去结果优先关系表里多出一堆莫名其妙的行和列分析时又对不上号。6.2 优先关系表出现冲突怎么处理如果算出的优先关系表中同一对终结符既出现了又出现了或者既≐又那基本可以断定文法不是算符优先文法。遇到这种情况不要试着“手工改表”而要回到文法层面解决。最常见的处理手段是改写文法。比如原本有产生式E → E E | E * E | (E) | i这个文法有二义性i i * i可以有两种不同的语法树导致和*的优先关系无法唯一确定。解决办法就是把它分层拆成我们前面用的E → E T | T、T → T * F | F这种形式让优先级通过文法层级天然体现。拆完之后再算优先关系表冲突就消失了。还有一种情况是左结合和右结合混用导致的问题。比如要支持赋值运算的右结合直接写E → id E | ...会引入 还是 的疑问。多数教材的处理方式是把右结合的运算单独用一层产生式表示或者在算优先函数时特殊处理。考试和面试里最常见的考法就是给你一个二义性文法让你判断它“是否是算符优先文法”并说明理由答案的核心就落在“两个终结符之间存在不止一种优先关系”这一点上。6.3 面试常问的几个“为什么”面试官问到优先分析法时通常不是考你会不会构造表而是考你对概念边界的理解。以下几个问题是我多次遇到的也是我觉得最值得提前想清楚答案的。问算符优先分析和 LR 分析的核心区别是什么答LR 分析是规范归约每次归约的必然是最右推导的逆过程对应的句柄算符优先分析只比较终结符之间的优先关系归约的是最左素短语不是规范归约。LR 分析能力强、适用范围广但分析表和状态机构建复杂算符优先分析表小、实现简单适合表达式类文法但无法处理非算符优先文法。问为什么算符优先分析归约时不关心非终结符的具体名字答因为优先关系只定义在终结符之间非终结符既不参与比较也不影响移进归约决策。归约时只需要把素短语替换成一个非终结符并继续分析语法树的构建是后续语义动作的事。问句柄和素短语有什么区别答句柄是规范归约中每一步要归约的短语它一定是短语且是最左的素短语是至少含一个终结符且内部不再含更小短语的短语。对算符优先分析来说最左素短语是归约对象但它不一定是句柄。一个经典反例是简单优先分析法中句柄和素短语可能不一致的情况不过在算符优先分析的适用范围里最左素短语已经足够完成语法识别。6.4 实验课测试用例选择经验最后分享一点实验课的实际经验。写完算符优先分析器之后不要只测i i * i这种教科书用例一定要准备几组边界测试。我建议至少要测四类一是正常优先级测试比如i i * i、(i i) * i验证乘除优先和括号处理二是连续运算测试比如i i i验证同级左结合的处理三是嵌套括号测试比如i * (i (i i))验证多层括号场景四是错误输入测试比如i 、()、i i、i * * i预期行为是程序能够报告语法错误而不是陷入死循环或者数组越界。尤其要注意i i这种错误输入。由于表中i和i没有优先关系分析器比较栈顶符号和当前输入符时应该立刻报错。如果程序在这种输入下发散大概率是“无优先关系”被当成了或处理检查一下比较逻辑里是否严格判断了空格字符。在实际写代码过程中我的体会是算符优先分析适合用“先把表打出来、再手工验证几条路径”的方式调试。建一个很小的文法打印 FIRSTVT、LASTVT 和优先关系表对照教材答案核对确认无误后再去跑分析程序。比起直接调一个庞大的分析器这样分阶段验证能省下大量排查时间。优先分析法虽然不如 LR 强大但它的简洁性至今仍是处理表达式文法的有效工具也是理解更复杂自下而上分析算法的重要一步。