14

私はこの正規表現を持っています：

regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}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

「FunwithRuby1.9 Regular Expressions」には、次のように文脈自由文法のように見えるように、実際に正規表現のすべての部分を配置する例があります。

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

正規表現の一部を再配置するための彼の手法と、再帰的な名前付きキャプチャグループの例との間で、これは、Ruby 1.9の正規表現が文脈自由文法と同等の能力を持っていることを意味しますか？

4

1 に答える 1

7

これは、Ruby1.9で使用されている鬼車正規表現エンジンのすばらしい点の1つです。パーサーの機能を備えており、正規言語の認識に制限されていません。ポジティブとネガティブの先読み/後読みがあり、文脈自由ではない一部の言語を認識するために使用することもできます。例として以下を取り上げます。

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」の数は等しくなければなりません。等しくない場合は一致しません。

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

ボンネットの下を覗いたことはありませんが、鬼車は名前の付いたグループを単純な再帰下降で処理し、何かが一致しない場合はバックアップするようです。私はそれが左再帰に対処できないことを観察しました。例えば：

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

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

于 2012-01-22T21:20:37.753 に答える