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

本页记录了通过示例定义的宏跟随规则的形式规范。它们最初在 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：由词法单元（叶子）、复杂 NT 和词法单元树的有限序列形成的树结构。
• delimiter token：用于分隔一个片段结束和下一个片段开始的词法单元。
• separator token：复杂 NT 中的可选分隔词法单元，用于分隔匹配重复中的每对元素。
• separated complex NT：具有自己分隔词法单元的复杂 NT。
• delimited sequence：在序列的开头和结尾具有适当开/闭分隔符的词法单元树序列。
• empty fragment：分隔音法单元的不可见 Rust 语法类别，即空白，或（在某些词法上下文中）空词法单元序列。
• fragment specifier：简单 NT 中指定 NT 接受哪个片段的标识符。
• 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 作为各自片段说明符的简单 NT。

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

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

（请注意，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) 可以。因此，此定义允许 M 接受 ε 当且仅当 ε ∈ ALPHA_SET(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(expr_2021) = FOLLOW(stmt) = {=>, ,, ;}`。

• FOLLOW(ty) = FOLLOW(path) = {{, [, ,, =>, :, =, >, >>, ;, |, as, where, block nonterminals}。

• FOLLOW(vis) = {, 除 priv 外的任何关键字或标识符；可以开始类型的任何词法单元；ident、ty 和 path 非终结符}。

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

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

截至撰写本文时，可以开始类型的词法单元是 {(, [, !, *, &, &&, ?, lifetimes, >, >>, ::, any non-keyword identifier, 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) 中。