Являются ли регулярные выражения Ruby 1.9 одинаково мощными для контекстной свободной грамматики?

У меня есть это регулярное выражение:

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

"Fun with Ruby 1.9 Regular Exions" имеет пример, где он фактически упорядочивает все части регулярного выражения так, чтобы он выглядел как контекстно-свободная грамматика следующим образом

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 имеют силу, эквивалентную контекстно-свободной грамматике?

Ответы

Ответ 1

Это одна из удивительных вещей, связанных с движком Regexp Oniguruma, используемым в Ruby 1.9, - она ​​обладает силе анализатора и не ограничивается распознаванием обычных языков. У этого есть положительный и отрицательный lookahead/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" должно быть равно или оно не будет соответствовать.

(Одно ограничение: вы не можете использовать названные группы в lookahead и lookbehind.)

Хотя я havent заглянул под капот, Oniguruma, похоже, имеет дело с именованными группами простым рекурсивным спуском, создавая резервную копию, когда что-то не соответствует. Ive заметил, что он не может справиться с левой рекурсией. Например:

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

Я не очень хорошо помню мою теорию синтаксического анализа, но я думаю, что не детерминированный синтаксический анализатор сверху вниз должен иметь возможность анализировать любой контекстно-свободный язык. ( "язык", а не "грамматика", если ваша грамматика оставила рекурсию, вам придется преобразовать ее в правильную рекурсию.) Если это неверно, отредактируйте это сообщение.