Regexes kompilieren (durch Substitution)

21

Ihre Aufgabe ist es, reguläre Ausdrücke zu kompilieren ... indem Sie für jedes Zeichen in einem regulären Ausdruck eine Ersetzung angeben.

Regexes

Die Regexes unterstützen diese

REGEX       = (LITERAL REGEX / GROUP REGEX / STAR REGEX / ALTERNATIVE)
LITERAL     = 1 / 0
GROUP       = '(' REGEX ')'
STAR        = (LITERAL / GROUP) '*'
ALTERNATIVE = '('REGEX ('|' REGEX)*')'

Warum nur 1 oder 0? Es dient der Vereinfachung. Der Regex hat also nur die folgenden Zeichen:

*()|10

Es wird wie folgt interpretiert:

  1. * ist Kleene-Stern (Wiederholung der linken Gruppe oder 0-mal oder öfter).
  2. | ist eine Abwechslung (Übereinstimmung, wenn entweder der reguläre Ausdruck nach links oder der reguläre Ausdruck nach rechts übereinstimmt).
  3. () gruppiert.
  4. 1 stimmt mit Zeichen 1 überein.
  5. 0 Entspricht dem Zeichen 0.

Wie kompiliere ich?

Sie geben sechs Codefragmente an: eines, um jedes reguläre Zeichen zu ersetzen. Zum Beispiel, wenn Ihre Antwort lautet:

*: FSAGFSDVADFS
|: GSDGSAG
(: GSDG
): GDSIH
1: RGIHAIGH
0:GIHEBN

Dann ersetzen Sie jeden regulären Ausdruck durch das entsprechende Code-Snippet.

(0|11)*

wird verwandelt in:

GSDGGIHEBNGSDGSAGRGIHAIGHRGIHAIGHGDSIHFSAGFSDVADFS

Was soll das resultierende Programm tun?

Ihr Programm wird:

  1. Nimm die Eingabe.
  2. Gibt einen Wahrheitswert aus, wenn der reguläre Ausdruck mit der gesamten Eingabe übereinstimmt.
  3. Anderenfalls wird ein falscher Wert ausgegeben.

Eingaben außerhalb 01sind undefiniertes Verhalten. Die Eingabe kann leer sein.

Zusätzliche Regeln

  1. Für ein bestimmtes Regex-Zeichen muss das resultierende Snippet immer dasselbe sein.
  2. Danach wird kein Präfix- oder Suffixzeichen hinzugefügt.
  3. Der reguläre Ausdruck ist garantiert nicht leer.

Wertung

Das am wenigsten kombinierte Snippet ist der Gewinner. Die Punktzahl für den Beispielfall würde also folgendermaßen berechnet:

FSAGFSDVADFS+ GSDGSAG+ GSDG+ GDSIH+ RGIHAIGH+GIHEBN

12 + 7 + 4 + 5 + 8 + 6 = 42

Akangka
quelle
Soll jedes Snippet mindestens 1 Zeichen lang sein?
Trichoplax
Das Snippet kann eine Länge von Null haben. Die Bearbeitung ist OK.
Akangka
Ist die Sprache RegEx für diese Herausforderung gültig? : P
Loovjo
Ich denke, RegEx hat RegEx eingebaut. Ich bin gezwungen das zu tun. Ich möchte Retina und Regex ausschließen, laut Mego ist dies jedoch nicht erlaubt. Noch weiß ich nicht über Schnecken und Freunde.
Akangka
@ChristianIrwan Interessanterweise bin ich mir immer noch nicht sicher, ob dies in der Retina überhaupt lösbar ist, und selbst wenn, es wird alles andere als wettbewerbsfähig sein.
Martin Ender

Antworten:

7

Schnecken , 48 Bytes

0 -> )0(\0!(l.)(~

1 -> )0(\1!(l.)(~

( -> )0({{(

) -> )0}}(~

| -> )0}|{(

* -> )0),(~

Wenn wir nach Teilübereinstimmungen suchen müssten, anstatt nur die vollständigen Eingaben abzugleichen, wäre dies sehr einfach. 0würde werden \0, 1würde werden \1, *würde werden ,, und die anderen würden sich selbst zuordnen. Stattdessen gibt es eine Menge Spielereien, die verhindern, dass Spiele an einem anderen Ort als dem Anfang beginnen oder an einem anderen Ort als dem Ende enden. !(l.)ist eine Zusicherung, die fehlschlägt, wenn der Beginn der Übereinstimmung nicht am Anfang der Eingabe liegt. ~Stimmt mit einer Zelle außerhalb der Eingabe überein, sodass sie zu allen Zeichen hinzugefügt wird, die am Ende des regulären Ausdrucks stehen dürfen. Wenn ein anderes Regex-Zeichen folgt, wird es durch einen numerischen Quantifizierer aufgehoben0was erfordert, dass es 0-mal übereinstimmt und im Wesentlichen auskommentiert. Damit *( ,) korrekt funktioniert, obwohl der Dummy-Out-of-Bound-Test im Weg ist, werden die Regeln für die Klammerzuordnung der Sprache häufig verwendet. Aus der Dokumentation:

Übereinstimmende Paare von Klammern ()oder geschweiften Klammern {}verhalten sich erwartungsgemäß (wie Klammern in Regex), es ist jedoch auch möglich, die Hälfte eines Paares wegzulassen und es nach den folgenden Regeln abzuleiten. )oder }gruppiert alles nach links, bis die nächste nicht geschlossene Gruppenöffnungsanweisung desselben Typs ( (bzw. desselben Typs {) oder der Beginn des Musters, falls keine vorhanden ist. Es schließt alle nicht geschlossenen Öffnungsanweisungen des entgegengesetzten Typs in der Mitte dieses Bereichs. Ein ansonsten nicht passendes Muster (oder {wird am Ende des Musters geschlossen.

Klar wie Schlamm, oder?

Feersum
quelle
Seufz, ich vergesse, dass es außerhalb von Regex sogar eine passende Sprache gibt. Gute Arbeit, aber leider keine Gegenstimme (auch keine Gegenstimme)
Akangka
@ChristianIrwan Auf dieser Website gibt es tatsächlich eine Herausforderung für die Entwicklung von 2d-Matching-Sprachen, von denen die meisten 1d-Anwendungen entartet sind. codegolf.stackexchange.com/questions/47311/…
Sparr
7

CJam, 151 Bytes

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

Die Zeilen entsprechen den Zeichen 01(|)*(in dieser Reihenfolge). Probieren Sie es online!

Dies verwendet keine eingebauten regulären Ausdrücke oder andere Arten der Mustererkennung. Tatsächlich hat CJam keine dieser Funktionen. Stattdessen beginnt es mit dem regulären Ausdruck, den es darstellt, und erstellt alle möglichen Zeichenfolgen, mit denen es übereinstimmen könnte , um schließlich zu überprüfen, ob die Benutzereingabe eine davon ist.

Testläufe

Im Folgenden wird ein Programm verwendet, das einen regulären Ausdruck aus STDIN liest, jedes seiner Zeichen durch das richtige Snippet ersetzt und schließlich den generierten Code auswertet, um festzustellen, ob er mit der im Befehlszeilenargument angegebenen Eingabe übereinstimmt.

$ cat regex.cjam
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

"N%ers~
$ cjam regex.cjam '' <<< '(|)'
1
$ cjam regex.cjam '0' <<< '(|)'
0
$ cjam regex.cjam '' <<< '0(|)'
0
$ cjam regex.cjam '0' <<< '0(|)'
1
$ cjam regex.cjam '' <<< '(0|11)*'
1
$ cjam regex.cjam '0' <<< '(0|11)*'
1
$ cjam regex.cjam '11' <<< '(0|11)*'
1
$ cjam regex.cjam '011011000' <<< '(0|11)*'
1
$ cjam regex.cjam '1010' <<< '(0|11)*'
0

Dies ist leider nicht besonders schnell. Es wird ziemlich schnell ersticken, wenn mehr als 9 Zeichen in der Eingabe oder mehr als ein einzelner Kleene-Stern in der Regex enthalten sind.

Auf Kosten von 5 zusätzlichen Bytes - für insgesamt 156 Bytes - können kürzere Zeichenfolgen generiert werden, um die potenziellen Eingaben mit diesen abzugleichen und sie zu deduplizieren. Dies ändert nichts an der Funktionsweise des Codes. es macht es nur effizienter.

$ cat regex-fast.cjam 
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+eas,)m*:sSf-L|\"T

"N%ers~
$ cjam regex-fast.cjam '0101001010' <<< '(01|10)*'
0
$ cjam regex-fast.cjam '011001101001' <<< '(01|10)*'
1
$ cjam regex-fast.cjam '0' <<< '(0*1)*'
0
$ time cjam regex-fast.cjam '101001' <<< '(0*1)*'
1
Dennis
quelle
Ich habe noch eine Idee, wie ich das kürzer und / oder schneller machen könnte. Ich werde eine Erklärung hinzufügen, wenn ich mit den Ergebnissen zufrieden bin.
Dennis
Es scheint überflüssig zu sein `-escaping of the für „` im Muster *. Unabhängig davon , dass ich dieses Programm nicht bekommen konnte jede Eingabe akzeptieren, auch für den einfachstenen Fall , in dem der Regex nur aus a 0(Test in siehe Online - Interpreter ). Am
Mache
1
@matz Mein Code verwendet Befehlszeilenargumente, die in diesem Interpreter nicht implementiert sind. Versuchen Sie es stattdessen mit diesem.
Dennis