附录: 宏的参照集歧义性形式化规范

该规范是为了帮助理解 Rust 宏展开期间的参照集歧义性而设计的。 参照集是指给定上下文环境下宏可能展开的所有可能性集合。 在某些情况下，这些集合可能会有歧义，这会导致宏展开出现问题。

本页面记录了 实例宏 的正式规范，其中包括以下规则。 这些规则最初在 RFC 550 中进行了规定，本文大部分内容均来自该规范，并在随后的 RFC 中进行了扩展。

定义和约定

• macro: 宏指在源代码中以 foo!(...) 形式调用的内容。
• MBE: 指的是由 macro_rules 定义的实例宏。
• matcher: 匹配器指的是 macro_rules 调用规则的左侧部分或其子部分。
• macro parser: 宏解析器指的是 Rust 解析器中，将使用从所有匹配器派生的语法分析输入的代码部分的过程。
• fragment: 片段指的是给定匹配器将接受 (或 "匹配" 的) Rust 语法类别。
• repetition: 重复指的是遵照规律重复模式的片段。
• NT: 非终端，可以出现在匹配器中的各种 "元变量" 或重复匹配器，在 MBE 语法中使用前缀 $ 字符指定。
• simple NT: 一种 "元变量" 非终端符 (下面会进一步讨论)。
• complex NT: 通过重复运算符 (* 、 + 、 ? ) 指定的重复匹配非终端符。
• token: 匹配器的最小元素，即标识符、运算符、开/闭定界符、 以及 简单 NT 。
• token tree: 由 token (叶子)、复杂 NT 和 token 树的有限序列形成的树结构。
• delimiter token: 用于分隔一个片段的结尾和下一个片段的开头的 token 。
• separator token: 复杂 NT 中的可选分隔符 token ，用于分隔匹配重复中每对元素。
• separated complex NT: 具有自己的分隔符 token 的复杂 NT 。
• delimited sequence: 带有适当的开/闭定界符的 token 树序列。
• empty fragment: Rust 语言中分隔 token 的无形语法类，即空格或 (在某些词法上下文中) 空 token 序列。
• fragment specifier: 简单 NT 中指定 NT 接受的片段的标识符。
• language: 形式自由的语言。

Example:

#![allow(unused)]
fn main() {
macro_rules! i_am_an_mbe {
    (start $foo:expr $($i:ident),* end) => ($foo)
}
}

(start $foo:expr $($i:ident),* end) 是一个匹配器。 整个匹配器是一个带有开/闭定界符 ( 和 ) 的定界序列， $foo 和 $i 是具有 expr 和 ident 作为它们各自的片段规格的简单 NT 。

$(i:ident),* 也是一个 NT ; 它是一个复杂 NT ，用于匹配逗号分隔的标识符的重复。 , 是复杂 NT 的分隔符 token ；它出现在匹配片段的每一对元素 (如果有的话) 之间。

$(hi $e:expr ;)+ 是一个复杂的非终端符(NT)的例子，它匹配形式为 hi <expr>; hi <expr>; ... 的片段，其中至少包含一次 hi <expr>; 。请注意，这个复杂的非终端符并没有专用的分隔符令牌。

(注意， Rust 的解析器确保定界序列始终具有正确嵌套的 token 树结构和正确匹配的开/闭定界符。)

我们通常使用变量 "M" 代表一个匹配器，变量 "t" 和 "u" 代表任意单个 token ，变量 "tt" 和 "uu" 代表任意 token 树。 ( "tt" 的使用可能存在潜在的歧义，因为它还作为片段规格的额外角色；但从上下文中可以清楚地知道意思。)

"SEP" 将遍历分隔符 token ， "OP" 将遍历重复运算符 * 、 + 和 ? ， "OPEN"/"CLOSE" 将遍历匹配定界序列的 token 对 (例如 [ 和 ] )。

希腊字母 "α" "β" "γ" "δ" 表示可能为空的 token 树序列。 (然而，希腊字母 "ε" (epsilon) 在表述中具有特殊作用，不代表 token 树序列。)

• 这种希腊字母约定通常只在序列的存在是技术细节时使用；特别地，当我们希望 强调 我们正在操作 token 树序列时，将使用符号 "tt ..." 表示序列，而不是希腊字母。

请注意，匹配器仅仅是一个 token 树。如上所述，"简单 NT" 是一个元变量 NT；因此它是一个非重复项。 例如， $foo:ty 是一个简单的 NT ，但 $($foo:ty)+ 是一个复杂的 NT。

还请注意，在这种形式化语境下，术语 "token" 通常包括简单的 NT。

最后，读者应该记住，根据这个形式化的定义，没有简单的 NT 匹配空片段，同样，没有 token 匹配 Rust 语法的空片段。 (因此，唯一可以匹配空片段的 NT 是复杂的 NT。) 这实际上并不正确，因为 vis 匹配器可以匹配空片段。 因此，为了形式化的目的，我们将把 $v:vis 实际上视为 $($v:vis)? ，并要求匹配器匹配一个空片段。

匹配器的不变性

要有效，匹配器必须符合以下三个不变量。FIRST 和 FOLLOW 的定义将在后面描述。

1. 对于匹配器 M 中的任意两个连续的 token 树序列 (即 M = ... tt uu ...，其中 uu ... 非空) ，我们必须有 FOLLOW(... tt) ∪ {ε} ⊇ FIRST(uu ...)。
2. 对于匹配器中的任何分隔的复杂 NT，M = ... $(tt ...) SEP OP ...，我们必须有 SEP ∈ FOLLOW(tt ...)。
3. 对于匹配器中的未分隔的复杂 NT，M = ... $(tt ...) OP ...，如果 OP = * 或 +，则我们必须有 FOLLOW(tt ...) ⊇ FIRST(tt ...)。

第一个不变量表示，无论匹配器后面有什么实际 token (如果有的话) ，它都必须在预定的 FOLLOW 集中的某个位置。 这确保了一个合法的宏定义将继续分配相同的决定，即 ... tt 结束并且 uu ... 开始的位置，即使语言中添加了新的语法形式。

第二个不变量表示，分隔的复杂 NT 必须使用作为 NT 内部内容预定 FOLLOW 集的分隔符 token 。 这确保了一个合法的宏定义将继续将输入片段解析为相同的 tt ... 的定界序列，即使语言中添加了新的语法形式。

第三个不变量表示，当我们有一个复杂的 NT 可以匹配两个或多个连续的相同元素而不需要分隔符时，根据第一个不变量，这些元素必须可以被放在一起。 该不变量还要求它们必须是非空的，这消除了可能的歧义。

注意: 由于历史遗漏和对该行为的重要依赖，目前未执行第三个不变量。 目前尚未决定如何继续处理此问题。不遵守此行为的宏在 Rust 的未来版本中可能会变得无效。 请参见 问题跟踪。

FIRST 和 FOLLOW，非正式描述

一个给定的匹配器 M 映射到三个集合: FIRST(M)、LAST(M) 和 FOLLOW(M)。

这三个集合都由 token 组成。 FIRST(M) 和 LAST(M) 还可能包含一个特殊的非 token 元素 ε ("epsilon") ，它表示 M 可以匹配空片段。(但 FOLLOW(M) 总是由一组 token 组成。)

非正式地说：

• FIRST(M)：在将片段与 M 匹配时，收集可能首先使用的 token 。

• LAST(M)：在将片段与 M 匹配时，收集可能最后使用的 token 。

• FOLLOW(M)：在 M 匹配某个片段之后立即允许其后面紧跟的 token 集合。

  换句话说：当且仅当存在 (可能为空的) token 序列 α β γ δ 时，t ∈ FOLLOW(M)，其中：

• M 匹配 β，

• t 匹配 γ ，以及

• 连接 α β γ δ 是一个可解析的 Rust 程序。

我们使用简写 ANYTOKEN 来表示所有 token (包括简单的 NT )。例如，如果在匹配器 M 之后任何 token 都是合法的，则 FOLLOW(M) = ANYTOKEN 。

(为了回顾对上述非正式描述的理解，读者此时可能希望跳转到 FIRST/LAST的示例 ，然后再阅读它们的正式定义。)

FIRST, LAST

以下是 FIRST 和 LAST 的正式归纳定义。

"A ∪ B" 表示并集， "A ∩ B" 表示交集， "A \ B" 表示差集 (即 A 中所有在 B 中不存在的元素)。

FIRST

对于序列 M 及其第一个 token 树的结构 (如果有) ，对 FIRST(M) 进行情况分析定义：

• 如果 M 是空序列，则 FIRST(M) = { ε }，

• 如果 M 以一个 token t 开头，则 FIRST(M) = { t } ，

  (注意：这涵盖了 M 以定界的 token 树序列开头的情况， M = OPEN tt ... CLOSE ... ，在这种情况下，t = OPEN，因此 FIRST(M) = { OPEN }。)

  (注意：这主要依赖于一个属性，即没有简单的 NT 可以匹配空片段。)

• 否则， M 是以复杂的 NT 开头的 token 树序列： M = $( tt ... ) OP α 或 M = $( tt ... ) SEP OP α ， (其中 α 是匹配器的其余部分的 (可能为空的) token 树序列)。

  • 如果 SEP 存在且 ε ∈ FIRST(tt ...) ，则让 SEP_SET(M) = { SEP }; 否则，SEP_SET(M) = {}。

• 如果 OP = * 或 ? ，则让 ALPHA_SET(M) = FIRST(α) ，如果 OP = +，则 ALPHA_SET(M) = {}。

• FIRST(M) = (FIRST(tt ...) \ {ε}) ∪ SEP_SET(M) ∪ ALPHA_SET(M) 。

复杂非终端符的定义需要一些解释。 SEP_SET (M) 定义了分隔符可能是 M 的有效首个符号的可能性，当定义了分隔符并且重复片段可能为空时会发生这种情况。 ALPHA_SET (M) 定义了复杂非终端符可以为空的可能性，这意味着 M 的有效首个符号是以下 token-tree 序列 α 中的符号。 当使用 * 或 ? 时会发生这种情况，此时可能没有重复。理论上，如果使用 + 并带有潜在为空的重复片段，则也可能发生这种情况，但这被第三个不变量禁止。

从这里开始，显然 FIRST(M) 可以包括来自 SEP_SET(M) 或 ALPHA_SET(M) 的任何令牌，如果复合 NT 匹配非空，则任何以 FIRST(tt ...) 开头的令牌也可以使用。 考虑的最后一个部分是 ε 。 SEP_SET(M) 和 FIRST(tt ...) \ {ε}不能包含 ε，但 ALPHA_SET(M) 可能会包含。 因此，这个定义允许 M 接受 ε ，当且仅当 ε∈ALPHA_SET(M) 。这是正确的，因为对于 M 在复合 NT 情况下接受 ε ，复合 NT 和 α 都必须接受它。 如果 OP = + ，意味着复合 NT 不能为空，根据定义， ε∉ALPHA_SET(M) 。 否则，复合 NT 可以接受零次重复，然后 ALPHA_SET(M)=FOLLOW(α) 。因此，这个定义在 ε 方面是正确的。

LAST

LAST(M) 是根据 M 本身 (一个令牌树序列) 的情况分析定义的。

• 如果 M 是空序列，则 LAST(M) = { ε } 。

• 如果 M 是单个令牌 t ，则 LAST(M) = { t } 。

• 如果 M 是单一的复合 NT ，重复出现零次或多次，如 M = $( tt ... ) * 或 M = $( tt ... ) SEP *，则 LAST(M)={LAST('tt ...')}。

  • 如果存在 SEP ，则令 sep_set = { SEP } ；否则，令 sep_set = {} 。
  • 如果 ε ∈ LAST(tt ...) ，则 LAST(M) = LAST(tt ...) ∪ sep_set 。
  • 否则，序列'tt ...'必须是非空的；LAST(M) = LAST(tt ...) ∪ {ε} 。

• 如果 M 是重复出现一次或多次的单一复合 NT ，如 M = $( tt ... ) + 或 M = $( tt ... ) SEP + ，

  • 如果存在 SEP ，则令 sep_set = { SEP } ；否则，令s ep_set = {} 。
  • 如果 ε ∈ LAST(tt ...) ，则 LAST(M) = LAST(tt ...) ∪ sep_set 。
  • 否则，序列 tt ... 必须是非空的；LAST(M) = LAST('tt ...')。

• 如果 M 是重复出现零次或一次的单一复合 NT ，如 M = $( tt ...) ?，则 LAST(M) = LAST(tt ...) ∪ {ε} 。

• 如果 M 是一个定界的 token 树序列 OPEN tt ... CLOSE ，则 LAST(M) = { CLOSE }。

• 如果 M 是一个非空的令牌树的序列 tt uu ... ，

  • 如果 ε ∈ LAST(uu ...) ，那么 LAST(M) = LAST(tt) ∪ (LAST(uu ...) \ { ε }) .

  • 否则，序列 uu ... 必须是非空的；那么 LAST(M) = LAST(uu ...) 。

FIRST和LAST的例子

以下是一些 FIRST 和 LAST 的例子。 (特别注意，基于输入的不同部分之间的交互，特殊元素 ε 是如何被引入和消除的。)

我们的第一个例子以树形结构呈现，以详细阐述匹配器的分析是如何组合的。 (一些简单的子树已省略。)

INPUT:  $(  $d:ident   $e:expr   );*    $( $( h )* );*    $( f ; )+   g
            ~~~~~~~~   ~~~~~~~                ~
                |         |                   |
FIRST:   { $d:ident }  { $e:expr }          { h }


INPUT:  $(  $d:ident   $e:expr   );*    $( $( h )* );*    $( f ; )+
            ~~~~~~~~~~~~~~~~~~             ~~~~~~~           ~~~
                        |                      |               |
FIRST:          { $d:ident }               { h, ε }         { f }

INPUT:  $(  $d:ident   $e:expr   );*    $( $( h )* );*    $( f ; )+   g
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~    ~~~~~~~~~~~~~~    ~~~~~~~~~   ~
                        |                       |              |       |
FIRST:        { $d:ident, ε }            {  h, ε, ;  }      { f }   { g }


INPUT:  $(  $d:ident   $e:expr   );*    $( $( h )* );*    $( f ; )+   g
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                                        |
FIRST:                       { $d:ident, h, ;,  f }

因此:

• FIRST($($d:ident $e:expr );* $( $(h)* );* $( f ;)+ g) = { $d:ident, h, ;, f }

值得注意:

• FIRST($($d:ident $e:expr );* $( $(h)* );* $($( f ;)+ g)*) = { $d:ident, h, ;, f, ε }

以下是类似的例子，但现在是关于 LAST 的。

• LAST($d:ident $e:expr) = { $e:expr }
• LAST($( $d:ident $e:expr );*) = { $e:expr, ε }
• LAST($( $d:ident $e:expr );* $(h)*) = { $e:expr, ε, h }
• LAST($( $d:ident $e:expr );* $(h)* $( f ;)+) = { ; }
• LAST($( $d:ident $e:expr );* $(h)* $( f ;)+ g) = { g }

FOLLOW(M)

最后， FOLLOW(M) 的定义如下构建。 pat ， expr 等表示具有给定片段说明符的简单非终端符。

• FOLLOW(pat) = {=>, ,, =, |, if, in}`.

• FOLLOW(expr) = FOLLOW(stmt) = {=>, ,, ;}`.

• FOLLOW(ty) = FOLLOW(path) = {{, [, ,, =>, :, =, >, >>, ;,|, as, where, 块非终端符}。

• FOLLOW(vis) = { , l 除非是非原始的 priv ，任何关键字或标识符; 可以开始类型的任何令牌; ident ， ty 和 path 非终端符}。

• 对于任何其他简单的 token ，包括 block 、 ident 、 tt 、 item 、 lifetime 、 literal 和 meta 的简单非终端符以及所有终端符， FOLLOW(t) = ANYTOKEN 。

• 对于任何其他 M ， FOLLOW(M) 的定义是对 (LAST(M){ε}) 的所有 t 的 FOLLOW(t) 的交集，其中 t 在终端符中范围。

可以开始类型的令牌是，截至本写作时，为 {(、[、!、*、&、&&、?、lifetime、>、>>、::、任何非关键字标识符、super、self、Self、extern、crate、$crate、_、for、impl、fn、unsafe、typeof、dyn}，尽管此列表可能不完整，因为人们不会总是记得在添加新令牌时更新附录。

复杂 M 的 FOLLOW 的例子:

• FOLLOW($( $d:ident $e:expr )*) = FOLLOW($e:expr)
• FOLLOW($( $d:ident $e:expr )* $(;)*) = FOLLOW($e:expr) ∩ ANYTOKEN = FOLLOW($e:expr)
• FOLLOW($( $d:ident $e:expr )* $(;)* $( f |)+) = ANYTOKEN

有效和无效匹配器的示例

有了上述规范，我们可以提出为什么特定匹配器合法而其他匹配器不合法的论据。

• ($ty:ty < foo ,) : 不合法, 因为 FIRST(< foo ,) = { < } ⊈ FOLLOW(ty)

• ($ty:ty , foo <) : 合法, 因为 FIRST(, foo <) = { , } is ⊆ FOLLOW(ty).

• ($pa:pat $pb:pat $ty:ty ,) : 不合法, 因为 FIRST($pb:pat $ty:ty ,) = { $pb:pat } ⊈ FOLLOW(pat), 而且 FIRST($ty:ty ,) = { $ty:ty } ⊈ FOLLOW(pat).

• ( $($a:tt $b:tt)* ; ) : 合法, 因为 FIRST($b:tt) = { $b:tt } is ⊆ FOLLOW(tt) = ANYTOKEN, as is FIRST(;) = { ; }.

• ( $($t:tt),* , $(t:tt),* ) : 合法, (尽管任何尝试实际使用此宏都将在扩展期间发出局部歧义错误的信号。).

• ($ty:ty $(; not sep)* -) : 不合法，因为 FIRST($(; not sep)* -) = { ;, - } 不在 FOLLOW(ty) 中。

• ($($ty:ty)-+)：不合法，因为分隔符 - 不在 FOLLOW(ty) 中。

• ($($e:expr)*)：不合法，因为表达式 NT 不在 FOLLOW(expr NT) 中。