Is it possible to have regexp that matches all valid regular expressions?

Question

Is it possible to detect if a given string is valid regular expression, using just regular expressions?

Say I have some strings, that may or may not be a valid regular expressions. I'd like to have a regular expression matches those string that correspond to valid regular expression. Is that possible? Or do I have use some higher level grammar (i.e. context free language) to detect this? Does it affect if I am using some extended version of regexps like Perl regexps?

If that is possible, what the regexp matching regexp is?

Answer 1

No, it is not possible. This is because valid regular expressions involve grouping, which requires balanced parentheses.

Balanced delimiters cannot be matched by a regular expression; they must instead be matched with a context-free grammar. (The first example on that article deals with balanced parentheses.)

Answer 2

See an excellent write-up here:

http://stackoverflow.com/questions/2789407/regular-expression-for-regular-expressions/2790801#2790801

The answer is that regexes are NOT written using a regular grammar, but a context-free one.

Answer 3

If your question had been "match all valid regular expressions", the answer is (perhaps surprisingly) 'yes'. The regular expression .* match all valid (and non-valid) regular expressions, but is pretty useless for determining if you're looking at a valid one.

However, as the question is "match all and only valid regular expressions", the answer is (as DVK and Platinum Azure" have said 'no'.