正規表現エンジンが内部で使う AST（抽象構文木）
正規表現は文字列として書かれますが、エンジンはこの文字列を直接走査しているわけではありません。正規表現エンジンはまず入力を解析して AST（抽象構文木） を構築し、そこから NFA や VM 用命令列を生成します。AST は正規表現の構造を適切に表現する中間形式であり、優先順位の処理や最適化のために不可欠です。
AST の基本構造
正規表現エンジンは、入力パターンを次のようなノードから構成される木に変換します。
これらが組み合わさって正規表現の意味が表されます。
Literal
個々の文字を表すノードです。
例: a, b, 1, _ など。
複数の連続したリテラルは最適化でまとめられることがあります。
CharacterClass
角かっこで表す文字集合です。
[abc] や [^0-9] が典型です。
内部では、許可するコードポイント集合として保持されます。
Concatenation
スペースなしで隣接する要素はすべて連結ノードの子になります。
例: abc は a → b → c の順で連結されます。
Alternation
| で区切られた複数候補です。
例: a|b|c など。
AST では Alternation ノードの子として複数パターンを持ちます。
Quantifier
量指定子を表すノードです。
* → {0, ∞}+ → {1, ∞}? → {0, 1}{m,n} → {m, n}量指定子は常に直前のノードに作用します。
Group
かっこで囲まれたパターンを表します。次のように種類があります。
(...)(?:...)(?=...)(?!...)(?<=...)(?後読みは AST の段階で長さ制約などの検証が入ることがあります。
Anchor
文字そのものではなく、位置を表すノードです。
^ → 行頭$ → 行末\b → 単語境界\B → 非単語境界AST 生成の流れ
入力文字列から AST が作られる順序は以下のようになります。
字句解析（トークナイズ）
構文解析（AST の生成）
AST の最適化（不要ノード削除や連結統合）
NFA や VM 命令列の生成
実行
AST は NFA 生成の前段階として構造を明確化し、バックトラッキングに関する最適化を可能にします。
例1: /ab+c/ の AST
Concat
├─ Literal('a')
├─ Quantifier
│ ├─ Literal('b')
│ └─ {min=1, max=∞}
└─ Literal('c')例2: ^(foo|bar)$ の AST
Concat
├─ Anchor('^')
├─ Group
│ └─ Alternation
│ ├─ Literal('foo')
│ └─ Literal('bar')
└─ Anchor('$')例3: (?<=\n)[A-Z]+ の AST
Concat
├─ Lookbehind
│ └─ Literal('\n')
└─ Quantifier
├─ CharacterClass([A-Z])
└─ {min=1, max=∞}AST が重要な理由
AST は正規表現エンジンの中核を成す要素であり、高性能なマッチングアルゴリズムの基盤になっています。
4views
