15
\$\begingroup\$

Write a non-trivial regex that matches itself.

For example, #.*$ will match a comment outside of a string in python until the end-of-line, and also matches itself in perl regex syntax.

Rules:

  • The regular expression must do something useful or practical.
  • Tell what regex syntax you are using (e.g. perl or POSIX).
  • Winner is the highest voted compliant answer.
  • Be creative!
\$\endgroup\$

closed as too broad by user62131, Timtech, Mego, Riley, Laikoni Mar 9 '17 at 14:26

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    \$\begingroup\$ There was a question on SO a while ago, whether there is a regex that matches valid regexes: stackoverflow.com/questions/172303/… \$\endgroup\$ – Patrick Oscity Jul 27 '12 at 20:13
  • 5
    \$\begingroup\$ Define non-trivial. I mean, OK, A would be trivial, but where do you draw the line? And by "self-matching" do you mean it can only match itself, or is it allowed to match other strings too? Would . qualify? \$\endgroup\$ – Mr Lister Jul 28 '12 at 13:58
  • 1
    \$\begingroup\$ @padde which actually wasn't a regex because the grammar that describes regular expression is context-free. \$\endgroup\$ – FUZxxl Jul 29 '12 at 11:39
  • 1
    \$\begingroup\$ @FUZxxl yes, that is true but one could still write a regex that matches other regexes, but doesnt care about the validity of the matched regexes. \$\endgroup\$ – Patrick Oscity Jul 29 '12 at 13:20
  • 1
    \$\begingroup\$ @padde Well, what is an invalid regex then? An invalid regex obviously isn't a regex. So you essentially say: "yes, that is true but one could still write a regex that matches other regexes, but doesnt care if the matched regex really is a regex" (sic!) \$\endgroup\$ – FUZxxl Jul 29 '12 at 16:19
17
\$\begingroup\$
/(^|[^/])\/(?!\/)(\[.+?]|\\.|[^/\r\n])+\/[gim]{0,3}(?=\s*($|[\r\n,.;})]))/g

Stolen from https://github.com/LeaVerou/prism/blob/gh-pages/components/prism-javascript.js. This should match (in JavaScript) all JavaScript regular expressions.

\$\endgroup\$
11
\$\begingroup\$

PYTHON

Below is a self-matching regex generator. You provide two lists, one contains training data that the regex should match (in addition to matching itself), the other contains training data the the regex should NOT match:

from random import choice, randrange
import re
from itertools import zip_longest, chain, islice
from operator import itemgetter

CHAR_SET = [chr(i) for i in range(128)] + [r"\\", r"\d", r"\D",
                                           r"\w", r"\W", r"\s",
                                           r"\S", r"?:", r"\1",
                                           r"\2", r"\A", r"\b",
                                           r"\B", r"\Z", r"\.",
                                           r"\[", r"\]", r"\(",
                                           r"\)", r"\{", r"\}",
                                           r"\+", r"\|", r"\?",
                                           r"\*"]

CHAR_SAMPLE = []
BREAKPOINT = re.compile(
    r"""
    \(.*?\)|
    \[.*?\]|
    \{.*?\}|
    \w+(?=[\(\[\{])?|
    \S+?|
    \.\*\??|
    \.\+\??|
    \.\?\??|
    \\.|
    .*?
    """,
    re.VERBOSE)

MATCH_BRACKETS = {'(': ')', '[': ']', '{': '}'}
CLOSE_BRACKETS = {')', ']', '}'}
REGEX_SEEDER = [
    r".*?",
    r"(?:.*?)",
    r"\w|\s",
    r"(?<.*?)",
    r"(?=.*?)",
    r"(?!.*?)",
    r"(?<=.*?)",
    r"(?<!.*?)",
    ]

LEN_LIMIT = 100

def distribute(distribution):
    global CHAR_SAMPLE
    for item in CHAR_SET:
        if item in distribution:
            CHAR_SAMPLE.extend([item] * distribution[item])
        else:
            CHAR_SAMPLE.append(item)

def rand_index(seq, stop=None):
    if stop is None:
        stop = len(seq)
    try:
        return randrange(0, stop)
    except ValueError:
        return 0

def rand_slice(seq):
    try:
        start = randrange(0, len(seq))
        stop = randrange(start, len(seq))
        return slice(start, stop)
    except ValueError:
        return slice(0,  0)


#Mutation Functions

def replace(seq):
    seq[rand_index(seq)] = choice(CHAR_SAMPLE)

def delete(seq):
    del seq[rand_index(seq)]

def insert(seq):
    seq.insert(rand_index(seq, len(seq) + 1), choice(CHAR_SAMPLE))

def duplicate(seq):
    source = rand_slice(seq)
    seq[source.stop: source.stop] = seq[source]

def swap(seq):
    if len(seq) < 2: return
    a = rand_index(seq, len(seq) - 1)
    seq[a], seq[a + 1] = seq[a + 1], seq[a]

dummy = lambda seq: None

MUTATE = (
    replace,
    delete,
    insert,
    duplicate,
    swap,
    dummy,
    dummy,
    )

def repair_brackets(seq):
    """Attempts to lower the percentage of invalid regexes by
    matching orphaned brackets"""

    p_stack, new_seq = [], []
    for item in seq:
        if item in MATCH_BRACKETS:
            p_stack.append(item)
        elif item in CLOSE_BRACKETS:
            while p_stack and MATCH_BRACKETS[p_stack[-1]] != item:
                new_seq.append(MATCH_BRACKETS[p_stack[-1]])
                p_stack.pop()
            if not p_stack:
                continue
            else:
                p_stack.pop()
        new_seq.append(item)
    while p_stack:
        new_seq.append(MATCH_BRACKETS[p_stack.pop()])
    return new_seq

def compress(seq):
    new_seq = [seq[0]]
    last_match = seq[0]
    repeat = 1
    for item in islice(seq, 1, len(seq)):
        if item == last_match:
            repeat += 1
        else:
            if repeat > 1:
                new_seq.extend(list("{{{0}}}".format(repeat)))
            new_seq.append(item)
            last_match = item
            repeat = 1
    else:
        if repeat > 1:
            new_seq.extend(list("{{{0}}}".format(repeat)))
    return new_seq


def mutate(seq):
    """Random in-place mutation of sequence"""
    if len(seq) > LEN_LIMIT:
        seq[:] = seq[:LEN_LIMIT]
    c = choice(MUTATE)
    c(seq)

def crossover(seqA, seqB):
    """Recombination of two sequences at optimal breakpoints
    along each regex strand"""

    bpA = [item.start() for item in BREAKPOINT.finditer(''.join(seqA))]
    bpB = [item.start() for item in BREAKPOINT.finditer(''.join(seqA))]
    slObjA = (slice(*item) for item in zip(bpA, bpA[1:]))
    slObjB = (slice(*item) for item in zip(bpB, bpB[1:]))
    slices = zip_longest(
        (seqA[item] for item in slObjA),
        (seqB[item] for item in slObjB),
        fillvalue=[]
        )
    recombinant = (choice(item) for item in slices)
    return list(chain.from_iterable(recombinant))

#Fitness testing

def match_percentage(match):
    """Calculates the percentage a text actually matched
    by a regular expression"""

    if match and match.endpos:
        return (match.end() - match.start()) / match.endpos
    else:
        return 0.001

def fitness_test(seq, pos_matches, neg_matches):
    """Scoring algorithm to determine regex fitness"""

    try:
        self_str = ''.join(seq)
        regex = re.compile(self_str)
    except (re.error, IndexError):
        seq[:] = repair_brackets(seq)
        try:
            self_str = ''.join(seq)
            regex = re.compile(self_str)
        except (re.error, IndexError):
            return 0.001

    pos_score = sum(match_percentage(regex.search(item))
                    for item in pos_matches) / len(pos_matches) / 3

    neg_score = (1 - sum(match_percentage(regex.search(item))
                    for item in neg_matches) / len(neg_matches)) / 3

    self_score = match_percentage(regex.search(self_str)) / 3

    return pos_score + self_score + neg_score

#Population Management

def generate_pop(pos_matches, neg_matches, pop_size):
    sources = (pos_matches, REGEX_SEEDER)
    return [crossover(
        choice(choice(sources)), choice(choice(sources))
        ) for i in range(pop_size)]

def glean_pop(population, cutoff, fit_test, ft_args=()):
    scores = (fit_test(bug, *ft_args) for bug in population)
    ranked = sorted(zip(population, scores), key=itemgetter(1), reverse=True)
    maxItem = ranked[0]
    new_pop = next(zip(*ranked))[:cutoff]
    return maxItem, new_pop

def repopulate(population, pop_size):
    cutoff = len(population)
    for i in range(pop_size // cutoff):
        population.extend([crossover(choice(population), choice(population))
                           for i in range(cutoff)])
    population.extend([population[i][:] for i in range(pop_size - len(population))])

#Simulator
def simulate(pos_matches, neg_matches, pop_size=50, cutoff=10, threshold=1.0):
    population = generate_pop(pos_matches, neg_matches, pop_size)
    while True:
        for bug in population:
            mutate(bug)

        #Scoring step
        max_item, population = glean_pop(
            population,
            cutoff,
            fitness_test,
            (pos_matches, neg_matches)
            )

        #Exit condition:
        max_regex, max_score = max_item
        if max_score >= threshold:
            return max_score, max_regex
        """
        print(max_score, ''.join(max_regex))
        input("next?")"""

        #Repopulation Step:
        population = list(population)
        repopulate(population, pop_size)
\$\endgroup\$
  • 1
    \$\begingroup\$ Is this Python? \$\endgroup\$ – Griffin Aug 2 '12 at 11:04
  • 1
    \$\begingroup\$ @JoelCornett Writing my own simulate function is part of the usage? Your simulate function doesn't use argument #2. \$\endgroup\$ – Casey Kuball Aug 2 '12 at 16:18
  • 1
    \$\begingroup\$ @Darthfett: No that is an example of how you would call the function. I used variable names that were descriptive of their (hypothetical) contents. My mistake about parameter 2, it was a typo. no_match is supposed to be renamed no_match_list. Edited \$\endgroup\$ – Joel Cornett Aug 2 '12 at 16:26
  • 1
    \$\begingroup\$ Why do you call population = generate_pop(pos_matches, neg_matches, pop_size), but the generate_pop function never makes use of the neg_matches parameter? Also, can you please include an example of calling the function? Could I call it like simulate(["Hello","World","world"], ["woah","bad","dont match"])? \$\endgroup\$ – mbomb007 Jun 23 '15 at 19:03
  • 1
    \$\begingroup\$ Hey, it's been a few years since I wrote this. Just reading over the code without testing, it appears that yes, you can call the simulate() function as you described. And yes, you are right: I don't use the negative data for generating the initial population. \$\endgroup\$ – Joel Cornett Jun 24 '15 at 10:48
5
\$\begingroup\$

JavaScript regular expression that matches stuff like it.

/^\/\^\\\/\\\^[\\\[\]\/\^\${},\dd]{34}$/

You can test it like so:

(function test() {
    var re =/^\/\^\\\/\\\^[\\\[\]\/\^\${},\dd]{34}$/;
    var m  =/=([^;]+)/.exec(test)[1];
    return re.exec(m);
})();
\$\endgroup\$
  • 1
    \$\begingroup\$ What is "stuff like it"? Is this practical or useful in any way? \$\endgroup\$ – Casey Kuball Aug 4 '12 at 4:45
  • 2
    \$\begingroup\$ @Darthfett: It matches similar regular expressions that attempt to match themselves and this regular expression. No, it's not practical or useful in any way, but the only possible practical or useful, but also interesting, regular expression that matches itself is a regular expression to match regular expressions. Which has been done. \$\endgroup\$ – Ry- Aug 4 '12 at 14:08

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