附录：宏 Follow 集歧义形式化规范

此页面记录了示例宏的 follow 规则的形式化规范。它们最初在RFC 550中指定，本文的大部分内容均复制自该 RFC，并在后续 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 tree 的有限序列形成的树结构。
• delimiter token：旨在分隔一个片段的结尾和下一个片段的开始的 token。
• separator token：复杂 NT 中的可选分隔符 token，用于分隔匹配重复项中每对元素。
• separated complex NT：具有自己的分隔符 token 的复杂 NT。
• delimited sequence：token tree 序列，在序列的开始和结尾处具有适当的开和闭分隔符。
• empty fragment：分隔 token 的不可见 Rust 语法类别，即空格，或（在某些词法上下文中）空 token 序列。
• 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 是简单 NT，其片段说明符分别为 expr 和 ident。

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

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

（请注意，Rust 的解析器确保带分隔符的序列始终以 token tree 结构的正确嵌套和开和闭分隔符的正确匹配出现。）

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

“SEP”将涵盖分隔符 token，“OP”将涵盖重复运算符 *、+ 和 ?，“OPEN”/“CLOSE”将涵盖包围带分隔符序列的匹配 token 对（例如 [ 和 ]）。

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

• 仅当序列的存在是技术细节时，才通常使用此希腊字母约定；特别是，当我们希望强调我们正在对 token tree 序列进行操作时，我们将使用符号“tt ...”表示序列，而不是希腊字母。

请注意，匹配器仅仅是一个 token tree。“简单 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 tree 序列（即 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 必须使用分隔符 token，该 token 是 NT 内部内容的预定 follow 集的一部分。这确保了即使向语言中添加了新的语法形式，合法的宏定义也将继续将输入片段解析为相同的 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 集合。

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

  • M 匹配 β，

  • t 匹配 γ，并且

  • 串联 α β γ δ 是可解析的 Rust 程序。

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

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

FIRST、LAST

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

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

FIRST

FIRST(M) 通过对序列 M 及其第一个 token tree（如果有）的结构进行案例分析来定义

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

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

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

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

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

  • 如果 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 的有效第一个 token 的可能性，当存在已定义的分隔符并且重复片段可能为空时，就会发生这种情况。ALPHA_SET(M) 定义了复杂 NT 可能为空的可能性，这意味着 M 的有效第一个 token 是以下 token tree 序列 α 的 token。当使用 * 或 ? 时，就会发生这种情况，在这种情况下，可能存在零次重复。理论上，如果 + 与可能为空的重复片段一起使用，也可能发生这种情况，但这被第三个不变式禁止。

从那里，显然 FIRST(M) 可以包含 SEP_SET(M) 或 ALPHA_SET(M) 中的任何 token，并且如果复杂 NT 匹配为非空，则任何以 FIRST(tt ...) 开头的 token 也可以工作。要考虑的最后一部分是 ε。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 本身（token tree 序列）进行案例分析来定义

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

• 如果 M 是单个 token 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 是带分隔符的 token tree 序列 OPEN tt ... CLOSE，则 LAST(M) = { CLOSE }。

• 如果 M 是非空的 token tree 序列 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) = {,l 任何关键字或标识符，但非原始 priv 除外；任何可以开始类型的 token；ident、ty 和 path 非终结符}。

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

• 对于任何其他 M，FOLLOW(M) 定义为 FOLLOW(t) 的交集，其中 t 的范围为 (LAST(M) \ {ε})。

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

复杂 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) 中。