Hacker NewsがNikita Popovの正規表現エッセイを再浮上させ、重要な分断を再び開いた
Hacker Newsが14年前のNikita Popovによるエッセイを再び取り上げ、プログラミング上の略称によってしばしば隠される対立を再燃させた。この記事は、現代のregexエンジンが形式的な正規言語をはるかに超える言語を認識できると論じている。Hacker Newsでの反応は、その追加的な表現力に伴う代償に焦点を当てた。
Popovは、Stack OverflowでPHP関連の質問に頻繁に回答していた2012年6月15日にこのエッセイを公開した。対象となったのはよく知られた禁則だった。HTMLは正規ではないため、正規表現では扱えないというものだ。
この規則は今も有用だが、Popovはその理論的な説明が誤解を招きうる理由を示した。PCREパターンは、数学で正規表現と呼ばれる対象に限定されない。再帰、後方参照、アサーション、条件分岐、サブルーチン呼び出しにより、一部のエンジンははるかに広い範囲を扱える。
したがって、この再燃した議論は、Popovが巧妙なパターンを見つけたかどうかではない。開発者がregexという言葉で何を指すのか、実装上の選択を経てもどの保証が維持されるのか、そして認識がいつパースの代替として不適切になるのかが争点である。
Hacker Newsが2012年のregex論争を再燃させた理由
日常的なソフトウェア用語において、その中心的な区別がいまだ解消されていないため、このエッセイは再び注目を集めた。
Popovの2012年のエッセイは、開発者が日常的に混同する二つの意味を分けるところから始まる。形式的な正規表現は正規言語を記述する。一方、実運用のregexエンジンは、その形式的なクラスを超える追加演算子を実装していることが多い。
正規言語は有限状態で認識できる。つまり、マッチャーは入力の深さに応じて無限に伸びるスタックを必要としない。一般的な例には、識別子、単純な数値形式、固定的なトークンパターン、多くの検索フィルターがある。
Perl-Compatible Regular Expressionsの略であるPCREは、この構図を変える構文を追加する。サブパターンは自分自身を呼び出せるため、マッチャーは入れ子構造をたどれる。後方参照は、後続のテキストが先にキャプチャしたテキストと等しいことを要求できる。
これらの機能により、「regular expression」という用語は歴史的には馴染み深い一方で、数学的には不正確になる。開発者は通常、regexをパターン言語の総称として用いる。形式言語の専門家は、有限オートマトンと等価な表現にこの用語を限定する場合がある。
この区別が8月の議論を動かした。一方では、このエッセイが真の正規表現とPCRE固有のパターンマッチングを混同する危険があると論じられた。他方では、Popovはより広いプログラマー的な意味を検討する前に、この区別を明示しているとの反論があった。
どちらの読み方も重要な点を捉えている。エッセイは対象範囲を慎重に述べているが、その挑発的なタイトルは、異なるエンジンを一つの技術として扱うよう読者を誘う。再帰を使うPCREパターンは、JavaScript、RE2、Rust、POSIX、あるいは別の実装で何が受理されるかについて、開発者にほとんど教えてくれない。
議論は理論を超えて広がった。コメント投稿者は、可読性、エンジン差、メモリ使用量、バックトラッキング、サービス拒否への露出、AI生成の式を取り上げた。こうした懸念こそ、2012年のエッセイがいまなお現代的に感じられる理由である。
現代のコードアシスタントは、保守担当者が実行の仕組みを理解していることを保証せずに、密度の高いパターンを生成できる。対象エンジンでサポートされていない構文を提案することもある。regex生成へのアクセスが容易になっても、適切なマッチャーを選ぶ必要はなくならない。
元の記事が今も価値を持つのは、単純化されすぎた限界に異議を唱えるからだ。再び始まった議論が重要なのは、欠けていた運用上の問いを提示するからである。その追加的な表現力には、どのようなコストがあるのか。
PCRE Regexの力は正規言語の外側にある機能から生まれる
この記事の中心的な結論はPCRE系エンジンに属するものであり、regexを名乗るすべてのシステムに当てはまるわけではない。
Popovは、形式言語を生成するのに必要な文法に応じて分類するチョムスキー階層から始める。正規言語は文脈自由言語の内部にあり、文脈自由言語は文脈依存言語の内部にある。
伝統的な正規表現は最小のグループに属する。連結、選択、文字クラス、繰り返しによって、あらゆる正規言語を記述できる。しかし、それらだけでは、無制限の入れ子深さを記憶したり、任意のキャプチャ済み部分文字列を複製したりはできない。
PCREの再帰は最初の制約を変える。Popovは再帰グループを用い、a文字が同数並んだ後にb文字が続く文字列を認識する。この言語は文脈自由だが正規ではない。
その仕組みは簡潔だ。パターンは一つのaを消費し、周囲のグループを再帰的に呼び出し、その後に一つのbを消費する。より深い呼び出しごとに、入れ子になったマッチの周囲へ対応する一組が追加される。
現行のPCRE2ドキュメントでも、再帰パターン構文が説明されている。均衡の取れた括弧が直接的な例として示されている。グループは開き括弧、通常の内部文字または別のグループ呼び出し、そして閉じ括弧にマッチする。
これは意味のある能力である。従来の有限状態マッチングが対応できるのは、あらかじめ定められた入れ子の上限までに限られる。再帰的マッチングは、エンジンのリソース制限と動作に従いつつ、入力の入れ子深さを追跡できる。
続いてPopovは、文脈自由文法の規則を名前付きPCREサブパターンへ写像する。(?(DEFINE)...)構文は、入力を消費せずに定義を保持する。名前付きサブルーチン呼び出しにより、ある規則から別の規則を呼び出せる。
彼の拡張例では、RFC 5322のメール文法の一部をこの表記へ変換している。結果は、拡張モードで空白とコメントを有効にした、regexリテラル内に埋め込まれた文法のように見える。
これは、互換性のない左再帰を変換すれば、PCRE系の再帰が文脈自由言語を認識できるというエッセイの印象的な主張を支えている。すべての短いregexがすべての文脈自由言語を処理できる、という意味ではない。
また、これによってマッチャーが完全なパーサーになるわけでもない。認識は、入力がある言語に属するかどうかを答える。パースは、入力が文法にどのように適合するかを記録した構造化出力を生成する。
この違いはHTMLで決定的になる。マッチャーは、整形式のフラグメントが文法に適合するかを判断できるかもしれない。しかしアプリケーションが通常必要とするのは、要素、属性、テキストノード、エラー回復、エンティティ処理、文書走査である。
実際のHTMLにはもう一つの複雑さがある。ブラウザーは、不正な文書を定められた回復動作に従って処理する。理想化された整形式言語にマッチしても、その動作は再現されない。
Popovは両方の制約を認めている。一般的なHTML処理にはDOMライブラリを推奨し、regexは限定された状況に留めている。したがって、有名な主張は多くの語り直しが示すよりも限定的である。
後方参照は、古典的な正規表現をさらに一歩超える。後方参照は、グループが以前にキャプチャした正確なテキストにマッチする。たとえばパターン^(.+)\1$は、同一の二つの半分から成る文字列を認識する。
有限オートマトンは一般に、任意の長さの前半を記憶して後半と比較することはできない。エンジンはキャプチャ内容を保持し、分割位置の候補を探索する必要がある。この追加状態は、表現可能な範囲と計算上の振る舞いの両方を変える。
Popovはさらに、再帰と先読み・後読みアサーションを組み合わせ、少なくとも一部の文脈依存言語を認識する。先読み・後読みは、その位置で文字を消費せずに周囲のテキストを検査する。
彼は、PCREがすべての文脈依存言語を認識できるとは主張しない。この抑制は重要である。意図的に広いタイトルを用いながらも、エッセイは実証された構成と未解決の問いを区別している。
形式的Regexとバックトラッキングエンジンは異なる約束を最適化する
主な対立は理論と実践の間にあるのではない。予測可能な実行と、より大きなパターン言語の間にある。
正規言語の構文に限定されたエンジンは、オートマトンによってパターンを実行できる。一つの経路に固定して失敗時に戻るのではなく、各入力文字の後に到達可能な状態の集合を追跡する。
バックトラッキングエンジンは、より深さ優先探索に近い形で選択肢をたどる。一つの分岐を選んで先へ進み、後続のマッチが失敗すると以前の判断へ戻る。この手法は、直感的なセマンティクスでキャプチャや高度な動作を支える。
しかし、同じ作業を繰り返す可能性もある。曖昧な入れ子の量指定子は、同じ入力を分割する多数の方法を生み出しうる。ほぼマッチする接尾辞は、失敗を報告する前にエンジンへそれらの組み合わせを探索させることがある。
このリスクは、パターンが再帰や後方参照を使う場合だけに現れるわけではない。バックトラッキング実装は、形式的には正規であるパターンでも過剰な時間を要することがある。構文のクラスと実行戦略は関連しているが、同一ではない。
この点は、オンライン上の議論における一つの過度な単純化を正した。非正規の拡張を削除しても、すべての実装が自動的に線形になるわけではない。エンジンは、指数的な経路探索を避けるアルゴリズムも採用する必要がある。
Googleの線形時間エンジンは意図的なトレードオフを行う。RE2は入力長に対して漸近的に線形のマッチ時間を保証し、設定可能なメモリ予算内で動作する。
RE2は、同じ保証を維持したまま後方参照や先読み・後読みアサーションをサポートする方法を設計者が把握していないため、これらの構文を除外している。再帰的なサブルーチン呼び出しも除外している。
その結果、PCRE2より表現力は低いが、信頼できないパターンを受け入れるサービスや、信頼できないテキストを処理するサービスにとっては、より予測可能になる。この違いはアーキテクチャ上の判断であり、一方のエンジンが他方を普遍的に置き換える証拠ではない。
PCRE2は、マッチ制限、深さ制限、代替実行経路、慎重なパターン構築など、実運用システムで利用できる制御機構を提供する。これらの制御は露出を減らすが、意図的な設定とテストを必要とする。
実務上の選択は、誰がパターンと入力を制御するかに左右される。境界が定められたレコードに対する開発者管理の式と、共有サービス内で大きなペイロードを走査するユーザー提供の式では、リスクが異なる。
必要な出力も重要である。検索コマンドに必要なのは、真偽値のマッチ結果か数個のキャプチャだけかもしれない。コンパイラー、文書処理系、設定リーダーには、構造化された結果と有用な失敗位置が必要になる。
これが、「regexでマッチできる」というだけではエンジニアリング上の判断がほとんど決着しない理由である。能力は可能性を示す。しかし、保守性、リソース境界、診断品質、互換性を示すものではない。
この枠組みで見ると、Hacker News上の不一致はより明瞭になる。Popovは特定のエンジンが何を表現できるかを説明する。批判者は、その表現力に依存した場合にアプリケーションがどの保証を失うのかを問う。
これらの立場は対立するものではない。同じシステムの異なる層を扱っている。重要な誤りは、ある層の主張を無条件に別の層へ持ち込むことだ。
HTMLの問題は認識における実務上の限界を示す
言語にマッチすることは、信頼できる文書表現を構築することと同じ仕事ではない。
regexベースのHTML処理に対する一般的な警告は、いくつかの論点を組み合わせている。HTMLは入れ子構造であり、実際の文書には不正なものがあり、埋め込み言語がトークン境界を複雑にし、アプリケーションは通常構造化出力を必要とする。
このうち、形式言語の表現力に直接関わるのは最初の論点だけである。PCREの再帰は入れ子に対応できる。しかし、その事実だけで残る要件を解決できるわけではない。
アプリケーションがリンクを抽出する場面を考えてみよう。単純な正規表現でも、単一のテンプレートが生成する管理されたマークアップなら機能するかもしれない。しかし、引用符で囲まれた属性値の中に > が現れたり、スクリプトのテキストがタグのように見えたりすると、失敗する可能性がある。
コメント、文字参照、名前空間、省略可能なタグ、そしてブラウザのエラー回復規則によって、さらに多くのケースが加わる。条件を追加するたびにパターンは膨らむ一方で、その出力は DOM よりも構造化されないままだ。
だからといって、すべての HTML 正規表現が無責任というわけではない。入力契約が厳格で、失敗時の影響が小さい場合には、限定的な表現が適切なこともある。
対象範囲を明示しなければならない。「自社で生成したフラグメントから既知のマーカーを見つける」は、範囲の限定されたテキスト処理だ。「ブラウザのように任意の Web ページを解釈する」は、文書処理の仕事である。
パーサーは各構文要素に名前付きの役割を与える。ソース上の位置を関連付け、予期しないトークンを報告し、エラー後に回復し、後続の変換に利用できるツリーを公開できる。
大規模な正規表現では、こうした区別がグループと制御フローに圧縮されがちだ。名前付きサブパターンや拡張フォーマットは役立つものの、エンジンが返すのはネイティブな構文木ではなく一致結果である。
要件が変わると、保守性の差は拡大する。パーサーで別の文法規則をサポートする場合、通常はルールを追加または修正すればよい。密結合した正規表現では、別の箇所のバックトラッキングやキャプチャ動作まで変えてしまう可能性がある。
したがってテストは、代表的な有効入力例だけでは不十分だ。チームには、無効な入力、ほぼ一致する入力、大規模入力、入れ子の入力、Unicode のケース、そして高コストな経路を引き起こすよう設計された敵対的文字列が必要になる。
ここでドキュメントは、装飾ではなく運用上の役割を果たす。複雑な表現には、対象エンジン、フラグ、受け入れる入力契約、期待するキャプチャ、サイズ制限、そしてパーサーを使わない理由を記載すべきだ。
技術的な意思決定を残すチームは、こうした制約を検索可能な実装記録のそばに置ける。共有されたエンジニアリング・ナレッジベースは、将来の保守担当者が簡潔なマッチングコードの背後にある意図を取り戻す助けとなる。
重要な判断は、正規表現とパーサーを対立するアイデンティティとして選ぶことではない。必要なのが認識、抽出、変換、回復、完全な解釈のどれなのか、という点である。
正規表現は、トークン化、制約のあるルール下での検証、検索、ログのフィルタリング、小規模な抽出に引き続き優れている。文法構造がアプリケーションの作業データとなる場合は、パーサーのほうが望ましい。
Popov 自身の結論も、この境界に沿っている。彼は絶対的な理論上の禁止を退けつつ、汎用的な HTML 処理には DOM ライブラリを使うべきだという実務上の推奨を維持している。
このニュアンスはオンラインではしばしば失われる。「正規表現では HTML をパースできない」という言葉が残り続けるのは、よくある失敗を防ぐからだ。「一部の正規表現エンジンは文脈自由構造を認識できる」も、基盤となる能力が存在する以上、依然として真である。
成熟したエンジニアリング上の原則は、両方の主張を受け入れられる。有用なデフォルトを定理と混同してはならず、理論上の構成を本番設計と混同してもならない。
正規表現をめぐる議論がなお過小評価していること
表現力の拡張は、成功したテストスイートだけでは見えないセキュリティと保守の責務を生む。
正規表現によるサービス拒否、すなわち ReDoS は、細工された入力に対してマッチャーが選択肢の探索に過剰な時間を費やすときに発生する。攻撃者は大量のトラフィックを送らずとも、処理能力を消費させられる。
ReDoS のガイダンスでは、曖昧なパターンが敵対的な文字列に遭遇した際、エンジンの実行時間が極端に長くなることが説明されている。危険は、マッチ失敗の直前によく現れる。
検証器は、最初の分岐が成功する通常入力なら高速に処理できるかもしれない。しかし攻撃者は、多くの経路に適合する長い接頭辞の後に、すべての経路を無効にする一文字を与えられる。
するとエンジンは、以前の選択を再訪しなければならない。入れ子の反復、重複する選択肢、任意要素は、探索空間を増大させうる。簡潔なパターンでも、コードレビューではこの挙動を隠し得る。
後方参照は、さらに別の複雑性をもたらす。その表現力の限界に関する研究では、多くの主要エンジンがサポートする実質的な拡張として扱われている。その挙動は、通常の有限状態マッチングには還元できない。
Popov のエッセイは、後方参照によるマッチングが NP 完全のケースを導入すると指摘している。これは一般問題についての記述であり、個々のパターンが遅く実行されるという予測ではない。
キャプチャと後方参照を含む多くの表現は、通常入力ではすぐに完了する。複雑性の結果が警告するのは、計算量理論の大きな前提が変わらない限り、すべてのケースをカバーする効率的な一般解は存在しないということだ。
再帰は、別のリソース上の懸念をもたらす。深く入れ子になった入力に従うパターンは、エンジン管理の深さ、またはそれに相当する状態を消費する。実装ごとに制限があり、再帰とバックトラッキングの相互作用も異なる。
エンジンのバージョンも重要だ。PCRE2 は、特定の状況で Perl により近づくよう、時間をかけて再帰の意味論を変更してきた。あるバージョンでテストされたパターンでも、移行後には異なる動作をする可能性がある。
したがって、Perl 互換と説明されるエンジン同士であっても移植性は限定的だ。構文サポート、Unicode の規則、キャプチャ値、マッチ順序、再帰の意味論は異なり得る。
AI 生成の正規表現は、かつて複雑さを抑えていた摩擦を生成によって減らすため、リスクを高める。開発者は文法向けの単一表現を要求し、数秒で構文上もっともらしいものを受け取れる。
生成されたパターンは、誤った方言を対象にしているかもしれない。プロンプト内の例には通っても、不正な入力を見逃したり、過剰なリソースを消費したり、予期しない意味論のキャプチャを返したりする可能性がある。
レビュー担当者は、生成された正規表現を生成コードとして扱うべきだ。対象エンジンを特定し、重要でないとは言えない各構文要素を理解し、敵対的テストを実行し、入力と実行の制限を強制する必要がある。
ここで可読性は見た目の問題ではない。読めない制御フローは、保守担当者が重複する選択肢を特定したり、小さな編集が破滅的バックトラッキングを生むことに気付いたりするのを妨げる。
拡張モードは、それをサポートするエンジンで空白とコメントを利用可能にする。名前付きグループは、変動しやすい数値インデックスへの依存を減らす。より小さく合成されたパターンは、責務を明確にできる。
こうした実践は役立つが、合成はエンジンの構文に従わなければならない。一部のホスト言語は、正規表現コンパイラが見る前に文字列を補間するため、エスケープと注入の可能性という別の層が生まれる。
信頼できない断片を、エンジンに適したエスケープなしにパターンへ挿入してはならない。信頼できないユーザーに、共有サービス内のバックトラッキング型マッチャーへの無制限のアクセスを与えてはならない。
懐疑的な結論は、「高度な正規表現を決して使うな」よりも限定的だ。それは、高度な構文要素の一つひとつがシステムの予測可能性という予算を一部消費する、ということである。
開発者は、見返りとして何を得るのかを説明できるべきだ。再帰は、範囲が限定された入れ子構造を簡潔に認識できるようにする。後方参照は、本来なら手続き型コードを必要とする等値制約を強制できる。
利点が小さなパーサーを避けることだけなら、そのトレードオフは正当化しにくくなる。パーサーは、多くの場合、より良いエラー、より明確な進化、そして下流コードが直接利用できる出力を提供する。
この教訓が定着するかを決める三つの兆候
持続的な成果は、エンジン選択、生成コードのレビュー、そしてチームが例だけでなく失敗時の挙動をテストするかどうかに左右される。
第一の兆候は、より広範で明示的なエンジン選択である。開発者は正規表現を単一の移植可能な言語として扱うのをやめ、パターンの対象が PCRE2、RE2、JavaScript、Java、.NET、Rust、あるいは別の実装のどれかを文書化すべきだ。
ライブラリとプラットフォームが実行保証を可視化すれば、Hacker News での議論は解決しやすくなる。開発者は、過剰な意味を負ったラベルについて論じるのではなく、定義されたエンジンについて議論できる。
第二の兆候は、コーディング支援ツールが正規表現の要求をどう扱うかだ。有用なシステムは、複雑な表現を生成する前に、対象の方言、入力境界、信頼できるデータに関する前提、必要なキャプチャを尋ねるべきである。
また、サポートされない構文要素を説明し、要求される出力が構造化されている場合はパーサーを提案すべきだ。こうした確認なしに支援ツールが密度の高いパターンを生成し続けるなら、保守性とセキュリティの失敗は増加する。
第三の兆候は、敵対的テストが日常的に行われることだ。チームは、成功するマッチ、遅い失敗、長い反復入力、深い入れ子、Unicode 境界、曖昧性を最大化するよう形作られた入力を測定すべきである。
友好的な十個の例に通ったパターンが確立した正しさは、その例に対するものだけだ。許容可能な最悪時挙動や、本番環境の制限との互換性までは確立していない。
これらの兆候は、Popov のより広い教訓を強化しながら、その適用範囲を狭める。現代のパターンエンジンは、その名称が示唆する形式的限界を超えられる。この事実は理解されるべきであり、普遍的な設計上の推奨として使われるべきではない。
復活したエッセイは、両陣営に有益な修正も示している。形式理論が重要なのは、どの保証が利用可能かを説明するからだ。実装の詳細が重要なのは、実際に配備されるエンジンのすべてがそれらの保証を維持しているわけではないからである。
Hacker News の議論を追う開発者にとって、次の行動は具体的だ。本番環境で最も複雑なパターンの背後にあるエンジンを特定し、その入力契約を文書化し、最も遅い失敗ケースをテストする。そのうえで、アプリケーションに必要なのが認識なのか、構造化されたパースなのかを問うべきだ。
パターンが明確で、範囲が限定され、測定可能なままであれば、維持すればよい。その正しさが文書化されていない方言固有の挙動や脆弱なバックトラッキングに依存するなら、隠れた文法を明示的なパーサーへ置き換えるべきである。
