Regex bệnh lý có thể phát sinh (thời gian và bộ nhớ)?

Question

Regex bệnh lý nào làm phát sinh nhiều trình phân tích cú pháp (cả trong thời gian & bộ nhớ)? và trình phân tích cú pháp nào? Điểm thưởng cơ bản hơn và chuẩn là regex, và nhiều khả năng người dùng không độc hại có thể ngây thơ đến với nó. Hãy thoải mái đăng dữ liệu thời gian thực và bộ nhớ cũng như phiên bản phân tích cú pháp.

(tôi dường như nhớ rằng khẳng định lookbehind quá mức hoặc (EDIT:) backtracking trong PERL được cho là để làm điều này, hoặc ít nhất đã từng là gì nữa.?)

Answer 1

Phỏng theo ví dụ đầu tiên trong bài viết Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...):

perl -e '$n=29; ("a" x $n) =~ (("a?" x $n).("a" x $n))' 

nào mất 40 giây trên hệ thống của tôi. Sau đó, hãy làm theo số $n++ để tăng số mũ vui vẻ ...

Answer 2

Từ Russ của Cox tuyệt vời article: $ perl -e '("a" x 100000) =~ /^(ab?)*$/;'. Điều này dường như gây ra một segfault. Có nhiều hơn trong bài báo.

Answer 3

tôi luôn luôn sử dụng regex này để phù hợp với chuỗi bên trong PHP hoặc mã nguồn JavaScript trong PHP:

~'(\\.|[^'])*'|"(\\.|[^"])*"~s 

Và nó hầu như luôn luôn thất bại trên một chuỗi rất dài (khoảng 50000 ký tự dài sẽ làm).