Is there a regular expression to detect a valid regular expression?

Question

Is is possible to detect a valid regular expression with another regular expression? If so please give example code below.

Answer 1

Unlikely.

Evaluate it in a try..catch or whatever your language provides.

Answer 2

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

This is a recursive regex, and is not supported by many regex engines. PCRE based ones should support it.

Without whitespace and comments:

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

Edit: Added some description.
Edit2: Added recursion constructs, possessive quantifiers, and string edge assertions. It now matches itself (the short version at least).

Answer 3

Good question. True regular languages can not decide arbitrarily deeply nested well formed parenthesis. Ie, if your alphabet contains '(' and ')' the goal is to decide if a string of these has well-formed matching parenthesis. Since this is a necessary requirement for regular expressions the answer is no.

However: if you loosen the requirement and add recursion you can probably do it. The reason is that the recursion can act as a 'stack' letting you 'count' the current nesting depth by pushing onto this stack.

Russ Cox has written a wonderful treatise on regex engine implementation: Regular Expression Matching Can Be Simple And Fast

Answer 4

No if you are strictly speaking about reguralr expressions and not including some regular expression implementations that are actually context free grammars.

There is one limitation of regular expressions which makes it impossible to write a regex that matches a regex. You cannot match implementations such as braces which are paired. Regex's use many such constructs, lets take [] as an example. Whenever there is an [ there must be a matching ]. Simple enough for a regex "[.*]".

What makes it impossible for regexe's is that they can be nested. How can you write a regex that matches nested brackets? The answer is you can't without an infinitely long regex. You can match any number of nested parens through brute force but you can't ever match an arbitrarily long set of nested brackets.

This capability is often referred to as counting (you're counting the depth of the nesting). A regex by definition does not have the capability to count.

EDIT: Ended up writing a blog post about this: Regular Expression Limitations

Answer 5

Though it is perfectly possible to use a recursive regex as MizardX has posted, for this kind of things it is much more useful a parser. Regexes were originally intended to be used with regular languages, being recursive or having balancing groups is just a patch.

The language that defines valid regexes is actually a context free grammar, and you should use an appropriate parser for handling it. Here is an example for a university project for parsing simple regexes (without most constructs). It uses JavaCC. And yes, comments are in Spanish, though method names are pretty self-explanatory.

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

Answer 6

The above may or may not be useful in practice (I didn't review them in detail, nor am I a particularly good judge), but formally, IIRC (at least some) regular expression languages are Turing complete, and as such it is impossible to construct a tester that will correctly evaluate the correctness of all possible regular expressions in those languages. See Gödel's Incompleteness Theorem and the Church-Turing thesis.

Answer 7

This example on the pyparsing wiki gives a grammar for parsing some regexes, for the purposes of returning the set of matching strings. As such, it rejects those re's that include unbounded repetition terms, like '+' and '*'. But it should give you an idea about how to structure a parser that would process re's.