Is there a regular expression to detect a valid regular expression? – Dev

The best answers to the question “Is there a regular expression to detect a valid regular expression?” in the category Dev.

QUESTION:

Is it possible to detect a valid regular expression with another regular expression? If so please give example code below.

ANSWER:

Unlikely.

Evaluate it in a try..catch or whatever your language provides.

ANSWER:

/
^                                             # start of string
(                                             # first group start
  (?:
    (?:[^?+*{}()[\]\\|]+                      # literals and ^, $
     | \\.                                    # escaped characters
     | \[ (?: \^?\\. | \^[^\\] | [^\\^] )     # character classes
          (?: [^\]\\]+ | \\. )* \]
     | \( (?:\?[:=!]|\?<[=!]|\?>)? (?1)?? \)  # parenthesis, with recursive content
     | \(\? (?:R|[+-]?\d+) \)                 # recursive matching
     )
    (?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )?   # quantifiers
  | \|                                        # alternative
  )*                                          # repeat content
)                                             # end first group
$                                             # end of string
/

This is a recursive regex, and is not supported by many regex engines. PCRE based ones should support it.

Without whitespace and comments:

/^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*)$/

.NET does not support recursion directly. (The (?1) and (?R) constructs.) The recursion would have to be converted to counting balanced groups:

^                                         # start of string
(?:
  (?: [^?+*{}()[\]\\|]+                   # literals and ^, $
   | \\.                                  # escaped characters
   | \[ (?: \^?\\. | \^[^\\] | [^\\^] )   # character classes
        (?: [^\]\\]+ | \\. )* \]
   | \( (?:\?[:=!]
         | \?<[=!]
         | \?>
         | \?<[^\W\d]\w*>
         | \?'[^\W\d]\w*'
         )?                               # opening of group
     (?<N>)                               #   increment counter
   | \)                                   # closing of group
     (?<-N>)                              #   decrement counter
   )
  (?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )? # quantifiers
| \|                                      # alternative
)*                                        # repeat content
$                                         # end of string
(?(N)(?!))                                # fail if counter is non-zero.

Compacted:

^(?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>|\?<[^\W\d]\w*>|\?'[^\W\d]\w*')?(?<N>)|\)(?<-N>))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*$(?(N)(?!))

From the comments:

Will this validate substitutions and translations?

It will validate just the regex part of substitutions and translations. s/<this part>/.../

It is not theoretically possible to match all valid regex grammars with a regex.

It is possible if the regex engine supports recursion, such as PCRE, but that can’t really be called regular expressions any more.

Indeed, a “recursive regular expression” is not a regular expression. But this an often-accepted extension to regex engines… Ironically, this extended regex doesn’t match extended regexes.

“In theory, theory and practice are the same. In practice, they’re not.” Almost everyone who knows regular expressions knows that regular expressions does not support recursion. But PCRE and most other implementations support much more than basic regular expressions.

using this with shell script in the grep command , it shows me some error.. grep: Invalid content of {} . I am making a script that could grep a code base to find all the files that contain regular expressions

This pattern exploits an extension called recursive regular expressions. This is not supported by the POSIX flavor of regex. You could try with the -P switch, to enable the PCRE regex flavor.

Regex itself “is not a regular language and hence cannot be parsed by regular expression…”

This is true for classical regular expressions. Some modern implementations allow recursion, which makes it into a Context Free language, although it is somewhat verbose for this task.

I see where you’re matching []()/\. and other special regex characters. Where are you allowing non-special characters? It seems like this will match ^(?:[\.]+)$, but not ^abcdefg$. That’s a valid regex.

[^?+*{}()[\]\\|] will match any single character, not part of any of the other constructs. This includes both literal (az), and certain special characters (^, $, .).

ANSWER:

Good question.

True regular languages can not decide arbitrarily deeply nested well-formed parenthesis. If your alphabet contains '(' and ')' the goal is to decide if a string of these has well-formed matching parenthesis. Since this is a necessary requirement for regular expressions the answer is no.

However, if you loosen the requirement and add recursion you can probably do it. The reason is that the recursion can act as a stack letting you “count” the current nesting depth by pushing onto this stack.

Russ Cox wrote “Regular Expression Matching Can Be Simple And Fast” which is a wonderful treatise on regex engine implementation.

ANSWER:

No, if you are strictly speaking about regular expressions and not including some regular expression implementations that are actually context free grammars.

There is one limitation of regular expressions which makes it impossible to write a regex that matches all and only regexes. You cannot match implementations such as braces which are paired. Regexes use many such constructs, let’s take [] as an example. Whenever there is an [ there must be a matching ], which is simple enough for a regex "\[.*\]".

What makes it impossible for regexes is that they can be nested. How can you write a regex that matches nested brackets? The answer is you can’t without an infinitely long regex. You can match any number of nested parenthesis through brute force but you can’t ever match an arbitrarily long set of nested brackets.

This capability is often referred to as counting, because you’re counting the depth of the nesting. A regex by definition does not have the capability to count.


I ended up writing “Regular Expression Limitations” about this.