CODEWITHSUNDEEP
regexcomputer-scienceregular-language
Juha Syrjälä
Juha Syrjälä

Reputation: 34281

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

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?

Upvotes: 6

Views: 282

Answers (3)

Vatine
Vatine

Reputation: 21288

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

Upvotes: 0

DVK
DVK

Reputation: 129491

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.

Upvotes: 1

Platinum Azure
Platinum Azure

Reputation: 46203

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

Upvotes: 8

Related Questions