Bu normal ifadeyi nasıl "felaket geri dönüşü" ile sonuçlanamaz?

Question

Ben another question cevapları dayanarak http://daringfireball.net/2010/07/improved_regex_for_matching_urls

(?xi) 
\b 
(      # Capture 1: entire matched URL 
    (?: 
    https?://    # http or https protocol 
    |      # or 
    www\d{0,3}[.]   # "www.", "www1.", "www2." … "www999." 
    |       # or 
    [a-z0-9.\-]+[.][a-z]{2,4}/ # looks like domain name followed by a slash 
) 
    (?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 
    (?:      # End with: 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
    |        # or 
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]  # not a space or one of these punct chars 
) 
) 

aldığım düzenli ifade ile eşleşen bir URL kullanmaya çalışıyorum, backtrack catastrophically bu regex neden durumlar vardır anlaşılmaktadır. Örneğin:

(?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 

:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA)") 

... sorun bu kod bölümünün bulunduğunu

Bana öyle geliyor (Chrome'da örneğin) yürütmek için gerçekten uzun bir zaman alabilir

... hangi (.+)+

içeren gibi o önlemek olacaktır yapabilir bir değişiklik var mı görünüyor ki, (.+|\((.+|(\(.+\)))*\))+ kabaca eşdeğer gibi görünüyor?

Answer 1

aşağıdakilere bunu değiştirme katastrofik backtracking önleyecektir:

(?xi) 
\b 
(      # Capture 1: entire matched URL 
    (?: 
    https?://    # http or https protocol 
    |      # or 
    www\d{0,3}[.]   # "www.", "www1.", "www2." … "www999." 
    |       # or 
    [a-z0-9.\-]+[.][a-z]{2,4}/ # looks like domain name followed by a slash 
) 
    (?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 
    (?:      # End with: 
    \(([^\s()<>]|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
    |        # or 
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]  # not a space or one of these punct chars 
) 
) 

"dengeli Pars" regex bölümlerinin her birinde birinci [^\s()<>] sonra + kaldırmak oldu yapıldığı tek değişiklik.

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA") 

orijinal regex sorunu kısmı dengeli parantez bölümdür, geri adım tamamen gidiyorum neden olduğunu da açıklamayı basitleştirmek için: Burada

JS ile test için tek satırlık versiyonu burada değil alakalı yüzünden iç içe parantezler kısmını kaldırın:

\(([^\s()<>]+|(\([^\s()<>]+\)))*\) # original 
\(([^\s()<>]+)*\)      # expanded below 

\(    # literal '(' 
(    # start group, repeat zero or more times 
    [^\s()<>]+  # one or more non-special characters 
)*    # end group 
\)    # literal ')' 

dize '(AAAAA' burada olur düşünün, edebi ( maç ve ardındanediyorum Grup tarafındantüketilir ve ) eşleşmez. Bu noktada grup, AAAA'u yakalayan ve bu noktada maçı devam ettirmeye çalışan bir A'dan vazgeçerdi. Grup, onu takip eden bir * olduğundan, grup birden çok kez eşleşebilir, böylece AAAA ile eşleşen ([^\s()<>]+)* ve ikinci geçişte A olacaktır. Bu başarısız olduğunda ek bir A orijinal yakalama tarafından verilecek ve ikinci yakalama tarafından tüketilecektir.

Bu için giderdim uzun bir örneği eşleşti aşağıdaki her virgülle ayrılmış grup grup eşleştiğini farklı bir zamanı gösterir maç için girişimleri, ve kaç karakter sonuçlanan ederken:

AAAAA 
AAAA, A 
AAA, AA 
AAA, A, A 
AA, AAA 
AA, AA, A 
AA, A, AA 
AA, A, A, A 
.... 

Yanlış sayılmış olabilir, ancak regex'in eşleşemediğine karar vermeden önce 16 adıma kadar eklediğinden eminim. Dizeye ek karakterler eklemeye devam ettiğinizde, bunu anlamaya yönelik adım sayısı katlanarak büyür.

+'u kaldırıp bunu \(([^\s()<>])*\) olarak değiştirerek, bu geri bildirim senaryosundan kaçınmalısınız.

İç içe geçme parantezleri denetlemek için tekrar ekleme eklenmesi herhangi bir soruna neden olmaz. Şu anda "http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA" hemen önce ( kadar maç olacak çünkü, dizenin sonuna kadar çapa çeşit eklemek isteyebilirsiniz

Not yüzden re.test(...)truehttp://google.com/?q= çünkü eşleşmeleri dönecekti.