11 分で読了 #compilers #構文解析
このページの目次

AST設計とエラーリカバリ

パーサーの出力は文字列ではなく木構造——ASTの設計（非同構 vs 同構、spanエンコーディング）がその後の全passの使いやすさを決定し、エラーリカバリはコードの途中でもIDEが有用な補完を提示できるかどうかを決定する。

概要

パーサーの出力は抽象構文木(AST)⁠である。これはCST(Concrete Syntax Tree, 構文木)とは異なる。CSTは文法の導出の各ステップを正確に反映しており、括弧、セミコロン、キーワードのすべてが木上に存在する。ASTは意味的に意味のあるノードのみを保持し、括弧は捨て（入れ子で代替）、セミコロンは捨て（文リストで代替）、キーワードは捨て（ノードタイプで代替）する。ここではASTの3つの設計アプローチ、位置情報の正しいエンコーディング方法、そして入力に構文エラーがある場合にASTが「崩壊せず有用な情報を提供する方法」について解説する。

3つのAST設計アプローチ

非同構AST: 各ノードタイプごとに型を定義

代数的データ型(ADT、Rustではenum)を使用して、各構文構成に対して専用のノードタイプを定義する。

enum Expr {
    Number(i64, Span),
    Binary(BinOp, Box<Expr>, Box<Expr>, Span),
    Call(Box<Expr>, Vec<Expr>, Span),
    // ...
}

enum Stmt {
    Let(String, Option<Expr>, Box<Expr>, Span),
    If(Box<Expr>, Box<Stmt>, Option<Box<Stmt>>, Span),     ← elseは省略可能
    While(Box<Expr>, Box<Stmt>, Span),
    Return(Option<Box<Expr>>, Span),
    // ...
}

これは産業用コンパイラでの主流な選択である(Clang, Rustc, Swiftcすべてがこのアプローチを採用)。利点:⁠型安全性⁠(後続のpassで各ノードに対してパターンマッチングを行い、コンパイラが網羅性を保証する)、⁠明確さ⁠(enumのvariantを見るだけでそれがどのような構文構成かがわかる)。欠点:ノードの種類が多く、AST定義のコード量が多くなる。また、後続のpassで新しい解析を追加するたびに、各ノードタイプごとにmatch armを書く必要がある。

同構AST: 1つの汎用ノードタイプ

すべてのノードが共通のタイプを使用し、tagで区別する。

struct Node {
    kind: NodeKind,          ← Number, Binary, Call, ...
    children: Vec<Node>,     ← 子ノードリスト
    span: Span,
}

Lisp風コンパイラ、JSON/XMLパーサー、protobufコンパイラなどでよく使われる。利点:⁠トラバースパターンが統一される⁠(すべてのノードが同じAPIを持ち、再帰的なトラバースは同じ関数で実行可能)、⁠拡張性が高い⁠(新しいpassを追加する際に、N種類のノードすべてにmatch armを書く必要がない)。欠点:コンパイル時の型安全性が欠如している(child[0]をExprとして期待してもコンパイラは保証せず、誤ったアクセスは実行時才发现)、意味情報が弱い(Ifの3番目のchildがelse節なのか存在しないのか判断できない)。

CSTを先行させ、その後ASTに降格

一部のコンパイラ(Rustc, GHC)は、パーシング後に中間表現層を導入する。RustcではAST → HIR(糖衣除去+型関連処理)、GHCではCoreなど。CSTはすべての構文詳細(括弧、セミコロン、コメント)を含み、パーサーが直接出力する。その後、「lowering」passによってCSTからASTへの変換が行われる(純粋に構文的なノードを捨て、名前参照を解決する)。このアプローチの動機は以下の通り。

  • IDE/フォーマッターはCSTを必要とする⁠(補完、ジャンプ、フォーマットはいずれもCSTの完全な位置情報に依存する)。
  • コメントの帰属問題⁠——コメントはASTの外で破棄されるが、ドキュメントジェネレーターはコメントを対応するASTノードに紐付ける必要がある。CSTにはコメントが保持されており、lowering passによって帰属処理が行われる。

Rustcのast.rsは実際にはCSTに近い豊富な情報を持つASTであり(macro invocationなどの詳細を保持)、その後hir.rs(High-Level IR)が糖衣除去された真の抽象表現となる。

位置情報: Spanのエンコーディング

各ASTノードにはSpanが伴い、ソースコード内の位置を示す。Spanには少なくとも以下が必要である。

Span {
    start: BytePos,       ← ファイル内の開始バイトオフセット
    end: BytePos,         ← 終了バイトオフセット (排他的)
}

Spanから導出できるもの: ソーステキスト(source[span.start..span.end])、行番号/列番号(line tableを通じて逆算)、そして「この木がカバーする全体の範囲」(木の中で最も左の子のstartから最も右の子のendまで)。

SpanをASTノードに保存するか、それとも別途管理するか? 両方のアプローチが存在する。RustcはSpanをノード内に保存する(各ノードに1つのSpan)。LLVMや一部のIRは位置情報をグローバルなsource-level debug infoテーブルに保存し、ASTノードはIDのみを保持する。前者の利点: 単純で、トラバース時にテーブル参照が不要。後者の利点: 「ソースコード位置を持たないノード」(例えばコンパイラが合成したコード)に対して余分なメモリを消費しない。

エラーリカバリ: ASTはエラーに出会って空になってはならない

パーサーがx = 1 + ;(式が不完全)に出会った場合、Noneを返したりクラッシュしたりしてはならない。その後の意味解析、IDE補完、ドキュメント生成はいずれもASTが存在することに依存している。エラーリカバリの目標は:⁠合法なASTを出力し、エラーノードを「エラー」としてマークすることである。

Panic mode: 同期マークまでスキップ

最も古典的なリカバリ手法で、LR分析でも言及されている。

パーサーが予期しないトークンに出会った場合:
  1. エラーを報告
  2. 同期マーク(例えば ';' や '}')に出会うまで後続のトークンをスキップ
  3. 同期マークの後に解析を再開

代償として、「スキップされたトークンの範囲」内のすべての構文構成が失われる——ASTの部分木が一切生成されない。IDEにとってこれは最悪のケースである。ユーザーが編集中の領域で補完やジャンプのニーズがあるかもしれないが、すべてが失われてしまう。

Error productions: 明示的なエラー規則の記述

文法に明示的にエラー生成規則を追加し、パーサーに「正しくなくても帰約できる」出口を与える。

Stmt → error ';'
Expr → '(' error ')'

エラーが発生した場合、パーサーはerrorシンボルに帰約する(同期マークに出会うまで、見たあらゆるトークンにマッチし)、エラーマーク付きのASTノードを生成する。これはPanic modeより優れている——少なくとも「ここに何らかの文/式が存在する」という構造が保持され、後続のpassで緩やかな解析を行うことができる。

エラーノード: AST内に「壊れたノード」が存在する

手書きパーサー(LLアプローチで一般的)の究極的な解決策:⁠パーサーはエラーに出会ってもASTノードを構築し続けるが、それを「内部にエラーがある」としてマークする⁠。

enum Expr {
    Number(i64, Span),
    Binary(BinOp, Box<Expr>, Box<Expr>, Span),
    Error(String, Span),    ← 「壊れた式」、エラー情報とそれがカバーするトークンのspanを保持
}

パーサーはx = 1 + ;において、+の後に項目が不足していることを検出する→ Expr::Error("expected expression after +", span_of_plus_to_semicolon)を構築し、このAST部分木を「エラー式」として返す。上位(Stmt::Let)は式を正常に受け取る(内容は間違っているが)、解析は継続する。

利点は、AST全体が常に完全であること——IDE/LSPはエラーのあるAST上でもトークン aware な補完を行うことができ⁠、空白に対処する必要がない。RustcとClangの両方のアプローチがこの方向に進んでいる。実際の実装では、is_error()メソッドや専用のErrorKind enumを組み合わせ、エラータイプを区別し、意味解析passがスキップまたは処理できるようにしている。

エラーリカバリの品質基準

良いエラーリカバリは以下を満たすべきである。

  • エラーのない部分のASTを破棄しない⁠——エラーはそれが存在する局所的な部分木のみに影響する。
  • 単一エラーは1回だけ報告⁠——リカバリ中に同じ構文エラーに対して繰り返しエラーを報告しない。
  • リカバリ後にファイルの終わりまで解析を継続⁠——最初のエラーで終了するのではなく、すべての構文エラーを特定する。

参考文献

  • Nystrom: 「Crafting Interpreters」、第5-6章 (CST/ASTの実践的デザイン、PrattパーサーとAST構築)
  • Clang: include/clang/AST/Expr.h — 非同構ASTの産業標準、各式に対して1つのノードクラス
  • Rustc: compiler/rustc_ast/src/ast.rs (CST/AST)、compiler/rustc_hir/src/hir.rs (糖衣除去後)

Keywords: AST, abstract syntax tree, CST, concrete syntax tree, heterogeneous AST, homogeneous AST, sum type, enum, span, position, BytePos, lowering, error recovery, panic mode, synchronizing token, error production, error node, parse error, incremental parsing, IDE

関連ページ

© 2026 liz's doc