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

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

13 голосов
/ 22 января 2012

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

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

" Удовольствие от регулярных выражений Ruby 1.9 " есть пример, в котором он фактически упорядочивает все части регулярного выражения так, чтобы это выглядело как контекстная грамматика следующим образом: 

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 Ответ

7 голосов
/ 23 января 2012

Это одна из замечательных особенностей движка Oniguruma regexp, используемого в Ruby 1.9 - он обладает возможностями синтаксического анализатора и не ограничивается распознаванием обычных языков. Он имеет положительный и отрицательный взгляд / взгляд назад, который даже может использоваться для распознавания некоторых языков, которые не не зависят от контекста! В качестве примера возьмем следующее: 

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

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

...