Приложение: Формальная спецификация неоднозначности множества следования макросов

Эта страница документирует формальную спецификацию правил следования для Макросов по примеру. Они были первоначально определены в RFC 550, из которого скопирована основная часть этого текста, и расширены в последующих RFC.

rmacro.ambiguity.convention: https://github.com/rust-lang/rust/issues/56575

Определения и соглашения

• macro: всё, что может быть вызвано как foo!(...) в исходном коде.
• MBE: макрос по примеру (macro-by-example), макрос, определенный с помощью 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 являются простыми NT с expr и ident в качестве соответствующих спецификаторов фрагментов.

$(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” - соответствующие пары токенов, окружающие разделенную последовательность (например, [ и ]).

Греческие буквы “α” “β” “γ” “δ” обозначают потенциально пустые последовательности деревьев токенов. (Однако греческая буква “ε” (эпсилон) играет особую роль в изложении и не обозначает последовательность деревьев токенов.)

• Это соглашение с греческими буквами обычно используется, когда наличие последовательности является технической деталью; в частности, когда мы хотим подчеркнуть, что мы работаем с последовательностью деревьев токенов, мы будем использовать обозначение “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 ...).

Первый инвариант говорит, что любой фактический токен, который идет после сопоставителя, если таковой имеется, должен быть somewhere в predetermined множестве следования. Это гарантирует, что legal определение макроса будет продолжать присваивать то же определение тому, где заканчивается ... tt и начинается uu ..., даже при добавлении новых синтаксических форм в язык.

Второй инвариант говорит, что разделяемый сложный NT должен использовать токен-сепаратор, который является частью predetermined множества следования для внутреннего содержимого NT. Это гарантирует, что legal определение макроса будет продолжать разбирать входной фрагмент в ту же разделенную последовательность tt ..., даже при добавлении новых синтаксических форм в язык.

Третий инвариант говорит, что когда у нас есть сложный NT, который может сопоставлять две или более копии одной и той же вещи без разделения между ними, должно быть допустимо размещать их рядом друг с другом в соответствии с первым инвариантом. Этот инвариант также требует, чтобы они были непустыми, что устраняет возможную неоднозначность.

ПРИМЕЧАНИЕ: Третий инвариант в настоящее время не применяется из-за исторического упущения и значительной зависимости от поведения. В настоящее время не решено, что делать с этим в будущем. Макросы, которые не соблюдают поведение, могут стать недействительными в будущей редакции Rust. См. отслеживаемую проблему.

FIRST и FOLLOW, неформально

Данный сопоставитель M отображается в три множества: FIRST(M), LAST(M) и FOLLOW(M).

Каждое из трех множеств состоит из токенов. FIRST(M) и LAST(M) также могут содержать выделенный нетокенный элемент ε (“эпсилон”), который указывает, что M может сопоставляться с пустым фрагментом. (Но FOLLOW(M) всегда просто множество токенов.)

Неформально:

• FIRST(M): собирает токены, потенциально используемые первыми при сопоставлении фрагмента с M.

• LAST(M): собирает токены, потенциально используемые последними при сопоставлении фрагмента с M.

• FOLLOW(M): множество токенов, разрешенных следовать immediately после некоторого фрагмента, сопоставленного 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 и thus FIRST(M) = { OPEN }.)

  (Примечание: это критически зависит от свойства, что никакой простой NT не сопоставляется с пустым фрагментом.)

• В противном случае, M - это последовательность деревьев токенов, начинающаяся со сложного NT: M = $( tt ... ) OP α, или M = $( tt ... ) SEP OP α, (где α - (потенциально пустая) последовательность деревьев токенов для остальной части сопоставителя).

  • Пусть SEP_SET(M) = { SEP }, если SEP присутствует и ε ∈ FIRST(tt ...); иначе SEP_SET(M) = {}.

• Пусть ALPHA_SET(M) = FIRST(α), если OP = * или ?, и ALPHA_SET(M) = {}, если OP = +.

• 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(α). Так что это определение также корректно относительно ε.

LAST

LAST(M), определяется анализом случаев самой M (последовательности деревьев токенов):

• если M - пустая последовательность, то LAST(M) = { ε }

• если M - одиночный токен t, то LAST(M) = { t }

• если M - одиночный сложный NT, повторяющийся ноль или более раз, M = $( tt ... ) *, или M = $( tt ... ) SEP *

  • Пусть sep_set = { SEP }, если SEP присутствует; иначе sep_set = {}.

  • если ε ∈ LAST(tt ...) тогда LAST(M) = LAST(tt ...) ∪ sep_set

  • иначе последовательность tt ... должна быть непустой; LAST(M) = LAST(tt ...) ∪ {ε}.

• если M - одиночный сложный NT, повторяющийся один или более раз, M = $( tt ... ) +, или M = $( tt ... ) SEP +

  • Пусть sep_set = { SEP }, если 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. (Обратите внимание, в частности, как вводится и устраняется специальный элемент ε на основе взаимодействия между частями ввода.)

Наш первый пример представлен в древовидной структуре, чтобы подробно описать, как компилируется анализ сопоставителя. (Некоторые из более простых поддеревьев были опущены.)

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


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

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


ВВОД:  $(  $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, >, >>, ::, любой неключевой идентификатор, super, self, Self, extern, crate, $crate, _, for, impl, fn, unsafe, typeof, dyn}, хотя этот список может быть неполным, потому что люди не всегда помнят обновлять приложение, когда добавляются новые.

Примеры FOLLOW для сложных M:

• 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, как и 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).