テキストおよび日常ツール · テキスト ツールキット
Kleene から JavaScript まで: 正規表現の短い歴史
· 背景
正規表現 JavaScript 計算履歴
1950 年代のオートマトン理論から ed、grep、Perl を経て、あらゆるブラウザーの JavaScript フレーバーに至る正規表現を追跡し、構文がなぜそのように見えるのか、どの機能がいつ登場したかを説明します。
誰もが半ば知っている奇妙な小さな言語 — 正規表現構文が古くて一貫性がないように感じる理由
正規表現は、実質的にそれが本質であるため、時代を超えて組み立てられた言語のように感じられます。交互、繰り返し、およびグループ化のコンパクトなコアは、数学的表記法からエディター コマンド、コマンドライン フィルター、プログラミング言語機能へと成長しました。各ホストが独自の利便性、制約、用語を追加しながら、句読点は存続しました。
この歴史は、パターンが見慣れているように見えても、grep、Perl、Python、JavaScript の間で動作が異なる理由を説明しています。 「正規表現」はファミリーネームであり、1 つの普遍的な文法ではありません。独学のアナリストにとって有益な教訓は、すべての方言を暗記することではなく、借用したパターンを信頼する前にエンジン、フラグ、置換ルールを特定することです。
クリーンの定期的なイベント — 私たちにスターを与えた有限オートマトンの 1950 年代の数学
Stephen Cole Kleene の有限オートマトンと「定期的なイベント」に関する研究は、1950 年代の理論的根幹を提供しました。彼の表記法は、結合、連結、閉包などの演算を使用してシンボル シーケンスのセットを記述しました。クロージャ操作は、Kleene スターになりました。`A*` は、単に「1 回以上繰り返す」ではなく、A から抽出される 0 個以上の繰り返しを意味します。
有限オートマトンによって認識される正式な正規言語は、現在正規表現ラベルで販売されている多くの構造よりも範囲が狭いです。たとえば、後方参照は、古典的なモデルを超えた条件を表現できます。したがって、最新のエンジンは、歴史的な名前と表記法の多くを維持しながら、その機能と実行戦略が Kleene の元の数学的オブジェクトを超えて拡張されるパターン言語を実装しています。
Thompson、ed、および grep — 1960 年代後半から 1970 年代初頭にかけて、正規表現がどのようにして Unix ツールにテキスト編集に組み込まれたのか
Ken Thompson は、理論を実用的なテキスト ツールに結び付けました。彼の 1968 Communications of ACM 論文では、テキストを検索するために正規表現をマシン コードにコンパイルする方法について説明しており、彼の以前のエディターの仕事は、パターン マッチングを Unix 系譜内に配置するのに役立ちました。 `ed` エディターは、一致する行を選択して変換するコマンドで正規表現を使用しました。
`grep` という名前は、一般に `g/re/p` としてレンダリングされる `ed` コマンドに由来しています。正規表現に一致する行をグローバルに選択して出力します。初期の grep は今日の GNU オプションのコレクションではなく、その後の基本 POSIX 形式と拡張 POSIX 形式は異なります。この永続的な変化は実用的でした。小さな記号言語がテキストを検索するための日常的なインターフェイスになりました。
Perl および PCRE — 貪欲でない量指定子、ルックアラウンド、および現在ほとんどのツールがコピーする構文を追加した拡張機能
Perl は、より豊富なパターン言語を汎用プログラミングの中心にしました。プログラマは、そのバージョン全体にわたって、非常に可視的な 1 つのエコシステム内でキャプチャ グループ、後方参照、アサーション、遅延量指定子、およびパターン修飾子に遭遇しました。 Perl 5 ドキュメントには、古い Unix 形式にはない多くの機能とともに、最小限の一致のための `*?` や肯定的な先読みのための `(?=...)` などの構造が記録されています。
Perl があらゆる拡張機能を発明したと考えるよりも、Perl がこのスタイルを普及させたと言った方が安全です。 PCRE は意図的に Perl 互換の構文を提供しましたが、他のエンジンは選択されたアイデアを採用し、他のエンジンは拒否しました。句読点を共有すると、さまざまなセマンティクス、Unicode の動作、またはパフォーマンスが隠蔽される場合があります。したがって、「Perl に似た」とは広範な影響を表すものであり、Perl パターンの移植性を保証するものではありません。
Perl は、より大規模で実用的なパターン言語を普及させました。後のエンジンは選択的に借用されました
JavaScript は、ブラウザーや他の ECMAScript 環境で実行されるプログラム用に、独自の `RegExp` オブジェクトと `/pattern/gi` などのリテラル構文を標準化しました。そのフレーバーには、キャプチャーグループと非キャプチャーグループ、後方参照、先読み、遅延量指定子、文字クラスが含まれます。後のエディションでは、ES2018 仕様に名前付きキャプチャ グループと後読みアサーションが追加されました。
JavaScript は、区切り文字が異なる PCRE や Python ではありません。機能が利用できるかどうかは、エンジンによって実装されている ECMAScript のエディションによって異なり、フラグは装飾ではなく動作の一部です。 MDN の正規表現ガイドは、ブラウザ構文に関する実用的なリファレンスですが、有効な JavaScript の例でも、特定のインターフェイスが公開していないフラグに依存している場合があります。
ES2018 では JavaScript に名前付きグループと後読みが追加されましたが、エンジンとフラグは依然として異なります
ブラウザは、通常のテキスト処理に近い JavaScript 正規表現エンジンを搭載しています。ページは、テキストを特殊な正規表現サービスに送信せずに、パターンをコンパイルし、一致をカウントし、それを `String.prototype.replace` に渡すことができます。この可用性により、ブラウザ側の検索と置換インターフェイスが可能になりますが、より広範なプライバシーの主張のために周囲のページを個別に検査する必要があります。
ToolAcre の実装は、`compilePattern` 内の `new RegExp` を呼び出し、コンパイルの失敗をキャッチし、スローする代わりにエラーを返します。 `findReplace` は、標準の置換操作を適用する前に一致をカウントします。その結果、キャプチャ参照などの JavaScript 置換トークンはホスト文字列 API に従います。正規表現構文と置換構文は関連していますが、別個の言語です。
これでカバーされないもの — 基本を超えた形式言語理論とエンジンのパフォーマンス内部
この短い歴史は、実用的なエンジンと有限オートマトンの間の同等性を証明したり、正規表現の実行アルゴリズムを調査したり、実装を速度でランク付けしたりするものではありません。バックトラッキング、線形時間技術および病理学的パターンは、別個に扱う必要があります。 ToolAcre ガードは構文エラーを検出しますが、過剰なバックトラッキングを実行してブラウザのメイン スレッドを停止させる有効な式は検出しません。
また、タイムラインはすべてのメタキャラクターを 1 人の発明者に割り当てるわけでもありません。ソフトウェア機能は、1 回のクリーンな引き継ぎではなく、論文、エディター、言語リリース、互換性のある再実装を通じて提供されることがよくあります。ソースは特定のマイルストーンをサポートしています。これらは、ある製品が最新の正規表現を大規模に作成したとか、後のフレーバーが同じ動作を継承したという単純な話を正当化するものではありません。
要点 — Text Toolkit の正規表現モードは JavaScript フレーバーであるため、ブラウザーのドキュメントのパターンは記述どおりに機能します
実際の継承は ToolAcre で確認できます。正規表現をオンにすると、検索テキストがブラウザーの JavaScript エンジンによってコンパイルされます。 Regex をオフのままにすると、メタ文字がエスケープされ、リテラル検索になります。単語全体が ASCII スタイルの `` 境界で式をラップしますが、大文字と小文字の区別は、`i` フラグが常に存在するグローバル `g` フラグを伴うかどうかを制御します。
この最後の詳細は、ブラウザーのドキュメント パターンが書かれたとおりに機能するというアウトラインの大まかな約束を修正します。 ToolAcre は複数行、ドットオール、スティッキー、または Unicode フラグを公開しないため、`m`、`s`、`y`、`u`、または `v` を必要とする例は適応する必要があり、一部はそこで再現できません。このツールを使用して、サポートされている JavaScript パターンをテストし、置換カウントを読み取り、調整する前に元に戻します。