なぜ正規表現はStackOverflowの

Question

私はScalaのLIB（RE2での作業）を使用して、上記の正規表現で一致しようとすると、コードは1分から下記のパスと倍になり得ること：

正規表現：

(([a-z0-9!#$%&'*+?^_`{|}~-]+(?:.[a-z0-9!#$%&'*+=?^_`{|}~-]+)*@(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9]))) 

スタックトレースを：

at java.util.regex.Pattern$CharProperty.match(Pattern.java:3693) 
at java.util.regex.Pattern$Curly.match(Pattern.java:4125) 
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3694) 
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556) 
at java.util.regex.Pattern$Loop.match(Pattern.java:4683) 
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615) 
at java.util.regex.Pattern$Curly.match0(Pattern.java:4170) 
at java.util.regex.Pattern$Curly.match(Pattern.java:4132) 
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3694) 

長い時間が経過しても無限ループになるかわかりません。 私は、この表現が正確に何が起こっているのか、この表現を改善する方法を理解するのを助ける必要があります。

Answer 1

正規表現にネストされた量指定子（たとえば、(a+)*）があります。このworks well with re2ではなく、not with most other regular expression enginesです。

Answer 2

文字クラス外の正規表現内のエスケープされていないドットは、改行記号以外の任意の文字に一致します。つまり、あなたのパターンには、隣接するサブパターンと同じパターン（(?:.と?.)+）と一致する2つのエスケープされていないドットがあります。

パターンをregex101.comにロードしてggggg@ggggggggggggggggggggに対してテストすると、（PCRE設定で）エンジンがマッチングを完了するために何千ものステップを必要とすることがわかります。

エスケープされていないドットが定量化されたグループ内にあるために起こります。

また、ggggg@ccccもあなたのパターンと一致する理由です。あなたはおそらくリテラルドットと一致することを意味するので

することは、それらをエスケープ：

(([a-z0-9!#$%&'*+?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+=?^_`{|}~-]+)*@(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9]))) 

はあなたが行うので、パターン全体の周りに2つのキャプチャグループを削除する場合がありますregex demo

ノートを参照してください。それらを必要としていないようです。