1. 项目概述为什么算符优先分析是“老派”但管用的手艺如果你写过编译器或者哪怕只是尝试过手写一个表达式求值器大概率都遇到过那个经典难题1 2 * 3应该先算哪个人脑一看就知道是2*3先算但怎么让计算机也“知道”这个规则这就是算符优先分析要解决的核心问题。它不是什么新潮技术在龙书《编译原理原理、技术与工具》里属于语法分析章节中比较“古典”的方法但恰恰是这种古典让它成为理解编译器如何“思考”表达式优先级和结合性的绝佳入口。简单说算符优先分析就是一种专门用来处理表达式语法的自底向上语法分析方法。它不搞复杂的LR分析表也不依赖庞大的状态机核心思想就一条通过比较相邻算符操作符之间的优先级关系来决定规约reduce的顺序。这听起来有点抽象我打个比方它就像给加减乘除这些算符定了一套“社交礼仪”。乘除*,/优先级高见面了就得先“处理”计算加减,-优先级低得等着。同一优先级的比如连续的加减是左结合从左往右算还是右结合从右往左算也得靠这套“礼仪”来约定。你可能会问现在都有成熟的Yacc、Bison或者ANTLR这些工具了谁还手写算符优先分析这话对了一半。对于工业级编译器确实直接用工具生成LR或LL分析器更高效可靠。但理解算符优先分析的价值绝不在于让你去造一个生产级的编译器前端而在于它帮你彻底吃透了“优先级”和“结合性”这两个概念的底层实现逻辑。当你搞懂了它怎么通过一个简单的优先级表来驱动分析过程你再去看任何语言的表达式求值甚至去配置一些工具的优先级规则都会有一种“哦原来如此”的通透感。尤其是当你需要快速实现一个领域特定语言DSL的表达式解析或者去优化某个热点代码的求值逻辑时这门“老手艺”往往能带来最直接、最轻量的解决方案。2. 核心思路拆解算符之间的“强弱关系”如何驱动分析算符优先分析的核心是把语法分析问题转化为了一个比较相邻算符优先级的问题。它不再严格区分“终结符”和“非终结符”在栈里的状态而是聚焦于终结符主要是算符之间的关系。这套方法的运转依赖于三个核心概念优先关系表、素短语和最左素短语。2.1 优先关系大于、小于与等于算符之间的优先关系有三种我们可以想象它们在分析栈和剩余输入串的“边界”上进行比较关系栈顶的算符优先级低于待输入串首的算符。这意味着栈顶的算符还不能参与计算需要先把后面更高优先级的算符及其操作数移进shift栈中。例如面对和* *成立所以看到1 2 * ...时要等*进来。关系栈顶的算符优先级高于待输入串首的算符。这意味着栈顶部分已经可以作为一个可规约的单元进行计算了。例如面对*和* 成立所以在... * 2 ...时* 2这部分可以先计算。关系栈顶算符与待输入串首算符优先级相等。这通常出现在具有相同优先级的算符之间或者括号匹配的情况下。对于左结合的算符如,-,*,/当遇到关系时也意味着栈顶部分可以规约了以确保从左到右计算。注意这里的,,是关系符号不是算术比较符。它们定义了算符间的优先次序是算法进行移进-规约决策的唯一依据。2.2 素短语与最左素短语找到规约的“最小单元”在自底向上分析中我们需要知道把栈里的哪一部分替换规约成某个语法符号。算符优先分析找的不是句柄handle而是最左素短语。素短语是指至少包含一个终结符算符并且除自身之外不再包含任何更小的素短语的短语。你可以把它理解为表达式树中以某个最低优先级算符为根的子树所对应的符号串。最左素短语就是当前句型栈内容剩余输入中最左边的那个素短语。算符优先分析算法每次规约的就是当前的最左素短语。找到最左素短语的方法很直观在分析栈中从左到右找到第一个满足关系 的算符对然后以这两个算符为边界它们之间的部分包括算符和操作数就是最左素短语。例如对于栈内容... a * b如果栈顶是*且下一个算符是假设* 那么a * b就可能是一个最左素短语的候选。2.3 算法流程移进与规约的舞蹈有了优先关系表和最左素短语的概念算法的骨架就清晰了。它维护一个符号栈初始时栈底有一个特殊的分界符#通常表示输入开始/结束。算法不断比较栈顶的终结符算符和当前输入串首的终结符算符之间的优先关系来决定动作移进Shift如果栈顶算符优先级低于输入串首算符即关系说明栈顶的运算还不能进行需要将输入符号压入栈中继续读取下一个输入。规约Reduce如果栈顶算符优先级高于输入串首算符即关系说明栈顶已经形成了一个可计算的表达式单元最左素短语。此时算法在栈中找到这个最左素短语的边界即找到 ... 这样的模式将这一整段内容弹出栈并压入一个代表表达式结果的符号比如一个临时变量名或抽象语法树节点E。接受Accept当栈中只剩下#和最终规约得到的文法开始符号如E并且输入也只剩下#时分析成功。报错Error如果栈顶算符和输入串首算符之间的优先关系未定义或者规约时找不到合法的素短语则说明表达式存在语法错误。这个过程的本质就是通过优先关系来模拟一棵表达式语法树的后序遍历构建过程。规约动作对应着为子树根节点赋值移进动作对应着继续遍历子节点。3. 构建优先关系表手工推导与算法实现算符优先分析器能否正确工作完全依赖于那张算符优先关系表。这张表定义了所有可能相邻的算符对之间的关系,,或空表示错误。构建方法主要有两种基于算符优先文法的形式化推导以及更实用的、基于算符优先级和结合性声明的方法。3.1 基于算符优先文法的推导一个算符优先文法需要满足严格的条件任何产生式的右部不含两个相邻的非终结符并且算符之间的优先关系是唯一的。对于这样的文法我们可以通过以下步骤计算优先关系定义 FIRSTVT 和 LASTVT 集合FIRSTVT(P)非终结符P能推导出的所有串的第一个终结符的集合。LASTVT(P)非终结符P能推导出的所有串的最后一个终结符的集合。 计算这两个集合是构建关系表的基础它们帮助确定当非终结符出现在栈中时其“代表”的边界算符是什么。计算三种优先关系关系直接看产生式。如果产生式形如... A b B ...或... A b ...或... b A ...其中b是终结符则可能存在b b的关系对于括号就是( )。关系如果存在产生式A - ... B b ...那么对于FIRSTVT(B)中的每一个终结符a都有a b。关系如果存在产生式A - ... b B ...那么对于LASTVT(B)中的每一个终结符a都有b a。这个过程比较繁琐更适合教学理解。在实际的编程语言中算符种类繁多文法复杂很少直接用手工推导整个优先关系表。3.2 更实用的方法优先级与结合性声明在实践中更常用的方法是直接根据算符的优先级数字和结合性来动态计算优先关系。这也是许多工具如早期版本的Yacc内部采用的思想。具体步骤是为每个算符定义优先级和结合性。例如*,/: 优先级 3左结合,-: 优先级 2左结合: 优先级 1右结合赋值(,): 特殊处理括号具有最高“强制”优先级。动态计算关系当需要比较栈顶算符top_op和输入算符next_op时如果next_op是)而top_op是(则关系为括号匹配。如果top_op是(或next_op是)通常需要特殊处理移进或等待匹配不直接比较优先级。否则比较top_op和next_op的优先级数值prec(top_op)和prec(next_op)如果prec(top_op) prec(next_op)则关系为移进。如果prec(top_op) prec(next_op)则关系为规约。如果prec(top_op) prec(next_op)则看结合性左结合关系为规约保证从左到右计算。右结合关系为移进保证从右到左计算如赋值语句a b c。无结合如某些语言中的比较运算符报错。这种方法无需维护一个庞大的、静态的N x N关系表只需一个算符到优先级结合性的映射字典在运行时按需计算更加灵活和节省空间。我在实现一些小型的解释器或DSL时几乎都采用这种方法。3.3 一个简单算术表达式的优先表示例假设我们只有,*,(,)和操作数id优先级*括号最高左结合。我们可以得到如下优先关系表#作为起止符优先级最低*****()id#*****()id#实操心得手工填这个表很容易出错特别是括号的处理。一个检查技巧是对于左结合的算符其同行关系如对通常是这保证了从左到右计算而同列关系则反映了移进条件。(所在行基本都是除了对)是因为它期待被匹配)所在列基本都是除了对(是因为它表示一个子表达式结束可以规约了。4. 算法实现详解从伪代码到可运行的程序理解了原理和表格我们来动手实现一个核心的算符优先分析器。这里我用一个高度简化的算术表达式仅包含,-,*,/,(,)和数字作为例子采用上面提到的动态优先级比较法来实现。这样代码更清晰也更容易扩展到更多算符。4.1 数据结构定义与初始化首先我们需要定义算符的优先级和结合性。为了处理方便我们使用两个栈一个操作数栈operand_stack存放数字或中间结果一个算符栈operator_stack存放算符和#。# 定义算符优先级和结合性 # 优先级数值越大优先级越高 PRECEDENCE { : 1, -: 1, *: 2, /: 2, # ( 在栈内时具有特殊最低优先级或单独标记在栈外时具有最高优先级需要特殊处理 } ASSOC { : L, -: L, *: L, /: L, # 赋值运算符 可以是 R (右结合) } # 初始化栈 operator_stack [#] # 栈底放入哨兵 # operand_stack [] # 辅助函数获取栈顶算符的优先级考虑 ( 的特殊情况 def get_prec(op, in_stackTrue): if op (: # 在栈内时( 的优先级被设为最低防止它被其他算符规约直到遇到 ) # 在栈外时即输入中( 拥有最高优先级强制被移进 return 0 if in_stack else float(inf) return PRECEDENCE.get(op, -1) # 默认返回-1用于处理未知符号或 # # 辅助函数应用一次二元运算 def apply_operation(op, right, left): # 注意顺序操作数栈是后进先出所以先弹出的是右操作数 if op : return left right elif op -: return left - right elif op *: return left * right elif op /: if right 0: raise ZeroDivisionError(Division by zero) return left / right else: raise ValueError(fUnknown operator: {op})4.2 核心分析循环核心算法是一个while循环不断读取输入令牌token并根据栈顶算符和当前输入算符的优先级关系做决策。def evaluate_expression(tokens): tokens: 一个令牌列表例如 [2, , 3, *, (, 4, -, 1, ), #] # 作为输入结束标志 operator_stack [#] operand_stack [] tokens.append(#) # 确保输入以#结束 i 0 while i len(tokens): current_token tokens[i] # 情况1当前令牌是数字操作数 if current_token.isdigit(): operand_stack.append(int(current_token)) i 1 continue # 情况2当前令牌是算符包括括号 top_op operator_stack[-1] # 比较优先级 # prec_top: 栈顶算符的优先级在栈内的状态 # prec_cur: 当前输入算符的优先级在栈外的状态 prec_top get_prec(top_op, in_stackTrue) prec_cur get_prec(current_token, in_stackFalse) # 处理 ( 和 ) 的特殊逻辑 if current_token (: # ( 总是直接入栈 operator_stack.append(current_token) i 1 elif current_token ): # 遇到 )不断弹出栈顶算符进行运算直到遇到 ( while operator_stack[-1] ! (: if operator_stack[-1] #: raise SyntaxError(Unmatched parenthesis) # 执行规约 op operator_stack.pop() right operand_stack.pop() left operand_stack.pop() result apply_operation(op, right, left) operand_stack.append(result) # 弹出匹配的 ( operator_stack.pop() i 1 # 常规算符优先级比较 elif prec_cur prec_top: # 当前算符优先级更高移进 operator_stack.append(current_token) i 1 elif prec_cur prec_top: # 栈顶算符优先级更高规约 op operator_stack.pop() right operand_stack.pop() left operand_stack.pop() result apply_operation(op, right, left) operand_stack.append(result) # 注意这里不移动i因为规约后要用新的栈顶算符再次与current_token比较 else: # 优先级相等根据结合性决定 if ASSOC.get(current_token, L) L: # 左结合规约 op operator_stack.pop() right operand_stack.pop() left operand_stack.pop() result apply_operation(op, right, left) operand_stack.append(result) else: # 右结合移进 operator_stack.append(current_token) i 1 # 检查是否到达输入末尾且栈中只剩 # if current_token # and len(operator_stack) 1 and operator_stack[0] #: break # 最终结果应在操作数栈顶 if len(operand_stack) 1: return operand_stack[0] else: raise RuntimeError(Evaluation error, operand stack has unexpected size.)4.3 算法执行过程模拟让我们用表达式2 3 * (4 - 1)来手动模拟一下核心步骤输入令牌流为[2, , 3, *, (, 4, -, 1, ), #]。步骤操作数栈算符栈 (栈顶在右)剩余输入动作说明初始[][#]2 3 * ( 4 - 1 ) #1[2][#] 3 * ( 4 - 1 ) #移进数字22[2][#, ]3 * ( 4 - 1 ) ##移进3[2, 3][#, ]* ( 4 - 1 ) #移进数字34[2, 3][#, , *]( 4 - 1 ) #*移进*5[2, 3][#, , *, (]4 - 1 ) #*(移进(6[2, 3, 4][#, , *, (]- 1 ) #移进数字47[2, 3, 4][#, , *, (, -]1 ) #(-移进-8[2, 3, 4, 1][#, , *, (, -]) #移进数字19[2, 3, 3][#, , *, (]) #-)? 不)触发规约4 - 1 310[2, 3, 3][#, , *]#(遇到)弹出(输入指针移到#11[2, 9][#, ]#*#规约3 * 3 912[11][#]##规约2 9 11结束[11][#]栈中只剩#和结果接受。这个过程清晰地展示了优先级*先于计算和括号改变计算顺序是如何被算法严格遵守的。踩坑记录在实现时最容易出错的地方就是括号的处理和结合性的判断。(在栈内和栈外的优先级必须区别对待否则算法会提前规约导致错误。另外对于像^幂运算这样的右结合算符在优先级相等时必须选择移进而不是规约这一点和左结合算符相反一不留神就会搞反。5. 算符优先分析的局限性、优势与适用场景没有一种语法分析方法是万能的算符优先分析也不例外。清楚它的边界才能更好地决定何时使用它。5.1 主要局限性文法限制严格标准的算符优先文法要求不能有两个相邻的非终结符。这意味着它无法直接处理像if condition then statement这样的控制流语句因为condition和statement通常都是非终结符。它基本被限制在表达式语法的范畴内。无法识别所有语法结构由于它只根据算符优先级做决策对语法结构的检查能力较弱。例如它很难检测出像a b这样的错误虽然可以通过优先关系表设为空来报错但错误信息可能不精确。错误恢复困难相比LR分析器算符优先分析在遇到语法错误时更难进行智能的恢复和继续分析因为它对全局语法结构的把握较弱。需要预先定义所有算符关系对于一门拥有大量操作符的语言手工维护优先关系表非常繁琐且易错。虽然动态优先级法缓解了这个问题但仍需明确定义每个算符的优先级和结合性。5.2 独特优势尽管有局限但在特定场景下它优势明显实现极其简单核心算法就是一个循环加一个优先级比较函数代码量可能只有几十行。比实现一个完整的LR分析器或递归下降分析器要简单得多。运行效率高分析过程只需要比较相邻算符和简单的栈操作没有复杂的状态转移表查找速度很快。非常适合表达式解析这是它的“主场”。对于嵌入式系统、计算器、配置文件解析、模板引擎渲染等需要轻量级表达式求值的场景它是绝佳选择。易于理解和调试整个分析过程非常直观栈的内容和每一步决策都可以很容易地打印出来对于教学和调试极其友好。5.3 典型应用场景基于其优缺点算符优先分析最适合以下场景小型解释器或脚本语言的表达式求值部分例如为一个简单的游戏脚本或领域特定语言DSL实现计算功能。计算器程序从简单的命令行计算器到图形化科学计算器其核心表达式引擎几乎都是算符优先分析的变体。配置文件中的条件表达式很多软件允许在配置文件中使用简单的逻辑或算术表达式如memory_limit 1024 cpu_cores 2用算符优先分析来解析这些表达式非常合适。模板引擎中的变量运算在网页模板或文档模板中经常需要处理像{{ price * quantity * (1 - discount) }}这样的表达式。作为更复杂分析器的一部分在一些编译器中算符优先分析可能被用作一个子模块专门负责快速解析复杂的表达式然后将生成的抽象语法树片段交给更大的语法分析器处理。6. 常见问题、调试技巧与实战建议在实际动手实现和使用的过程中你肯定会遇到各种“坑”。下面是我总结的一些典型问题和解决思路。6.1 常见错误与排查表现象可能原因排查思路与解决方案结果计算错误如23*420优先级关系错误导致先于*规约。1. 检查优先关系表或动态优先级设置确保*的优先级数值大于。2. 检查结合性设置对于左结合的和*同级相遇时应触发规约关系。遇到括号就报错或结果异常括号(和)的优先级处理不当。1.(在输入时优先级应最高强制移进在栈内时优先级应最低防止被规约。2.)不参与常规优先级比较它唯一的作用是触发规约直到遇到匹配的(。3. 确保(和)成功匹配并同时从栈中清除。处理右结合运算符如^出错结合性判断逻辑写反。对于优先级相等的右结合算符应该移进而不是规约。在动态优先级比较中当prec(top) prec(current)时检查结合性判断分支左结合则规约()右结合则移进()。栈操作顺序错误导致运算对象错乱从操作数栈弹出两个操作数时顺序弄反。栈是后进先出LIFO所以先弹出的是右操作数后弹出的是左操作数。牢记apply_operation(op, right, left)的参数顺序。在规约时先弹出的b是右操作数后弹出的a是左操作数计算a op b。画图模拟栈的变化有助于理解。输入结束后栈未清空或状态不对算法循环结束条件有误未能处理完栈中所有算符。在输入令牌消耗完后遇到#必须继续循环不断规约算符栈中剩余的算符直到栈中只剩下#。循环结束条件应是当前令牌为 # 且 算符栈顶也为 #。多位数或浮点数解析错误词法分析分词阶段没做好把123拆成了[1,2,3]。算符优先分析前提是已有正确的词法分析器Tokenizer。确保在输入算法前已将源代码字符串正确分割成令牌流如12.345-[12.3, , 45]。6.2 调试技巧打印详细日志在算法的每一步都打印出当前的操作数栈、算符栈、剩余输入和即将执行的动作移进/规约/应用运算。这是最直接的调试方式上面的模拟表就是这种日志的体现。先测试简单表达式从12、1*23开始再测试12*3、(12)*3最后测试复杂的嵌套表达式。逐步增加复杂度。单元测试为你的分析器编写一组全面的测试用例覆盖各种边界情况单操作数123简单运算a b,a * b优先级a b * c,a * b c括号(a b) * c,a * (b c)结合性a - b - c左结合,a b c右结合如果支持错误输入a b,(a b,a b)6.3 实战建议与扩展与词法分析器结合一个完整的表达式求值器需要词法分析Lexer将字符串拆分成令牌token。你可以先写一个简单的词法分析器识别数字、算符和括号。构建抽象语法树AST上面的实现直接求值。更通用的做法是在规约时不直接计算而是构建AST节点。例如规约a b时不计算ab的值而是创建一个形如BinaryOpNode(, left_node, right_node)的节点压入操作数栈。最终栈顶会得到整个表达式的AST根节点。这为后续的语义分析、优化和代码生成提供了可能。支持变量和函数调用要支持变量如x y操作数栈里存放的可以是变量名或值。你需要一个符号表来存储变量值。对于函数调用如sin(x)需要扩展文法将函数名和(视为一个整体进行特殊处理这通常超出了经典算符优先分析的范围可能需要混合其他方法。错误处理的增强基础的算法遇到错误直接抛出异常。可以增强错误处理比如在优先关系未定义时给出更友好的错误信息“第N个字符附近有语法错误”甚至尝试恢复如跳过非法字符继续分析。算符优先分析就像编程世界里的“螺丝刀”它不是万能的电动工具但在拧表达式这颗“螺丝”时格外顺手和高效。理解它不仅能让你在面试中应对诸如“如何实现一个计算器”这类经典问题更能让你深刻理解优先级和结合性这些基础概念是如何在编译器中落地的。下次当你再看到复杂的表达式时或许就能在脑海里自动上演一遍栈与优先关系的精妙舞蹈了。