부록: 매크로 follow-set 모호성 공식 명세

부록: 매크로 follow-set 모호성 공식 명세

macro_rules!로 정의하는 매크로, 즉 매크로-바이-예제(MBE) 의 follow 규칙에 대한 공식 명세를 다루는 부록이에요. 이 규칙들은 원래 RFC 550에서 정해졌고, 이후 여러 RFC에서 확장됐어요. 이 페이지의 대부분 텍스트는 그 RFC에서 가져온 거예요.

출처: Rust Reference - Appendix: Macro follow-set ambiguity formal specification

본문

정의와 관례

자주 쓰일 용어들을 먼저 정리할게요.

  • macro: 소스 코드에서 foo!(...)처럼 호출할 수 있는 모든 것.
  • MBE: 매크로-바이-예제. macro_rules로 정의된 매크로.
  • matcher: macro_rules 호출에서 규칙의 왼쪽, 혹은 그 일부분.
  • macro parser: Rust 파서 안에서 모든 matcher에서 파생된 문법으로 입력을 파싱하는 코드 조각.
  • fragment: 주어진 matcher가 받아들이는(매치하는) Rust 구문의 종류(class).
  • repetition: 규칙적인 반복 패턴을 따르는 fragment.
  • NT: 비터미널(non-terminal). matcher에 나타날 수 있는 다양한 "메타 변수"나 반복 matcher. MBE 문법에서 앞에 $ 문자가 붙어요.
  • simple NT: "메타 변수" 형태의 비터미널(아래에서 더 설명).
  • complex NT: 반복 연산자(*, +, ?)로 지정되는, 반복 매칭을 하는 비터미널.
  • token: matcher의 원자적 요소. 식별자, 연산자, 열림/닫힘 구분자, simple NT를 포함해요.
  • token tree: token(잎), complex NT, 그리고 token tree의 유한한 수열로 이루어진 트리 구조.
  • delimiter token: 한 fragment의 끝과 다음 fragment의 시작을 나누는 역할을 하는 token.
  • separator token: complex NT 안에서 매치된 반복의 각 요소 쌍을 구분하는 선택적인 delimiter token.
  • separated complex NT: 자신의 separator token을 가진 complex NT.
  • delimited sequence: 시작과 끝에 적절한 열림/닫힘 구분자가 있는 token tree의 수열.
  • empty fragment: token을 구분하는 보이지 않는 Rust 구문의 종류. 즉 공백, 또는 (어떤 어휘 맥락에서) 빈 token 수열.
  • fragment specifier: simple NT에서 그 NT가 받아들일 fragment를 지정하는 식별자.
  • language: 문맥 자유 언어(context-free language).

예를 들어 볼게요.

#![allow(unused)]
fn main() {
macro_rules! i_am_an_mbe {
    (start $foo:expr $($i:ident),* end) => ($foo)
}
}
  • (start $foo:expr $($i:ident),* end)는 matcher예요. 전체 matcher는 delimited sequence(열림/닫힘 구분자가 (과 ))이고, $foo와 $i는 fragment specifier가 각각 expr과 ident인 simple NT예요.
  • $(i:ident),*도 NT인데, 쉼표로 구분된 식별자 반복을 매치하는 complex NT예요. 여기서 ,는 이 complex NT의 separator token으로, 매치된 fragment의 각 요소 쌍 사이(있다면)에 위치해요.

complex NT의 또 다른 예시로 $(hi $e:expr ;)+가 있어요. 이건 hi <expr>; hi <expr>; ... 형태의 fragment를 매치하는데, hi <expr>;가 최소 한 번 이상 나타나야 해요. 이 complex NT는 전용 separator token이 없다는 점에 주목하세요.

(Rust의 파서는 delimited sequence가 항상 token tree 구조의 올바른 중첩과 열림/닫힘 구분자의 올바른 매칭으로 발생하도록 보장해요.)

  • "M"은 matcher를, "t"와 "u"는 임의의 개별 token을, "tt"와 "uu"는 임의의 token tree를 나타내는 변수로 자주 쓸게요. ("tt"는 fragment specifier로서의 추가 역할 때문에 잠재적 모호성이 있지만, 문맥에서 어느 뜻인지 분명해요.)
  • "SEP"는 separator token, "OP"는 반복 연산자 *, +, ?, "OPEN"/"CLOSE"는 delimited sequence를 둘러싸는 매칭 token 쌍(예: [와 ])을 나타내요.
  • 그리스 문자 "α" "β" "γ" "δ"는 잠재적으로 빈 token-tree 수열을 나타내요. (다만 "ε"(엡실론)은 발표에서 특별한 역할을 하며 token-tree 수열을 나타내지 않아요.) 이 관례는 수열의 존재가 기술적 세부 사항일 때 주로 쓰여요. 특히 token-tree 수열을 강조하고 싶을 때는 그리스 문자 대신 "tt …" 표기법을 써요.

matcher는 단지 token tree 하나일 뿐이에요. "simple NT"는 메타 변수 형태의 NT라서 비-반복이에요. 예를 들어 $foo:ty는 simple NT지만 $($foo:ty)+는 complex NT예요. 이 형식주의의 맥락에서 "token"이라는 용어는 일반적으로 simple NT를 포함해요.

마지막으로, 이 형식주의의 정의에 따르면 어떤 simple NT도 empty fragment를 매치하지 않고, 어떤 token도 Rust 구문의 empty fragment를 매치하지 않아요. (따라서 empty fragment를 매치할 수 있는 유일한 NT는 complex NT예요.) 실제로는 정확히 그렇지 않아요. vis matcher가 empty fragment를 매치할 수 있기 때문이에요. 그래서 이 형식주의의 목적을 위해 $v:vis를 실제로는 $($v:vis)?로 취급하고, matcher가 empty fragment를 매치해야 한다는 요구 사항을 붙여요.

matcher 불변식(invariant)

유효하려면 matcher는 다음 세 가지 불변식을 만족해야 해요. FIRST와 FOLLOW의 정의는 뒤에서 설명할게요.

  1. matcher M의 어떤 두 연속 token-tree 수열에 대해서도(즉 M = ... tt uu ...이고 uu ...가 비어 있지 않으면), FOLLOW(... tt) ∪ {ε} ⊇ FIRST(uu ...)를 만족해야 해요.
  2. matcher의 어떤 separated complex NT, M = ... $(tt ...) SEP OP ...에 대해서도 SEP ∈ FOLLOW(tt ...)를 만족해야 해요.
  3. matcher의 어떤 unseparated complex NT, M = ... $(tt ...) OP ...에 대해서도, 만약 OP = * 또는 +라면 FOLLOW(tt ...) ⊇ FIRST(tt ...)를 만족해야 해요.

각 불변식이 뜻하는 바를 풀어볼게요.

  • 첫 번째 불변식: matcher 뒤에 실제로 오는 token이 있다면, 그것은 미리 정해진 follow 집합 안 어딘가에 있어야 해요. 이렇게 하면 언어에 새 구문 형태가 추가되어도, 합법적인 매크로 정의가 ... tt가 끝나고 uu ...가 시작되는 지점을 같은 방식으로 결정하게 보장돼요.
  • 두 번째 불변식: separated complex NT는 그 NT 내부 내용에 대해 미리 정해진 follow 집합의 일부인 separator token을 써야 해요. 이렇게 하면 새 구문 형태가 추가되어도 합법적인 매크로 정의가 입력 fragment를 같은 delimited sequence(tt ...의 수열)로 계속 파싱하게 보장돼요.
  • 세 번째 불변식: 사이에 구분 없이 같은 것의 두 개 이상 복사본을 매치할 수 있는 complex NT가 있을 때, 첫 번째 불변식에 따라 그것들이 나란히 놓이는 것이 허용 가능해야 해요. 이 불변식은 또한 그것들이 비어 있지 않아야 한다고 요구해서, 가능한 모호성을 제거해요.

참고: 세 번째 불변식은 현재 시행되지 않아요. 역사적 누락과 이 동작에 대한 상당한 의존 때문이에요. 앞으로 이걸 어떻게 할지는 아직 결정되지 않았어요. 이 동작을 지키지 않는 매크로는 미래 Rust 에디션에서 유효하지 않게 될 수도 있어요. (추적 이슈 참조.)

FIRST와 FOLLOW, 비공식적으로

주어진 matcher M은 세 집합 FIRST(M), LAST(M), FOLLOW(M)에 대응돼요. 세 집합 모두 token으로 이루어져 있어요. FIRST(M)와 LAST(M)는 M이 empty fragment를 매치할 수 있음을 나타내는 구별되는 비-token 요소 ε("엡실론")도 포함할 수 있어요. (FOLLOW(M)은 항상 token 집합일 뿐이에요.)

비공식적으로는:

  • FIRST(M): fragment를 M에 매치할 때 잠재적으로 처음에 쓰이는 token들을 모은 것.
  • LAST(M): fragment를 M에 매치할 때 잠재적으로 마지막에 쓰이는 token들을 모은 것.
  • FOLLOW(M): M이 매치한 어떤 fragment 바로 뒤에 허용되는 token들의 집합.

다시 말해 t ∈ FOLLOW(M)인 것은 (잠재적으로 빈) token 수열 α, β, γ, δ가 존재해서 다음을 만족할 때와 필요충분이에요: M이 β를 매치하고, t가 γ를 매치하며, 연결 α β γ δ가 파싱 가능한 Rust 프로그램이에요.

ANYTOKEN을 모든 token(단순 NT 포함)의 집합을 나타내는 약칭으로 쓸게요. 예를 들어 어떤 token이 matcher M 뒤에 합법적이면 FOLLOW(M) = ANYTOKEN이에요.

(위 비공식 설명에 대한 이해를 점검하고 싶다면, 지금 FIRST/LAST의 공식 정의를 읽기 전에 아래 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이 delimited token-tree 수열 M = OPEN tt ... CLOSE ...로 시작하는 경우도 포함하는데, 그 경우 t = OPEN이라 FIRST(M) = { OPEN }이 돼요.) (이건 어떤 simple NT도 empty fragment를 매치하지 않는다는 성질에 결정적으로 의존해요.)
  • 그 외의 경우, M은 complex NT로 시작하는 token-tree 수열이에요: M = $( tt ... ) OP α 또는 M = $( tt ... ) SEP OP α (α는 matcher의 나머지 부분에 대한, 잠재적으로 빈 token tree 수열).

이때:

  • 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).

complex NT에 대한 정의는 조금 설명이 필요해요. SEP_SET(M)은 separator가 M의 유효한 첫 token이 될 가능성을 정의해요. 이는 separator가 정의되어 있고 반복되는 fragment가 비어 있을 수 있을 때 발생해요. ALPHA_SET(M)은 complex NT가 비어 있을 가능성을 정의해요. 즉 M의 유효한 첫 token이 다음 token-tree 수열 α의 token들이라는 뜻이에요. 이건 *나 ?가 쓰여서 0회 반복이 가능할 때 발생해요. 이론상 +와 잠재적으로 빈 반복 fragment와 함께 쓰여도 발생할 수 있지만, 세 번째 불변식에 의해 금지돼요.

따라서 FIRST(M)은 SEP_SET(M)이나 ALPHA_SET(M)의 token을 포함할 수 있고, complex NT 매치가 비어 있지 않으면 FIRST(tt ...)를 시작하는 어떤 token도 될 수 있어요. 마지막으로 고려할 조각은 ε이에요. SEP_SET(M)과 FIRST(tt ...) \ {ε}은 ε을 포함할 수 없지만 ALPHA_SET(M)은 포함할 수 있어요. 그래서 ε ∈ ALPHA_SET(M)일 때만 M이 ε을 받아들일 수 있게 정의돼요. 이는 정확해요. complex NT 경우에서 M이 ε을 받아들이려면 complex NT와 α가 모두 ε을 받아들여야 하기 때문이에요. OP = +이면 complex NT가 비어 있을 수 없으므로 정의에 따라 ε ∉ ALPHA_SET(M)이에요. 그 외에는 complex NT가 0회 반복을 받아들일 수 있고, 그러면 ALPHA_SET(M) = FOLLOW(α)예요. 그래서 이 정의는 ε에 대해서도 정확해요.

LAST

LAST(M)은 M 자체(token-tree의 수열)에 대한 경우 분석으로 정의돼요.

  • M이 빈 수열이면 LAST(M) = { ε }.
  • M이 단일 token t이면 LAST(M) = { t }.
  • M이 0회 이상 반복하는 단일 complex 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이 1회 이상 반복하는 단일 complex 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이 0회 또는 1회 반복하는 단일 complex NT일 때, M = $( tt ... ) ?이면 LAST(M) = LAST(tt ...) ∪ {ε}.
  • M이 delimited 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의 예시예요. (특히 특별한 ε 요소가 입력 조각들 사이의 상호작용에 따라 어떻게 도입되고 제거되는지 주목해요.)

첫 번째 예시는 matcher의 분석이 어떻게 구성되는지 설명하기 위해 트리 구조로 제시해요. (일부 더 단순한 하위 트리는 생략됐어요.)

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 등은 주어진 fragment specifier를 가진 simple 비터미널을 나타내요.

  • FOLLOW(pat) = {=>, ,, =, |, if, in}.
  • FOLLOW(expr) = FOLLOW(expr_2021) = FOLLOW(stmt) = {=>, ,, ;}.
  • FOLLOW(ty) = FOLLOW(path) = {{, [, ,, =>, :, =, >, >>, ;, |, as, where, 블록 비터미널}.
  • FOLLOW(vis) = {l이 아닌 raw가 아닌 priv를 제외한 어떤 키워드나 식별자; 타입을 시작할 수 있는 어떤 token; ident, ty, path 비터미널}.
  • FOLLOW(t) = ANYTOKEN. 여기서 t는 block, ident, tt, item, lifetime, literal, meta simple 비터미널과 모든 터미널을 포함한 다른 단순 token.
  • 그 외의 다른 M에 대한 FOLLOW(M) 은 t가 (LAST(M) \ {ε}) 범위를 지날 때 FOLLOW(t)의 교집합으로 정의돼요.

참고로, 타입을 시작할 수 있는 token은 (이 글을 쓰는 시점 기준) {(, [, !, *, &, &&, ?, 라이프타임, >, >>, ::, 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

유효/무효 matcher 예시

위 명세를 갖추면 특정 matcher가 왜 합법적이고 다른 것들은 왜 아닌지 주장할 수 있어요.

  • ($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)-+): 불법. separator -가 FOLLOW(ty)에 없기 때문이에요.
  • ($($e:expr)*): 불법. expr NT가 FOLLOW(expr NT)에 없기 때문이에요.

더 알아보기 (Learn more)