Regex validando regex [fechado]

17

Crie um regex que aceite uma string regex como entrada e verifique se é válido. Basicamente, seu regex deve poder se validar. (Qualquer regex inválido não deve ser validado, portanto você não pode usá-lo .*.;)

Seu sabor deve ser totalmente suportado por implementações conhecidas (Perl, sed, grep, gawk, etc.) e deve suportar totalmente o que essas implementações suportam. [Não se preocupe com o advogado falar; Estou apenas tentando remover possíveis brechas para os espertos.]

Eu daria um código de golfe , mas estou preocupado que isso dê vantagem a quem conhece e usa sabores que não são ricos em recursos. Ou minhas preocupações são infundadas?

code-challenge code-golf code-golf game sudoku code-challenge math ai-player code-challenge sorting rosetta-stone code-challenge code-challenge programming-puzzle code-golf number code-golf maze code-golf math regular-expression code-golf sequence code-golf graph-theory code-golf string word-puzzle natural-language brainfuck metagolf optimized-output fastest-algorithm code-golf game-of-life cellular-automata code-golf puzzle-solver grid code-golf combinatorics binary-tree popularity-contest code-challenge code-golf ascii-art kolmogorov-complexity brainfuck metagolf code-golf c date code-golf word-puzzle crossword word-search code-golf code-golf quine code-golf string random Mateen Ulhaq
fonte
8
não for possível, os suportes de aninhamento arbitrário fazer uma regex uma gramática livre de contexto, (substituindo-o por uma notação polonês também precisa de uma pilha)
catraca aberração
@ratchet Augh, você pode estar certo.
Mateen Ulhaq
11
algumas extensões sobre as linguagens regulares existem que podem permitir combinar os colchetes, mas não sei como fazê-lo
catraca aberração
8
É possível que seja possível com as expressões regulares do Perl.
Peter Taylor
11
As expressões regulares do @BrianVandenberg implementadas nos idiomas modernos praticamente não são regulares ... assim que você adiciona referências anteriores, é possível corresponder aos idiomas não regulares. Além disso, o Perl / PCRE e o .NET são poderosos o suficiente para corresponder ao aninhamento correto.
Martin Ender

Respostas:

22

Rubi

Tentei igualar a sintaxe real do sabor de regex de Ruby, tanto quanto possível, mas existem algumas peculiaridades: ele aceita alguns lookbehinds que são realmente inválidos (like (?<=(?<!))) e reconhece intervalos de caracteres vazios como D-A. O último pode ser corrigido para ASCII, mas o regex é longo o suficiente.

\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

Versão ilegível:

\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
fonte
28
Eles não são a versão ilegível?
Kibbee
2
@Kibbee O primeiro é razoavelmente legível se você conhece bem a regex.
Lowjacker 8/09/11
11
Como isso garante que não haja referências remotas numéricas inválidas?
Martin Ender
11
Eu acho que não. Por outro lado, não é a única limitação que possui (veja acima). Algumas coisas poderiam ser consertadas, mas a regex se tornaria ridiculamente longa.
Lowjacker