Existe uma expressão regular para detectar uma expressão regular válida?

1007

É possível detectar uma expressão regular válida com outra expressão regular? Se sim, por favor, dê o código de exemplo abaixo.

psytek
fonte
58
Portanto, seu problema é validar uma regex, você escolheu uma regex para resolvê-la. Gostaria de saber se a propriedade de aumento de número de problemas de expressões regulares é aditiva ou multiplicativa. Parece que 4 problemas em vez de 2 :)
abesto
15
Existem muitas notações para expressões regulares - alguns recursos e suas grafias são comuns à maioria, outros são escritos de maneira diferente ou estão disponíveis apenas em uma notação específica. A maioria dessas notações não é "regular" no sentido gramatical regular - você precisaria de um analisador sem contexto para lidar com o agrupamento ilimitado de subexpressões - embora muitas notações modernas de "expressão regular" tenham extensões que vão além da definição formal original e pode permitir que suas próprias notações sejam reconhecidas. De qualquer forma, por que não perguntar à sua biblioteca de regex se cada regex é válido?
Steve314
1
@bevacqua eu preciso validar regexp no esquema XML. Como posso fazer isso sem outra regexp?
Zenden2k 9/09/2015
3
Na verdade, compile / execute o regex (padrão) a ser verificado, sob um mecanismo de tratamento de exceções que seu idioma possui. Portanto, o próprio mecanismo de regex / compilador do idioma verificará isso. (Isso pressupõe a sintaxe básica correta para que o programa seja executado, mas isso pode ser incluído na verificação usando os recursos de seus idiomas para avaliar a cadeia de caracteres para o regex como código (possivelmente sintaticamente errado) ou algo assim.)
zdim
Esta é a resposta perfeita para os usuários Python: stackoverflow.com/questions/19630994/...
Gianni

Respostas:

979
/
^                                             # start of string
(                                             # first group start
  (?:
    (?:[^?+*{}()[\]\\|]+                      # literals and ^, $
     | \\.                                    # escaped characters
     | \[ (?: \^?\\. | \^[^\\] | [^\\^] )     # character classes
          (?: [^\]\\]+ | \\. )* \]
     | \( (?:\?[:=!]|\?<[=!]|\?>)? (?1)?? \)  # parenthesis, with recursive content
     | \(\? (?:R|[+-]?\d+) \)                 # recursive matching
     )
    (?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )?   # quantifiers
  | \|                                        # alternative
  )*                                          # repeat content
)                                             # end first group
$                                             # end of string
/

Este é um regex recursivo e não é suportado por muitos mecanismos de regex. Os baseados em PCRE devem apoiá-lo.

Sem espaço em branco e comentários:

/^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*)$/

O .NET não suporta recursão diretamente. (As construções (?1)e (?R).) A recursão teria que ser convertida na contagem de grupos equilibrados:

^                                         # start of string
(?:
  (?: [^?+*{}()[\]\\|]+                   # literals and ^, $
   | \\.                                  # escaped characters
   | \[ (?: \^?\\. | \^[^\\] | [^\\^] )   # character classes
        (?: [^\]\\]+ | \\. )* \]
   | \( (?:\?[:=!]
         | \?<[=!]
         | \?>
         | \?<[^\W\d]\w*>
         | \?'[^\W\d]\w*'
         )?                               # opening of group
     (?<N>)                               #   increment counter
   | \)                                   # closing of group
     (?<-N>)                              #   decrement counter
   )
  (?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )? # quantifiers
| \|                                      # alternative
)*                                        # repeat content
$                                         # end of string
(?(N)(?!))                                # fail if counter is non-zero.

Compactado:

^(?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>|\?<[^\W\d]\w*>|\?'[^\W\d]\w*')?(?<N>)|\)(?<-N>))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*$(?(N)(?!))

Dos comentários:

Isso validará substituições e traduções?

Ele validará apenas a parte regular de substituições e traduções. s/<this part>/.../

Teoricamente, não é possível combinar todas as gramáticas válidas de regex com uma regex.

É possível se o mecanismo regex suportar recursão, como PCRE, mas isso não puder mais ser chamado de expressões regulares.

De fato, uma "expressão regular recursiva" não é uma expressão regular. Mas essa é uma extensão geralmente aceita para mecanismos de regex ... Ironicamente, esse regex estendido não corresponde a regexes estendidas.

"Na teoria, teoria e prática são iguais. Na prática, não são". Quase todo mundo que conhece expressões regulares sabe que expressões regulares não suportam recursão. Mas o PCRE e a maioria das outras implementações suportam muito mais do que expressões regulares básicas.

usando isso com o script shell no comando grep, ele mostra um erro .. grep: conteúdo inválido de {}. Eu estou criando um script que poderia grep uma base de código para encontrar todos os arquivos que contêm expressões regulares

Esse padrão explora uma extensão chamada expressões regulares recursivas. Isso não é suportado pelo sabor POSEX da regex. Você pode tentar com a opção -P para ativar o sabor de regex PCRE.

O próprio Regex "não é uma linguagem regular e, portanto, não pode ser analisado por expressões regulares ..."

Isso é verdade para expressões regulares clássicas. Algumas implementações modernas permitem recursão, o que a torna uma linguagem livre de contexto, embora seja um pouco detalhada para esta tarefa.

Eu vejo onde você está combinando []()/\. e outros caracteres regex especiais. Onde você está permitindo caracteres não especiais? Parece que isso vai combinar ^(?:[\.]+)$, mas não ^abcdefg$. Esse é um regex válido.

[^?+*{}()[\]\\|]corresponderá a qualquer caractere único, não parte de nenhuma das outras construções. Isso inclui tanto literal ( a- z), e determinados caracteres especiais ( ^, $, .).

Markus Jarderot
fonte
10
Esta resposta envia as pessoas completamente na direção errada. Eles nunca devem usar regEx para localizar expressões regulares, porque ele não pode funcionar corretamente em todos os casos. Veja minha resposta adicionada.
Vitaly-t
1
.{,1}é incomparável. Mude para ^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d*(?:,\d*)?\})[?+]?)?|\|)*)$correspondências. Mudar \d+para\d*
yunzen
4
regex por def não deve ter recursão, pelo menos diga algo assim em sua resposta, seu mecanismo de regex provavelmente é "muito poderoso" e não é realmente um mecanismo de regex.
Charlie Parker
Apenas uma nota que você esqueceu a bandeira x
RedClover 31/08
Esse validador parece ter sido feito para expressões PCRE, mas passará muitos EREs POSIX inválidos. Notavelmente, eles são um pouco mais exigente em intervalos de classe de caracteres, por exemplo, isso é válido em PCRE mas não em ERE: [a-b-c].
Pedro Gimeno
321

Improvável.

Avalie-o em um try..catchou o que o seu idioma fornecer.

Dan
fonte
228

Não, se você estiver falando estritamente sobre expressões regulares e não incluindo algumas implementações de expressão regular que são na verdade gramáticas livres de contexto.

Há uma limitação de expressões regulares que torna impossível escrever uma regex que corresponda a todas e somente regexes. Você não pode corresponder a implementações como chaves que estão emparelhadas. Regexes usam muitas dessas construções, vamos tomar []como exemplo. Sempre que houver um [, deve haver uma correspondência ], o que é bastante simples para uma regex "\[.*\]".

O que torna impossível para as expressões regulares é que elas podem ser aninhadas. Como você pode escrever uma regex que corresponda a colchetes aninhados? A resposta é que você não pode sem uma regex infinitamente longa. Você pode corresponder a qualquer número de parênteses aninhados através da força bruta, mas nunca pode corresponder a um conjunto arbitrariamente longo de colchetes aninhados.

Esse recurso costuma ser chamado de contagem, porque você está contando a profundidade do aninhamento. Um regex por definição não tem a capacidade de contar.


Acabei escrevendo " Limitações de expressão regular " sobre isso.

JaredPar
fonte
53

Boa pergunta.

Os idiomas regulares verdadeiros não podem decidir entre parênteses bem formados aninhados arbitrariamente profundamente. Se o seu alfabeto contiver '('e ')'o objetivo for decidir se uma sequência destes possui parênteses correspondentes bem formados. Como esse é um requisito necessário para expressões regulares, a resposta é não.

No entanto, se você soltar o requisito e adicionar recursão, provavelmente poderá fazê-lo. O motivo é que a recursão pode atuar como uma pilha, permitindo que você "conte" a profundidade atual do aninhamento pressionando essa pilha.

Russ Cox escreveu " A correspondência de expressão regular pode ser simples e rápida ", que é um maravilhoso tratado sobre a implementação do mecanismo de expressão regular .

EU RESPONDO AO CRAP
fonte
16

Não, se você usar expressões regulares padrão.

O motivo é que você não pode satisfazer o lema de bombeamento para idiomas regulares. Os estados Pumping Lemma que uma string pertencente à linguagem "L" é regular se existe um número "N" tal que, depois de dividir a string em três substrings x, y, z, de tal forma que |x|>=1 && |xy|<=N, você pode repetir yquantas vezes quiser eo a string inteira ainda pertencerá L.

Uma conseqüência do lema de bombeamento é que você não pode ter cadeias regulares no formulário a^Nb^Mc^N, ou seja, duas substrings com o mesmo comprimento separadas por outra cadeia. De qualquer maneira que você dividir essas cordas em x, ye z, você não pode "bomba" ysem a obtenção de uma string com um número diferente de "a" e "c", deixando assim a língua original. É o caso, por exemplo, de parênteses em expressões regulares.

Davide Visentin
fonte
5
Essa não é uma descrição muito precisa do lema de bombeamento. Primeiro, é toda a linguagem que pode ser regular ou não, e não uma única string. Segundo, é uma condição necessária, e não suficiente, para regularidade. Finalmente, apenas cordas suficientemente longas são bombeáveis.
darij grinberg 08/09/19
13

Embora seja perfeitamente possível usar uma regex recursiva como o MizardX postou, para esse tipo de coisa é muito mais útil um analisador. Regexes foram originalmente projetados para serem usados ​​com idiomas regulares, sendo recursivo ou ter grupos de balanceamento é apenas um patch.

A linguagem que define expressões regulares válidas é, na verdade, uma gramática livre de contexto, e você deve usar um analisador apropriado para manipulá-la. Aqui está um exemplo de um projeto universitário para analisar expressões regulares simples (sem a maioria das construções). Ele usa JavaCC. E sim, os comentários são em espanhol, embora os nomes dos métodos sejam bastante auto-explicativos.

SKIP :
{
    " "
|   "\r"
|   "\t"
|   "\n"
}
TOKEN : 
{
    < DIGITO: ["0" - "9"] >
|   < MAYUSCULA: ["A" - "Z"] >
|   < MINUSCULA: ["a" - "z"] >
|   < LAMBDA: "LAMBDA" >
|   < VACIO: "VACIO" >
}

IRegularExpression Expression() :
{
    IRegularExpression r; 
}
{
    r=Alternation() { return r; }
}

// Matchea disyunciones: ER | ER
IRegularExpression Alternation() :
{
    IRegularExpression r1 = null, r2 = null; 
}
{
    r1=Concatenation() ( "|" r2=Alternation() )?
    { 
        if (r2 == null) {
            return r1;
        } else {
            return createAlternation(r1,r2);
        } 
    }
}

// Matchea concatenaciones: ER.ER
IRegularExpression Concatenation() :
{
    IRegularExpression r1 = null, r2 = null; 
}
{
    r1=Repetition() ( "." r2=Repetition() { r1 = createConcatenation(r1,r2); } )*
    { return r1; }
}

// Matchea repeticiones: ER*
IRegularExpression Repetition() :
{
    IRegularExpression r; 
}
{
    r=Atom() ( "*" { r = createRepetition(r); } )*
    { return r; }
}

// Matchea regex atomicas: (ER), Terminal, Vacio, Lambda
IRegularExpression Atom() :
{
    String t;
    IRegularExpression r;
}
{
    ( "(" r=Expression() ")" {return r;}) 
    | t=Terminal() { return createTerminal(t); }
    | <LAMBDA> { return createLambda(); }
    | <VACIO> { return createEmpty(); }
}

// Matchea un terminal (digito o minuscula) y devuelve su valor
String Terminal() :
{
    Token t;
}
{
    ( t=<DIGITO> | t=<MINUSCULA> ) { return t.image; }
}
Santiago Palladino
fonte
11

Você pode enviar a regex para a preg_matchqual retornará false se a regex não for válida. Não se esqueça de usar o @para suprimir as mensagens de erro:

@preg_match($regexToTest, '');
  • Retornará 1 se o regex for //.
  • Retornará 0 se a regex estiver correta.
  • Caso contrário, retornará falso.
Richard - Rogue Wave Limited Empresas
fonte
6

O exemplo a seguir de Paul McGuire, originalmente do wiki pyparsing, mas agora disponível apenas na Wayback Machine , fornece uma gramática para analisar algumas regexes, com o objetivo de retornar o conjunto de strings correspondentes. Como tal, rejeita aqueles re que incluem termos de repetição ilimitada, como '+' e '*'. Mas você deve ter uma idéia de como estruturar um analisador que processaria re's.

# 
# invRegex.py
#
# Copyright 2008, Paul McGuire
#
# pyparsing script to expand a regular expression into all possible matching strings
# Supports:
# - {n} and {m,n} repetition, but not unbounded + or * repetition
# - ? optional elements
# - [] character ranges
# - () grouping
# - | alternation
#
__all__ = ["count","invert"]

from pyparsing import (Literal, oneOf, printables, ParserElement, Combine, 
    SkipTo, operatorPrecedence, ParseFatalException, Word, nums, opAssoc,
    Suppress, ParseResults, srange)

class CharacterRangeEmitter(object):
    def __init__(self,chars):
        # remove duplicate chars in character range, but preserve original order
        seen = set()
        self.charset = "".join( seen.add(c) or c for c in chars if c not in seen )
    def __str__(self):
        return '['+self.charset+']'
    def __repr__(self):
        return '['+self.charset+']'
    def makeGenerator(self):
        def genChars():
            for s in self.charset:
                yield s
        return genChars

class OptionalEmitter(object):
    def __init__(self,expr):
        self.expr = expr
    def makeGenerator(self):
        def optionalGen():
            yield ""
            for s in self.expr.makeGenerator()():
                yield s
        return optionalGen

class DotEmitter(object):
    def makeGenerator(self):
        def dotGen():
            for c in printables:
                yield c
        return dotGen

class GroupEmitter(object):
    def __init__(self,exprs):
        self.exprs = ParseResults(exprs)
    def makeGenerator(self):
        def groupGen():
            def recurseList(elist):
                if len(elist)==1:
                    for s in elist[0].makeGenerator()():
                        yield s
                else:
                    for s in elist[0].makeGenerator()():
                        for s2 in recurseList(elist[1:]):
                            yield s + s2
            if self.exprs:
                for s in recurseList(self.exprs):
                    yield s
        return groupGen

class AlternativeEmitter(object):
    def __init__(self,exprs):
        self.exprs = exprs
    def makeGenerator(self):
        def altGen():
            for e in self.exprs:
                for s in e.makeGenerator()():
                    yield s
        return altGen

class LiteralEmitter(object):
    def __init__(self,lit):
        self.lit = lit
    def __str__(self):
        return "Lit:"+self.lit
    def __repr__(self):
        return "Lit:"+self.lit
    def makeGenerator(self):
        def litGen():
            yield self.lit
        return litGen

def handleRange(toks):
    return CharacterRangeEmitter(srange(toks[0]))

def handleRepetition(toks):
    toks=toks[0]
    if toks[1] in "*+":
        raise ParseFatalException("",0,"unbounded repetition operators not supported")
    if toks[1] == "?":
        return OptionalEmitter(toks[0])
    if "count" in toks:
        return GroupEmitter([toks[0]] * int(toks.count))
    if "minCount" in toks:
        mincount = int(toks.minCount)
        maxcount = int(toks.maxCount)
        optcount = maxcount - mincount
        if optcount:
            opt = OptionalEmitter(toks[0])
            for i in range(1,optcount):
                opt = OptionalEmitter(GroupEmitter([toks[0],opt]))
            return GroupEmitter([toks[0]] * mincount + [opt])
        else:
            return [toks[0]] * mincount

def handleLiteral(toks):
    lit = ""
    for t in toks:
        if t[0] == "\\":
            if t[1] == "t":
                lit += '\t'
            else:
                lit += t[1]
        else:
            lit += t
    return LiteralEmitter(lit)    

def handleMacro(toks):
    macroChar = toks[0][1]
    if macroChar == "d":
        return CharacterRangeEmitter("0123456789")
    elif macroChar == "w":
        return CharacterRangeEmitter(srange("[A-Za-z0-9_]"))
    elif macroChar == "s":
        return LiteralEmitter(" ")
    else:
        raise ParseFatalException("",0,"unsupported macro character (" + macroChar + ")")

def handleSequence(toks):
    return GroupEmitter(toks[0])

def handleDot():
    return CharacterRangeEmitter(printables)

def handleAlternative(toks):
    return AlternativeEmitter(toks[0])


_parser = None
def parser():
    global _parser
    if _parser is None:
        ParserElement.setDefaultWhitespaceChars("")
        lbrack,rbrack,lbrace,rbrace,lparen,rparen = map(Literal,"[]{}()")

        reMacro = Combine("\\" + oneOf(list("dws")))
        escapedChar = ~reMacro + Combine("\\" + oneOf(list(printables)))
        reLiteralChar = "".join(c for c in printables if c not in r"\[]{}().*?+|") + " \t"

        reRange = Combine(lbrack + SkipTo(rbrack,ignore=escapedChar) + rbrack)
        reLiteral = ( escapedChar | oneOf(list(reLiteralChar)) )
        reDot = Literal(".")
        repetition = (
            ( lbrace + Word(nums).setResultsName("count") + rbrace ) |
            ( lbrace + Word(nums).setResultsName("minCount")+","+ Word(nums).setResultsName("maxCount") + rbrace ) |
            oneOf(list("*+?")) 
            )

        reRange.setParseAction(handleRange)
        reLiteral.setParseAction(handleLiteral)
        reMacro.setParseAction(handleMacro)
        reDot.setParseAction(handleDot)

        reTerm = ( reLiteral | reRange | reMacro | reDot )
        reExpr = operatorPrecedence( reTerm,
            [
            (repetition, 1, opAssoc.LEFT, handleRepetition),
            (None, 2, opAssoc.LEFT, handleSequence),
            (Suppress('|'), 2, opAssoc.LEFT, handleAlternative),
            ]
            )
        _parser = reExpr

    return _parser

def count(gen):
    """Simple function to count the number of elements returned by a generator."""
    i = 0
    for s in gen:
        i += 1
    return i

def invert(regex):
    """Call this routine as a generator to return all the strings that
       match the input regular expression.
           for s in invert("[A-Z]{3}\d{3}"):
               print s
    """
    invReGenerator = GroupEmitter(parser().parseString(regex)).makeGenerator()
    return invReGenerator()

def main():
    tests = r"""
    [A-EA]
    [A-D]*
    [A-D]{3}
    X[A-C]{3}Y
    X[A-C]{3}\(
    X\d
    foobar\d\d
    foobar{2}
    foobar{2,9}
    fooba[rz]{2}
    (foobar){2}
    ([01]\d)|(2[0-5])
    ([01]\d\d)|(2[0-4]\d)|(25[0-5])
    [A-C]{1,2}
    [A-C]{0,3}
    [A-C]\s[A-C]\s[A-C]
    [A-C]\s?[A-C][A-C]
    [A-C]\s([A-C][A-C])
    [A-C]\s([A-C][A-C])?
    [A-C]{2}\d{2}
    @|TH[12]
    @(@|TH[12])?
    @(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9]))?
    @(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9])|OH(1[0-9]?|2[0-9]?|30?|[4-9]))?
    (([ECMP]|HA|AK)[SD]|HS)T
    [A-CV]{2}
    A[cglmrstu]|B[aehikr]?|C[adeflmorsu]?|D[bsy]|E[rsu]|F[emr]?|G[ade]|H[efgos]?|I[nr]?|Kr?|L[airu]|M[dgnot]|N[abdeiop]?|Os?|P[abdmortu]?|R[abefghnu]|S[bcegimnr]?|T[abcehilm]|Uu[bhopqst]|U|V|W|Xe|Yb?|Z[nr]
    (a|b)|(x|y)
    (a|b) (x|y)
    """.split('\n')

    for t in tests:
        t = t.strip()
        if not t: continue
        print '-'*50
        print t
        try:
            print count(invert(t))
            for s in invert(t):
                print s
        except ParseFatalException,pfe:
            print pfe.msg
            print
            continue
        print

if __name__ == "__main__":
    main()
PaulMcG
fonte