2つの正規表現の差異と共通部分を計算

 (phylactery.org)
2 ポイント 投稿者 GN⁺ 2023-09-12 | 1件のコメント | WhatsAppで共有
  • 正規表現を文字列集合として比較したいとき、antimirov は 2 つの式 α と β の包含関係と同値性、共通部分・差集合を 1 画面で計算してくれる
  • 結果エリアでは補集合と関係式もあわせて表示され、~α, α < β, α = β, α & β, α ^ β, α - β のような演算を確認できる
  • 別途文字列 s を入力すると、s ∈ α, s ∈ β により各正規表現にマッチするかをすぐに検証できる
  • 構文は ., 連接, 選択 |, 反復 *・+・?・{n}・{m,n}, 文字クラス, 否定文字クラス, エスケープ, UTF-16 Unicode エスケープをサポートする
  • アンカー、ゼロ幅アサーション、後方参照、サブグループ抽出、検索・部分一致、大文字小文字無視のような動作変更機能はサポートしない

正規表現の比較と集合演算

  • 入力エリアは 2 つの正規表現 α と β を受け取る
  • 出力では 2 つの正規表現の補集合と関係・集合演算をあわせて表示する
    • ~α, ~β: 各正規表現の補集合
    • α < β, α = β, α > β: 2 つの正規表現の包含関係と同値性
    • α & β: 共通部分
    • α ^ β: 対称差
    • α - β: 差集合
  • 文字列 s を入力すると、s ∈ α, s ∈ β の形で各正規表現に属するかどうかを確認できる
  • 各正規表現のサイズとDFA 状態数も表示される
    • 例の画面では |α| = 1, |β| = 1
    • 例の画面では dfa(α) と dfa(β) はそれぞれ 1 状態を持つ

サポートされる正規表現構文

  • 基本演算子は単一文字、連接、選択、反復を扱う
    • .: 任意の単一文字にマッチ
    • xy: x の次に y にマッチする連接
    • x|y: x または y にマッチ
    • x*: 0 回以上の反復
    • (xyz): グループ化
    • (): 空文字列にマッチする空の正規表現
  • よく使われる反復の短縮構文もサポートする
    • x+: 1 回以上の反復で、xx* と同値
    • x?: 任意一致で、(x|) と同値
    • x{n}: x を n 回連接
    • x{m,n}: x を m 回以上 n 回以下連接
  • 文字集合とエスケープには次の形式を使える
    • [a-z0-9]: グループ内の単一文字にマッチ
    • [^a-z0-9]: グループに含まれない単一文字にマッチ
    • \\c: 特殊文字 c をエスケープ
    • \\u001a: 対応する UTF-16 文字にマッチ
    • そのほか a, b, c のような文字はそれ自身にマッチする

サポートしない機能

  • antimirov は正規表現を集合演算の対象として扱うことに重点を置いており、次の機能は除外されている
    • アンカー ^, $
      • ただし ^ と $ は引き続きエスケープが必要
    • ゼロ幅アサーション 例: (?=...), (?<=...)
    • 後方参照 例: \\1, \\2
    • サブグループ抽出
    • 検索または部分一致
    • 大文字小文字無視のように動作を変えるその他のフラグ
  • 詳細は non/antimirov で確認できる

関連記事

1件のコメント

 
GN⁺ 2023-09-12
Hacker News のコメント

  • 正規表現が パース → NFA → DFA → 最小 DFAへ変わっていく過程を示し、最小 DFA から LLVM IR/Javascript/WebAssembly まで出力する、似たような Web デモを作ったことがある
    http://compiler.org/reason-re-nfa/src/index.html

    • ただし、NFA から明示的な DFA へ進むのが常に良い選択とは限らない
      参考までに、正規表現マッチングの代替手法として使える Brzozowski 微分も興味深いかもしれない: https://en.wikipedia.org/wiki/Brzozowski_derivative

  • このライブラリは文字列クラスの階層を作るのに使え、その結果、型付き文字列をより積極的に活用できる
    例えばメールアドレスと URL には特殊な文法があり、その値空間はすべての空でない文字列の部分集合で、空でない文字列はすべての文字列の部分集合である
    型システムが、メールアドレス文字列は空でない文字列のサブタイプだと分かっていれば、空でない文字列を要求する関数にメールアドレスを渡しても有効だと判断できる
    このライブラリは、そのような文字列型の定義と階層を検証するのに使え、階層の実装は言語によってサブクラス化、トレイト境界などさまざまになる

    • タグ付きユニオン型がある言語では、このやり方はよく使われる。Haskell 風の疑似コードではおおよそこんな感じ
      Address コンストラクタはエクスポートせず型だけをエクスポートし、fromString :: Text -> Maybe Address の中で検証して、不正なアドレスなら Nothing を返す
      妥当性はデータの中に混ぜず別経路でシグナルし、出力が必要なときは toText :: Address -> Text でラップされた値を取り出す
    • メールアドレス検証に正規表現を使わないほうがよい
      https://news.ycombinator.com/item?id=31092912
    • 晩夏の朝に、@ の左側でメールアドレスとして何が許され何が許されないのかを掘り下げることほど妙なこともない
      「有効なメールアドレス」を表現しようとする正規表現はすべて間違っている、と見る単純なヒューリスティックはかなり安全だが、楽しみは全部台無しにしてしまう
    • 「値空間」とはどういう意味なのか気になる

  • 正規表現は、かなり見事で複雑な数学理論を価値あるインターフェースに包み込んだ良い例だ
    線形代数も似たように感じる

    • 適切な体が与えられると、本当に多くの数学を線形代数に変換できるというのはいつも驚きだ
      複素平面上の Möbius 変換 w=(az+b)/(cz+d) でさえ線形代数に変えられる
    • たいていその場合、表現が真実に近づいているという意味だ
      良いインターフェースには本質的な価値があるが、結果重視の多くの人はそれをあまり認めない
    • 記憶が正しければ、Conway の https://store.doverpublications.com/0486485838.html に線形代数とのつながりが出ていた気がする。ざっと眺めただけだけど

  • この素晴らしいページは、正規表現のペア間の二項関係を計算し、DFA をグラフで示してくれる
    正規表現上で行うかなり非自明な操作を、本当に印象的に実演している

    • とても素晴らしいが、厳密に言えばもはや正規表現ではなくしてしまう機能をサポートしていないのも驚きではない
      それでも ^ と $ のアンカーは問題ないと思っていた

  • “regex filter numbers divisible by 3” を貼り付けてみたら、ページが完全に固まった: https://stackoverflow.com/q/10992279/41948
    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$
    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
    もっと短い表現があるのか気になる

    • この Web ページは、状態数の多い DFAを作る正規表現で固まる
      例えば (ab+c+)+、(abc){100}、a.*quick brown fox jumps over the lazy dog のようなものだ
    • どのみちページの説明では、アンカーはサポートしていないと書かれている

  • 文法的に有効な URL とメールアドレスの共通部分を見たかったが、下の URL 正規表現を入力するだけでもページの処理に時間がかかりすぎる
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    出典: https://stackoverflow.com/a/3809435/623763

    • (...){1,256} のような表現は非常に重く、Scala JS コードが最終的にタイムアウトするかブラウザを落としてしまう
      それを (...)+ に変えると、少なくとも私の環境では動く。(...){1,6} のような小さい表現なら大丈夫そうだ

  • 和集合と共通部分で生成される正規表現が特に簡潔ではないことに驚いたが、すぐ納得した
    例えば "y.+" と ".+z" の共通部分は "y.*z" という非常に単純な表現で書け、ページでも同値性が確認できる。しかしツールは yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz* を出力する
    こうした結果になる理由はあるのだろうが、文字数のような基準で最小の正規表現を出すのはずっと難しい可能性が高い

    • 理由の一つは、".+z" が決定性オートマトンに変換されたあと、より大きくごちゃごちゃしたものになるからだと思う

  • 以前この概念を使って、「IP RegEx filter」設定の検証ロジックを書いたことがある
    目的は、ユーザーが正規表現でIPフィルターを設定できるようにすることだった。マーケティング側はCIDRを理解しておらず、Google Analyticsのために正規表現は知っていた
    有効な正規表現をどう定義できるだろうか？「すべてのIPv4アドレス」の正規表現との共通部分が空でなく、同時に「すべてのIPv4アドレス」の正規表現と同じでもない必要があった
    フィルターが何もしないという不満はかなり防げたが、誤ったフィルター入力そのものを防ぐことはできなかった

    • もっと単純な解決策も可能だったのではないか？フィルター正規表現を検証しようとするより、サンプルIPアドレスを表示するか、ユーザーにアドレスのまとまりを入力してもらい、どのアドレスがマッチし、どのアドレスがマッチしないかを見せればよい
      誤ったフィルターの問題に対処するうえでも役立つ

  • モバイルでもっと使いやすくするには、正規表現入力フィールドの自動候補をオフにするとよさそう
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • 似たような3で割り切れる数の正規表現2つでページをテストしたところ、両端の^と$を取り除いても止まった
    Regex 1: ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))*
    Regex 2: ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))*
    最後の*の直前まではすべてパースされるが、*を付けた瞬間にページ全体が止まる
    *がなければ、桁の合計が3で割り切れる数の断片をパースする有効な検証器を作り出せた