17
\$\begingroup\$

Build a regex that will accept a regex string as input and check if it's valid. Basically, your regex should be able to validate itself. (Any invalid regex should not be validated, so you can't use .*. ;))

Your flavor must be fully supported by well known implementations (Perl, sed, grep, gawk, etc), and it must fully support what those implementations support. [Don't worry about the lawyer speak; I'm just trying to remove any possible loopholes for the smart***es.]


I'd it, but I'm worried it'll give an edge to those who know and use non-feature-rich flavors. Or are my worries unfounded?

\$\endgroup\$
  • 8
    \$\begingroup\$ not possible, the arbitrary nesting brackets make a regex a context free grammar, (replacing it with a polish notation also needs a stack) \$\endgroup\$ – ratchet freak Aug 29 '11 at 23:27
  • \$\begingroup\$ @ratchet Augh, you might be right. \$\endgroup\$ – Mateen Ulhaq Aug 29 '11 at 23:45
  • 1
    \$\begingroup\$ some extensions on the regular languages exist that may allow matching the brackets but I don't know how to do it \$\endgroup\$ – ratchet freak Aug 29 '11 at 23:57
  • 8
    \$\begingroup\$ It's bound to be possible with Perl regexes. \$\endgroup\$ – Peter Taylor Aug 30 '11 at 5:46
  • 1
    \$\begingroup\$ @BrianVandenberg regular expressions implemented in modern languages are pretty much all non-regular ... as soon as you add backreferences, you can match non-regular languages. Moreover, both Perl/PCRE and .NET are powerful enough to match correct nesting. \$\endgroup\$ – Martin Ender Jun 4 '14 at 23:16
23
\$\begingroup\$

Ruby

I tried to match the actual syntax of Ruby's regex flavor as much as possible, but there are a few quirks: it accepts a few lookbehinds that are actually invalid (like (?<=(?<!))), and it recognizes empty character ranges like D-A. The latter could be fixed for ASCII, but the regex is long enough as it is.

\A(?<main>
    (?!
        \{(\d+)?,(\d+)?\} # do not match lone counted repetition
    )
    (?:
        [^()\[\]\\*+?|<'] | # anything but metacharacters
        (?<cclass>
            \[ \^? (?: # character class
                (?: # character class
                    [^\[\]\\-] | # anything but square brackets,  backslashes or dashes
                    \g<esc> |
                    \[ : \^? (?: # POSIX char-class
                        alnum | alpha | word | blank | cntrl | x?digit | graph | lower | print | punct | space | upper
                    ) : \] |
                    - (?!
                        \\[dwhsDWHS]
                    ) # range / dash not succeeded by a character class
                )+ |
                \g<cclass> # more than one bracket as delimiter
            ) \]
        ) |
        (?<esc>
            \\[^cuxkg] | # any escaped character
            \\x \h\h? | # hex escape
            \\u \h{4} | # Unicode escape
            \\c . # control escape
        ) |
        \\[kg] (?:
            < \w[^>]* (?: > | \Z) |
            ' \w[^']* (?: ' | \Z)
        )? | # named backrefs
        (?<! (?<! \\) \\[kg]) [<'] | # don't match < or ' if preceded by \k or \g
        \| (?! \g<rep> ) | # alternation
        \( (?: # group
            (?:
                \?
                (?:
                    [>:=!] | # atomic / non-capturing / lookahead
                    (?<namedg>
                        < [_a-zA-Z][^>]* > |
                        ' [_a-zA-Z][^']* ' # named group
                    ) |
                    [xmi-]+: # regex options
                )
            )?
            \g<main>*
        ) \) |
        \(\?<[!=] (?<lbpat>
            (?! \{(\d+)?,(\d+)?\} )
            [^()\[\]\\*+?] |
            \g<esc>  (?<! \\[zZ]) |
            \g<cclass> |
            \( (?: # group
                (?:
                    \?: |
                    \? \g<namedg> |
                    \? <[!=]
                )?
                \g<lbpat>*
            ) \) |
            \(\?\# [^)]* \)
        )* \)
        |
        \(\? [xmi-]+ \) # option group
        (?! \g<rep> ) 
        |
        \(\?\# [^)]*+ \) # comment
        (?! \g<rep> )
    )+
    (?<rep>
        (?:
            [*+?] | # repetition
            \{(\d+)?,(\d+)?\} # counted repetition
        )
        [+?]? # with a possessive/lazy modifier
    )?
)*\Z

Unreadable version:

\A(?<main>(?!\{(\d+)?,(\d+)?\})(?:[^()\[\]\\*+?|<']|(?<cclass>\[\^?(?:(?:[^\[\]\\-]|\g<esc>|\[:\^?(?:alnum|alpha|word|blank|cntrl|x?digit|graph|lower|print|punct|space|upper):\]|-(?!\\[dwhsDWHS]))+|\g<cclass>)\])|(?<esc>\\[^cuxkg]|\\x\h\h?|\\u\h{4}|\\c.)|\\[kg](?:<\w[^>]*(?:>|\Z)|'\w[^']*(?:'|\Z))?|(?<!(?<!\\)\\[kg])[<']|\|(?!\g<rep>)|\((?:(?:\?(?:[>:=!]|(?<namedg><[_a-zA-Z][^>]*>|'[_a-zA-Z][^']*')|[xmi-]+:))?\g<main>*)\)|\(\?<[!=](?<lbpat>(?!\{(\d+)?,(\d+)?\})[^()\[\]\\*+?]|\g<esc>(?<!\\[zZ])|\g<cclass>|\((?:(?:\?:|\?\g<namedg>|\?<[!=])?\g<lbpat>*)\)|\(\?#[^)]*\))*\)|\(\?[xmi-]+\)(?!\g<rep>)|\(\?#[^)]*+\)(?!\g<rep>))+(?<rep>(?:[*+?]|\{(\d+)?,(\d+)?\})[+?]?)?)*\Z
| improve this answer | |
\$\endgroup\$
  • 30
    \$\begingroup\$ Aren't they both the unreadable version? \$\endgroup\$ – Kibbee Sep 7 '11 at 1:59
  • 2
    \$\begingroup\$ @Kibbee The first one is reasonably readable if you know regex well. \$\endgroup\$ – Lowjacker Sep 8 '11 at 23:15
  • 1
    \$\begingroup\$ How does this ensure that there are no invalid numeric backreferences? \$\endgroup\$ – Martin Ender Jun 4 '14 at 23:21
  • 1
    \$\begingroup\$ I guess it doesn't. Then again, it's not the only limitation it has (see above). Some things could be fixed, but the regex would become ridiculously long. \$\endgroup\$ – Lowjacker Jun 8 '14 at 14:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.