Regex, die nur sich selbst entspricht

339

Es gibt einige ziemlich coole Herausforderungen, bei denen es um Regex geht ( selbstanpassender Regex , Regex-Validierung von Regex )

Das mag unmöglich sein, aber gibt es einen regulären Ausdruck, der NUR mit sich selbst übereinstimmt?

HINWEIS: Trennzeichen müssen enthalten sein:

zum Beispiel /thing/muss passen /thing/und nicht thing. Die einzige Übereinstimmung, die für Ihren Ausdruck möglich ist, muss der Ausdruck selbst sein. Viele Sprachen ermöglichen die Implementierung einer Zeichenfolge anstelle eines regulären Ausdrucks. Zum Beispiel in Go

package main

import "fmt"
import "regexp"

func main() {

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

Um der Herausforderung willen soll der Ausdruck jedoch abgegrenzt sein (Startsymbol, Ausdruck, Endsymbol ex: /fancypantpattern/oder @[^2048]@), wenn Sie Anführungszeichen als Trennzeichen verwenden möchten, sei es auch. Ich denke, angesichts der offensichtlichen Schwierigkeit dieses Problems wird es keinen großen Unterschied machen.

Um Ihnen weiterzuhelfen:

Schneller Hack, den ich für rubular.com zusammengestellt habe (eine Webseite für die Bearbeitung von 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;

Auch wenn dies technisch gesehen ein "Code-Golf" ist, bin ich sehr beeindruckt, wenn jemand eine Antwort findet / beweist, dass dies unmöglich ist.

Link ist jetzt behoben. Entschuldigung an alle

Bisher beste Antwort: jimmy23013 mit 40 Zeichen

Dylan Madisetti
quelle
3
Offensichtlich funktioniert jeder reguläre Ausdruck, der nur Literale enthält: //, / a /, / xyz / usw. Es kann sinnvoll sein, zu verlangen, dass der reguläre Ausdruck eine nicht-wörtliche Operation enthält.
Brotkasten
9
Literale funktionieren nicht, weil Sie die Backslashes zum Beispiel / aaa / passen müssen, aaaaber nicht / aaa /
Dylan Madisetti
2
@DylanMadisetti Müssen wir //Trennzeichen verwenden oder können wir andere Trennzeichen auswählen (PCRE unterstützt so ziemlich jedes Zeichen, und Sie können insbesondere übereinstimmende Klammern / Klammern / Klammern als Trennzeichen verwenden).
Martin Ender
3
Ich denke, dass dies ein ziemlich nettes mathematisches / rechnerisches Problem ist und der Beweis möglicherweise nicht einfach ist ... Viele wichtige Theoreme begannen als eine einfache Frage, mit der man spielen konnte, also wird es vielleicht in 5 Jahren einen Wikipedia-Artikel "Madisetti-Problem" geben;)
Paweł Tokarz
3
Ja genau. In einigen Sprachen (z. B. grep in bash) ist das Trennzeichen im Wesentlichen eine leere Zeichenfolge. Die Annahme, dass reguläre Ausdrücke Trennzeichen erfordern, ist also schon an erster Stelle falsch. Da grep eine der frühesten Implementierungen von regulären Ausdrücken ist, hat die kanonische Definition von regulären Ausdrücken keine Begrenzer. Die falscheste Manifestation dieser Annahme ist PHP, für das zwei Trennzeichen erforderlich sind: "/und/"
slebetman

Antworten:

590

PCRE-Geschmack, 261 289 210 184 127 109 71 53 51 44 40 Bytes

Ja, es ist möglich!

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

Probieren Sie es hier aus. ( /Wird jedoch als Begrenzer für Regex101 angezeigt.)

Bitte nehmen Sie keine unnötigen Änderungen (Updates) auf der Regex101-Seite vor. Wenn Ihre Bearbeitung nicht das Verbessern, Ausprobieren oder Testen dieser regulären Ausdrücke beinhaltet, können Sie sie auf der Startseite abspalten oder neue erstellen .

Die Version funktioniert auf Regex101 (44 Bytes) korrekter:

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

Probieren Sie es hier aus.

Dies ist viel einfacher als die ursprüngliche Version und funktioniert eher wie eine traditionelle Quine. Es wird versucht, eine Zeichenfolge zu definieren, ohne sie zu verwenden, und sie an einer anderen Stelle zu verwenden. Sie kann also sehr nahe an einem Ende des regulären Ausdrucks platziert werden, um die Anzahl der Zeichen zu verringern, für die mehr Zeichen zum Definieren des übereinstimmenden Musters benötigt und die mehrmals wiederholt werden.

Erklärungen:

  • \Q^\/()(?R){2}\/\z|\1\Qstimmt mit der Zeichenfolge überein ^\/()(?R){2}\/\z|\1\Q. Dabei wird eine Eigenheit verwendet, \Q...\Edie nicht geschlossen werden muss, und Trennzeichen ohne Trennzeichen funktionieren in \Q. Dies hat dazu geführt, dass einige frühere Versionen nur auf Regex101 und nicht lokal funktionieren. Aber zum Glück hat die neueste Version funktioniert, und ich habe damit ein paar Bytes mehr abgezogen.
  • \1vor den \QÜbereinstimmungen mit der erfassten Gruppe 1. Da Gruppe 1 in dieser Option nicht vorhanden ist, kann sie nur in rekursiven Aufrufen übereinstimmen. Bei rekursiven Aufrufen werden leere Zeichenfolgen abgeglichen.
  • (?R){2}ruft den gesamten regulären Ausdruck zweimal rekursiv auf, was ^\/()(?R){2}\/\z|\1\Qfür jedes Mal zutrifft .
  • () Fängt nur eine leere Zeichenfolge in Gruppe 1 ein, wodurch die andere Option in rekursiven Aufrufen aktiviert wird.
  • ^\/()(?R){2}\/\zÜbereinstimmungen (?R){2}mit Begrenzungszeichen hinzugefügt, vom Anfang bis zum Ende. Die \/vor den rekursiven Aufrufen haben auch sichergestellt, dass diese Option selbst nicht mit rekursiven Aufrufen übereinstimmt, da sie nicht am Anfang der Zeichenfolge steht.

51 Bytes mit geschlossen \Q...\E:

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

Probieren Sie es hier aus.

Originalversion, 188 Bytes

Vielen Dank an Martin Büttner für das Abschlagen von ca. 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}$/

Probieren Sie es hier aus.

Oder 210 Bytes ohne \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

Probieren Sie es hier aus.

Erweiterte Version:

/^(?=.{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

Erweiterungen mögen (?=und \1haben die sogenannten "regulären" Ausdrücke nicht mehr regulär gemacht, was auch Quines ermöglicht. Rückverweis ist nicht regelmäßig, Lookahead jedoch.

Erläuterung:

  • Ich benutze \2\anstelle von \Sonderzeichen zu entkommen. Wenn \2die leere Zeichenfolge übereinstimmt \2\x(wobei xes sich um ein Sonderzeichen handelt), stimmt sie mit der Zeichenfolge xselbst überein . Wenn \2Übereinstimmungen vorhanden sind \2\, werden sie \2\xmit der entkoppelten übereinstimmen. \2In den beiden Spielen der Gruppe 1 kann Regex unterschiedlich sein. Beim ersten Mal \2sollte die leere Zeichenfolge übereinstimmen, und beim zweiten Mal \2\.
  • \Q\2\)){2}.{11}$\E\/\z(Zeile 1) entspricht 15 Zeichen vom Ende. Und .{11}$(Zeile 7) entspricht 11 Zeichen ab dem Ende (oder vor einer abschließenden neuen Zeile). Das Muster unmittelbar vor dem zweiten Muster muss also mit den ersten 4 oder 3 Zeichen des ersten Musters \2\.\2\|\2\)\2\)übereinstimmen , muss also mit ...\2\)oder übereinstimmen ...\2\. Es darf keinen nachgestellten Zeilenumbruch geben, da das letzte Zeichen sein soll ). Der übereinstimmende Text enthält keinen anderen Text )vor dem am weitesten rechts stehenden, daher müssen alle anderen Zeichen in der Liste enthalten sein \2. \2ist definiert als (.2.|), so kann es nur sein \2\.
  • In der ersten Zeile entspricht der gesamte Ausdruck genau 188 Zeichen, da alle Zeichen eine feste Länge haben. Die beiden Zeiten von Gruppe 1 entsprechen 45 * 2 Zeichen plus 29 Zeichen \2. Und Dinge nach Gruppe 1 stimmen mit 11 Zeichen überein. Die Gesamtlänge der beiden Male \2muss also genau 3 Zeichen betragen. Wissen \2zum zweiten Mal ist 3 Zeichen lang, es muss zum ersten Mal leer sein.
  • Alles außer dem Lookahead und \2sind Literale in Gruppe 1. Mit den zwei \2bekannten und den letzten aus der ersten Zeile bekannten Zeichen stimmt dieser reguläre Ausdruck genau mit einer Zeichenfolge überein.
  • Martin Büttner hat die Idee, mit Lookahead Gruppe 2 einzufangen und mit dem Quine-Teil zu überlappen. Dadurch wurden die Zeichen entfernt, die zwischen den beiden Zeiten von Gruppe 1 nicht auf die normale Weise maskiert wurden, und es wurde vermieden, dass das Muster mit denen meiner ursprünglichen Version übereinstimmt, und der reguläre Ausdruck wurde erheblich vereinfacht.

Regex ohne Rekursionen oder Rückverweise, 85 Bytes

Jemand könnte argumentieren, dass Ausdrücke mit Rekursionen oder Rückverweisen keine echten "regulären" Ausdrücke sind. Ausdrücke mit nur Lookahead können jedoch immer noch nur mit regulären Sprachen übereinstimmen, obwohl sie viel länger sein können, wenn sie durch traditionelle reguläre Ausdrücke ausgedrückt werden.

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

Probieren Sie es hier aus.

610 Bytes ohne \Q...\E(zum Golfen):

/^(?=.{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

Probieren Sie es hier aus.

Die Idee ist ähnlich.

/^(?=.{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

Der grundlegende reguläre Ausdruck

Wenn Lookahead nicht erlaubt ist, ist das Beste, was ich jetzt tun kann:

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

welche passt

\\(\\\(\\

Wenn ein {m,n}Quantifizierer nicht zulässig ist, ist dies unmöglich, da nichts, was nur mit einer Zeichenfolge übereinstimmen kann, mit einer Zeichenfolge übereinstimmen kann, die länger als sie selbst ist. Natürlich kann man immer noch so etwas erfinden, \qdas nur passt /\q/, und immer noch Ausdrücke mit diesem regulären Ausdruck sagen. Aber anscheinend wird nichts dergleichen von wichtigen Implementierungen unterstützt.

jimmy23013
quelle
5
Beeindruckend. Ich habe eine Weile damit verbracht, etwas anderes zusammenzubringen, ohne Erfolg.
Primo
76
Wie (zur Hölle) könnte ein Mensch so etwas hervorbringen?
Xem
61
Dies ist die Antwort mit der höchsten Bewertung auf dieser Website.
Cruncher
44
Das ist das Absurdeste, Unglaublichste, was ich je gesehen habe.
Alex A.
22
Jemand hat diesen Beitrag getwittert, also habe ich an einem Tag 49 Upvotes erhalten ...
jimmy23013