Có phải Ruby 1.9 biểu thức chính quy không kém phần mạnh mẽ đối với ngữ cảnh tự do ngữ cảnh không?

Question

Tôi có biểu thức chính quy này:

regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x 

Khi tôi kiểm tra nó chống lại một số chuỗi, nó dường như là mạnh mẽ như một bối cảnh ngữ pháp miễn phí vì nó xử lý các đệ quy đúng cách.

regex.match("aaacaaa") 
# => #<MatchData "aaacaaa" foo:"aaacaaa"> 
regex.match("aacaa") 
# => #<MatchData "aacaa" foo:"aacaa"> 
regex.match("aabcbaa") 
# => #<MatchData "aabcbaa" foo:"aabcbaa"> 
regex.match("aaacaa") 
# => nil 

"Fun with Ruby 1.9 Regular Expressions" có một ví dụ nơi ông thực sự sắp xếp tất cả các bộ phận của một regex để nó trông giống như một ngữ pháp ngữ cảnh miễn phí như sau:

sentence = %r{ 
    (?<subject> cat | dog | gerbil ){0} 
    (?<verb>  eats | drinks| generates){0} 
    (?<object> water | bones | PDFs  ){0} 
    (?<adjective> big | small | smelly ){0} 

    (?<opt_adj> (\g<adjective>\s)? ){0} 

    The\s\g<opt_adj>\g<subject>\s\g<verb>\s\g<opt_adj>\g<object> 
}x 

giữa kỹ thuật của anh cho việc sắp xếp lại những phần của regex, và ví dụ của tôi về các nhóm thu hồi được đặt tên đệ quy, điều này có nghĩa là các biểu thức chính quy của Ruby 1.9 có sức mạnh tương đương với ngữ pháp không có ngữ cảnh không?

Answer 1

Đây là một trong những điều tuyệt vời về công cụ regexp Oniguruma được sử dụng trong Ruby 1.9 - nó có sức mạnh của một trình phân tích cú pháp và không bị hạn chế trong việc nhận dạng các ngôn ngữ thông thường. Nó có giao diện/lookbehind tích cực và tiêu cực, thậm chí có thể được sử dụng để nhận ra một số ngôn ngữ là không không có ngữ cảnh! Đi theo sau là một ví dụ:

regexp = /\A(?<AB>a\g<AB>b|){0}(?=\g<AB>c)a*(?<BC>b\g<BC>c|){1}\Z/ 

regexp này ghi nhận chuỗi như “abc”, “aabbcc”, “aaabbbccc”, và vân vân - số “a”, “b”, và “c” phải bằng hoặc không khớp.

(Một giới hạn: bạn không thể sử dụng các nhóm có tên trong lookahead và lookbehind.)

Mặc dù tôi đã không ngó dưới mui xe, Oniguruma dường như để đối phó với các nhóm được đặt tên bởi gốc đệ quy đơn giản, sao lưu khi một cái gì đó không phù hợp. Tôi đã quan sát thấy rằng nó không thể đối phó với việc đệ quy trái. Ví dụ:

irb(main):013:0> regexp = /(?<A>\g<A>a|)/ 
SyntaxError: (irb):13: never ending recursion: /(?<A>\g<A>a|)/ 
    from C:/Ruby192/bin/irb:12:in `<main>' 

Tôi không nhớ lý thuyết phân tích cú pháp của tôi rất rõ ràng, nhưng tôi nghĩ rằng một tổ chức phi xác định phân tích cú pháp từ trên xuống như thế này sẽ có thể phân tích bất kỳ ngôn ngữ bối cảnh tự do. ("Ngôn ngữ", không phải "ngữ pháp"; nếu ngữ pháp của bạn đã để lại đệ quy, bạn sẽ phải chuyển đổi nó thành đệ quy đúng.) Nếu điều đó không chính xác, vui lòng chỉnh sửa bài đăng này.