Regex validating regex [geschlossen]

17

Erstellen Sie einen regulären Ausdruck, der einen regulären Ausdruck als Eingabe akzeptiert, und überprüfen Sie, ob dieser gültig ist. Grundsätzlich sollte Ihr Regex in der Lage sein, sich selbst zu validieren. (Ungültige reguläre Ausdrücke sollten nicht validiert werden, daher können Sie sie nicht verwenden .*.;))

Ihre Version muss von bekannten Implementierungen (Perl, sed, grep, gawk usw.) vollständig unterstützt werden und die von diesen Implementierungen unterstützten Funktionen müssen vollständig unterstützt werden. [Mach dir keine Sorgen über den Anwalt sprechen; Ich versuche nur, mögliche Schlupflöcher für die Schlauen zu beseitigen.]


Ich würde es mit , aber ich bin besorgt, dass es denjenigen einen Vorteil verschafft, die nicht funktionsreiche Aromen kennen und verwenden. Oder sind meine Sorgen unbegründet?

Mateen Ulhaq
quelle
8
nicht möglich, die willkürlichen Klammern machen eine Regex zu einer kontextfreien Grammatik (das Ersetzen durch eine polnische Notation erfordert auch einen Stapel)
Ratschenfreak
@ratchet Augh, du könntest recht haben.
Mateen Ulhaq
1
Es gibt einige Erweiterungen der regulären Sprachen, mit denen die Klammern übereinstimmen können, aber ich weiß nicht, wie das geht
Ratschenfreak
8
Mit regulären Ausdrücken von Perl ist das möglich.
Peter Taylor
1
@BrianVandenberg In modernen Sprachen implementierte reguläre Ausdrücke sind so gut wie nicht regulär. Sobald Sie Rückverweise hinzufügen, können Sie nicht reguläre Sprachen zuordnen. Darüber hinaus sind sowohl Perl / PCRE als auch .NET leistungsfähig genug, um der korrekten Verschachtelung zu entsprechen.
Martin Ender

Antworten:

22

Rubin

Ich habe versucht, die tatsächliche Syntax von Rubys Regex-Variante so gut wie möglich zuzuordnen, aber es gibt ein paar Besonderheiten: Es akzeptiert ein paar Lookbehinds, die tatsächlich ungültig (wie (?<=(?<!))) sind, und es erkennt leere Zeichenbereiche wie D-A. Letzteres könnte für ASCII behoben werden, aber der reguläre Ausdruck ist lang genug.

\A(?<main>
    (?!
        \{(\d+)?,(\d+)?\} # do not match lone counted repetition
    )
    (?:
        [^()\[\]\\*+?|<'] | # anything but metacharacters
        (?<cclass>
            \[ \^? (?: # character class
                (?: # character class
                    [^\[\]\\-] | # anything but square brackets,  backslashes or dashes
                    \g<esc> |
                    \[ : \^? (?: # POSIX char-class
                        alnum | alpha | word | blank | cntrl | x?digit | graph | lower | print | punct | space | upper
                    ) : \] |
                    - (?!
                        \\[dwhsDWHS]
                    ) # range / dash not succeeded by a character class
                )+ |
                \g<cclass> # more than one bracket as delimiter
            ) \]
        ) |
        (?<esc>
            \\[^cuxkg] | # any escaped character
            \\x \h\h? | # hex escape
            \\u \h{4} | # Unicode escape
            \\c . # control escape
        ) |
        \\[kg] (?:
            < \w[^>]* (?: > | \Z) |
            ' \w[^']* (?: ' | \Z)
        )? | # named backrefs
        (?<! (?<! \\) \\[kg]) [<'] | # don't match < or ' if preceded by \k or \g
        \| (?! \g<rep> ) | # alternation
        \( (?: # group
            (?:
                \?
                (?:
                    [>:=!] | # atomic / non-capturing / lookahead
                    (?<namedg>
                        < [_a-zA-Z][^>]* > |
                        ' [_a-zA-Z][^']* ' # named group
                    ) |
                    [xmi-]+: # regex options
                )
            )?
            \g<main>*
        ) \) |
        \(\?<[!=] (?<lbpat>
            (?! \{(\d+)?,(\d+)?\} )
            [^()\[\]\\*+?] |
            \g<esc>  (?<! \\[zZ]) |
            \g<cclass> |
            \( (?: # group
                (?:
                    \?: |
                    \? \g<namedg> |
                    \? <[!=]
                )?
                \g<lbpat>*
            ) \) |
            \(\?\# [^)]* \)
        )* \)
        |
        \(\? [xmi-]+ \) # option group
        (?! \g<rep> ) 
        |
        \(\?\# [^)]*+ \) # comment
        (?! \g<rep> )
    )+
    (?<rep>
        (?:
            [*+?] | # repetition
            \{(\d+)?,(\d+)?\} # counted repetition
        )
        [+?]? # with a possessive/lazy modifier
    )?
)*\Z

Unlesbare Version:

\A(?<main>(?!\{(\d+)?,(\d+)?\})(?:[^()\[\]\\*+?|<']|(?<cclass>\[\^?(?:(?:[^\[\]\\-]|\g<esc>|\[:\^?(?:alnum|alpha|word|blank|cntrl|x?digit|graph|lower|print|punct|space|upper):\]|-(?!\\[dwhsDWHS]))+|\g<cclass>)\])|(?<esc>\\[^cuxkg]|\\x\h\h?|\\u\h{4}|\\c.)|\\[kg](?:<\w[^>]*(?:>|\Z)|'\w[^']*(?:'|\Z))?|(?<!(?<!\\)\\[kg])[<']|\|(?!\g<rep>)|\((?:(?:\?(?:[>:=!]|(?<namedg><[_a-zA-Z][^>]*>|'[_a-zA-Z][^']*')|[xmi-]+:))?\g<main>*)\)|\(\?<[!=](?<lbpat>(?!\{(\d+)?,(\d+)?\})[^()\[\]\\*+?]|\g<esc>(?<!\\[zZ])|\g<cclass>|\((?:(?:\?:|\?\g<namedg>|\?<[!=])?\g<lbpat>*)\)|\(\?#[^)]*\))*\)|\(\?[xmi-]+\)(?!\g<rep>)|\(\?#[^)]*+\)(?!\g<rep>))+(?<rep>(?:[*+?]|\{(\d+)?,(\d+)?\})[+?]?)?)*\Z
Lowjacker
quelle
28
Sind sie nicht beide die unlesbare Version?
Kibbee
2
@ Kibbee Der erste ist einigermaßen lesbar, wenn Sie Regex gut kennen.
Lowjacker
1
Wie wird sichergestellt, dass keine ungültigen numerischen Rückverweise vorhanden sind?
Martin Ender
1
Ich denke nicht. Andererseits ist dies nicht die einzige Einschränkung (siehe oben). Einige Dinge könnten behoben werden, aber der reguläre Ausdruck würde lächerlich lang werden.
Lowjacker