Regex that matches any regex

Question

Your task is to write a regular expression that matches any valid regular expression and no invalid expression.

You may pick any regex flavour for your answer, but you have to match regular expressions of that same flavour.

This is regex-golf, so the shortest regex wins.

You can't invent your own regex language for this. That would be an example of a standard loophole.

Answer 1

Not possible in Ruby!

I wanted to write a regular expression in Ruby that matches valid regular expressions in Ruby, but I must conclude that writing one is not possible.

At first, Ruby seems like a good choice. If I want to check for matching parentheses, I can write a recursive expression like (?<mparen>([^()]|\(\g<mparen>\))*) where mparen matches zero or more things that are either not parentheses, or are a set of parentheses with mparen inside.

So I listed things that are valid and not valid in Ruby regular expressions. Then I found things that I cannot check with regular expressions.

Empty ranges of characters

In Ruby, [a-b] is a valid, but [b-a] is not valid, because a comes before b. This rule is common to several flavors of regular expressions:

$ ruby21 -e '/[b-a]/'
-e:1: empty range in char class: /[b-a]/
$ perl -e 'qr/[b-a]/'
Invalid [] range "b-a" in regex; marked by <-- HERE in m/[b-a <-- HERE ]/ at -e line 1.
$ sed '/[b-a]/!d'   
sed: 1: "/[b-a]/!d": RE error: invalid character range

So how do I write a regular expression that matches a-b but not b-a, and works with any range? I can't.

I would like to write (?<begin>.)-[\k<begin>-z] using a backreference to the first character. This would become a-[a-z] or b-[b-z] or so on. (Later I would change z to the highest character, but for now I test lowercase letters.) This fails because I can't use backreferences in ranges! [\k<begin>-z] is the same as [<>-z], as the range >-z includes the letters begkin.

I can write in 202 characters:

a-[a-z]|b-[b-z]|c-[c-z]|d-[d-z]|e-[e-z]|f-[f-z]|g-[g-z]|h-[h-z]|i-[i-z]|j-[j-z]|k-[k-z]|l-[l-z]|m-[m-z]|n-[n-z]|o-[o-z]|p-[p-z]|q-[q-z]|r-[r-z]|s-[s-z]|t-[t-z]|u-[u-z]|v-[v-z]|w-[w-z]|x-[x-z]|y-[yz]|z-z

This covers 26 lowercase letters, but only in their literal forms. Octal and hex escapes are also part of the regular expression syntax. Now a is also \141 and \x61, and z is also \172 and \x7a. My regular expression would need to match \141-\172 and \x61-\x7a, and also a-\172 and \x61-z and so on.

(a|\\141|\\x61)-([a-z]|\\1(4[2-7]|[5-7][0-7])|\\x(4[1-9a-fA-F]|[5-7]\h))

I would not try to extend this to the 1112064 codepoints of Unicode.

Missing capture groups

A regular expression is not valid if it has a backreference to an undefined capture group. For example, (?<a>)\k<b> is not valid because it has no capture group b. So, my regular expression for valid regular expressions would need to check \k<b> against the set of valid names. I can't think of a way to do this in one regular expression.

The answer is not (?<=\(\?<b>.*)\\k<b>. This would use the lookbehind feature to match \k<b> if there was a (?<b> earlier in the string. It fails because variable quantifiers like * are not valid in lookbehind expressions.

Another problem happens with subexpression calls. It is valid for two capture groups to share the same name, but it is not valid for a subexpression call to use a multiplex name. So (?<a>)(?<a>) is valid but (?<a>)(?<a>)\g<a> is not.

Encoding troubles

A valid regular expression must also be valid in its character encoding. If the encoding is UTF-8, then \xc4\x80 is valid but \x80\x80 is not. My regular expression for regular expressions would also need to validate UTF-8. It is valid to mix octal and hex escapes, so \xc4\200 and \304\x80 are valid too.

Ruby has other encodings. My regular expression would also need to validate EUC-JP, Windows-31J, GB18030, and every other ASCII-compatible encoding known to Ruby. That's not possible! My regular expression can't know which encoding to validate.

Is \200 a valid regular expression? Regexp.new '\200'.encode('binary') is valid, but Regexp.new '\200'.encode('utf-8') is not valid. My regular expression can't see the encoding tag. It can only see the four ASCII characters in \200, so it can't decide whether \200 is valid.

I might fix this if I decree that my regular expression for regular expressions only works with one encoding. I might pick 'us-ascii', which has only 128 characters. This does not fix my problem with capture groups.