--- title: 具象構文木とRed Green Tree tags: author: [nuskey](https://www.docswell.com/user/nuskey) site: [Docswell](https://www.docswell.com/) thumbnail: https://bcdn.docswell.com/page/4EZL1G4R73.jpg?width=480 description: コンパイラのコンパの部分 #2の登壇資料です。 https://compiler.connpass.com/event/376756/ published: April 17, 26 canonical: https://www.docswell.com/s/nuskey/Z6NVW8-cst-and-red-green-tree --- # Page. 1 ![Page Image](https://bcdn.docswell.com/page/4EZL1G4R73.jpg) 具象構文木とRed Green Tree > Roslyn/libSyntax/rust-analyzerに学ぶ構文木の扱い方 2026/04/17 @BLUE FRONT SHIBAURA TOWER コンパイラのコンパの部分 #2 #コンパイラのコンパの部分 1 # Page. 2 ![Page Image](https://bcdn.docswell.com/page/Y76WLY317V.jpg) - @nuskey8 (a.k.a @annulusgames) - 大学生です - Unity・C#・RustのOSS開発やってます - 最近はフロントエンド書いたりVJしたりしてます #コンパイラのコンパの部分 # # 自己紹介 2 # Page. 3 ![Page Image](https://bcdn.docswell.com/page/G75M1GLL74.jpg) - 構文木とは？ - Red Green Treeとは？ - [Demo] rowanを用いたRed Green Treeの実装 #コンパイラのコンパの部分 # # LTの内容 3 # Page. 4 ![Page Image](https://bcdn.docswell.com/page/9J291YL3ER.jpg) # 構文木とは？ #コンパイラのコンパの部分 4 # Page. 5 ![Page Image](https://bcdn.docswell.com/page/DEY4ZGQ8JM.jpg) - プログラムなどの構造化テキストを木構造で表現したもの 1 + 2 * 3 - e.g. 1 + 2 * 3 + - 字句解析を経てトークン化されたものを 構文解析で構築するフローが一般的 * 1 2 #コンパイラのコンパの部分 # # 構文木とは？ 3 5 # Page. 6 ![Page Image](https://bcdn.docswell.com/page/VJNY3GK978.jpg) - Abstract Syntax Tree (AST) 1 + 2 * 3 - 構文木のうち、コメントや空白などの構文に 影響しない要素を含まないもの - コンパイラやインタプリタなどを作る時に 「構文木」といえば大体こっち #コンパイラのコンパの部分 # # 抽象構文木 (AST) 6 # Page. 7 ![Page Image](https://bcdn.docswell.com/page/YE9P9WV3J3.jpg) 1 + 2 * 3 - Concrete Syntax Tree (CST) - ソースコードの文法構造をそのままツリーにしたもの - セミコロンや括弧などの記号もそのまま含める - 用途によっては位置情報や空白、コメントなども - ソースコードの完全な情報を失うことなく保持する構文木は 「Lossless Syntax Tree」と呼ばれたりもする #コンパイラのコンパの部分 # # 具象構文木 (CST) 7 # Page. 8 ![Page Image](https://bcdn.docswell.com/page/GE8D9NPLED.jpg) - 意味表現に不要な情報を捨てているため、ソースコード→ASTの操作が可逆的でない - フォーマッタや言語サーバーなどの実装には位置情報やコメント、改行など要素を 保持する必要がある → 具象構文木が必要 #コンパイラのコンパの部分 # # なぜ抽象構文木では不十分なのか？ 8 # Page. 9 ![Page Image](https://bcdn.docswell.com/page/LELMWP1Q7R.jpg) ## [余談] triviaを保持する - コメントや空白などの構文の意味に関係がない装飾的な要素を Roslynでは”trivia”と呼ぶ - 抽象構文木のパーサは基本的に字句解析時点でスキップするが、 具象構文木を作りたいならtriviaも同時に収集する必要がある - このtriviaを構文木に保持するのは実は結構難しい #コンパイラのコンパの部分 9 # Page. 10 ![Page Image](https://bcdn.docswell.com/page/4JMY945KJW.jpg) - 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 # Page. 11 ![Page Image](https://bcdn.docswell.com/page/PJR9GW3679.jpg) # Red Green Treeとは？ #コンパイラのコンパの部分 11 # Page. 12 ![Page Image](https://bcdn.docswell.com/page/PEXQXP4DJX.jpg) - ナイーブな実装では、ソースコードを変更するたびに構文木を再構築する必要が生じる - 通常ソースコードの変更は部分的であるため、構文木をインクリメンタルに更新したい - 言語サーバーの実装では処理速度が開発体験に直結するため重要 - でもどうやって実装すればいい？ #コンパイラのコンパの部分 # # インクリメンタルに更新したい 12 # Page. 13 ![Page Image](https://bcdn.docswell.com/page/3EK9WDZDED.jpg) - 効率的な書き換えを実現するための具象構文木の実装手法 - 発祥はRoslyn(C#)! - rust-analyzerやlibSyntaxも採用している - RedとGreenの2つのNodeを使い分けることで効率的な構文木の書き換えを実現する #コンパイラのコンパの部分 # # Red Green Treeの導入 13 # Page. 14 ![Page Image](https://bcdn.docswell.com/page/L73W1RDP75.jpg) - 内部表現のためのImmutableな 構文木のノード - ノードは絶対的な位置情報ではなく ”文字幅”を保持する - 子要素となるノードを保持し、 トップダウンに走査できる - これらのノードはキャッシュされ、 再利用される #コンパイラのコンパの部分 # # Green Node 14 # Page. 15 ![Page Image](https://bcdn.docswell.com/page/87DKXYP3JG.jpg) - 外部に露出するGreen Nodeのラッパー - 文字のオフセットと、内部に抱える Green Nodeへの参照を保持する - 親要素への参照を持ち、ボトムアップに走査できる - Green Nodeとは異なり、こちらは再利用されず 変更のたびに再構築される #コンパイラのコンパの部分 # # Red Node 15 # Page. 16 ![Page Image](https://bcdn.docswell.com/page/VJPKP6NPE8.jpg) - 文字幅とオフセットを別々にもたせることでGreen Nodeを再利用可能にする - Red Nodeは再利用されないが、それ自体は軽量なラッパーのため問題ない - 実際にAPIとして露出するのはRed Node側になる #コンパイラのコンパの部分 # # なぜ2つのNodeを使うのか？ 16 # Page. 17 ![Page Image](https://bcdn.docswell.com/page/2EVV23KVEQ.jpg) # [Demo] rowanを用いたRed Green Treeの実装 #コンパイラのコンパの部分 17 # Page. 18 ![Page Image](https://bcdn.docswell.com/page/57GLR3Q1EL.jpg) - rust-analyzer内部で使われるRed Green Treeの構築には rowanクレートが用いられる - rowan自体は言語に依存しないRed Green Treeの実装 - Losslessな構文木を非常にコンパクトかつハイパフォーマンスに 表現することができる #コンパイラのコンパの部分 # # rowanクレート 18 # Page. 19 ![Page Image](https://bcdn.docswell.com/page/4EQYV5KNJP.jpg) - repo: https: github.com/nuskey8/red-green-tree-example - rowanを用いて簡単な整数+四則演算のRed-Green Treeを構築する例 - Lexerの実装はlogosクレートを利用 - ファイルのwatchし、変更に応じて構文木を再構築する - Green Nodeが適切にキャッシュされ、必要に応じて 再利用される - 構文解析自体はシンプルな再帰降下パーサの実装で インクリメンタルではないことに注意 / / #コンパイラのコンパの部分 # # [Demo] rowanを用いたパーサ実装 19 # Page. 20 ![Page Image](https://bcdn.docswell.com/page/KJ4WM9P371.jpg) # まとめ #コンパイラのコンパの部分 20 # Page. 21 ![Page Image](https://bcdn.docswell.com/page/LE1Y8K9Z7G.jpg) - 構文木には抽象構文木・具象構文木がある - 効率的な構文木のデータ構造としてRed Green Treeが用いられる - rowanはいいぞ #コンパイラのコンパの部分 # # まとめ 21 # Page. 22 ![Page Image](https://bcdn.docswell.com/page/GEWGZDQ6J2.jpg) # Thank you for listening! #コンパイラのコンパの部分 22