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

Question

Est est possible de détecter une expression régulière valide avec une autre expression régulière ? Dans l’affirmative, veuillez donner exemple de code ci-dessous.

Answer 1

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

C'est un appel récursif de la regex, et n'est pas pris en charge par de nombreux regex moteurs. PCRE base doit être pris en charge.

Sans les espaces et les commentaires:

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

Edit: Ajouté un peu de description.
Edit2: Ajout de la récursivité des constructions, possessif quantificateurs, et la chaîne de bord des assertions. Il correspond désormais à lui-même (la version courte, au moins).
Edit3: correction de Bug. "|" n'est pas littérale,"|?" n'est pas valide.
Edit4: mise à Jour des classes de caractères. Ils peuvent avoir en option la négation, doit avoir au moins un caractère, et le premier caractère peut être ] sans la fermeture de la classe.

Answer 2

Peu probable.

L’évaluer dans une `` ou quel que soit votre langue fournit.

Answer 3

Non si vous êtes strictement parlant de reguralr expressions et non, y compris, de façon régulière, l'expression des implémentations qui sont en fait des grammaires hors contexte.

Il y a une limitation des expressions régulières qui fait qu'il est impossible d'écrire une expression régulière qui correspond à une expression régulière. Vous ne pouvez pas combiner les implémentations comme accolades qui sont appariés. Regex de l'utiliser beaucoup de constructions, permet de prendre [] comme un exemple. Chaque fois qu'il y a un [ il doit y avoir une correspondance ]. Assez Simple pour une expression rationnelle "[.*]".

Ce qui fait qu'il est impossible pour regexe est qu'ils peuvent être imbriquées. Comment pouvez-vous écrire une expression régulière qui correspond à imbriquée entre parenthèses? La réponse est que vous ne pouvez pas sans infiniment longue, regex. Vous pouvez faire correspondre n'importe quel nombre de parenthèses imbriquées par le biais de la force brute, mais vous ne pouvez pas toujours correspondre arbitrairement une longue série de parenthèses imbriquées.

Cette capacité est souvent désigné comme le comptage (vous faites le décompte de la profondeur de la nidification). Une regex, par définition, n'a pas la capacité de compter.

EDIT: Fini par écrire un billet de blog à ce sujet: Expression Régulière Limitations

Answer 4

Bonne question. Vrai langages réguliers ne peuvent pas décider arbitrairement profondément imbriqués bien formé entre parenthèses. C'est à dire, si votre alphabet contient '(' et ')' l'objectif est de décider si une chaîne a bien formé correspondance entre parenthèses. Puisque c'est une condition nécessaire pour les expressions régulières, la réponse est non.

Cependant: si vous desserrez l'exigence et ajouter la récursivité vous pouvez probablement le faire. La raison en est que la récurrence peut agir comme une "pile" vous permettant de "compter" le courant d'imbrication en appuyant sur cette pile.

Russ Cox a écrit un magnifique traité sur le moteur d'expressions régulières de mise en œuvre: Expression Régulière Correspondant Peut Être Simple Et Rapide

Answer 5

Bien qu'il est parfaitement possible d'utiliser un circuit regex comme MizardX a posté, pour ce genre de choses, il est beaucoup plus utile d'un analyseur. Regexes étaient à l'origine destinés à être utilisés avec des langages réguliers, étant récursive ou avoir l'équilibrage des groupes est juste un patch.

La langue qui définit valide regexes est en fait un contexte exempt de grammaire, et vous devez utiliser un analyseur approprié pour le traitement. Voici un exemple pour un projet de l'université pour l'analyse simple regexes (sans la plupart des constructions). Il utilise de JavaCC. Et oui, les commentaires sont en espagnol, bien que la méthode noms sont 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; }
}