¿Existe una expresión regular para detectar una expresión regular válida?

¿Es posible detectar una expresión regular válida con otra expresión regular? Si es así, indique el código de ejemplo a continuación.

/
^                                             # 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
/

Esta es una expresión regular recursiva, y no es compatible con muchos motores de expresión regular. Los basados ​​en PCRE deberían ser compatibles.

Sin espacios en blanco y sin comentarios:

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

.NET no admite la recursión directamente. (Las construcciones (?1)y (?R).) La recursión tendría que convertirse a contar 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.

Comprimido:

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

De los comentarios:

¿Esto validará sustituciones y traducciones?

Validará solo la parte regex de las sustituciones y traducciones. s/<this part>/.../

No es teóricamente posible hacer coincidir todas las gramáticas de expresiones regulares válidas con una expresión regular.

Es posible si el motor regex admite la recursión, como PCRE, pero eso ya no se puede llamar expresiones regulares.

De hecho, una "expresión regular recursiva" no es una expresión regular. Pero esta es una extensión a menudo aceptada para motores de expresiones regulares ... Irónicamente, esta expresión regular extendida no coincide con las expresiones regulares extendidas.

"En teoría, la teoría y la práctica son lo mismo. En la práctica, no lo son". Casi todos los que conocen las expresiones regulares saben que las expresiones regulares no admiten la recursividad. Pero PCRE y la mayoría de las otras implementaciones admiten mucho más que las expresiones regulares básicas.

usando esto con el script de shell en el comando grep, me muestra un error ... grep: Contenido no válido de {}. Estoy creando un script que podría codificar una base de código para encontrar todos los archivos que contienen expresiones regulares

Este patrón explota una extensión llamada expresiones regulares recursivas. Esto no es compatible con el sabor POSIX de regex. Puede probar con el interruptor -P para habilitar el sabor de expresión regular PCRE.

Regex en sí mismo "no es un lenguaje regular y, por lo tanto, no se puede analizar mediante una expresión regular ..."

Esto es cierto para las expresiones regulares clásicas. Algunas implementaciones modernas permiten la recursividad, lo que lo convierte en un lenguaje sin contexto, aunque es algo detallado para esta tarea.

Veo dónde estás haciendo juego []()/\. y otros caracteres especiales de expresiones regulares. ¿Dónde estás permitiendo personajes no especiales? Parece que esto coincidirá ^(?:[\.]+)$, pero no ^abcdefg$. Esa es una expresión regular válida.

[^?+*{}()[\]\\|]coincidirá con cualquier carácter individual, no parte de ninguna de las otras construcciones. Esto incluye tanto literal ( a- z), y algunos caracteres especiales ( ^, $, .).

Improbable.

Evaluarlo en uno try..catcho en cualquier idioma

No, si habla estrictamente de expresiones regulares y no incluye algunas implementaciones de expresiones regulares que en realidad son gramáticas libres de contexto.

Hay una limitación de las expresiones regulares que hace que sea imposible escribir una expresión regular que coincida con todas y solo expresiones regulares. No puede hacer coincidir implementaciones como llaves que están emparejadas. Las expresiones regulares usan muchas de estas construcciones, tomemos []como ejemplo. Siempre que haya un [debe haber una coincidencia ], que es lo suficientemente simple para una expresión regular "\[.*\]".

Lo que hace que sea imposible para las expresiones regulares es que se pueden anidar. ¿Cómo puedes escribir una expresión regular que coincida con paréntesis anidados? La respuesta es que no puedes sin una expresión regular infinitamente larga. Puede hacer coincidir cualquier número de paréntesis anidados a través de la fuerza bruta, pero nunca puede hacer coincidir un conjunto arbitrariamente largo de paréntesis anidados.

Esta capacidad a menudo se conoce como contar, porque estás contando la profundidad de la anidación. Una expresión regular, por definición, no tiene la capacidad de contar.

Terminé escribiendo " Limitaciones de expresión regular " sobre esto.

Buena pregunta.

Los lenguajes regulares verdaderos no pueden decidir paréntesis bien formados, arbitrariamente anidados Si su alfabeto contiene '('y ')'el objetivo es decidir si una cadena de estos tiene paréntesis coincidentes bien formados. Como este es un requisito necesario para las expresiones regulares, la respuesta es no.

Sin embargo, si afloja el requisito y agrega recursividad, probablemente pueda hacerlo. La razón es que la recursión puede actuar como una pila que le permite "contar" la profundidad de anidamiento actual presionando sobre esta pila.

Russ Cox escribió " La coincidencia de expresiones regulares puede ser simple y rápida ", que es un maravilloso tratado sobre la implementación del motor de expresiones regulares .

No, si usa expresiones regulares estándar.

La razón es que no puede satisfacer el lema de bombeo para los idiomas normales. Los estados de bombeo lemma que una cadena pertenece al lenguaje "L" es regular si existe un número "N" de tal manera que, después de dividir la cadena en tres subseries x, y, z, de tal manera que |x|>=1 && |xy|<=N, se puede repetir ytantas veces como se desee y el toda la cadena seguirá perteneciendo L.

Una consecuencia del lema de bombeo es que no puede tener cadenas regulares en el formulario a^Nb^Mc^N, es decir, dos subcadenas que tienen la misma longitud separadas por otra cadena. En cualquier forma que dividir dichas cadenas en x, yy z, no se puede "bomba" ysin obtener una cadena con un número diferente de "a" y "c", dejando así el idioma original. Ese es el caso, por ejemplo, con paréntesis en expresiones regulares.

Aunque es perfectamente posible usar una expresión regular recursiva como MizardX ha publicado, para este tipo de cosas es mucho más útil un analizador. Originalmente, las expresiones regulares estaban destinadas a ser utilizadas con lenguajes regulares, ser recursivo o tener grupos de equilibrio es solo un parche.

El lenguaje que define expresiones regulares válidas es en realidad una gramática libre de contexto, y debe usar un analizador apropiado para manejarlo. Aquí hay un ejemplo para un proyecto universitario para analizar expresiones regulares simples (sin la mayoría de las construcciones). Utiliza JavaCC. Y sí, los comentarios están en español, aunque los nombres de los métodos se explican por sí mismos.

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

Puede enviar la expresión regular a la preg_matchque devolverá falso si la expresión regular no es válida. No olvide usar el @para suprimir mensajes de error:

@preg_match($regexToTest, '');

• Devolverá 1 si la expresión regular es // .
• Devolverá 0 si la expresión regular está bien.
• Volverá falso de lo contrario.

El siguiente ejemplo de Paul McGuire, originalmente del wiki de pyparsing, pero ahora disponible solo a través de Wayback Machine , ofrece una gramática para el análisis algunas expresiones regulares, con el fin de devolver el conjunto de cadenas coincidentes. Como tal, rechaza aquellos re que incluyen términos de repetición ilimitados, como '+' y '*'. Pero debería darle una idea sobre cómo estructurar un analizador que procese los re.

# 
# 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()