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?

Commercial

possible duplicate of Is there a regular expression to detect a valid regular expression? – Intercellular

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.)

Lewls

Ok, thats true with normal regular expressions. How about something like Perl regex? – Eirene

@Juha Syrjälä: Actually, I was thinking about Perl regexes specifically. The grouping parentheses cannot be matched with a regex, as I have explained. – Lewls

PCRE and .NET extend regular expressions to also match balancing subgroups. Perl 6 expands regexes with rules that also enable this. But by now the description "regular expression" is no longer accurate. In fact, most of what today is understood by "regular expression" is no longer regular. – Berndt

Answer 2

See an excellent write-up here:

Regular expression for regular expressions?

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

Stravinsky

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'.

Speedwriting