1

今日、ソース コードの特定のセグメントをすばやく見つけようとして、テキスト エディター (Sublime) でいくつかの正規表現を書いていました。たとえば、jQuery セレクターを探していました。

$("div[class='should_be_using_dot_notation']");

$(escapeJQSelector("[name='crazy{"+getName(object)+"}']"));

私のお気に入りのパワーツール (正規表現) の 1 つがこの種の検索を行うのに役立つと期待するのは不合理だとは思いませんが、2 つのレベルがあるため、コードの 2 番目のビットを解析するために必要な式がいくぶん複雑になることは明らかです。ネストされた括弧の。

私は理論に十分精通しており、この種の構文解析はまさに文脈自由文法パーサーの目的であり、正規表現を構築することはより多くのメモリと時間を消費する可能性が高いことを知っています (おそらく O( ではなく指数関数で) n^3) ファッション)。しかし、私のテキスト エディターや Web ブラウザーでそのような機能がすぐに利用できるようになるとは思っていません。

これから（これは、ネストされた括弧のゼロレベルに一致し、単純な空のものには一致しません）：

\$\([^)(]+?\)

私が思いついた1レベルのネストされた括弧は次のようになります。

\$\(((\([^)(]*\))|[^)(])+?\)

それを分解する：

\$\(                   begin text
    (                  groups the contents of the $() call
        (\(            groups a level 1 nested pair of parens
            [^)(]*     only accept a valid pair of parens (it shall contain anything but parens)
        \))            close level 1 nesting
        |              contents also can be
        [^)(]          anything else that also is not made of parens
    )+?                not sure if this should be plus or star or if can be greedy (the contents are made up of either a level 1 paren group or any other character)
\)                     end

これはうまくいきました！しかし、もう 1 レベルのネスティングが必要です。

エディターで 2 レベルのネストされた式を入力し始めました*。

それで諦めて regextester.com に移動したところ、あっという間にブラウザのタブ全体がフリーズしてしまいました。

私の質問は 2 つあります。

  1. 任意レベルの正規表現を構築する良い方法は何ですか? これは、人間のパターン認識だけが達成できるものなのでしょうか? 最初の 2 つのレベルの類似性に基づいて、正規表現を 2 つのレベルのネストに一致させる方法について、かなりの直感を得ることができるように思えます。これは、いくつかの「ガイドライン」に要約できると思います。

  2. 非巨大な正規表現の正規表現解析がブロックまたはフリーズするのはなぜですか?

O(n) 線形時間は n に対するものであり、n は正規表現を実行する入力の長さ (つまり、テスト文字列) であることを理解しています。しかし、新しい文字を入力するたびに正規表現を再コンパイルするシステムでは、何が原因でフリーズするのでしょうか? これは必然的に正規表現コードのバグですか? エディターから別の正規表現テスターに​​移行した理由の 1 つは、ソース コードの約 2000 行すべてに対して (キーを押すたびに) 実行する必要がなくなったということでしたが、環境全体がロックアップするのを防ぐことはできませんでした。私の正規表現を編集しました。正規表現で変更された各文字が、その式を表す DFA の単純な変換に対応する場合は、意味があります。しかし、そうではないようです。

その間、次の上位のネストされた正規表現を手動で作成し、テストの準備ができたらフィールドにコピーします...

4

2 に答える 2

1

()ネストの各レベルで 1 つのペアのみを使用して、任意の数のネストされた に一致させるには、次を使用して、必要な2ネストの数に変更します。()

/(?:\([^)(]*){2}(?:[^)(]*\)){2}/

過剰なバックトラックを避けるために、ネストされた量指定子の使用を避ける必要があります。特に、内側の代替の両側のサブパターンが同じ部分文字列に一致する可能性がある場合はそうです。

于 2013-04-17T19:55:00.927 に答える
1

うーん。わかりましたので、誰も答えを書きたがりませんが、基本的にここでの答えは

バックトラッキング

特定の貪欲でないことを行うと、指数関数的なランタイムが発生する可能性があります。

私の質問の最初の部分への答え：

2 ネストされた式は次のとおりです。

\$\(((\(((\([^)(]*\))|[^)(])*\))|[^)(])*\)

次のネストされた式を作成するための変換は、のインスタンスを[^)(]*メタ((\([^)(]*\))|[^)(])*正規表現として置き換えることです (replace-with セクションはエスケープする必要はありません)。

s/\[^\)\(\]\*/((\([^)(]*\))|[^)(])*/

これは概念的には簡単です。N レベルのネストに一致する式で、それ以上のネストを禁止する部分を、もう 1 レベルのネストに一致するものに置き換えると、N+1 レベルのネストの式が得られます。

于 2013-04-17T19:44:08.780 に答える