Cụm từ thông dụng (regex) có thực sự thường xuyên không?

Question

Tôi hiểu cách thức các cụm từ thông dụng nhận tên của họ và đã đọc câu hỏi liên quan (Why are regular expressions called "regular" expressions?), nhưng tôi vẫn băn khoăn liệu cụm từ thông dụng có thường xuyên không.

Ví dụ: cách tham chiếu ngược có thể là thông thường? Điều đó không đòi hỏi một số bộ nhớ và do đó không thể phù hợp/tạo ra bởi một automaton nhà nước hữu hạn?

Answer 1

Liên kết trong câu trả lời cho câu hỏi mà bạn tham chiếu (wikipedia), trái ngược với nhiều công cụ biểu thức thông thường được cung cấp bởi ngôn ngữ lập trình hiện đại, được tăng cường với các tính năng cho phép nhận dạng ngôn ngữ biểu thức chính quy cổ điển.

Vì vậy, tôi sẽ nói rằng sự tiến hóa của regex đã chuyển nó ra khỏi ý tưởng ban đầu của nó là thể hiện các ngôn ngữ thông thường.

Từ Wikipedia article on regular expressions:

Nhiều tính năng được tìm thấy trong hầu như tất cả các biểu thức chính quy hiện đại thư viện cung cấp một khả năng diễn đạt rằng vượt xa thường xuyên ngôn ngữ. Ví dụ: nhiều triển khai cho phép nhóm biểu thức con với dấu ngoặc đơn và gọi lại giá trị mà chúng khớp với nhau trong cùng một biểu thức (backreferences). Điều này có nghĩa là, trong số các điều khác, một mẫu có thể khớp với chuỗi các từ lặp lại như "papa" hoặc "WikiWiki", được gọi là hình vuông trong lý thuyết ngôn ngữ chính thức. Mẫu cho các chuỗi này là (.+)\1.

Answer 2

Tiện ích mở rộng hiện đại bao gồm tham chiếu ngược giúp hệ thống regex không phải là ứng cử viên của ngôn ngữ thông thường, tuy nhiên IMO có thể được chuyển sang ngôn ngữ không có ngữ cảnh chứ không phải đến máy Turing.

Ngữ pháp thông thường có chung một đặc tính chung gọi là bơm bổ đề. Bạn có thể kiểm tra ví dụ here để chứng minh 0 ^{n n} không phải là ngữ pháp thông thường (tương tự như tham chiếu ngược). Đây là cách nó có thể được hiển thị rằng tài liệu tham khảo trở lại không đáp ứng bất động sản bơm bổ sung.

• bơm Bổ đề trong bối cảnh hiện nay: để chứng minh rằng một hệ thống regex là thường xuyên ngữ pháp, cần phải có một thời gian hữu hạn p như vậy mà tất cả các chuỗi phù hợp với regex và có chiều dài tương đương hoặc lớn hơn p có thể chia thành ba phần xyz sao cho y không phải là một chuỗi rỗng và tất cả các chuỗi được biểu diễn bởi xy ^* z (y được bơm trong [0, vô hạn) lần) phù hợp với regex.

• Nếu chúng tôi có thể cho thấy không có p nào có thể đáp ứng các điều kiện cho regex thì nó không có ngữ pháp thông thường.

• Đối với tham chiếu ngược, chúng tôi sẽ cần phải có hai trong số các chuỗi bơm này có chiều dài bằng nhau, một cho mẫu con trong nhóm được chụp và một ở mặt sau. Đây chính xác là những gì mà các ngôn ngữ tự do hoặc ngữ cảnh tự do đẩy xuống. Ngoài ra còn có một bổ đề bơm cho ngữ pháp miễn phí ngữ cảnh được dựa trên chia tách thành uvwxy nơi v và x có thể được bơm bằng nhau n lần. Chúng ta có thể chỉ ra rằng regex với hệ thống tham chiếu ngược đáp ứng bổ đề này.