10

私は (C# で) 古典的な C によく似たスクリプト言語を処理する単純なパーサーを作成しています。

私が持っているスクリプト ファイルの 1 つで、/* ブロック コメント */ を認識するために使用している正規表現がある種の無限ループに入り、何年にもわたって 100% の CPU を使用しています。

私が使用している正規表現は次のとおりです。

/\*([^*]|[\r\n]|(\*+([^*/]|[\r\n])))*\*+/

これがロックされる理由について何か提案はありますか?

または、代わりに使用できる別の正規表現は何ですか?

詳しくは：

  • .NET 3.5 を対象とする C# 3.0 での作業。
  • Regex.Match(string,int) メソッドを使用して、文字列の特定のインデックスで照合を開始しています。
  • プログラムを 1 時間以上実行したままにしましたが、一致は完了しません。
  • Regex コンストラクターに渡されるオプションはRegexOptions.Multiline、および RegexOptions.IgnorePatternWhitespace; です。
  • 正規表現は、453 個のテスト ファイルのうち 452 個で正しく機能します。
4

5 に答える 5

18

私があなたの正規表現で見るいくつかの問題：

|[\r\n]正規表現のシーケンスは必要ありません。のような否定文字クラスは、行区切り記号を含む、を[^*]除くすべてに一致します。それらと一致しない*のは（ドット）メタ文字だけです。.

コメントの中に入ると、探す必要のある文字はアスタリスクだけです。それらのいずれかが表示されない限り、必要な数の文字をむさぼり食うことができます。[^*]つまり、代わりに使用できる場合に使用しても意味がありません[^*]+。実際、それをアトミックグループに入れる(?>[^*]+)方がよいでしょう---一度それらを一致させたら、それらのアスタリスク以外のいずれかをあきらめる理由は決してないからです。

無関係なジャンクを除外すると、最も外側の括弧内の最後の選択肢はです\*+[^*/]。これは、「1つ以上のアスタリスクの後に、アスタリスクまたはスラッシュではない文字が続く」ことを意味します。これは、コメントの最後にあるアスタリスクと常に一致し、次の文字がスラッシュであるため、常にそれをあきらめる必要があります。実際、最後のスラッシュに至るまでに20個のアスタリスクがある場合、正規表現のその部分はそれらすべてに一致し、1つずつすべてを放棄します。次に、最後の部分\*+/---キープのためにそれらを一致させます。

最大のパフォーマンスを得るには、次の正規表現を使用します。

/\*(?>(?:(?>[^*]+)|\*(?!/))*)\*/

これは整形式のコメントと非常に迅速に一致しますが、さらに重要なことに、有効なコメントではないものと一致し始めた場合、可能な限り迅速に失敗します。

Davidの好意により、ネストされたコメントを任意のレベルのネストと一致させるバージョンを次に示します。

(?s)/\*(?>/\*(?<LEVEL>)|\*/(?<-LEVEL>)|(?!/\*|\*/).)+(?(LEVEL)(?!))\*/

.NETのバランシンググループを使用するため、他のフレーバーでは機能しません。完全を期すために、Perl、PCRE、およびOniguruma /Onigmoでサポートされている再帰グループ構文を使用する別のバージョン（RegexBuddyのライブラリから）を次に示します。

/\*(?>[^*/]+|\*[^/]|/[^*])*(?>(?R)(?>[^*/]+|\*[^/]|/[^*])*)*\*/
于 2009-01-20T22:06:10.847 に答える
15

ダメダメダメ！正規表現をマスターする(第3版) 読んだ人いないの!? この中で、Jeffrey Friedl はこの正確な問題を調べ、それを例として使用して (ページ 272-276)、彼の「ループ展開」テクニックを説明しています。ほとんどの正規表現エンジンに対する彼のソリューションは次のようになります。

/\*[^*]*\*+(?:[^*/][^*]*\*+)*/

ただし、正規表現エンジンが (Perl のように) 遅延量指定子を処理するように最適化されている場合、最も効率的な式は (上で提案したように) はるかに単純になります。

/\*.*?\*/

(もちろん、同等の 's' の「すべてに一致するドット」修飾子が適用されます。) 私は .NET を使用していないので、そのエンジンに対してどちらのバージョンが速いかはわかりません。

于 2010-10-15T20:05:54.293 に答える
2

複数行ではなく単一行オプションを試してみると、\r\n について心配する必要はありません。これを有効にすると、複数行にまたがるコメントを含む簡単なテストで次のことが機能しました。

/\*.*?\*/
于 2009-01-20T20:14:38.700 に答える
1

現時点ではこれを使用しています

\/\*[\s\S]*?\*\/
于 2014-05-10T23:01:31.140 に答える
1

あなたの表現は複雑すぎると思います。大きな文字列に適用すると、多くの代替手段が多くのバックトラックを意味します。これがパフォーマンス ヒットの原因だと思います。

基本的な仮定が から"/*"最初"*/"に遭遇するまでのすべてに一致することである場合、それを行う 1 つの方法は次のとおりです (通常、正規表現はネストされた構造には適していないため、ブロック コメントのネストは機能しません)。

/\*(.(?!\*/))*.?\*/             // run this in single line (dotall) mode

本質的にこれは次の"/*"ように言います:"*/""*/"

または、より単純なものを使用できます。

/\*.*?\*/                       // run this in single line (dotall) mode

このような非貪欲なマッチングは、エッジ ケースでうまくいかない可能性があります。現在、この式が失敗する可能性があるケースは考えられませんが、完全にはわかりません。

于 2009-01-20T20:15:33.143 に答える