Regex que corresponde apenas a si próprio

339

Há alguns desafios bem legais lá fora, envolvendo regex ( regex auto-matching , Regex validar regex )

Isso pode muito bem ser impossível, mas existe uma regex que SÓ corresponderá a si mesma?

NOTA, delimitadores devem ser incluídos:

por exemplo, /thing/deve corresponder /thing/e não thing. A única correspondência possível para sua expressão deve ser a própria expressão. Muitos idiomas permitem a implementação de uma string no lugar de uma expressão regular. Por exemplo, em Go

package main

import "fmt"
import "regexp"

func main() {

    var foo = regexp.MustCompile("bar")
    fmt.Println(foo.MatchString("foobar"))
}

mas para o desafio, deixe a expressão ser delimitada (símbolo inicial, expressão, símbolo final ex: /fancypantpattern/ou @[^2048]@), se você quiser argumentar aspas como seu delimitador, que assim seja. Penso que, dada a aparente dificuldade deste problema, não fará muita diferença.

Para ajudá-lo:

Corte rápido que montei para o rubular.com (uma página da web para edição de ruby ​​regex):

var test = document.getElementById("test")
,regex = document.getElementById("regex")
,delimiter="/"
,options = document.getElementById("options")
,delay = function(){test.value = delimiter + regex.value + delimiter + options.value}
,update = function(e){
    // without delay value = not updated value
    window.setTimeout(delay,0);
}
regex.onkeydown = update;
options.onkeydown = update;

Mesmo que isso seja tecnicamente 'código de golfe', ficarei muito impressionado se alguém puder encontrar uma resposta / provar que é impossível.

O link agora está corrigido. Desculpe a todos

Resposta vencedora até agora: jimmy23013 com 40 caracteres

Dylan Madisetti
fonte
3
Obviamente, qualquer expressão regular que inclua apenas literais funcionará: //, / a /, / xyz /, etc. Pode ser bom exigir que o regex inclua uma operação não literal.
breadbox 30/05
9
literais não vai funcionar porque você é obrigado a corresponder as barras invertidas, por exemplo / aaa / irá corresponder aaa, mas não / aaa /
Dylan Madisetti
2
@DylanMadisetti Temos que usar //delimitadores ou podemos escolher outros delimitadores (o PCRE suporta praticamente qualquer caractere e, em particular, você pode usar parênteses / chaves / colchetes correspondentes como delimitadores).
Martin Ender
3
Eu acho que esse é um problema matemático / computacional bastante agradável e a prova pode não ser fácil ... Muitos teoremas importantes começaram como uma pergunta simples de se jogar, então talvez em cinco anos haja o artigo da Wikipedia "Problema Madisetti";)
Paweł Tokarz
3
Sim, exatamente. Em alguns idiomas (pense em grep no bash), o delimitador é essencialmente uma string vazia. Portanto, supor que o regexp exija delimitadores já está errado em primeiro lugar. De fato, como grep é uma das implementações mais antigas do regexp, a definição canônica de regexp não possui delimitadores. A manifestação mais errada deste pressuposto é PHP que requer dois delimitadores: "/e/"
slebetman

Respostas:

590

Sabor PCRE, 261 289 210 184 127 109 71 53 51 44 40 bytes

Sim, é possível!

<^<()(?R){2}>\z|\1\Q^<()(?R){2}>\z|\1\Q>

Experimente aqui. (Mas /é mostrado como o delimitador no Regex101.)

Evite fazer edições desnecessárias (atualizações) na página Regex101. Se a sua edição não envolver realmente a melhoria, a tentativa ou o teste desse regex, você poderá bifurcar ou criar novos a partir da página inicial .

A versão funciona mais corretamente no Regex101 (44 bytes):

/^\/()(?R){2}\/\z|\1\Q^\/()(?R){2}\/\z|\1\Q/

Experimente aqui.

Isso é muito mais simples que a versão original e funciona mais como um quine tradicional. Ele tenta definir uma string sem usá-la e usá-la em um local diferente. Portanto, ele pode ser colocado muito próximo a uma extremidade da regex, para reduzir o número de caracteres que precisam de mais caracteres para definir o padrão de correspondência e repetir mais vezes.

Explicações:

  • \Q^\/()(?R){2}\/\z|\1\Qcorresponde à string ^\/()(?R){2}\/\z|\1\Q. Isso usa uma peculiaridade que \Q...\Enão precisa ser fechada e delimitadores sem escape trabalham \Q. Isso fez com que algumas versões anteriores funcionassem apenas no Regex101 e não localmente. Felizmente, porém, a versão mais recente funcionou e eu dediquei mais alguns bytes usando isso.
  • \1antes da \Qcorrespondência com o grupo capturado 1. Como o grupo 1 não existe nesta opção, ele pode corresponder apenas em chamadas recursivas. Em chamadas recursivas, corresponde a cadeias vazias.
  • (?R){2}chama o regex inteiro duas vezes recursivamente, o que corresponde ^\/()(?R){2}\/\z|\1\Qa cada vez.
  • () não faz nada além de capturar uma sequência vazia no grupo 1, o que habilita a outra opção em chamadas recursivas.
  • ^\/()(?R){2}\/\zcombina (?R){2}com delimitadores adicionados, do começo ao fim. O \/antes das chamadas recursivas também assegurava que essa opção não correspondesse nas chamadas recursivas, porque não estará no início da sequência.

51 bytes com fechado \Q...\E:

/\QE\1|^\/(\\)Q(?R){2}z\/\E\1|^\/(\\)Q(?R){2}z\/\z/

Experimente aqui.

Versão original, 188 bytes

Agradecemos a Martin Büttner por jogar cerca de 100 bytes!

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.\2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{11}$/

Experimente aqui.

Ou 210 bytes sem \Q...\E:

/^(?=.{194}\\2\\.\)\{2}\.\{12}\$\/D$)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{194}\2\\\2\\2\2\\\2\\\2\.\2\\\2\)\2\\\2\{2}\2\\\2\.\2\\\2\{12}\2\\\2\$\2\\\2\/D\2\$\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{12}$/D

Experimente aqui.

Versão expandida:

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)        # Match things near the end.
((?=(.2.|))                               # Capture an empty string or \2\ into group 2.
   \2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.
   \2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)      # 1st line escaped.
   \2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\) # 2nd line escaped.
){2}
.{11}$/x

Extensões como (?=e \1tornaram as chamadas expressões "regulares" não mais regulares, o que também possibilita quines. A referência anterior não é regular, mas sim.

Explicação:

  • Eu uso \2\no lugar de \para escapar de caracteres especiais. Se \2corresponde à sequência vazia, \2\x(onde xé um caractere especial) corresponde à xprópria. Se \2corresponder \2\, \2\xcorresponde ao escapado. \2nas duas correspondências do grupo 1 podem ser diferentes em regex. Na primeira vez \2deve corresponder à cadeia vazia e na segunda vez \2\.
  • \Q\2\)){2}.{11}$\E\/\z(linha 1) corresponde a 15 caracteres no final. E .{11}$(linha 7) corresponde a 11 caracteres do final (ou antes de uma nova linha à direita). Portanto, o padrão imediatamente antes do segundo padrão deve corresponder aos 4 ou 3 primeiros caracteres do primeiro padrão, portanto, \2\.\2\|\2\)\2\)deve corresponder a ...\2\)ou ...\2\. Não pode haver uma nova linha à direita porque o último caractere deve ser ). E o texto correspondente não contém outro )antes do mais à direita, portanto, todos os outros caracteres devem estar no \2. \2é definido como (.2.|), portanto, só pode ser \2\.
  • A primeira linha faz com que toda a expressão corresponda exatamente a 188 caracteres, já que tudo tem um comprimento fixo. As duas vezes do grupo 1 correspondem a 45 * 2 caracteres mais 29 vezes \2. E as coisas após o grupo 1 correspondem a 11 caracteres. Portanto, o comprimento total das duas vezes \2deve ser exatamente 3 caracteres. Sabendo \2que a segunda vez tem 3 caracteres, ele deve estar vazio pela primeira vez.
  • Tudo, exceto o lookahead e \2é literal no grupo 1. Com os dois tempos \2conhecidos e os últimos poucos caracteres conhecidos da primeira linha, esse regex corresponde exatamente a uma sequência.
  • Martin Büttner tem a idéia de usar o lookahead para capturar o grupo 2 e fazer com que ele se sobreponha à parte quine. Isso removeu os caracteres que não escapavam da maneira normal entre os dois tempos do grupo 1 e ajudou a evitar o padrão para correspondê-los na minha versão original, além de simplificar muito o regex.

Regex sem recursões ou referências anteriores, 85 bytes

Alguém pode argumentar que expressões com recursões ou referências anteriores não são expressões "regulares" reais. Mas expressões com apenas lookahead ainda podem corresponder apenas a idiomas regulares, embora possam ser muito mais longas se expressadas por expressões regulares tradicionais.

/(?=.*(\QE\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\E\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\z/

Experimente aqui.

610 bytes sem \Q...\E(para jogar golfe):

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}(.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\(.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

Experimente aqui.

A ideia é semelhante.

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)
((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)
(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}
  (.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}
    (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\
    (.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}
  (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

A expressão regular básica

Se lookahead não for permitido, o melhor que posso fazer agora é:

/\\(\\\(\\\\){2}/

que corresponde

\\(\\\(\\

Se o {m,n}quantificador não for permitido, é impossível porque nada que possa corresponder apenas a uma sequência pode corresponder a uma sequência mais longa que ela mesma. É claro que ainda é possível inventar algo como o \qque apenas corresponde /\q/e ainda dizer expressões com esse regular. Mas, aparentemente, nada disso é suportado pelas principais implementações.

jimmy23013
fonte
5
Impressionante. Passei um tempo tentando fazê-lo corresponder a outra coisa, sem sucesso.
primo
76
como (diabos) um humano poderia produzir uma coisa dessas?
X16
61
Isso merece ser a resposta mais votada neste site.
Cruncher
44
Essa é a coisa mais absurda e incrível que eu já vi.
Alex A.
22
Alguém twittou este post assim que eu comecei 49 upvotes em um dia ...
jimmy23013