Phân tích trường hợp xấu nhất cho biểu thức chính quy

Question

Có công cụ nào có biểu thức chính quy cụ thể và trả về trường hợp xấu nhất về số lượng hoạt động cần thiết cho một số ký tự nhất định không?

Vì vậy, ví dụ: được đưa ra (f|a)oo.*[ ]baz, số bước mà động cơ có thể đi qua để khớp với 100 ký tự?

Tôi cũng sẽ quan tâm nếu có một công cụ có thể lấy một loạt các mẫu văn bản và hiển thị các hoạt động trung bình cho mỗi lần chạy.

Tôi nhận thấy điều này phụ thuộc rất nhiều vào công cụ được sử dụng và triển khai - nhưng tôi không biết gì về mức độ phổ biến của nó. Vì vậy, nếu nó là phổ biến cho nhiều ngôn ngữ (làm cho câu hỏi của tôi quá mơ hồ) Tôi sẽ đặc biệt quan tâm đến Perl và Python.

Answer 1

Regexbuddy's trình gỡ lỗi hiển thị số bước thực hiện để kết thúc trận đấu hoặc không kết hợp với một mẫu nhất định. Thông tin thêm về catastrophic backtracking và debugging regular expressions.

PS: Nó không phải là miễn phí nhưng họ cung cấp một tiền lại đảm bảo 3 tháng.

Answer 2

Lưu ý rằng tùy thuộc vào công cụ . Trong khi lý thuyết regex dựa trên lý thuyết automata thẳng, hầu hết các động cơ không phải là bản dịch nghiêm ngặt của những lý thuyết đó. Vì lý do này, ví dụ, một số động cơ phải chịu thời gian theo cấp số nhân trong khi xử lý NFA nghiêm ngặt thì không.

Answer 3

Bạn có thể nhận được những gì bạn đang tìm kiếm một cái gì đó như sử dụng re.compile với re.DEBUG. Xem số excellent answer này từ Python Hidden Features Wiki cộng đồng để có giải thích sâu rộng.