Regex autocompatible [cerrado]

15

Escriba una expresión regular no trivial que coincida con sí misma.

Por ejemplo, #.*$coincidirá con un comentario fuera de una cadena en python hasta el final de la línea, y también coincidirá con la sintaxis de expresiones regulares perl.

reglas :

  • La expresión regular debe hacer algo útil o práctico.
  • Indica qué sintaxis de expresiones regulares estás usando (por ejemplo, perl o POSIX).
  • El ganador es la respuesta más votada en cumplimiento.
  • ¡Ser creativo!
Casey Kuball
fuente
66
Hubo una pregunta sobre SO hace un tiempo, si hay una expresión regular que coincida con expresiones regulares válidas: stackoverflow.com/questions/172303/…
Patrick Oscity
55
Definir no trivial. Quiero decir, OK, Asería trivial, pero ¿dónde trazas la línea? Y por "autocompatibilidad", ¿quiere decir que solo puede coincidir con sí mismo, o también está permitido que coincida con otras cadenas? ¿ .Calificaría?
Sr. Lister
1
@padde que en realidad no era una expresión regular porque la gramática que describe la expresión regular no tiene contexto.
FUZxxl
1
@FUZxxl sí, eso es cierto, pero aún se podría escribir una expresión regular que coincida con otras expresiones regulares, pero no le importa la validez de las expresiones regulares coincidentes.
Patrick Oscity
1
@padde Bueno, entonces, ¿qué es una expresión regular no válida? Una expresión regular inválida obviamente no es una expresión regular. Así que esencialmente dice: "sí, eso es cierto, pero uno podría escribir una expresión regular que coincida con otras expresiones regulares, pero no le importa si la expresión regular coincidente es realmente una expresión regular" (¡sic!)
FUZxxl

Respuestas:

11

PITÓN

A continuación se muestra un generador de expresiones regulares de coincidencia automática. Proporciona dos listas, una contiene datos de entrenamiento que la expresión regular debe coincidir (además de coincidir), la otra contiene datos de entrenamiento que la expresión regular NO debe coincidir:

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)
Joel Cornett
fuente
1
¿Esto es Python?
Griffin
1
@JoelCornett ¿Escribir mi propia simulatefunción es parte del uso? Su simulatefunción no usa el argumento # 2.
Casey Kuball el
1
@Darthfett: No, ese es un ejemplo de cómo llamarías a la función. Usé nombres de variables que eran descriptivos de sus contenidos (hipotéticos). Mi error sobre el parámetro 2, fue un error tipográfico. no_matchse supone que debe renombrarse no_match_list. Editado
Joel Cornett
1
¿Por qué llamas population = generate_pop(pos_matches, neg_matches, pop_size), pero la generate_popfunción nunca hace uso del neg_matchesparámetro? Además, ¿puede incluir un ejemplo de llamada a la función? ¿Podría llamarlo así simulate(["Hello","World","world"], ["woah","bad","dont match"])?
mbomb007
1
Oye, han pasado algunos años desde que escribí esto. Simplemente leyendo el código sin probar, parece que sí, puede llamar a la simulate()función como lo describió. Y sí, tiene razón: no uso los datos negativos para generar la población inicial.
Joel Cornett
5

Expresión regular de JavaScript que coincide con cosas como esta.

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

Puedes probarlo así:

(function test() {
    var re =/^\/\^\\\/\\\^[\\\[\]\/\^\${},\dd]{34}$/;
    var m  =/=([^;]+)/.exec(test)[1];
    return re.exec(m);
})();
Ry-
fuente
1
¿Qué es "cosas así"? ¿Es esto práctico o útil de alguna manera?
Casey Kuball el
2
@Darthfett: coincide con expresiones regulares similares que intentan coincidir con esta expresión regular. No, no es práctico ni útil de ninguna manera, pero la única expresión práctica o útil posible, pero también interesante, que coincide con sí misma es una expresión regular que coincida con las expresiones regulares. Lo que se ha hecho.
Ry-