Die Erkennungsleistung von „modernen“ Regexes

StackOverflow https://stackoverflow.com/questions/4840988

Frage

Was Klasse von Sprachen werden echte moderne Regexes eigentlich erkennen?

Jedes Mal, wenn es eine unbeschränkte Länge Erfassungsgruppe mit einem Rückverweis (z (.*)_\1) ein regex nun eine nicht reguläre Sprache entsprechen. Aber dies auf seinem eigenen, ist nicht genug, um so etwas wie S ::= '(' S ')' | ε passen -. Die kontextfreie Sprache der passenden Paare von parens

rekursive Regexes (die mir neu sind, aber ich bin überzeugt, gibt es in Perl und PCRE) erscheinen zumindest die meisten CFL zu erkennen.

Hat jemand getan oder lesen jede Forschung in diesem Bereich? Was sind die Grenzen dieser „modernen“ reguläre Ausdrücke? Haben sie erkennen streng mehr oder streng weniger als CFG, von LL oder LR Grammatiken? Oder gibt es beiden Sprachen, die von einem regulären Ausdruck erkannt werden können, aber kein CFG und das Gegenteil?

Links zu relevanten Papiere würde sehr geschätzt werden.

War es hilfreich?

Lösung

Muster Rekursion

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

Das ist in Ordnung für eine Vielzahl von Problemen, aber wenn Sie wollen rekursiven Abstieg tatsächlich tun Parsing , müssen Sie Capture-Gruppen hier einfügen und dort, und es ist umständlich die volle Parse-Struktur zu erholen auf diese Weise. Damian Conways Regexp :: Grammatiken Modul für Perl verwandelt das einfache Muster in ein äquivalentes eines, das automatisch tut alles, was in eine rekursiven Datenstruktur namens Erfassung, für viele einfachen Abruf der analysierten Struktur zu machen. Ich habe eine Probe diese beiden Ansätze am Ende dieses Beitrages zu vergleichen.

Einschränkungen für Rekursion

Die Frage war, welche Arten von Grammatiken, dass rekursive Muster übereinstimmen können. Nun, sie sind sicherlich rekursiven Abstiegs Typ Matcher. Das einzige, was in den Sinn kommt, ist, dass die rekursive Muster nicht Linksrekursion verarbeiten kann. , dass man sie anwenden kann. Manchmal können Sie Ihre Produktionen neu ordnen zu Linksrekursion beseitigen.

BTW, PCRE und Perl unterscheiden sich geringfügig ab, wie Sie die Rekursion Begriff erlaubt sind. Siehe die Abschnitte „RECURSIVE patterns“ und „Recursion Unterschied von Perl“ in dem pcrepattern manpage. zB:. Perl kann ^(.|(.)(?1)\2)$ behandeln, in denen PCRE erfordert ^((.)(?1)\2|.)$ statt

Rekursion Demos

Die Notwendigkeit für rekursive Muster entsteht überraschend häufig. Ein gut besuchten Beispiel ist, wenn Sie passen müssen etwas, das Nest, wie ausgeglichen Klammern, Anführungszeichen oder sogar HTML / XML-Tags. Hier ist das Spiel für balenced Pars: 

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

Ich finde, dass trickier wegen seiner kompakten Natur zu lesen. Dies ist leicht heilbar mit /x Modus machen Leerzeichen nicht mehr von Bedeutung: 

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

Dann wieder, da wir Pars für unsere Rekursion verwenden, ein deutlicheres Beispiel wäre verschachtelte einfache Anführungszeichen passend: 

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

Eine andere rekursiv definiert, was Sie Spiel wünschen kann wäre ein Palindrom sein. Dieses einfache Muster funktioniert in Perl: 

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

, die Sie auf den meisten Systemen mit so etwas wie dies testen: 

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

Beachten Sie, dass PCRE-Implementierung von Rekursion erfordert die aufwändigere 

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

Dies ist wegen der Einschränkungen, wie PCRE Rekursion funktioniert.

Proper Parsing

Für mich über die Beispiele sind meist Spielzeug Streichhölzer, nicht alle , die interessant, wirklich. Wenn es wird interessant, wenn Sie eine echte Grammatik haben Sie versuchen zu analysieren. Zum Beispiel, RFC 5322 definiert eine Mail-Adresse ziemlich aufwendig. Hier ist ein „grammatische“ -Muster es zum Spiel: 

$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, die sehr ist BNF-like. Das Problem ist, es ist nur ein Spiel, kein Capture. Und Sie wollen wirklich nicht nur die ganze Sache mit der Erfassung Pars umgeben, weil das Ihnen nicht sagen, welche Produktion abgestimmt, welchen Teil. Unter Verwendung der zuvor erwähnten Regexp :: Grammatiken Modul, wir können. 

#!/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, durch eine sehr leicht unterschiedlichen Schreibweisen im Muster verwenden, erhalten Sie jetzt etwas, das den gesamten Parsing-Baum weg für Sie in der %/ Variable speichert, mit allem, was ordentlich beschriftet. Das Ergebnis der Transformation ist immer noch ein Muster, wie Sie durch den =~ Bediener sehen können. Es ist nur ein bisschen magisch.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top