Existe-t-il une expression régulière pour détecter une expression régulière valide?

Est-il possible de détecter une expression régulière valide avec une autre expression régulière? Si oui, veuillez donner un exemple de code ci-dessous.

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

Il s'agit d'une expression régulière récursive et n'est pas prise en charge par de nombreux moteurs d'expression régulière. Ceux basés sur PCRE devraient le supporter.

Sans espace ni commentaires:

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

.NET ne prend pas directement en charge la récursivité. (Les constructions (?1)et (?R).) La récursivité devrait être convertie en comptage des groupes équilibrés:

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

Compacté:

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

D'après les commentaires:

Cela validera-t-il les substitutions et les traductions?

Il validera uniquement la partie regex des substitutions et des traductions. s/<this part>/.../

Il n'est théoriquement pas possible de faire correspondre toutes les grammaires d'expressions rationnelles valides avec une expression régulière.

C'est possible si le moteur d'expression régulière prend en charge la récursivité, comme PCRE, mais cela ne peut plus vraiment être appelé des expressions régulières.

En effet, une "expression régulière récursive" n'est pas une expression régulière. Mais c'est une extension souvent acceptée des moteurs d'expression régulière ... Ironiquement, cette expression régulière étendue ne correspond pas aux expressions régulières étendues.

"En théorie, la théorie et la pratique sont les mêmes. En pratique, elles ne le sont pas." Presque tous ceux qui connaissent les expressions régulières savent que les expressions régulières ne prennent pas en charge la récursivité. Mais PCRE et la plupart des autres implémentations prennent en charge bien plus que les expressions régulières de base.

en utilisant ceci avec le script shell dans la commande grep, cela me montre une erreur. grep: Contenu invalide de {}. Je fais un script qui pourrait grep une base de code pour trouver tous les fichiers qui contiennent des expressions régulières

Ce modèle exploite une extension appelée expressions régulières récursives. Ceci n'est pas pris en charge par la saveur POSIX de l'expression régulière. Vous pouvez essayer avec le commutateur -P, pour activer la saveur regex PCRE.

Regex lui-même "n'est pas un langage régulier et ne peut donc pas être analysé par une expression régulière ..."

Cela est vrai pour les expressions régulières classiques. Certaines implémentations modernes autorisent la récursivité, ce qui en fait un langage sans contexte, bien qu'il soit quelque peu verbeux pour cette tâche.

Je vois où tu correspond []()/\. et d'autres caractères regex spéciaux. Où autorisez-vous les caractères non spéciaux? Il semble que cela correspondra ^(?:[\.]+)$, mais pas ^abcdefg$. C'est une expression rationnelle valide.

[^?+*{}()[\]\\|]correspondra à n'importe quel caractère unique, ne faisant partie d'aucune des autres constructions. Cela inclut à la fois littérale ( a- z), et certains caractères spéciaux ( ^, $, .).

Peu probable.

Évaluez-le dans un try..catchou ce que votre langue propose.

Non, si vous parlez strictement d'expressions régulières et que vous n'incluez pas certaines implémentations d'expressions régulières qui sont en fait des grammaires sans contexte.

Il existe une limitation des expressions régulières qui rend impossible l'écriture d'une expression régulière qui correspond à toutes et uniquement aux expressions régulières. Vous ne pouvez pas faire correspondre des implémentations telles que des accolades qui sont appariées. Les expressions rationnelles utilisent de nombreuses constructions de ce type, prenons l' []exemple. Chaque fois qu'il y a un, [il doit y avoir une correspondance ], ce qui est assez simple pour une expression régulière "\[.*\]".

Ce qui rend impossible les expressions régulières, c'est qu'elles peuvent être imbriquées. Comment pouvez-vous écrire une expression régulière qui correspond aux crochets imbriqués? La réponse est que vous ne pouvez pas sans une expression régulière infiniment longue. Vous pouvez faire correspondre n'importe quel nombre de parenthèses imbriquées par la force brute, mais vous ne pouvez jamais faire correspondre un ensemble arbitrairement long de crochets imbriqués.

Cette capacité est souvent appelée comptage, car vous comptez la profondeur de l'imbrication. Une expression régulière par définition n'a pas la capacité de compter.

J'ai fini par écrire " Limitations des expressions régulières " à ce sujet.

Bonne question.

Les vraies langues régulières ne peuvent pas décider de parenthèses bien formées profondément imbriquées. Si votre alphabet contient '('et ')'le but est de décider si une chaîne de ceux-ci a une parenthèse correspondante bien formée. Comme il s'agit d'une exigence nécessaire pour les expressions régulières, la réponse est non.

Cependant, si vous assouplissez l'exigence et ajoutez une récursivité, vous pouvez probablement le faire. La raison en est que la récursivité peut agir comme une pile vous permettant de "compter" la profondeur d'imbrication actuelle en poussant sur cette pile.

Russ Cox a écrit " La correspondance d'expression régulière peut être simple et rapide ", qui est un merveilleux traité sur la mise en œuvre du moteur regex.

Non, si vous utilisez des expressions régulières standard.

La raison en est que vous ne pouvez pas satisfaire le lemme de pompage pour les langues régulières. Les Etats lemme de pompage d' une chaîne appartenant au langage « L » est régulier s'il existe un certain nombre « N » de telle sorte que, après avoir divisé la chaîne en trois sous - chaînes x, y, z, de sorte que |x|>=1 && |xy|<=N, vous pouvez répéter yautant de fois que vous voulez et le la chaîne entière appartiendra toujours L.

Une conséquence du lemme de pompage est que vous ne pouvez pas avoir de chaînes régulières sous la forme a^Nb^Mc^N, c'est-à-dire deux sous-chaînes ayant la même longueur séparées par une autre chaîne. De toute façon, vous divisez ces chaînes en x, yet z, vous ne pouvez pas "pomper" ysans obtenir une chaîne avec un nombre différent de "a" et "c", laissant ainsi la langue d'origine. C'est le cas, par exemple, avec des parenthèses dans les expressions régulières.

Bien qu'il soit parfaitement possible d'utiliser une expression rationnelle récursive comme l'a signalé MizardX, pour ce genre de choses, il est beaucoup plus utile d'un analyseur. Les expressions rationnelles étaient à l'origine destinées à être utilisées avec des langages réguliers, étant récursives ou ayant des groupes d'équilibrage n'est qu'un patch.

Le langage qui définit les expressions rationnelles valides est en fait une grammaire sans contexte, et vous devez utiliser un analyseur approprié pour le gérer. Voici un exemple de projet universitaire d'analyse syntaxique des expressions rationnelles simples (sans la plupart des constructions). Il utilise JavaCC. Et oui, les commentaires sont en espagnol, bien que les noms de méthode soient assez explicites.

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

Vous pouvez soumettre l'expression rationnelle à preg_matchlaquelle retournera false si l'expression rationnelle n'est pas valide. N'oubliez pas d'utiliser le @pour supprimer les messages d'erreur:

@preg_match($regexToTest, '');

• Renvoie 1 si l'expression régulière est //.
• Renvoie 0 si l'expression régulière est correcte.
• Reviendra faux sinon.

L'exemple suivant de Paul McGuire, originaire du wiki Pyparsing, mais désormais disponible uniquement via la Wayback Machine , donne une grammaire pour analyser certaines expressions rationnelles, dans le but de renvoyer l'ensemble de chaînes correspondantes. En tant que tel, il rejette ceux qui incluent des termes de répétition illimités, comme «+» et «*». Mais cela devrait vous donner une idée de la façon de structurer un analyseur qui traiterait les 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()