ruby - 再帰文法定義のRuby正規表現?

Question

正規表現を使用して再帰的な文法定義を検証するにはどうすればよいですか? たとえば、次の文法があるとします。

   アルファ := <ベータ> ガンマ | <アルファ> <ベータ>
   ベータ := デルタ イプシロン

これは、再帰的定義が意味するものの例にすぎません。この問題に具体的に対処する正規表現を探しているのではなく、正規表現を使用してこのような問題に対処する方法を探しています。

Answer 1

Ruby 1.9 で再帰パターンに一致させる方法を次に示します。この場合は、任意のレベルのネストされた波括弧です。

#!/usr/bin/env ruby

text = "... { a { b { c } b } a { d } a } ...";
match = text.match(/(?<entire>\{(?:[^{}]+|\g<entire>)*\})/).captures
puts match

印刷されます：

{ a { b { c } b } a { d } a }

パターンの簡単な内訳:

(?<entire>        # start named capture group called <entire>
  \{              #   match the literal '{'
  (?:             #   start non capture group 1
    [^{}]+        #     match one or more chars other than '{' and '}'
    |             #     OR
    \g<entire>    #     recursively match named group <entire>
  )*              #   end non capture group 1 and repeat it zero or more times
  \}              #   match the literal '}'
)                 # end named capture group called <entire>