Ruby 1.9の正規表現は文脈自由文法に同等に強力ですか？</p>私は複数の文字列に対してテスト <pre><code>regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x </code></pre> <p>、適切に再帰を処理するため、文脈自由文法ほど強力であるように思われる：

Question

私はこの正規表現を持っています。部品を並べ替えるための彼の技術の間

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 

：

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」は、次のように、それは文脈自由文法のように見えるように、彼が実際に正規表現のすべての部分を配置例を持っていますと、再帰的な名前付きのキャプチャグループの私の例では、これはRuby 1.9の正規表現が文脈自由文法に等しいパワーを持つことを意味しますか？

Answer 1

これは、Ruby 1.9で使用されているOniguruma正規表現エンジンに関するすばらしいものの1つです。パーサーの力を持ち、通常の言語の認識に限られていません。それは肯定的および否定的な先読み/ lookbehindを持っており、ではなく文脈自由であるいくつかの言語を認識するために使用することさえできます！一例として、以下を取る：

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

この正規表現は、「ABC」、「AABBCC」、「AAABBBCCC」のような文字列を認識し、というように - 「A」、「B」の数を、そして「C」等しくなければならない、または一致しない。

（一つの制限：あなたは先読みと後読みに名前付きグループを使用することはできません）

私はボンネットの下に覗くていないが、鬼車はバックアップし、簡単な再帰下降によって名付けられたグループに対処するようです何かが一致しないとき。私はそれが左回帰を扱うことができないことを観察しました。たとえば：

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>' 

私は非常にはっきりと私の解析理論を覚えていないが、私はこのような非決定的トップダウンパーサは任意の文脈自由言語を解析することができるはずだと思います。 （「文法」ではなく「言語」）、文法が再帰を残している場合は、それを正しい再帰に変換する必要があります。それが間違っている場合は、この投稿を編集してください。