附录：宏跟随集歧义形式规范

本页记录了示例宏的跟随规则的形式规范。它们最初是在RFC 550中指定的，本文的大部分内容都是从该规范中复制而来，并在后续的 RFC 中进行了扩展。

定义和约定

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

示例

#![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 作为其片段说明符。

$(i:ident),* 也是一个非终结符；它是一个复杂非终结符，匹配以逗号分隔的标识符重复。, 是复杂非终结符的分隔符词法单元；它出现在匹配片段的每对元素（如果有）之间。

复杂非终结符的另一个例子是 $(hi $e:expr ;)+，它匹配形式为 hi <expr>; hi <expr>; ... 的任何片段，其中 hi <expr>; 至少出现一次。请注意，此复杂非终结符没有专用的分隔符词法单元。

（请注意，Rust 的解析器确保带分隔符的序列始终以正确的词法单元树结构嵌套和正确的打开和关闭分隔符匹配出现。）

我们倾向于使用变量“M”来表示匹配器，使用变量“t”和“u”来表示任意单个词法单元，使用变量“tt”和“uu”来表示任意词法单元树。（使用“tt”确实会与其作为片段说明符的附加角色产生潜在的歧义；但从上下文中可以清楚地看出是哪种解释。）

“SEP”将遍历分隔符标记，“OP”将遍历重复运算符 *、+ 和 ?，“OPEN”/“CLOSE”将遍历分隔序列周围的匹配标记对（例如 [ 和 ]）。

希腊字母“α”“β”“γ”“δ”代表可能为空的标记树序列。（但是，希腊字母“ε”（epsilon）在演示文稿中具有特殊作用，并不代表标记树序列。）

• 这种希腊字母约定通常仅在序列的存在是一个技术细节时使用；特别是，当我们希望*强调*我们正在对标记树序列进行操作时，我们将对序列使用符号“tt ...”，而不是希腊字母。

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

另请注意，在此形式主义的上下文中，术语“标记”通常*包括*简单 NT。

最后，读者需要记住，根据此形式主义的定义，没有简单的 NT 与空片段匹配，同样也没有标记与 Rust 语法的空片段匹配。（因此，*唯一*可以匹配空片段的 NT 是复杂 NT。）这实际上是不正确的，因为 vis 匹配器可以匹配空片段。因此，出于形式主义的目的，我们将 $v:vis 视为实际上是 $($v:vis)?，并要求匹配器匹配空片段。

匹配器不变量

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

1. 对于匹配器 M 中的任何两个连续标记树序列（即 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 ...)。

第一个不变量表示，匹配器之后的任何实际标记（如果有）都必须位于预定的跟随集中。这确保了即使将新的语法形式添加到语言中，合法的宏定义也将继续分配相同的确定，以确定 ... tt 在哪里结束以及 uu ... 在哪里开始。

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

第三个不变量表示，当我们有一个复杂的 NT 可以匹配同一个事物的两个或多个副本而中间没有分隔时，必须允许它们根据第一个不变量彼此相邻放置。此不变量还要求它们不能为空，这消除了可能的歧义。

注意：由于历史疏忽和对行为的严重依赖，目前未强制执行第三个不变量。目前尚未决定如何处理这个问题。不遵守该行为的宏在未来版本的 Rust 中可能会变得无效。请参阅跟踪问题。

FIRST 和 FOLLOW，非正式地

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

这三个集合中的每一个都由标记组成。FIRST(M) 和 LAST(M) 还可能包含一个区分的非标记元素 ε（“epsilon”），它表示 M 可以匹配空片段。（但 FOLLOW(M) 始终只是一组标记。）

非正式地

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

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

• FOLLOW(M)：允许在与 M 匹配的某个片段之后立即跟随的标记集。

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

  • M 匹配 β，

  • t 匹配 γ，并且

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

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

（为了回顾对上述非正式描述的理解，读者此时可能希望在阅读其正式定义之前跳到FIRST/LAST 的示例。）

FIRST、LAST

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

“A ∪ B”表示集合并集，“A ∩ B”表示集合交集，“A \ B”表示集合差集（即 A 中所有不存在于 B 中的元素）。

FIRST

FIRST(M) 由序列 M 及其第一个标记树（如果有）的结构的案例分析定义

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

• 如果 M 以标记 t 开头，则 FIRST(M) = { t }，

  （注意：这涵盖了 M 以分隔标记树序列开头的案例，M = OPEN tt ... CLOSE ...，在这种情况下 t = OPEN，因此 FIRST(M) = { OPEN }。）

  （注意：这关键取决于没有简单 NT 与空片段匹配的属性。）

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

  • 如果 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)。

复杂 NT 的定义值得商榷。SEP_SET(M) 定义了分隔符可能是 M 的有效第一个标记的可能性，这种情况发生在定义了分隔符并且重复片段可能为空时。ALPHA_SET(M) 定义了复杂 NT 可能为空的可能性，这意味着 M 的有效第一个标记是以下标记树序列 α 的第一个标记。当使用 * 或 ? 时会发生这种情况，在这种情况下可能存在零次重复。从理论上讲，如果 + 与可能为空的重复片段一起使用，也会发生这种情况，但这被第三个不变量禁止。

从那里，很明显 FIRST(M) 可以包含来自 SEP_SET(M) 或 ALPHA_SET(M) 的任何标记，如果复杂 NT 匹配不为空，那么从 FIRST(tt ...) 开始的任何标记也可以。最后要考虑的是 ε。SEP_SET(M) 和 FIRST(tt ...) \ {ε} 不能包含 ε，但 ALPHA_SET(M) 可以。因此，当且仅当 ε ∈ ALPHA_SET(M) 时，此定义才允许 M 接受 ε。这是正确的，因为要使 M 在复杂 NT 案例中接受 ε，复杂 NT 和 α 都必须接受它。如果 OP = +，这意味着复杂 NT 不能为空，则根据定义 ε ∉ ALPHA_SET(M)。否则，复杂 NT 可以接受零次重复，然后 ALPHA_SET(M) = FOLLOW(α)。所以这个定义对于 \varepsilon 也是正确的。

LAST

LAST(M)，由 M 本身（标记树序列）的案例分析定义

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

• 如果 M 是单个标记 t，则 LAST(M) = { t }

• 如果 M 是重复零次或多次的单个复杂 NT，M = $( tt ... ) * 或 M = $( tt ... ) SEP *

  • 如果 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 }；否则 sep_set = {}。

  • 如果 ε ∈ LAST(tt ...)，则 LAST(M) = LAST(tt ...) ∪ sep_set

  • 否则，序列 tt ... 必须为非空；LAST(M) = LAST(tt ...)

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

• 如果 M 是分隔标记树序列 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 非终结符}.

• 对于任何其他简单标记（包括块、ident、tt、item、lifetime、literal 和 meta 简单非终结符）以及所有终结符，FOLLOW(t) = ANYTOKEN。

• 对于任何其他 M，FOLLOW(M) 定义为当 t 在 (LAST(M) \ {ε}) 中取值时，FOLLOW(t) 的交集。

可以开始类型的标记，在撰写本文时，为 {(, [, !, *, &, &&, ?, 生命周期, >, >>, ::, 任何非关键字标识符, 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 <) = { , } 是 ⊆ 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 } 是 ⊆ FOLLOW(tt) = ANYTOKEN，FIRST(;) = { ; } 也是如此。

• ( $($t:tt),* , $(t:tt),* ) : 合法，（尽管任何实际使用此宏的尝试都会在扩展期间发出本地歧义错误信号）。

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

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

• ($($e:expr)*) : 非法，因为 expr NT 不在 FOLLOW(expr NT) 中。