Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

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

share|improve this question
95  
Who validates the validating regex? –  Nico Jul 4 '11 at 0:02
6  
@Nico Community. –  Janusz Lenar Jul 29 '12 at 13:39
8  
@Nico Quis regexiet ipsos regexes? –  Polynomial Oct 23 '12 at 12:20
3  
So your problem is validating a regex, you chose a regex for solving it. I wonder if the problem-number-increasing property of regexes is additive or multiplicative. It feels like 4 problems instead of 2 :) –  abesto Nov 18 '13 at 14:54
1  
There are many notations for regular expressions - some features and their spellings are common to most, some are spelled differently or only available in one particular notation. Most of those notations aren't "regular" in the regular grammar sense - you'd need a context free parser to handle the unbounded nesting of subexpressions - though many modern "regular expression" notations have extensions that go beyond the original formal definition and might allow their own notations to be recognized. In any case, why not simply ask your regex library if each regex is valid? –  Steve314 4 hours ago

9 Answers 9

up vote 205 down vote accepted
/
^                                             # 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).
Edit3: Bug fix. "|" is not a literal, so "|?" is not valid.
Edit4: Updated character classes. They can have optional negation, must have at least one character, and first character can be ] without closing the class.

share|improve this answer
65  
Voting you up on the presumption that this actually works. Since I've only had two cups of coffee today, I'm not up to the task of verifying it. –  Kirk Strauser Oct 5 '08 at 17:24
18  
Voting down. It is not theorotically possible to match all valid regex grammars with a regex. –  JaredPar Oct 5 '08 at 18:02
30  
JaredPar: It is possible if the regex engine supports recursion, such as PCRE, but that can't really be called regular expressions any more. –  Markus Jarderot Oct 5 '08 at 18:14
26  
Indeed, a "recursive regular expression" is not a regular expression. But this an often-accepted extension to regex engines... Ironically, this extended regex doesn't match extended regexes :D –  ephemient Oct 6 '08 at 5:22
55  
"Almost everyone who knows regular expressions knows that regular expressions does not support recursion." You'd be surprised what people don't know about regular expressions. I think many people see them as an inscrutable black box, where they ask the internet what regex solves their problem and it magically works. –  Chris Lutz Apr 27 '09 at 16:25

Unlikely.

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

share|improve this answer
34  
That's not very enterprisey of you. –  MusiGenesis Oct 5 '08 at 17:31
40  
I think this is a much better solution than attempting to validate it via a regex.... –  Mike Stone Oct 5 '08 at 19:02
6  
This is easy in PHP for example: $valid = (@preg_match($regex,'') !== FALSE); –  ColinM Dec 6 '12 at 23:00
    
Or in Python: exec "try: re.match(regex, '')\nexcept: print(1)" –  Stian OK Mar 4 at 16:18
1  
Doing that made me pass a Compilers final project in 5 minutes –  diegoaguilar Mar 25 at 6:19

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

share|improve this answer
1  
I often have to differentiate between the common text matching tool called regex and regular-expression upon which it was based. Sadly many don't see the distinction. RE2 is unique in that it only allows extension that can be translated back to plain RE. It also has all the advantages of RE (bounded memory, runtime, speed), with most of the syntax extensions. –  deft_code Nov 18 '13 at 17:49

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

share|improve this answer
    
Thanks for the link on Russ Cox article –  njsf Oct 5 '08 at 17:47

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; }
}
share|improve this answer
3  
Being a little nicer, I do agree that you should stick to one language. And, without sounding pro-English or "your language sucks", Linus Torvalds at least already suggests a standard. –  Chris Lutz Apr 27 '09 at 16:42
7  
I agree that using Spanish, English and Spanglish in the same code is not a happy practice. The problem is I'm used to code in English, but there were some guidelines to follow (such as commenting in Spanish, or using certain names for tokens) in the project. Anyway, the point was just to give an idea on the algorithm, not to give some full reference code. –  Santiago Palladino Apr 27 '09 at 17:29
    
Most of these words are extremely similar in both languages, anyway, so I think if you're not totally dense it should be easy to follow. –  emodendroket 20 mins ago

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.

share|improve this answer

You can submit the regex to preg_match which will return false if the regex is not valid. Don't forget to use the '@' to suppress error messages:

@preg_match($regexToTest, '');
  • will return 1 if the regex is '//'.
  • will return 0 if the regex is okay.
  • will return false otherwise.
share|improve this answer

This class does the trick in PHP:

class ValidateRegex{
public function exception_error_handler($errno, $errstr, $errfile, $errline ) {
        $this->_regex_has_errors=true;
}

private $_regex_has_errors;


public function validate($regex) {      

        $this->_regex_has_errors=false;
        set_error_handler(array($this,"exception_error_handler"));
        preg_match($regex, "");
        restore_error_handler();
        if($this->_regex_has_errors)
            return false;
        else        
            return true;
}
}
share|improve this answer
2  
-1: The question is about using regular expressions to validate regular expressions, not validating regular expressions some other way. –  Ingo Bürk Aug 15 '14 at 10:27
1  
May be off-topic, but it's a good solution nonetheless. –  Dennis Snell Nov 21 '14 at 1:04
    
Why don't you simply check for the return value of preg_match instead of using your own error handler? –  Sjoerd 46 mins ago

Construct the validator either for a single regular expression or a set (array) of regular expressions. By default validation is case sensitive but constructors are provided to allow case in-sensitive validation. For example to create a validator which does case in-sensitive validation for a set of regular expressions:

     String[] regexs = new String[] {...};
     RegexValidator validator = new RegexValidator(regexs, false);

Validate true or false: boolean valid = validator.isValid(value);

Validate returning an aggregated String of the matched groups: String result = validator.validate(value);

Validate returning the matched groups: String[] result = validator.match(value);

(For using above code you can use apache validator)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.