Tôi có thể sử dụng một biểu thức chính quy để xem liệu nó có giảm xuống không. *

Question

Tôi đang phát triển một ứng dụng mà người dùng nhập cụm từ thông dụng làm tiêu chí lọc, tuy nhiên tôi không muốn mọi người (dễ) có thể nhập .* (tức là phù hợp với bất cứ điều gì). Vấn đề là, nếu tôi chỉ sử dụng if (expression == ".*"), thì điều này có thể dễ dàng được sidestepped bằng cách nhập một cái gì đó chẳng hạn như .*.*.

Có ai biết thử nghiệm có thể lấy một phần của regex và xem liệu về cơ bản là .* nhưng ở dạng hơi phức tạp hơn?

những suy nghĩ của tôi là:

1. tôi có thể thấy nếu biểu thức là một hoặc nhiều lần lặp lại của .*, (tức là nếu nó phù hợp với (\.\*)+ (trích dẫn/thoát có thể không hoàn toàn chính xác, nhưng bạn sẽ có được ý tưởng). vấn đề với điều này là có thể có các hình thức khác của việc viết một trận đấu quốc tế (ví dụ với $ và ^) mà là quá đầy đủ để thậm chí nghĩ về trả trước, chúng ta hãy cùng thử nghiệm.

2. tôi có thể thử nghiệm một vài cách ngẫu nhiên tạo ra các chuỗi với nó và giả sử t mũ nếu tất cả đều vượt qua, người dùng đã nhập mẫu phù hợp trên toàn cầu. Vấn đề với cách tiếp cận này là có thể có những tình huống mà biểu thức là đủ chặt chẽ và tôi chỉ chọn chuỗi xấu để phù hợp với.

Suy nghĩ, bất kỳ ai?

(FYI, ứng dụng là trong Java nhưng tôi đoán đây là chi tiết của một câu hỏi thuật toán hơn một cho một ngôn ngữ cụ thể.)

Answer 1

Có rất nhiều, rất nhiều khả năng để đạt được một cái gì đó tương đương với .*. ví dụ. chỉ cần đặt bất kỳ lớp nhân vật nào và phần truy cập vào một lớp hoặc một sự thay đổi và nó sẽ khớp với bất kỳ thứ gì.
Vì vậy, tôi nghĩ với một biểu thức chính quy, không thể kiểm tra một biểu thức chính quy khác để tương đương với .*.

Đây là một số ví dụ mà sẽ phù hợp cùng hơn .* (họ sẽ bổ sung phù hợp với nhân vật newline)

/[\s\S]*/ 
/(\w|\W)*/ 
/(a|[^a])*/ 
/(a|b|[^ab])*/ 

Vì vậy, tôi cho rằng ý tưởng của bạn 2 sẽ dễ dàng hơn rất nhiều để đạt được.

Answer 2

Có, có một cách. Nó liên quan đến việc chuyển đổi regex thành một biểu diễn FSM chuẩn. Xem http://en.wikipedia.org/wiki/Regular_expression#Deciding_equivalence_of_regular_expressions

Bạn có thể tìm thấy mã được xuất bản hoạt động cho bạn. Nếu không, các bước chi tiết được mô tả ở đây: http://swtch.com/~rsc/regexp/regexp1.html

Nếu điều đó có vẻ quá nhiều công việc, thì bạn có thể sử dụng thử nghiệm xác suất nhanh và dơ bẩn. Chỉ cần tạo một số chuỗi ngẫu nhiên để xem chúng có khớp với regex của người dùng hay không. Nếu chúng phù hợp, bạn có một dấu hiệu khá tốt rằng regex quá rộng.

Answer 3

Cảm ơn mọi người,

Tôi đã bỏ lỡ thử nghiệm cho mục nhập tương đương trên wikipedia, điều này thật thú vị.

Kỷ niệm của tôi về DFA (dường như tôi phải chứng minh, hoặc ít nhất là chứng minh, trong kỳ thi năm thứ 2 CompSci rằng regex không thể kiểm tra palindromes) có lẽ là tốt nhất còn lại nghỉ tại thời điểm này!

Tôi sẽ đi xuống phương pháp tạo một chuỗi các chuỗi để kiểm tra. Nếu tất cả đều trôi qua, thì tôi khá tự tin rằng bộ lọc quá rộng và cần được kiểm tra thủ công. Trong khi đó, ít nhất một thất bại chỉ ra rằng biểu thức có nhiều khả năng phù hợp với mục đích hơn.

Bây giờ để quyết định loại dây để tạo ra để chạy thử nghiệm ....

Trân trọng! Russ.