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

2024/08/27 09:25:41

OXCでRustの実装やったよ記念も兼ねて、忘れないうちにいろいろと書き残しておく。

feat(regex_parser): Implement RegExp parser by leaysgur · Pull Request #3824 · oxc-project/oxc https://github.com/oxc-project/oxc/pull/3824

実装した仕様は、現時点でPublishされてる最新のES2024まで。

#15th Edition – ECMAScript® 2024 Language Specification https://tc39.es/ecma262/2024/

その他、これから先にどういった機能追加が待ってるかは、前に書いた記事を参照されたし。

ECMAScriptのRegExpに関するプロポーザルのまとめ | Memory ice cubes https://leaysgur.github.io/posts/2024/07/12/101358/

というわけで、まずは前提知識編からスタート。

ちなみに、Rustの話はほぼ出てきません。

`RegExp`について

ECMAScriptもといJavaScriptにおいて、正規表現を表すRegExpインスタンスを生み出すには、次の2パターンがある。

const re1 = /abc/u;
const re2 = new RegExp("abc", "u");

リテラルでもコンストラクタでも、どちらも構成要素は同じで、パターンとフラグの2要素から成る。

で、ここで最初に知っておくべきは、後者の場合、文字列リテラルの都合によって、\によるエスケープが発生する場合があるということ。

// "'`a\ を表現したいだけなのに
const dq = "\"'`\a\\";
const sq = '"\'`\a\\';
const bq = `"'\`\a\\`;

パーサーをJavaScriptで実装する場合は、これらは勝手に処理されてる（！）ので、この後の実装としても気にすることはなにもない。

しかし、それ以外の言語の場合、.jsファイルを読み出した時点では、おそらくこれらはそのままになってるはず。なので、エスケープを解いたりダブルクオート前提になおしたりと、リテラルで書いたときと同じ意味になるようにして扱えるようにしないと、正規表現としての意味が変わってしまう。

まぁだいたいは既にECMAScriptのパーサーがあって、その拡張で正規表現を・・・って流れがほとんどだと思う、が、もしそうでない場合は要注意ということで。

まぁそんなこんなで、

リテラル同等のパターン
フラグ

この2つを手に入れられた前提で、それをASTにしていく体で進める。

フラグを先にパース

パターン本体をパースする前に、先にフラグから情報を得ておく必要がある。

仕様としてはこのあたり。

12.9.5 Regular Expression Literals
- 12.9.5.1 SS: BodyText
- 12.9.5.2 SS: FlagText

っても、ここで知りたいことはこの2つの存在だけ。

uフラグ
vフラグ

他にもgとかiとかフラグはいろいろあるけど、シンタックスに影響を与えないのでどうでもいい。

パターン本体

さて、正規表現パターン本体をパースするためには、以下のページを把握する。

22.2 RegExp(Regular Expression) Objects
- 22.2.1 Patterns
  - 22.2.1.1 SS: Early Errors
  - 22.2.1.2 SS: CountLeftCapturingParensWithin ( node )
  - 22.2.1.3 SS: CountLeftCapturingParensBefore ( node )
  - 22.2.1.4 SS: CapturingGroupNumber
  - 22.2.1.5 SS: IsCharacterClass
  - 22.2.1.6 SS: CharacterValue
  - 22.2.1.7 SS: MayContainStrings
  - 22.2.1.8 SS: GroupSpecifiersThatMatch ( thisGroupName )
  - 22.2.1.9 SS: CapturingGroupName
  - 22.2.1.10 SS: RegExpIdentifierCodePoints
  - 22.2.1.11 SS: RegExpIdentifierCodePoint
- 22.2.3 Abstract Operations for RegExp Creation
  - 22.2.3.4 SS: ParsePattern ( patternText, u, v )

基本的なパターンは22.2.1に書かれていて、それらパターンをパースしていくのが最初の一歩。

その上で、意味的におかしくないか？を検証するSS（StaticSemantics）を実装すると、より忠実な実装になるイメージ。 22.2.1.1のEarly Errorsのページがそのリストで、それ以降のページはEarly Errorsのための変数（実際には関数か）って感じになってる。

Annex B

ECMAScriptには、ブラウザの後方互換性のためにいつまでも生き続けるAnnex Bというサブセットがあって、先述のページの各所に変更を入れる形で定義されてる。

B.1.2 Regular Expressions Patterns
- B.1.2.1 SS: Early Errors
- B.1.2.2 SS: CountLeftCapturingParensWithin and CountLeftCapturingParensBefore
- B.1.2.3 SS: IsCharacterClass
- B.1.2.4 SS: CharacterValue
- B.1.2.9 SS: ParsePattern ( patternText, u, v )

Annex Bをサポートするかどうかは悩ましいところ。

ECMAScript implementations are discouraged from implementing these features unless the implementation is part of a web browser or is required to run the same legacy ECMAScript code that web browsers encounter.

でもまぁそう言われてもな・・・ってなるやつ。

個人的には、あくまで実用的なものを作りたいなら、サポートせざるを得ない・・・という空気を感じた。Node.jsだろうとBunだろうと、結局ブラウザ由来なエンジンを積んでるおかげで、ブラウザじゃないけどレガシー文法は動く環境が世間の当たり前なので。

肌感としては、手間+30%って感じだった。そこまで大変ではないけど、なんだかな〜って感じ。

パーサーのモード

という表現が正しいかはさておき、パターン本体のパースに必要な変数となるものが3つある。

UnicodeMode
UnicodeSetsMode
NamedCaptureGroups

これらの変数が、仕様書のいたるところで出てくる。

Pattern[UnicodeMode, UnicodeSetsMode, NamedCaptureGroups] ::
  Disjunction[?UnicodeMode, ?UnicodeSetsMode, ?NamedCaptureGroups]

というように。（このBNFライクな仕様自体の読み方は割愛するけど、なんとなく雰囲気でわかると思う）

で、これら3つがどのような経緯で有効になるかは、22.2.3.4という奥深くのページに記載されてる。（一番最初に書いといて欲しいと思った）

`UnicodeMode`

uフラグおよび、vフラグが指定されていればtrue、それ以外はfalseになる。

uでもvでも有効になるってところがポイント。

`UnicodeSetsMode`

vフラグが指定されていればtrue、それ以外はfalseになる。

ちなみに、uとvを両方指定しちゃうと、それはそれでエラーになる決まり。

`NamedCaptureGroups`

Annex Bをサポートしない場合、いかなる場合もtrueになる。単純明快。

Annex Bをサポートする場合、デフォルトではfalseだが、以下のどれかに該当する場合はtrueになる。

uフラグかvフラグが指定されている
パターン中に名前付きキャプチャグループが存在する
- (?<name>...)みたいなやつ

つまり、uもvも指定されてない場合、「パターン文字列を一通りパースして、名前付きキャプチャグループの有無を確認」しなければ、最終的なモードが決められないってこと。

先人のパーサー実装たちが、条件によっては2度目のパースをやり直すってコードになってて、最初は「？」って思ってたけどこれのため。

サロゲートペアと文字ユニット

これも実装前に知っておくとよいJavaScriptネタ。

たとえば、/^.{1}$/という正規表現があるとする。どんなユニットでもいいから、1つだけに合致してほしい。

で、/^.{1}$/.test("🤞")はどうなるかというと、直感に反してfalseになる。これは、書記素クラスターとしては1つのEmojiに見えてても、JSの正規表現はデフォルトでUTF-16の単位で処理するので、この絵文字はサロゲートペアで表現され、2ユニット存在することになってるから。

そこでuかvフラグを使って、/^.{1}$/u.test("🤞")とすると、Unicode単位で処理できるようになるので、今度はtrueになる。

で、こういう違いを、パーサーの挙動・ASTとして、どこまで表現したい？という話。要するに、サロゲートペアの扱いをどうするか。

最もシンプルに考えるなら、uもしくはvフラグに応じて、以下のように処理ユニットを使い分けるはず。

// UnicodeMode: false = UTF16
"🤞".split("") // [ '\ud83e', '\udd1e' ]

// UnicodeMode: true = Unicode
[..."🤞"] // [ '🤞' ]

パーサーの実装として

実は、仕様で触れられていて、サロゲートペアに敏感になる必要があるのは、名前付きキャプチャグループのグループ名の部分だけ。

(?<name>.)
\k<name>

そしてここで仮にサロゲートペアを無視して扱ったとしても、不完全なグループ名だよエラーに収束するようだった。（少なくとも現状のTest262のテストでは）

このことから、パーサーの処理ユニットをUnicode単位に絞ってしまっても良いのでは？と思ったけど、予期せぬ野生の正規表現に出くわすリスクを考えると、踏み切れなかった。

他の実装案としては、「基本はUTF-16で読み出しつつ、UnicodeMode: true時にBMP文字以外を見つけたら、そのサロゲートペアを合算」することもできそう。

出力されるASTとして

「特別な意味を持たない文字の部分」にサロゲートペアが現れたとき、パースしたASTの結果として、それぞれを独立した表現にしたいかどうか。

つまり、/🤞!/という正規表現を、次のどっちで表現したいか。

// それぞれ表現するパターン
[HighSurrogate, LowSurrogate, BMP]

// まとめるパターン
[SurrogatePair, BMP]

このあたりはASTのデザイン次第かと。

あとは、構文エラーを見つけたときにここがおかしい！って親切に表示するためには、モード関係なく元のUTF-16の位置でスライスする必要があるのにも注意。

Rustなんかだと、サロゲートペアに対する有効なスライス位置を&str[start..end]でそもそも表現できなかったりするので悩ましい。

Part 2へ続く

今回はいわゆる前提知識パートでした。

次回は、パターンそれ自体について書いていきます。

RegExpについて