Rust構文解析器のトークン分割戦略

Rust

他の多くの言語と同様、Rustの字句解析器は貪欲にトークンを分割する。しかし構文解析の途中で必要に迫られて、さらに細かくトークンを分割する場合がある。

先にまとめ

以下の場合は、構文解析のタイミングで字句がさらに細かく分割される。

  • 式の位置に、前置の || が出現した場合。
  • 型・式・パターンの位置に、前置の && が出現した場合。
  • ジェネリクス引数や、修飾パスが期待される位置に、 << が出現した場合。
  • ジェネリクス引数や修飾パスの内部の > が期待される位置に、 >>, >=, >>= が出現した場合。

本編

他の多くの言語と同様、Rustの字句解析器は貪欲にトークンを分割する。

これは例えば次のようなコードを実行するとわかる。

macro_rules! stringify_each {
    ($($x:tt)*) => {
        stringify!($($x)/ *)
    }
}
fn main() {
    println!("{}", stringify_each!(abc a b c));
    println!("{}", stringify_each!(1.1.1.1.1));
    println!("{}", stringify_each!(&&&&&));
    println!("{}", stringify_each!(|||||));
    println!("{}", stringify_each!(<<<<<));
    println!("{}", stringify_each!(>>>>>));
    println!("{}", stringify_each!(=====));
}

abc / a / b / c
1.1 / . / 1.1 / . / 1
&& / && / &
|| / || / |
<< / << / <
>> / >> / >
== / == / =

ときには、この分割戦略が直感に反した挙動をすることがある。スペースで明示すれば対処できる話だが、いくつかのパターンでは構文解析時にリカバリーする戦略が取られている。

|| の処理

| を含む字句は |, ||, |= の3つであり、以下の場面で使われている。

これらの組み合わせで問題になるのは、クロージャの引数が0個の場合 | | { .. } である。

Rustではこれを || { .. } とも書けるようになっている。この実装はシンプルで、クロージャの予期される位置に || が出現したら引数なしと判断するだけでよい。

&& の処理

& を含む字句は &, &&, &= の3つであり、以下の場面で使われている。

  • ビットごとの論理積 & とその複合代入 &=
  • 短絡回路論理積 &&
  • 参照型 &, &mut およびそのselfショートカット &self, &mut self
  • 参照をとる操作 &, &mut
  • 参照外しパターン &, &mut

これらの組み合わせではいくつかの問題が発生しうる。最も考えやすいのは、二重参照の場合 & & x である。

fn f(x: &&u32) {}

Rustでは上記のようなソースコードも正しくパースする。これはexpect_andという関数で実現されている。この関数は以下のような動作をする。

  • & が来たら、そのトークンを消費して終了する。
  • && が来たら、該当トークンを破壊的に & に置き換える。トークンポインタは進めずに終了する。
  • それ以外が来たら失敗する。

つまり、参照型・参照操作・参照外しパターンのいずれかが期待される場所に && が現れたら、そのトークンは動的に2つの & に分割される。これにより上記のようなソースコードが正しくパースされるようになっている。Rustパーサーは深いバックトラックは行わないように設計されているため、復元処理は必要ない。

なお、A && B と A & &B はどちらも構文的にありえるため、この位置に && が来ても分割は行われない。

fn main() {
    println!("{}", &1 & &2);
    // println!("{}", &1&&2); // Error
}

<< と >> の処理

<, > を含む字句は <, >, <=, >=, <<, >>, <<=, >>=, <-, ->, => である。 (<- はplacementと呼ばれるunstable機能のためのトークン)

  • 比較の二項演算 <, >、 <=、 >=
  • 左/右シフト <<, >> とそれらの複合代入
  • placement X <- Y
  • fn や Fn*系トレイト、トレイト定義における戻り値型 ->
  • match の腕 =>
  • ジェネリクス引数の開始と終了 < .. >, ::< .. >
  • 修飾パスの開始 <SomeType>::, <SomeType as SomeTrait>::

なお、ジェネリクス引数の <, > と二項演算子としての <, > は、構文レベルで注意深く区別されている。

この中でトークン分割が問題になるのは、 <<, >> がジェネリクスの文脈で出てくる場合である。例えば、

fn main() {
    let x:Vec<u32>=Vec::<<u32 as ::std::ops::Add<u32>>::Output>::new();
    let x:Vec<Vec<u32>>=vec![];
}

は >=, >>=, >>, << が分割され、正しくコンパイルされる。

二項演算子の位置では << を分割することはできないから、以下のような場合はパースできない。

fn main() {
    println!("{}", 0 < <u32 as ::std::ops::Add<u32>>::add(1, 2));
    // println!("{}", 0 <<u32 as ::std::ops::Add<u32>>::add(1, 2)); // Error
}

0.0 の処理

次のような場合はエラーになる。

fn main() {
    println!("{}", ((0, 1), (2, 3)).0.0); // Error
}

ドットの直後に浮動小数点数が来る場合は、このように2つのフィールドの組み合わせを意図していると考えられる。コンパイラは、曖昧性をなくすために括弧をつけることを提案してくれるが、そのまま解釈はしてくれないようだ(1.16.0時点)。

括弧をつけるのではなく、スペースをつけることで回避することもできる。

fn main() {
    println!("{}", (((0, 1), (2, 3)).0).0);
    println!("{}", ((0, 1), (2, 3)).0 .0);
}

このパースが通るようにするのは原理的には可能であるように思えるが、少なくとも現在は実行されていない。