Phát hiện xem regexp có theo hàm mũ hay không

Question

article này cho thấy có một số regexp là O (2^n) khi quay ngược lại. Ví dụ là (x+x+)+y. Khi cố gắng khớp một chuỗi như xxxx ... p nó sẽ quay lại một lúc trước khi tìm ra nó không khớp.

Có cách nào để phát hiện regexp như vậy không?

nhờ

Answer 1

Nếu động cơ regexp của bạn cho thấy hành vi mũ thời gian chạy cho (x + x +) + y, sau đó nó là chia vì một DFA hoặc NFA có thể nhận ra mô hình này trong thời gian tuyến tính:

echo "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" | egrep "(x+x+)+y" 
echo "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy" | egrep "(x+x+)+y" 

cả câu trả lời ngay lập tức . Trong thực tế, chỉ có một vài trường hợp (như backreferences) trong đó backtracking thực sự cần thiết (chủ yếu là vì regexp với backreference là không phải là một biểu thức chính quy trong ý nghĩa lý thuyết ngôn ngữ nữa). Việc triển khai có khả năng chỉ nên chuyển sang chế độ backtracking khi các trường hợp góc này được đưa ra. Trong sự công bằng, DFA cũng có mặt tối, bởi vì một số regexp có yêu cầu kích thước theo cấp số nhân, nhưng một giới hạn kích thước dễ thực thi hơn ràng buộc thời gian và DFA lớn chạy tuyến tính trên đầu vào, vì vậy nó là một món hời tốt hơn so với một backtracker nhỏ nghẹt thở trên một vài X.

Bạn nên thực sự đọc Russ Cox loạt bài báo xuất sắc về việc thực hiện regexp (và hành vi bệnh hoạn của tùy ý): http://swtch.com/~rsc/regexp/

Để trả lời câu hỏi của bạn về decidability: Bạn không có thể. Vì không có một bản sao cho regexpr. Mỗi thực hiện đều có chiến lược riêng của mình để đối phó với sự tăng trưởng theo hàm mũ trong thuật toán của họ đối với một số trường hợp nhất định và không bao gồm những trường hợp khác. Một quy tắc có thể phù hợp cho ở đây và thảm khốc cho ở đó.

UPDATE:

Ví dụ, một thực thể chứa một ưu mà có thể sử dụng biến đổi đại số để đơn giản hóa regexps trước khi thực hiện chúng: (x+x+)+y là giống một xxx*y, mà không phải là một vấn đề đối với bất kỳ backtracker.Nhưng cùng một trình tối ưu hóa sẽ không nhận ra biểu thức tiếp theo và vấn đề là có một lần nữa. Ở đây có người mô tả làm thế nào để phác thảo một regexpr mà đánh lừa ưu Perl:

http://perlgeek.de/blog-en/perl-tips/in-search-of-an-exponetial-regexp.html

Answer 2

Không, tôi không nghĩ như vậy, nhưng bạn có thể sử dụng các nguyên tắc này:

• Nếu nó có chứa hai quantifiers được mở-kết thúc vào cuối cao và họ đang lồng sau đó nó có thể là O (2^n).
• Nếu nó không chứa hai định lượng như vậy thì tôi nghĩ rằng nó không thể là O (2^n).

Các số liệu có thể gây ra điều này là: *, + và {k,}. Cũng cần lưu ý rằng độ phức tạp của trường hợp đánh giá biểu thức chính quy tồi tệ nhất có thể rất khác so với độ phức tạp trên các chuỗi thông thường và độ phức tạp phụ thuộc vào công cụ biểu thức chính quy cụ thể.

Answer 3

Bất kỳ regex mà không backreferences có thể được xuất hiện trong thời gian tuyến tính, mặc dù nhiều công cụ regex ngoài kia trong thế giới thực không làm điều đó theo cách đó (ít nhất là nhiều động cơ regex được cắm vào môi trường thời gian chạy ngôn ngữ lập trình hỗ trợ backreferences, và không chuyển sang một mô hình thực hiện hiệu quả hơn khi không có backreferences).

Không có cách nào dễ dàng để tìm ra bao nhiêu thời gian một regex với backreferences sẽ tiêu thụ.

Answer 4

Bạn có thể phát hiện và từ chối lặp lại lồng nhau bằng cách sử dụng trình phân tích cú pháp regex, tương ứng với số star height của 1. Tôi vừa viết a module to compute and reject start heights of >1 sử dụng trình phân tích cú pháp regex từ npm.

$ node safe.js '(x+x+)+y' 
false 
$ node safe.js '(beep|boop)*' 
true 
$ node safe.js '(a+){10}' 
false 
$ node safe.js '\blocation\s*:[^:\n]+\b(Oakland|San Francisco)\b' 
true