企业官网建设流程全解析

Carbon 语言的偏序运算符优先级（Partial Order Operator Precedence）设计与解析器实现

【免费下载链接】carbon-langCarbon Language's main repository: documents, design, implementation, and related tools. (NOTE: Carbon Language is experimental; see README)项目地址: https://gitcode.com/GitHub_Trending/ca/carbon-lang

导读

本文围绕 Carbon 语言工具链的一项核心设计提案——p000555 Operator precedence——展开，解释为什么 Carbon 放弃传统语言“运算符优先级全序（total order）”的做法，改为偏序（partial order）：仅对开发者普遍能牢记的运算符对定义优先级关系，其余组合一律要求显式加括号，否则直接报歧义错误。读完本文，你将理解偏序优先级的设计动机、Hasse 图记法、何时该“添加优先级边”、如何把经典运算符优先级解析器扩展为偏序版本，以及该方案在 Carbon 解析器（toolchain/parse/precedence.cpp）与 yacc/bison 中的实际落地方式。

问题：全序优先级让错误表达式“合法地”存在

多数表达式型语言为每个运算符分配一个严格分层的优先级等级，形成全序。该思路成熟，但有明显缺陷：

• a & b << c * 3在 C++ 中是合法的，但大多数开发者无法一眼读懂它的含义；
• a & 3 == 3有“显而易见”的意图(a & 3) == 3，实际含义却是a & (3 == 3)——语言强行指定了一个反直觉的解析结果；
• 由于优先级规则并非人人皆知，开发者习惯性地打括号，但漏写括号在多数情况下连 lint 工具都不诊断，于是产生隐蔽 bug。

用解析的视角看：给定表达式，我们需要推断其结构——每个运算符的操作数是什么。在没有规则时a $ b ^ c是歧义的：(a $ b) ^ c还是a $ (b ^ c)？传统解法是给每个运算符一个优先级等级并定义全序。例如中缀*的优先级高于中缀+，则*比+绑定得更紧，与出现顺序无关。解析时，只需确定序列中哪个运算符是解析树的根（即表达式中优先级最低的那个），在其处切分表达式，再递归解析每个子表达式即可。

提案：用偏序取代全序

Carbon 的答案是：不给优先级等级定义全序，而是定义偏序。对没有相对顺序的运算符组合，必须由开发者用括号消歧；当程序含义依赖于两个运算符未定义的相对顺序时，因歧义而被拒绝编译。

默认策略是：任何新运算符对其它所有运算符都不定义优先级，与其它运算符组合时强制要求括号。只有当“可以合理期待大多数经常使用 Carbon 的开发者都能可靠记住该规则”时，才添加一条优先级规则。

这一策略有明确的经验依据：C++ 中很多开发者记不住&&vs||、&vs|、&vs<<的相对优先级，因此 Carbon 不应期待开发者记住类似规则。拿不准时，省略规则、等待真实世界的使用经验，是更优选择。

记号约定：用 Hasse 图表示偏序

提案的文档约定用Hasse 图表示运算符优先级偏序：低优先级运算符在下方并连线指向高优先级运算符；同优先级组内如有结合性，用包络箭头表示，左箭头（左到右）表示左结合。

下图来自提案本身（example.svg），它描述的偏序为：*（高）>+（低），两者均左结合；<<非结合；==的优先级低于上述所有运算符；括号(...)的优先级高于上述所有运算符：

依据该图：

• a + b * c解析为a + (b * c)，因为+优先级低于*；
• a + b << c是错误，因为+与<<优先级不可比较（无序），必须加括号。

该图由提案附带的 Python 脚本 figures.py 生成——它本质上是一个把算子分组、连线并交给 Graphvizdot渲染的生成器，其中group负责把一个优先级组内的运算符渲染成一个节点、edge负责添加优先级边、LtR/RtL/NonAssoc控制结合性箭头。

何时添加优先级边：以“能否被可靠记住”为门槛

对于含义对读者而言歧义的程序，拒绝它优于随意挑一个含义。Carbon 只在存在逻辑理由时才给两个运算符排序，而不是为了“给出某个答案”而排序。提案给出的目标是：

对每一种运算符组合，要么可以合理期待大多数经常使用 Carbon 的开发者可靠记住优先级，要么就不应有优先级规则。

例如a * b ^ c（*为乘法、^为按位异或）应被拒绝：没有逻辑理由让哪个先做，也不应期待开发者记住任意的平局裁决。用 C++ 经验校准“知识门槛”：既然许多 C++ 开发者记不住若干位运算/逻辑运算的相对优先级，Carbon 就不该期待开发者记住类似的规则。

偏序上的解析：扩展经典运算符优先级解析器

传统全序优先级可用**运算符优先级解析器（operator precedence parser）**实现，其核心维护一个“当前左侧操作数”和一个“环境优先级”（ambient precedence，即正在解析操作数的那个运算符的优先级；若表达式不是某运算符的操作数，则用占位的最低优先级）：

• 遇到新运算符时，与当前环境优先级比较：
  • 更高：递归（shift），把新运算符的优先级作为新的环境优先级，构造新运算符的右侧；右侧成形后把“左操作数 op 右操作数”组装成新的当前左侧操作数；
  • 相等：按该优先级的结合性处理——左结合则组装表达式；右结合则递归；非结合则报错；
  • 更低：返回已形成的表达式，它是更早运算符的完整操作数。

例如，这正是 Clang 中clang/lib/Parse/ParseExpr.cpp所使用的策略。

上述算法只适用于全序，因为它没有定义“新优先级与环境优先级不可比较”时该做什么。Carbon 提案的关键扩展只需增加一个分支：

• 新运算符优先级与环境优先级不可比较 → 立即产生歧义错误。

核心观察是：一旦看到... a * b ^ c ...且*、^优先级不可比较，后续任何 token 都无法消解歧义，因此可以立刻诊断。简要证明：若该表达式存在合法解析树，则*与^必然一个成为另一个的祖先；而在合法解析树中，从一个运算符到另一个运算符的路径上优先级单调递增，由偏序的传递性可知祖先运算符优先级低于后代运算符——这与两者不可比较矛盾。

提案还指出，偏序优先级同样可用 yacc/bison 实现：采用**优先级爬升法（precedence climbing）**变体。提案给出对应上述 Hasse 图的 yacc 文法：

expression: compare_expression | compare_operand; compare_expression: compare_lhs EQEQ compare_operand { $$ = ($1 == $3); }; compare_lhs: compare_expression | compare_operand; compare_operand: add_expression | multiply_expression | shift_expression | primary_expression; add_expression: add_lhs '+' add_operand { $$ = ($1 + $3); }; add_lhs: add_expression | add_operand; add_operand: multiply_expression | multiply_operand; multiply_expression: multiply_lhs '*' multiply_operand { $$ = ($1 * $3); }; multiply_lhs: multiply_expression | multiply_operand; multiply_operand: primary_expression; shift_expression: shift_lhs LSH shift_operand { $$ = ($1 << $3); }; shift_lhs: shift_expression | shift_operand; shift_operand: primary_expression; primary_expression: INT | '(' expression ')' { $$ = $2; };

注意此处刻意避免文法歧义：在优先级爬升法中，一个primary_expression同时会是shift_expression、multiply_expression和add_expression，若把primary_expression当作expression解释，既可以从shift_expression路径也可以从multiply_expression路径规约，造成歧义。上述文法通过把primary_expression从add_expression和shift_expression中排除，而将其作为compare_operand的独立产生式来规避。这样的 yacc 文法可以对任意优先级偏序系统化地生成。

仓库中的完整实现：yacc/flex 可运行示例

提案随附的 yacc-parser 目录提供了完整的可运行示例：

• example.y：yacc/bison 文法。除了上文的核心文法外，还定义了顶层interpreter产生式（循环读取表达式、以;结尾、打印结果），并声明%token INT LSH EQEQ、%define api.value.type {int}使语义值使用int；
• example.l：flex 词法规则，把[0-9]+映射为INT、<<映射为LSH、==映射为EQEQ，并把* + ( ) ;等直接返回对应字符 token；
• Makefile：一键构建。执行make会依次运行flex example.l、bison example.y --defines，再用clang链接example.tab.c lex.yy.c生成example可执行文件。

有了可执行文件后，输入1 + 2 * 3;会输出7（*绑定更紧），输入1 + 2 << 3;会触发 yacc 的语法错误（+与<<优先级不可比较），从而直观验证“偏序 + 优先级爬升”的解析行为。

落地于 Carbon 工具链：PrecedenceGroup 与优先级查找表

提案提到偏序优先级解析器“作为概念验证已在 Carbon 工具链中实现”。该实现如今在 toolchain/parse/precedence.h 与 toolchain/parse/precedence.cpp 中，由Carbon::Parse命名空间下的两个核心类型支撑：

• OperatorPriority：给定两个相邻运算符$和@与表达式a $ b @ c，枚举三种结果——LeftFirst（左运算符优先级高，解析为(a $ b) @ c）、Ambiguous（表达式歧义）、RightFirst（右运算符优先级高，解析为a $ (b @ c)）；
• Associativity：LeftToRight/None/RightToLeft，其中None意味着“其它运算符需要显式括号”——这正是提案“默认无序、必须加括号”的直接编码；
• PrecedenceGroup：与某个运算符或表达式关联的优先级组，可通过ForLeading（前缀运算符）与ForTrailing（中缀/后缀运算符，Trailing还带is_binary标记区分中缀与后缀一元）查询；另有ForTopLevelExpr、ForExprStatement、ForType、ForRequirements等“哨兵优先级”用于各种语法上下文。

偏序本身实现在 precedence.cpp 的OperatorPriorityTable中，编译期构造的二维查找表：

1. MarkHigherThan声明<高优先级组> → <低优先级组>的基础边，例如Multiplicative > Additive、Additive/位运算/移位 > Relational/Where等，类型构造则使用独立的优先级图（TypePrefix/TypePostfix）；
2. MakeTransitivelyClosed计算传递闭包：若a $ b @ c解析为(a $ b) @ c、b @ c % d解析为(b @ c) % d，则a $ b @ c % d应解析为((a $ b) @ c) % d；
3. MakeSymmetric使关系对称：若a $ b @ c解析为(a $ b) @ c，则a @ b $ c应解析为a @ (b $ c)（即反向后变成RightFirst）；
4. AddAssociativityRules填充对角线：Multiplicative、Additive、位运算与逻辑与/或等传统结合运算符设为LeftToRight，前缀运算符设为RightFirst，其它运算符“要求显式括号”（保持Ambiguous）；
5. ConsistencyCheck校验哨兵层级（Highest最高、Lowest最低）的一致性。

任何一对未建立传递闭包关系的优先级组在查找表中就是Ambiguous，直接对应提案“不可比较 → 歧义错误”的原则。

从语法测试验证“歧义即错误”

Carbon 的文件测试（file_test）体系在 toolchain/parse/testdata/operators 下保存了大量优先级相关用例，例如 fail_precedence_and_or.carbon：

fn F() { // error: parentheses are required to disambiguate operator precedence [OperatorRequiresParentheses] a and b or c; }

该测试断言and与or混用且无括号时，诊断器输出error: parentheses are required to disambiguate operator precedence [OperatorRequiresParentheses]——也就是偏序设计中“不可比较组合被拒绝”的运行时证据。同一目录下还有fail_precedence_as.carbon、fail_precedence_assign.carbon、fail_precedence_or_and.carbon、fail_precedence_where.carbon以及对应的precedence_*.carbon合法用例，分别覆盖as、赋值、where等运算符组合的行为。要单独运行这类测试，可按测试文件头注释执行bazel test //toolchain/testing:file_test --test_arg=--file_tests=...。

设计依据：Carbon 的目标

提案依据 Carbon 项目目标为其合理性辩护：

• 软件与语言演进：拿不准就不提供优先级关系，因为**“添加一条优先级规则比删除一条更容易”**，这符合渐进演进理念；
• 代码易读、易理解、易编写：通过让难以理解的构造非法，确保程序中使用的运算符表达式能被实践者轻松读懂。

备选方案对比

全序（Total order）

可为运算符优先级提供全序。提案并非与全序严格冲突——如果每个排序关系都有充分理由；但实践中必然存在没有明显优先级关系的运算符对。

• 支持：这是多数语言的既有实践；
• 反对：在任意或糟糕的选择下，该实践是 bug 的常见来源。

对左右操作数使用不同优先级

可为中缀运算符的左右两侧定义不同的优先级关系，例如允许<<左侧出现乘法但右侧不允许。这在 C++ 有先例：?:中的?右侧允许逗号运算符而左侧不允许。

• 支持：可能允许一些清晰且不令人意外的额外情形；
• 反对：规则更难学习，很可能无法通过“大多数经常使用 Carbon 的开发者知道规则”这一检验。

该提案与未来采纳此方向并不冲突。

弱于偏序的要求

也可以要求比偏序更弱的结构。提案依赖以下三点对人类理解的重要性：

• 表达式中优先级最低的运算符不依赖于运算符的相对顺序（仅当多个运算符同级时，以结合性作为平局裁决）；
• 若^表达式可以间接（无括号）出现在$表达式内，则^表达式也可以直接出现在$表达式内；
• 若a $ b ^ c中最低优先级运算符是$，且b ^ c # d中最低优先级运算符是^，则a $ b ^ c # d中最低优先级运算符是$。

这些假设共同推出“优先级应构成运算符等价类上的偏序”。若未来出现违反这些假设的动机，应重新考虑偏序方案；目前尚未发现这样的动机案例。

总结

Carbon 的运算符优先级设计以“拒绝歧义，而不是武断指定含义”为哲学核心：用偏序取代全序、以“能否被可靠记住”为添加优先级边的门槛、用 Hasse 图记录约定、把经典运算符优先级解析器扩展一个“不可比较即报错”的分支，并完整落地于 toolchain/parse/precedence.cpp 的编译期查找表与OperatorRequiresParentheses诊断中。对于语言设计者，这是一份“如何系统性消除一类隐蔽优先级 bug”的参考实现；对于工具链开发者，yacc-parser 提供了一份可在任何 LR 文法生成器中复用的最小范例。

【免费下载链接】carbon-langCarbon Language's main repository: documents, design, implementation, and related tools. (NOTE: Carbon Language is experimental; see README)项目地址: https://gitcode.com/GitHub_Trending/ca/carbon-lang