ソースコード解析

トークン化

Rustプログラムのコンパイルの最初のステップはトークン化です。 これはソースコードをトークン(これ以上分割できない字句単位。プログラミング言語の「単語」)の列に変換するステップです。 Rustにはさまざまな種類のトークンがあります。例えば:

  • 識別子: foo, Bambous, self, we_can_dance, LaCaravane, …
  • リテラル: 42, 72u32, 0_______0, 1.0e-40, "ferris was here", …
  • 予約語: _, fn, self, match, yield, macro, …
  • 記号: [, :, ::, ?, ~, @1, …

…など。上記において注意すべき点がいくつかあります。まず、selfは識別子であり、かつ予約語でもあるということです。 ほとんどすべての状況でselfは予約語ですが、識別子として扱われることも確かにあるのです。これについては後述します(たくさんの呪詛とともに)。 次に、予約語のリストはyieldやmacroといった怪しげな要素を含んでいます。これらは実際言語の一部ではないのですが、コンパイラは予約語として認識します—将来の利用のために予約されているのです。 <-は「名残」です。文法からは削除されたものの、字句解析器には残っているのです。 最後に、::が区別されたトークンであることに注意してください。:というトークンが2つ連続したものとは異なります。複数文字からなるすべての記号トークンについて同じことがいえます(Rust 1.2以降)。2

1

@には用途があるのですが、ほとんどの人は完全に忘れてしまっているようです: @はパターンの中で使い、パターンの非終端部分を名前に束縛します (訳注: 「パターンの非終端部分(non-terminal part of the pattern)」は、@束縛においてマッチ条件を表すパターンの部分を指すものと思われる)。

2

技術的には、Rustは現時点(1.46)で2つの字句解析器を持ちます。単一文字の記号のみをトークンとして出力するrustc_lexerと、複数文字の記号を個別のトークンとみなすrustc_parse内のlexerの2つです(訳注: 翻訳時点の最新版(1.67)においても同様)。

比較点として、まさにこの段階でマクロの展開を行う言語が存在する一方で、Rustはそうではありません。 例えば、C/C++のマクロは事実上この時点で処理されます。3

次のコードが動作するのはこのためです。4

#define SUB void
#define BEGIN {
#define END }

SUB main() BEGIN
    printf("Oh, the horror!\n");
END
3

実際のところ、CのプリプロセッサはC言語自体とは異なる字句構造を用いていますが、その違いはほとんど重要ではありません。

4

これが動作すべきか否かというのは全く別の問題です。

構文解析

次の段階は構文解析で、これはトークンの列を抽象構文木(Abstract Syntax Tree, AST)に変換します。 これはプログラムの構文構造をメモリ上に構築する処理を伴います。例えば、トークン列1 + 2は次のようなものに変換されます:

┌─────────┐   ┌─────────┐
│ BinOp   │ ┌╴│ LitInt  │
│ op: Add │ │ │ val: 1  │
│ lhs: ◌  │╶┘ └─────────┘
│ rhs: ◌  │╶┐ ┌─────────┐
└─────────┘ └╴│ LitInt  │
              │ val: 2  │
              └─────────┘

抽象構文木はプログラム全体の構造を含みますが、それは字句上の情報のみに基づくものです。 例えば、特定の式がaと呼ばれる変数を参照しているのをコンパイラが知っているとしても、aが何なのか、ひいてはそれがどこからやってきたのかを知る術はありません。

抽象構文木が構築された後、ついにマクロが処理されます。ですが、マクロの処理の考察に入る前に、トークン木について考えておかねばなりません。

トークン木 (Token trees)

トークン木は、トークンと抽象構文木の中間に位置するものです。 第一に、ほとんどすべてのトークンはトークン木でもあります。より正確にいえば、トークンは葉にあたります。 もう一種類トークン木の葉になりうるものが存在しますが、それについては後述します。

基本的なトークンのうち唯一葉ではないのが、(...), [...], {...}といった「グループ化」トークンです。 これらはトークン木の内部ノードにあたり、トークン木に構造をもたらすものです。具体的な例を挙げると、次のトークン列は…

a + b + (c + d[0]) + e

次のようなトークン木にパースされます:

«a» «+» «b» «+» «(   )» «+» «e»
          ╭────────┴──────────╮
           «c» «+» «d» «[   ]»
                        ╭─┴─╮
                         «0»

これは、この式が生成する抽象構文木とは何の関連もないということに注意してください。 1つの根ノードがあるのではなく、根のレベルに7つのトークン木があるのです。 参考までに、この式の抽象構文木を載せておきます:

              ┌─────────┐
              │ BinOp   │
              │ op: Add │
            ┌╴│ lhs: ◌  │
┌─────────┐ │ │ rhs: ◌  │╶┐ ┌─────────┐
│ Var     │╶┘ └─────────┘ └╴│ BinOp   │
│ name: a │                 │ op: Add │
└─────────┘               ┌╴│ lhs: ◌  │
              ┌─────────┐ │ │ rhs: ◌  │╶┐ ┌─────────┐
              │ Var     │╶┘ └─────────┘ └╴│ BinOp   │
              │ name: b │                 │ op: Add │
              └─────────┘               ┌╴│ lhs: ◌  │
                            ┌─────────┐ │ │ rhs: ◌  │╶┐ ┌─────────┐
                            │ BinOp   │╶┘ └─────────┘ └╴│ Var     │
                            │ op: Add │                 │ name: e │
                          ┌╴│ lhs: ◌  │                 └─────────┘
              ┌─────────┐ │ │ rhs: ◌  │╶┐ ┌─────────┐
              │ Var     │╶┘ └─────────┘ └╴│ Index   │
              │ name: c │               ┌╴│ arr: ◌  │
              └─────────┘   ┌─────────┐ │ │ ind: ◌  │╶┐ ┌─────────┐
                            │ Var     │╶┘ └─────────┘ └╴│ LitInt  │
                            │ name: d │                 │ val: 0  │
                            └─────────┘                 └─────────┘

抽象構文木とトークン木の違いはよく理解しておいてください。マクロを書く際は、これらを別々のものとして、両方とも扱う必要があるのです。

もう一つ注意すべき点は、トークン木が組になっていない括弧、あるいはネスト構造がおかしいグループを含むことはないということです。