Viết biểu thức regex tốt hơn cho không sử dụng lười biếng lặp lại lượng hóa

Question

Tôi có một biểu thức chính quy:

(<select([^>]*>))(.*?)(</select\s*>) 

Vì nó sử dụng lượng hóa lặp lại lười biếng, cho các chuỗi dài hơn (có tùy chọn hơn 500) nó backtracks hơn 100.000 lần và thất bại. Hãy giúp tôi tìm một cụm từ thông dụng tốt hơn không sử dụng định lượng lặp lại lười biếng

Answer 1

<select[^>]*>[^<]*(?:<(?!/select>)[^<]*)*</select> 

... hoặc trong con người có thể đọc được dạng:

<select[^>]*> # start tag 
[^<]*   # anything except opening bracket 
(?:    # if you find an open bracket 
    <(?!/select>) # match it if it's not part of end tag 
    [^<]*   # consume any more non-brackets 
)*    # repeat as needed 
</select>  # end tag 

Đây là ví dụ về kỹ thuật "vòng lặp không được kiểm soát" Friedl phát triển trong cuốn sách của mình, Mastering Regular Expressions. Tôi đã làm một bài kiểm tra nhanh trong RegexBuddy bằng cách sử dụng mẫu dựa trên các định lượng miễn cưỡng:

(?s)<select[^>]*>.*?</select> 

... và mất khoảng 6.000 bước để tìm kết quả phù hợp. Mẫu không được kiểm soát vòng chỉ mất 500 bước. Và khi tôi gỡ bỏ khung đóng từ thẻ kết thúc (</select), làm cho một trận đấu không thể, nó chỉ yêu cầu 800 bước để báo cáo lỗi.

Nếu hương vị regex của bạn hỗ trợ quantifiers sở hữu, đi trước và sử dụng chúng, quá:

<select[^>]*+>[^<]*+(?:<(?!/select>)[^<]*+)*+</select> 

Mất khoảng cùng một số bước để đạt được một trận đấu, nhưng nó có thể sử dụng ít hơn rất nhiều bộ nhớ trong quá trình. Và nếu không có trận đấu nào có thể, nó sẽ thất bại nhanh hơn; trong các thử nghiệm của tôi, nó mất khoảng 500 bước, cùng một số nó đã để tìm một trận đấu.

Answer 2

Thật không may, điều này không đúng, xem câu trả lời của Alan Moore cho một ví dụ chính xác!

(<select([^>]*>))(.*+)(</select\s*>) 

Từ manpage perl regexp:

Theo mặc định, khi một subpattern định lượng không cho phép phần còn lại của mô hình tổng thể để phù hợp, Perl sẽ quay lại. Tuy nhiên, hành vi này đôi khi không mong muốn. Vì vậy, Perl cũng cung cấp dạng số lượng "sở hữu" .

 *+  Match 0 or more times and give nothing back 
     ++  Match 1 or more times and give nothing back 
     ?+  Match 0 or 1 time and give nothing back 
     {n}+ Match exactly n times and give nothing back (redundant) 
     {n,}+ Match at least n times and give nothing back 
     {n,m}+ Match at least n but not more than m times and give nothing back 

Ví dụ,

 'aaaa' =~ /a++a/ 

sẽ không bao giờ phù hợp, như là "một ++" sẽ nuốt chửng tất cả các "a" 's trong chuỗi và won không để lại bất kỳ phần nào còn lại của mẫu. Tính năng này có thể cực kỳ hữu ích để đưa ra gợi ý perl về vị trí của nó không được quay lại. Ví dụ, các điển hình "phù hợp với một chuỗi dụng dấu ngoặc kép" Vấn đề có thể được thực hiện một cách hiệu quả nhất khi viết là:

 /"(?:[^"\\]++|\\.)*+"/