Regex that matches any regex
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 (?&lt;mparen&gt;([^()]|\(\g&lt;mparen&gt;\))*) 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 &lt;-- HERE in m/[b-a &lt;-- 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 (?&lt;begin&gt;.)-[\k&lt;begin&gt;-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&lt;begin&gt;-z] is the same as [&lt;&gt;-z], as the range &gt;-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, (?&lt;a&gt;)\k&lt;b&gt; is not valid because it has no capture group b. So, my regular expression for valid regular expressions would need to check \k&lt;b&gt; against the set of valid names. I can't think of a way to do this in one regular expression.

The answer is not (?&lt;=\(\?&lt;b&gt;.*)\\k&lt;b&gt;. This would use the lookbehind feature to match \k&lt;b&gt; if there was a (?&lt;b&gt; 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 (?&lt;a&gt;)(?&lt;a&gt;) is valid but (?&lt;a&gt;)(?&lt;a&gt;)\g&lt;a&gt; 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.