Welche Klasse von Sprachen erkennen echte moderne Regexe tatsächlich?

Immer wenn es eine Erfassungsgruppe mit unbegrenzter Länge und (.*)_\1einer Rückreferenz gibt (z. B. ), stimmt ein regulärer Ausdruck jetzt mit einer nicht regulären Sprache überein. Dies allein reicht jedoch nicht aus, um so etwas wie S ::= '(' S ')' | εdie kontextfreie Sprache passender Elternpaare zu erreichen.

Rekursive Regexes (die für mich neu sind, aber ich bin sicher, dass sie in Perl und PCRE existieren) scheinen zumindest die meisten CFLs zu erkennen.

Hat jemand in diesem Bereich Nachforschungen angestellt oder gelesen? Was sind die Grenzen dieser "modernen" Regexe? Erkennen sie streng mehr oder weniger als CFGs von LL- oder LR-Grammatiken? Oder gibt es beide Sprachen, die von einem regulären Ausdruck erkannt werden können, aber keine CFG und das Gegenteil?

Links zu relevanten Artikeln wären sehr dankbar.

Musterrekursion

Mit rekursiven Muster, haben Sie eine Form der rekursiven Abstiegs Anpassung .

Das ist in Ordnung für eine Vielzahl von Problemen, aber wenn man tatsächlich rekursive Abstieg tun möge Parsing , müssen Sie Capture - Gruppen hier einfügen und dort, und es ist umständlich die volle Parse - Struktur auf diese Weise zu erholen. Das Regexp :: Grammars- Modul von Damian Conway für Perl wandelt das einfache Muster in ein äquivalentes Muster um, das automatisch alle genannten Namen in eine rekursive Datenstruktur umwandelt, wodurch das Abrufen der analysierten Struktur erheblich vereinfacht wird. Ich habe ein Beispiel, das diese beiden Ansätze am Ende dieses Beitrags vergleicht.

Rekursionsbeschränkungen

Die Frage war, welche Arten von Grammatiken mit rekursiven Mustern übereinstimmen können. Nun, sie sind sicherlich rekursive Abstiegs- Matcher. Das einzige, was mir in den Sinn kommt, ist, dass rekursive Muster die linke Rekursion nicht verarbeiten können . Dies schränkt die Art der Grammatiken ein, auf die Sie sie anwenden können. Manchmal können Sie Ihre Produktionen neu anordnen, um die linke Rekursion zu vermeiden.

Übrigens unterscheiden sich PCRE und Perl geringfügig darin, wie Sie die Rekursion formulieren dürfen. Siehe die Abschnitte zu „RECURSIVE PATTERNS“ und „Recursion Difference from Perl“ in der Manpage pcrepattern . Beispiel: Perl kann damit umgehen, ^(.|(.)(?1)\2)$wo PCRE es erfordert ^((.)(?1)\2|.)$.

Rekursionsdemos

Der Bedarf an rekursiven Mustern tritt überraschend häufig auf. Ein gut besuchtes Beispiel ist, wenn Sie etwas finden müssen, das verschachtelt werden kann, z. B. ausgeglichene Klammern, Anführungszeichen oder sogar HTML / XML-Tags. Hier ist das Match für balenced parens:

\((?:[^()]*+|(?0))*\)

Ich finde das schwieriger zu lesen, weil es kompakt ist. Dies kann im /xModus leicht behoben werden, sodass Leerzeichen nicht mehr von Bedeutung sind:

\( (?: [^()] *+ | (?0) )* \)

Da wir für unsere Rekursion Parens verwenden, wäre ein klareres Beispiel das Abgleichen verschachtelter einfacher Anführungszeichen:

‘ (?: [^‘’] *+ | (?0) )* ’

Eine andere rekursiv definierte Sache, die Sie möglicherweise anpassen möchten, wäre ein Palindrom. Dieses einfache Muster funktioniert in Perl:

^((.)(?1)\2|.?)$

was Sie auf den meisten Systemen mit so etwas testen können:

$ perl -nle 'print if /^((.)(?1)\2|.?)$/i' /usr/share/dict/words

Beachten Sie, dass die Implementierung der Rekursion durch PCRE aufwändiger ist

^(?:((.)(?1)\2|)|((.)(?3)\4|.))

Dies liegt an Einschränkungen bei der Funktionsweise der PCRE-Rekursion.

Richtiges Parsen

Für mich sind die obigen Beispiele meistens Spielzeug-Streichhölzer, eigentlich gar nicht so interessant. Wenn es interessant wird, wenn Sie eine echte Grammatik haben, versuchen Sie zu analysieren. Beispielsweise definiert RFC 5322 eine E-Mail-Adresse ziemlich ausführlich. Hier ist ein "grammatikalisches" Muster, das dazu passt:

$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;

Wie Sie sehen, ist das sehr BNF-ähnlich. Das Problem ist, dass es sich nur um ein Match handelt, nicht um eine Erfassung. Und du willst das Ganze wirklich nicht nur mit dem Erfassen von Parens umgeben, denn das sagt dir nicht, welche Produktion zu welchem ​​Teil passt. Mit dem zuvor erwähnten Regexp :: Grammars-Modul können wir.

#!/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
    }
}

Wie Sie sehen, erhalten Sie durch die Verwendung einer etwas anderen Notation im Muster jetzt etwas, das den gesamten Analysebaum für Sie in der %/Variablen speichert , wobei alles ordentlich beschriftet ist. Das Ergebnis der Transformation ist immer noch ein Muster, wie Sie vom =~Operator sehen können. Es ist nur ein bisschen magisch.