Распознающая сила "современных" регулярных выражений
Какой класс языков действительно распознают современные современные регулярные выражения?
Всякий раз, когда существует группа захвата неограниченной длины с обратной ссылкой (например, (.*)_\1) регулярное выражение теперь соответствует нерегулярному языку. Но одного этого недостаточно, чтобы соответствовать S ::= '(' S ')' | ε - не зависящий от контекста язык пар соответствия.
Рекурсивные регулярные выражения (которые являются новыми для меня, но я уверен, что существуют в Perl и PCRE), по-видимому, распознают по крайней мере большинство CFL.
Кто-нибудь делал или читал какие-либо исследования в этой области? Каковы ограничения этих "современных" регулярных выражений? Распознают ли они строго больше или строго меньше, чем CFG, грамматик LL или LR? Или существуют оба языка, которые могут быть распознаны регулярным выражением, но не CFG, а наоборот?
Ссылки на соответствующие документы будут высоко ценится.
1 ответ
Pattern Recursion
С рекурсивными шаблонами у вас есть форма соответствия рекурсивного спуска.
Это хорошо для множества проблем, но как только вы захотите выполнить рекурсивный анализ спуска, вам нужно вставить группы захвата тут и там, и будет неудобно восстанавливать полную структуру разбора таким образом. Модуль Regexp::Grammars Дамиана Конвея для Perl преобразует простой шаблон в эквивалентный, который автоматически выполняет захват всех этих имен, в рекурсивную структуру данных, что значительно упрощает извлечение проанализированной структуры. У меня есть образец, сравнивающий эти два подхода в конце этой публикации.
Ограничения на рекурсию
Вопрос заключался в том, какие грамматики могут соответствовать рекурсивным шаблонам. Ну, они, конечно, сопоставители типа рекурсивного спуска. Единственное, что приходит на ум, - это то, что рекурсивные шаблоны не могут обрабатывать левую рекурсию. Это накладывает ограничения на виды грамматик, к которым вы можете применять их. Иногда вы можете изменить порядок своей продукции, чтобы исключить левую рекурсию.
Кстати, PCRE и Perl немного отличаются в том, как вам разрешено формулировать рекурсию. См. Разделы "Рекурсивные паттерны" и "Отличие рекурсии от Perl" в справочной странице pcrepattern. например: Perl может обрабатывать ^(.|(.)(?1)\2)$ где требуется PCRE ^((.)(?1)\2|.)$ вместо.
Демоверсии рекурсии
Потребность в рекурсивных шаблонах возникает на удивление часто. Один из наиболее популярных примеров - это когда вам нужно сопоставить что-то, что может быть вложено, например сбалансированные скобки, кавычки или даже теги HTML/XML. Вот матч для балеарных паренов:
\((?:[^()]*+|(?0))*\)
Я считаю, что читать сложнее из-за его компактности. Это легко излечимо с /x режим, чтобы сделать пробел больше не значимым:
\( (?: [^()] *+ | (?0) )* \)
Опять же, так как мы используем parens для нашей рекурсии, более понятным примером будет сопоставление вложенных одинарных кавычек:
‘ (?: [^‘’] *+ | (?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
}
}
Как видите, используя немного отличную запись в шаблоне, вы теперь получаете что-то, что хранит все дерево разбора для вас в %/ переменная, все аккуратно помечено. Результат преобразования по-прежнему является шаблоном, как вы можете видеть по =~ оператор. Это просто немного волшебно.