Какой класс языков действительно распознают настоящие современные регулярные выражения?
Всякий раз, когда есть группа захвата неограниченной длины с обратной ссылкой (например (.*)_\1
), регулярное выражение теперь соответствует нерегулярному языку. Но S ::= '(' S ')' | ε
одного этого недостаточно, чтобы сопоставить что-то вроде - контекстно-свободный язык сопоставления пар пар пар символов.
Рекурсивные регулярные выражения (которые для меня новы, но я уверен, что они существуют в Perl и PCRE), похоже, распознают по крайней мере большинство CFL.
Кто-нибудь делал или читал какие-либо исследования в этой области? Каковы ограничения этих «современных» регулярных выражений? Признают ли они строго больше или строго меньше, чем CFG, грамматик LL или LR? Или существуют оба языка, которые можно распознать с помощью регулярного выражения, но не с помощью CFG, и наоборот?
Будем очень признательны за ссылки на соответствующие статьи.
источник
Ответы:
Рекурсия шаблона
С рекурсивными шаблонами у вас есть форма сопоставления рекурсивного спуска .
Это нормально для множества проблем, но как только вы действительно хотите выполнить синтаксический анализ с рекурсивным спуском , вам нужно вставлять группы захвата здесь и там, и восстановить полную структуру синтаксического анализа таким способом неудобно. Модуль Regexp :: Grammars Дамиана Конвея для Perl преобразует простой шаблон в эквивалентный, который автоматически выполняет все перечисленные операции захвата в рекурсивную структуру данных, что значительно упрощает извлечение проанализированной структуры. В конце статьи у меня есть образец сравнения этих двух подходов.
Ограничения на рекурсию
Вопрос был в том, какие грамматики могут соответствовать рекурсивным шаблонам. Ну, это определенно сопоставители типов с рекурсивным спуском . Единственное, что приходит в голову, это то, что рекурсивные шаблоны не могут обрабатывать левую рекурсию . Это накладывает ограничения на типы грамматик, к которым вы можете их применять. Иногда вы можете изменить порядок своих постановок, чтобы исключить левую рекурсию.
Кстати, PCRE и Perl немного различаются в том, как вы можете сформулировать рекурсию. См. Разделы «РЕКУРСИВНЫЕ ШАБЛОНЫ» и «Отличия рекурсии от Perl» на странице руководства pcrepattern . например: Perl может работать
^(.|(.)(?1)\2)$
там, где^((.)(?1)\2|.)$
этого требует PCRE .Рекурсивные демонстрации
Потребность в рекурсивных шаблонах возникает на удивление часто. Один из часто посещаемых примеров - это когда вам нужно сопоставить что-то, что может быть вложенным, например сбалансированные круглые скобки, кавычки или даже теги HTML / XML. Вот совпадение с парными скобками:
\((?:[^()]*+|(?0))*\)
Мне его труднее читать из-за его компактности. Это легко исправить с помощью
/x
режима, чтобы пробелы больше не имели значения:\( (?: [^()] *+ | (?0) )* \)
Опять же, поскольку мы используем скобки для нашей рекурсии, более ясным примером будет сопоставление вложенных одинарных кавычек:
‘ (?: [^‘’] *+ | (?0) )* ’
Еще одна рекурсивно определенная вещь, которую вы, возможно, захотите сопоставить, - это палиндром. Этот простой шаблон работает в Perl:
^((.)(?1)\2|.?)$
которые вы можете протестировать на большинстве систем, используя что-то вроде этого:
$ perl -nle 'print if /^((.)(?1)\2|.?)$/i' /usr/share/dict/words
Обратите внимание, что реализация рекурсии в PCRE требует более сложных
^(?:((.)(?1)\2|)|((.)(?3)\4|.))
Это связано с ограничениями работы рекурсии PCRE.
Правильный разбор
На мой взгляд , приведенные выше примеры, в основном игрушка матчей, не все , что интересно, на самом деле. Интересно становится тогда, когда у вас есть настоящая грамматика, которую вы пытаетесь разобрать. Например, RFC 5322 довольно подробно определяет почтовый адрес. Вот подходящий ему «грамматический» шаблон:
$rfc5322 = qr{ (?(DEFINE) (?<address> (?&mailbox) | (?&group)) (?<mailbox> (?&name_addr) | (?&addr_spec)) (?<name_addr> (?&display_name)? (?&angle_addr)) (?<angle_addr> (?&CFWS)? < (?&addr_spec) > (?&CFWS)?) (?<group> (?&display_name) : (?:(?&mailbox_list) | (?&CFWS))? ; (?&CFWS)?) (?<display_name> (?&phrase)) (?<mailbox_list> (?&mailbox) (?: , (?&mailbox))*) (?<addr_spec> (?&local_part) \@ (?&domain)) (?<local_part> (?&dot_atom) | (?"ed_string)) (?<domain> (?&dot_atom) | (?&domain_literal)) (?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dcontent))* (?&FWS)? \] (?&CFWS)?) (?<dcontent> (?&dtext) | (?"ed_pair)) (?<dtext> (?&NO_WS_CTL) | [\x21-\x5a\x5e-\x7e]) (?<atext> (?&ALPHA) | (?&DIGIT) | [!#\$%&'*+-/=?^_`{|}~]) (?<atom> (?&CFWS)? (?&atext)+ (?&CFWS)?) (?<dot_atom> (?&CFWS)? (?&dot_atom_text) (?&CFWS)?) (?<dot_atom_text> (?&atext)+ (?: \. (?&atext)+)*) (?<text> [\x01-\x09\x0b\x0c\x0e-\x7f]) (?<quoted_pair> \\ (?&text)) (?<qtext> (?&NO_WS_CTL) | [\x21\x23-\x5b\x5d-\x7e]) (?<qcontent> (?&qtext) | (?"ed_pair)) (?<quoted_string> (?&CFWS)? (?&DQUOTE) (?:(?&FWS)? (?&qcontent))* (?&FWS)? (?&DQUOTE) (?&CFWS)?) (?<word> (?&atom) | (?"ed_string)) (?<phrase> (?&word)+) # Folding white space (?<FWS> (?: (?&WSP)* (?&CRLF))? (?&WSP)+) (?<ctext> (?&NO_WS_CTL) | [\x21-\x27\x2a-\x5b\x5d-\x7e]) (?<ccontent> (?&ctext) | (?"ed_pair) | (?&comment)) (?<comment> \( (?: (?&FWS)? (?&ccontent))* (?&FWS)? \) ) (?<CFWS> (?: (?&FWS)? (?&comment))* (?: (?:(?&FWS)? (?&comment)) | (?&FWS))) # No whitespace control (?<NO_WS_CTL> [\x01-\x08\x0b\x0c\x0e-\x1f\x7f]) (?<ALPHA> [A-Za-z]) (?<DIGIT> [0-9]) (?<CRLF> \x0d \x0a) (?<DQUOTE> ") (?<WSP> [\x20\x09]) ) (?&address) }x;
Как видите, это очень похоже на BNF. Проблема в том, что это просто совпадение, а не захват. И вы действительно не хотите просто окружать все это захватывающими скобками, потому что это не говорит вам, какая продукция соответствует какой части. Используя ранее упомянутый модуль Regexp :: Grammars, мы можем.
#!/usr/bin/env perl use strict; use warnings; use 5.010; use Data::Dumper "Dumper"; my $rfc5322 = do { use Regexp::Grammars; # ...the magic is lexically scoped qr{ # Keep the big stick handy, just in case... # <debug:on> # Match this... <address> # As defined by these... <token: address> <mailbox> | <group> <token: mailbox> <name_addr> | <addr_spec> <token: name_addr> <display_name>? <angle_addr> <token: angle_addr> <CFWS>? \< <addr_spec> \> <CFWS>? <token: group> <display_name> : (?:<mailbox_list> | <CFWS>)? ; <CFWS>? <token: display_name> <phrase> <token: mailbox_list> <[mailbox]> ** (,) <token: addr_spec> <local_part> \@ <domain> <token: local_part> <dot_atom> | <quoted_string> <token: domain> <dot_atom> | <domain_literal> <token: domain_literal> <CFWS>? \[ (?: <FWS>? <[dcontent]>)* <FWS>? <token: dcontent> <dtext> | <quoted_pair> <token: dtext> <.NO_WS_CTL> | [\x21-\x5a\x5e-\x7e] <token: atext> <.ALPHA> | <.DIGIT> | [!#\$%&'*+-/=?^_`{|}~] <token: atom> <.CFWS>? <.atext>+ <.CFWS>? <token: dot_atom> <.CFWS>? <.dot_atom_text> <.CFWS>? <token: dot_atom_text> <.atext>+ (?: \. <.atext>+)* <token: text> [\x01-\x09\x0b\x0c\x0e-\x7f] <token: quoted_pair> \\ <.text> <token: qtext> <.NO_WS_CTL> | [\x21\x23-\x5b\x5d-\x7e] <token: qcontent> <.qtext> | <.quoted_pair> <token: quoted_string> <.CFWS>? <.DQUOTE> (?:<.FWS>? <.qcontent>)* <.FWS>? <.DQUOTE> <.CFWS>? <token: word> <.atom> | <.quoted_string> <token: phrase> <.word>+ # Folding white space <token: FWS> (?: <.WSP>* <.CRLF>)? <.WSP>+ <token: ctext> <.NO_WS_CTL> | [\x21-\x27\x2a-\x5b\x5d-\x7e] <token: ccontent> <.ctext> | <.quoted_pair> | <.comment> <token: comment> \( (?: <.FWS>? <.ccontent>)* <.FWS>? \) <token: CFWS> (?: <.FWS>? <.comment>)* (?: (?:<.FWS>? <.comment>) | <.FWS>) # No whitespace control <token: NO_WS_CTL> [\x01-\x08\x0b\x0c\x0e-\x1f\x7f] <token: ALPHA> [A-Za-z] <token: DIGIT> [0-9] <token: CRLF> \x0d \x0a <token: DQUOTE> " <token: WSP> [\x20\x09] }x; }; while (my $input = <>) { if ($input =~ $rfc5322) { say Dumper \%/; # ...the parse tree of any successful match # appears in this punctuation variable } }
Как видите, используя в шаблоне несколько иную нотацию, вы теперь получаете то, что хранит все дерево синтаксического анализа в
%/
переменной, со всем аккуратно помеченным. Результатом преобразования остается узор, как вы можете видеть по=~
оператору. Это просто немного волшебно.источник
((DEFINE)…)
идея чрезвычайно мощна и полезна, позволяя отделить объявление (и его порядок) от выполнения, как и все программирование сверху вниз. Я не могу вспомнить, в каких других языках есть групповая рекурсия; это может быть что-то экзотическое, например C♯ или ему подобное.