ECMAScript `RegExp`パーサー実装の手引き Part 2

続きです。

ECMAScript RegExpパーサー実装の手引き Part 1 | Memory ice cubes https://leaysgur.github.io/posts/2024/08/27/092541/

今回は、正規表現のパターン本体について。

パース処理自体は、より上層のパターンから下層に向かって順にパースしていく再帰下降構文解析ってやつ。

特に注意点もなく、前回で紹介した3つのフラグを見ながら、ただ淡々と仕様書に従ってパーサーを実装していけばいい。

パターンの概観

Annex Bを無視した場合、大まかにこういう感じ。

- Pattern
  - Disjunction
    - Alternative
      - [empty]
      - Term
        - Assertion
        - Atom
          - PatternCharacter
          - .
          - \ AtomEscape
            - DecimalEscape
            - CharacterClassEscape
            - CharacterEscape
            - k GroupName
          - CharacterClass
          - ( GroupSpecifier? Disjunction )
          - (?: Disjunction )
        - Atom+Quantifier

内訳をざっくり紹介すると、

• アサーション
  • ^とか$とか
  • (?=...)とか(?<=...)とか
• 文字の1ユニット
  • .とか
  • \でエスケープされた1文字とか
  • 特別な意味を持たないただの文字とか
• 文字クラスエスケープ
  • \dとか\wとか
• ユニコード文字クラスエスケープ
  • \p{...}とか
• 文字クラス
  • [abc]とか
• キャプチャグループ
  • (?<named>...)とか(...)とか
• 非キャプチャグループグループ
  • (?:...)
• 後方参照
  • \1とか\k<name>とか

改めてみると、たったこれだけかって感じ。

この中で個人的に一番手間だったのは、[abc]みたく[]で囲まれた文字クラスという文法で、ここに全体工数の30%くらい持ってかれた体感がある。（パースの後も面倒が付いてくるし）

せっかくなので、深堀ってメモっておく。

CharacterClass

https://tc39.es/ecma262/2024/multipage/text-processing.html#prod-CharacterClass

正規表現としては、この「カッコ内で定義された何かしらにマッチする1ユニット」って意味。

• [ab\d]: aかbか\dにマッチする1つ
• [a-z]: aからzまでのレンジにある1つ
• [a-cx-z]: aからcまでの1つかxからzまでの1つ

みたいなバリエーションがある。

で、定義はこうなってる。

CharacterClass[UnicodeMode, UnicodeSetsMode] ::
  [ [lookahead ≠ ^] ClassContents[?UnicodeMode, ?UnicodeSetsMode] ]
  [^ ClassContents[?UnicodeMode, ?UnicodeSetsMode] ]

これはまあよい。^があったら意味が反転するよってだけで、本題はClassContentsってやつ。

ClassContents[UnicodeMode, UnicodeSetsMode] ::
  [empty]
  [~UnicodeSetsMode] NonemptyClassRanges[?UnicodeMode]
  [+UnicodeSetsMode] ClassSetExpression

vフラグによって決まるUnicodeSetsModeの有無でパターンが変わる。

NonemptyClassRanges

https://tc39.es/ecma262/2024/multipage/text-processing.html#prod-NonemptyClassRanges

vフラグがない場合。

最初はこの定義が本当に理解できなかった・・・。 ノンだのノーだの、何か同じようなことが無限に書いてある・・・って。

NonemptyClassRanges[UnicodeMode] ::
  ClassAtom[?UnicodeMode]
  ClassAtom[?UnicodeMode] NonemptyClassRangesNoDash[?UnicodeMode]
  ClassAtom[?UnicodeMode] - ClassAtom[?UnicodeMode] ClassContents[?UnicodeMode, ~UnicodeSetsMode]

NonemptyClassRangesNoDash[UnicodeMode] ::
  ClassAtom[?UnicodeMode]
  ClassAtomNoDash[?UnicodeMode] NonemptyClassRangesNoDash[?UnicodeMode]
  ClassAtomNoDash[?UnicodeMode] - ClassAtom[?UnicodeMode] ClassContents[?UnicodeMode, ~UnicodeSetsMode]

ClassAtom[UnicodeMode] ::
  -
  ClassAtomNoDash[?UnicodeMode]

ClassAtomNoDash[UnicodeMode] ::
  SourceCharacter but not one of \ or ] or -
  \ ClassEscape[?UnicodeMode]

要するに、-でつながってるならレンジを表すし、そうでないなら単品のClassAtomNoDashってこと。 なんの意味もないけど、[---]がちゃんとレンジを表せるようになってるがゆえに、こんな複雑な表現になってる。

（要約を書いておいてほしいよ・・・）

ちなみに、Annex Bをサポートする場合、ClassAtomNoDash配下に変更があり、構文がもう少し緩くなるイメージ。

ClassSetExpression

https://tc39.es/ecma262/2024/multipage/text-processing.html#prod-ClassSetExpression

次にvフラグのとき。こっちは新しい文法なので、Annex Bの影響を受けない。

ClassSetExpression ::
  ClassUnion
  ClassIntersection
  ClassSubtraction

ClassUnion ::
  ClassSetRange ClassUnionopt
  ClassSetOperand ClassUnionopt

ClassIntersection ::
  ClassSetOperand && [lookahead ≠ &] ClassSetOperand
  ClassIntersection && [lookahead ≠ &] ClassSetOperand

ClassSubtraction ::
  ClassSetOperand -- ClassSetOperand
  ClassSubtraction -- ClassSetOperand

ここまではよい。

• 3種類のパターンに分岐する
• まず先頭に何かしらあって
• &&でつながってればClassIntersection
• --でつながってればClassSubtraction
• それ以外はClassUnion
  • これはvフラグがないときのNonemptyClassRangesNoDash相当

なので、初手でレンジをパースできたなら、それはClassUnionで決定ということ。

あとは&&か--か、どっちかを見て決めればよく、これらは混在できない。

それぞれの構成要素はこの2つ。

ClassSetRange ::
  ClassSetCharacter - ClassSetCharacter

ClassSetOperand ::
  NestedClass
  ClassStringDisjunction
  ClassSetCharacter

ClassSetRangeは、vフラグがないときのレンジとだいたい同じ。

ClassSetOperandがちょい複雑なので、NestedClassとClassStringDisjunctionの特殊さだけ書いておく。

NestedClass

NestedClass ::
  [ [lookahead ≠ ^] ClassContents[+UnicodeMode, +UnicodeSetsMode] ]
  [^ ClassContents[+UnicodeMode, +UnicodeSetsMode] ]
  \ CharacterClassEscape[+UnicodeMode]

まさかの[abc]を、[[abc][def]]みたくネストできる。なんと[[[[[[[[[[[!]]]]]]]]]]]も正しい構文。

CharacterClassEscapeは、なんでここに書いてあるんやろうね。

ClassStringDisjunction

ClassStringDisjunction ::
  \q{ ClassStringDisjunctionContents }

ClassStringDisjunctionContents ::
  ClassString
  ClassString | ClassStringDisjunctionContents

\q{}で文字列の集合を自在に作れるやつ。

\q{a}みたく文字1つもあれば、\q{abc}みたく文字列1つもあれば、\q{a|bc|}みたくその組み合わせを|でつなげられるし、空もあり。

まぁパースするのは難しくない。

Part 3へ続く

というわけで、ひたすら仕様書をにらみながら、淡々とパース処理を書き続ける・・・わかってたけど単純作業になる部分。

パーサーの実装として悩ましいのは、仕様書に書いてあるパターン通りにifを並べる必要はないというところ。

似たりよったりな構文もあるので、同じ関数にまとめてフラグで対処〜とか、DRYな誘惑に駆られることはよくあるけど、後から見るときには仕様書のパターン通りになってるほうが絶対わかりやすいと思う。

最後は、Early Errorsを実装して仕上げ。