Phương ngữ biểu thức chính quy hiện đại có thường xuyên không?

Question

Tôi đã nhìn thấy một vài nhận xét ở đây đề cập đến các cụm từ thông dụng hiện đại vượt xa những gì có thể được thể hiện bằng ngôn ngữ thông thường. Cái này thế nào?

Tính năng nào của cụm từ thông dụng hiện đại không thường xuyên? Ví dụ sẽ hữu ích.

Answer 1

Việc đầu tiên mà nói đến cái tâm là backreferences:

(\w*)\s\1 

(phù hợp với một nhóm các ký tự chữ, tiếp theo là một nhân vật không gian và sau đó cùng một nhóm phù hợp trước đó) ví dụ: hello hello trận đấu, hello world doesn' t.

Cấu trúc này không thường xuyên (ví dụ: không thể được tạo bởi regular grammar).

---

Một tính năng được hỗ trợ bởi Perl RegExp Tương thích (PCRE) mà không phải là thường xuyên là mẫu đệ quy:

\((a*|(?R))*\) 

Điều này có thể được sử dụng để phù hợp với bất kỳ sự kết hợp của dấu ngoặc đơn cân bằng và "a" s (từ wikipedia)

Answer 2

Automaton hữu hạn xác định hoặc không xác định chỉ nhận ra các ngôn ngữ thông thường, được mô tả bằng cụm từ thông dụng. Định nghĩa của cụm từ thông dụng rất đơn giản. Hãy để S là một bảng chữ cái. Sau đó tập rỗng, chuỗi trống và mọi phần tử của S là các cụm từ thông dụng (trên S). Hãy để u và v là cụm từ thông dụng. Sau đó, công đoàn (u | v), nối (uv), và đóng cửa (u *) của u và v là những biểu hiện thường xuyên trên S. Định nghĩa này dễ dàng được mở rộng sang các ngôn ngữ thông thường. Không có biểu thức nào khác là cụm từ thông dụng. Như đã chỉ ra, một số tham chiếu ngược là một ví dụ. Các trang Wikipedia về ngôn ngữ và biểu thức thông thường là các tài liệu tham khảo tốt.

Về bản chất, một số "cụm từ thông dụng" nhất định không phải là thường xuyên vì không thể xây dựng tự động của một loại cụ thể để nhận ra chúng. Ví dụ, ngôn ngữ

{a^i b^i: i < = 0}

là không thường xuyên. Điều này là do việc chấp nhận automaton sẽ đòi hỏi vô số trạng thái, nhưng một automaton chấp nhận các ngôn ngữ thông thường phải có một số hữu hạn các trạng thái.

Answer 3

Một vài ví dụ:

• Regular expressions hỗ trợ nhóm. Ví dụ. trong Ruby: /my (group)/.match("my group")[1] sẽ xuất ra "nhóm". lưu trữ một cái gì đó trong một nhóm đòi hỏi một lưu trữ bên ngoài, mà một automaton hữu hạn không có.
• Nhiều ngôn ngữ, ví dụ: C#, hỗ trợ chụp, tức là mỗi trận đấu sẽ được chụp trên ngăn xếp - ví dụ: mẫu (?<MYGROUP>.)* có thể thực hiện nhiều lần chụp "." trong cùng một nhóm.
• Tạo nhóm được sử dụng để truyền lại như được chỉ ra bởi người dùng NullUserException ở trên. Backreferencing yêu cầu một hoặc nhiều ngăn xếp bên ngoài với sức mạnh của động cơ đẩy xuống (bạn phải có khả năng đẩy thứ gì đó lên chồng và liếc hoặc bật lên sau đó.
• Một số động cơ có khả năng đẩy và đẩy riêng biệt bên ngoài Trong .NET, trên thực tế, (?<MYGROUP>test) đẩy một ngăn xếp, trong khi (?<-MYGROUP>) bật một ngăn xếp.
• Một số công cụ như động cơ .NET có một khái niệm nhóm cân bằng - nơi ngăn xếp bên ngoài có thể được đẩy và Cú pháp nhóm cân bằng là (?<FIRSTGROUP-LASTGROUP>) bật ra LASTGROUP và đẩy ảnh chụp từ chỉ mục LASTGROUP trên ngăn xếp FIRSTGROUP. Điều này thực sự có thể được sử dụng để phù hợp với cấu trúc lồng nhau vô hạn chắc chắn nằm ngoài sức mạnh của một automato hữu hạn n.

ví dụ tốt Có lẽ khác tồn tại :-) Nếu bạn đang interessted hơn nữa trong một số chi tiết thi hành ngăn xếp bên ngoài kết hợp với của Regex và nhóm cân bằng và automata trật tự như vậy cao hơn automata hữu hạn, tôi đã từng viết hai bài báo ngắn về điều này (http://www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx và http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx).

Dù sao - finitieness hay không - tôi blieve rằng sức mạnh mà công cụ bổ sung này mang đến cho các ngôn ngữ thường xuyên là rất tốt :-)

Br. Morten