具象構文木とRed Green Tree

具象構文木とRed Green Tree > Roslyn/libSyntax/rust-analyzerに学ぶ構文木の扱い方 2026/04/17 @BLUE FRONT SHIBAURA TOWER コンパイラのコンパの部分 #2 #コンパイラのコンパの部分 1

- @nuskey8 (a.k.a @annulusgames) - 大学生です - Unity・C#・RustのOSS開発やってます - 最近はフロントエンド書いたりVJしたりしてます #コンパイラのコンパの部分 # # 自己紹介 2

- 構文木とは？ - Red Green Treeとは？ - [Demo] rowanを用いたRed Green Treeの実装 #コンパイラのコンパの部分 # # LTの内容 3

# 構文木とは？ #コンパイラのコンパの部分 4

- プログラムなどの構造化テキストを木構造で表現したもの 1 + 2 * 3 - e.g. 1 + 2 * 3 + - 字句解析を経てトークン化されたものを 構文解析で構築するフローが一般的 * 1 2 #コンパイラのコンパの部分 # # 構文木とは？ 3 5

- Abstract Syntax Tree (AST) 1 + 2 * 3 - 構文木のうち、コメントや空白などの構文に 影響しない要素を含まないもの - コンパイラやインタプリタなどを作る時に 「構文木」といえば大体こっち #コンパイラのコンパの部分 # # 抽象構文木 (AST) 6

1 + 2 * 3 - Concrete Syntax Tree (CST) - ソースコードの文法構造をそのままツリーにしたもの - セミコロンや括弧などの記号もそのまま含める - 用途によっては位置情報や空白、コメントなども - ソースコードの完全な情報を失うことなく保持する構文木は 「Lossless Syntax Tree」と呼ばれたりもする #コンパイラのコンパの部分 # # 具象構文木 (CST) 7

- 意味表現に不要な情報を捨てているため、ソースコード→ASTの操作が可逆的でない - フォーマッタや言語サーバーなどの実装には位置情報やコメント、改行など要素を 保持する必要がある → 具象構文木が必要 #コンパイラのコンパの部分 # # なぜ抽象構文木では不十分なのか？ 8

## [余談] triviaを保持する - コメントや空白などの構文の意味に関係がない装飾的な要素を Roslynでは”trivia”と呼ぶ - 抽象構文木のパーサは基本的に字句解析時点でスキップするが、 具象構文木を作りたいならtriviaも同時に収集する必要がある - このtriviaを構文木に保持するのは実は結構難しい #コンパイラのコンパの部分 9

- triviaの扱い方はRoslyn/libSyntaxと 1 + 1 A rust-analyzerで異なる - Roslyn/libSyntaxはトークン自体が前後の triviaを保持する (A) - rust-analyzerでは2つのノードの間のtriviaを 親ノードが保持する (B) B - 表現としてはrust-analyzer式がシンプルだが、 実際の扱いやすさはRoslyn式に軍配が上がる - rust-analyzerもこの方式に移行する提案が立っている ref: https: github.com/rust-lang/rust-analyzer/issues/6584 / / #コンパイラのコンパの部分 # # triviaの保持戦略 10

• https://github.com/rust-lang/rust-analyzer/issues/6584

# Red Green Treeとは？ #コンパイラのコンパの部分 11

- ナイーブな実装では、ソースコードを変更するたびに構文木を再構築する必要が生じる - 通常ソースコードの変更は部分的であるため、構文木をインクリメンタルに更新したい - 言語サーバーの実装では処理速度が開発体験に直結するため重要 - でもどうやって実装すればいい？ #コンパイラのコンパの部分 # # インクリメンタルに更新したい 12

- 効率的な書き換えを実現するための具象構文木の実装手法 - 発祥はRoslyn(C#)! - rust-analyzerやlibSyntaxも採用している - RedとGreenの2つのNodeを使い分けることで効率的な構文木の書き換えを実現する #コンパイラのコンパの部分 # # Red Green Treeの導入 13

- 内部表現のためのImmutableな 構文木のノード - ノードは絶対的な位置情報ではなく ”文字幅”を保持する - 子要素となるノードを保持し、 トップダウンに走査できる - これらのノードはキャッシュされ、 再利用される #コンパイラのコンパの部分 # # Green Node 14

- 外部に露出するGreen Nodeのラッパー - 文字のオフセットと、内部に抱える Green Nodeへの参照を保持する - 親要素への参照を持ち、ボトムアップに走査できる - Green Nodeとは異なり、こちらは再利用されず 変更のたびに再構築される #コンパイラのコンパの部分 # # Red Node 15

- 文字幅とオフセットを別々にもたせることでGreen Nodeを再利用可能にする - Red Nodeは再利用されないが、それ自体は軽量なラッパーのため問題ない - 実際にAPIとして露出するのはRed Node側になる #コンパイラのコンパの部分 # # なぜ2つのNodeを使うのか？ 16

# [Demo] rowanを用いたRed Green Treeの実装 #コンパイラのコンパの部分 17

- rust-analyzer内部で使われるRed Green Treeの構築には rowanクレートが用いられる - rowan自体は言語に依存しないRed Green Treeの実装 - Losslessな構文木を非常にコンパクトかつハイパフォーマンスに 表現することができる #コンパイラのコンパの部分 # # rowanクレート 18

- repo: https: github.com/nuskey8/red-green-tree-example - rowanを用いて簡単な整数+四則演算のRed-Green Treeを構築する例 - Lexerの実装はlogosクレートを利用 - ファイルのwatchし、変更に応じて構文木を再構築する - Green Nodeが適切にキャッシュされ、必要に応じて 再利用される - 構文解析自体はシンプルな再帰降下パーサの実装で インクリメンタルではないことに注意 / / #コンパイラのコンパの部分 # # [Demo] rowanを用いたパーサ実装 19

• https://github.com/nuskey8/red-green-tree-example

# まとめ #コンパイラのコンパの部分 20

- 構文木には抽象構文木・具象構文木がある - 効率的な構文木のデータ構造としてRed Green Treeが用いられる - rowanはいいぞ #コンパイラのコンパの部分 # # まとめ 21

# Thank you for listening! #コンパイラのコンパの部分 22