Распознающая сила “современных” регулярных выражений

Question

Какой класс языков на самом деле распознают реальные современные регулярные выражения?

Всякий раз, когда существует группа захвата неограниченной длины с обратной ссылкой (например (.*)_\1) регулярное выражение теперь соответствует нерегулярному языку.Но этого самого по себе недостаточно, чтобы соответствовать чему-то вроде S ::= '(' S ')' | ε — контекстно-свободный язык сопоставления пар скобок.

Рекурсивные регулярные выражения (которые являются новыми для меня, но я уверен, что они существуют в Perl и PCRE), похоже, распознают по крайней мере большинство CFLS.

Кто-нибудь проводил или читал какие-либо исследования в этой области?Каковы ограничения этих "современных" регулярных выражений?Распознают ли они строго больше или строго меньше, чем CFG, грамматик LL или LR?Или существуют ли оба языка, которые могут быть распознаны регулярным выражением, но не CFG и противоположное?

Мы были бы весьма признательны за ссылки на соответствующие документы.

Answer 1

Рекурсия шаблона

С рекурсивными шаблонами у вас есть форма рекурсивного спуска соответствие.

Это прекрасно подходит для решения множества задач, но как только вы захотите действительно выполнить рекурсивный спуск синтаксический анализ, вам нужно вставлять группы захвата здесь и там, и таким образом неудобно восстанавливать полную структуру синтаксического анализа.Дэмиан Конвей Регулярное выражение::Грамматики модуль для Perl преобразует простой шаблон в эквивалентный, который автоматически выполняет все, что называется захватом в рекурсивную структуру данных, что значительно упрощает извлечение проанализированной структуры.У меня есть пример сравнения этих двух подходов в конце этой публикации.

Ограничения на рекурсию

Вопрос заключался в том, каким типам грамматик могут соответствовать рекурсивные шаблоны.Что ж, они, безусловно, рекурсивный спуск сопоставители типов.Единственное, что приходит на ум, это то, что рекурсивные шаблоны не могут обрабатывать левая рекурсия. Это накладывает ограничение на типы грамматик, к которым вы можете их применять.Иногда вы можете изменить порядок своих работ, чтобы исключить левую рекурсию.

Кстати, PCRE и Perl немного отличаются в том, как вам разрешено формулировать рекурсию.Смотрите разделы “РЕКУРСИВНЫЕ ШАБЛОНЫ” и “Отличие рекурсии от Perl” в шаблон для ПК справочная страница.например: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) | (?&quoted_string))
     (?<domain>          (?&dot_atom) | (?&domain_literal))
     (?<domain_literal>  (?&CFWS)? \[ (?: (?&FWS)? (?&dcontent))* (?&FWS)?
                                   \] (?&CFWS)?)
     (?<dcontent>        (?&dtext) | (?&quoted_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) | (?&quoted_pair))
     (?<quoted_string>   (?&CFWS)? (?&DQUOTE) (?:(?&FWS)? (?&qcontent))*
                          (?&FWS)? (?&DQUOTE) (?&CFWS)?)

     (?<word>            (?&atom) | (?&quoted_string))
     (?<phrase>          (?&word)+)

     # Folding white space
     (?<FWS>             (?: (?&WSP)* (?&CRLF))? (?&WSP)+)
     (?<ctext>           (?&NO_WS_CTL) | [\x21-\x27\x2a-\x5b\x5d-\x7e])
     (?<ccontent>        (?&ctext) | (?&quoted_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
    }
}

Как вы видите, используя совсем немного другую нотацию в шаблоне, теперь вы получаете нечто, что сохраняет все дерево синтаксического анализа для вас в %/ переменная, со всем аккуратно помеченным.Результатом преобразования по-прежнему является шаблон, как вы можете видеть по =~ оператор.Это просто немного волшебно.