Tipps für Regex Golf

43

Ähnlich wie bei unseren Threads für sprachspezifische Golftipps: Was sind allgemeine Tricks, um reguläre Ausdrücke zu verkürzen?

Ich kann drei Gebrauch von regex sehen , wenn es um Golf geht: klassische regex Golf ( „hier ist eine Liste , die übereinstimmen sollten, und hier ist eine Liste , die fehlschlagen sollte“), Regex zu lösen Rechenprobleme und reguläre Ausdrücke als Teile der verwendeten größerer Golf Code. Sie können gerne Tipps zu einigen oder allen dieser Themen veröffentlichen. Wenn Ihr Tipp auf einen oder mehrere Geschmacksrichtungen beschränkt ist, geben Sie diese bitte oben an.

Halten Sie sich bitte wie gewohnt an einen Tipp (oder eine Familie eng verwandter Tipps) pro Antwort, damit die nützlichsten Tipps durch Abstimmung nach oben gelangen können.

Martin Ender
quelle
Flagrante Eigenwerbung: In welche Kategorie der Regex-Nutzung fällt diese? codegolf.stackexchange.com/a/37685/8048
Kyle Strand
@KyleStrand "Reguläre Ausdrücke, die als Teile eines größeren Code verwendet werden."
Martin Ender

Antworten:

24

Wenn nicht zu entkommen

Diese Regeln gelten für die meisten Geschmacksrichtungen, wenn nicht für alle:

  • ] muss nicht entkommen, wenn es nicht passt.

  • {und }brauchen nicht zu fliehen, wenn sie nicht Teil einer Wiederholung sind, zB {a}Streichhölzer im {a}wahrsten Sinne des Wortes. Auch wenn Sie so etwas abgleichen wollen {2}, müssen Sie nur einer davon entkommen, z {2\}.

In Charakterklassen:

  • ]Es muss nicht maskiert werden, wenn es das erste Zeichen in einem Zeichensatz ist, z. B. []abc]eines von ]abcoder wenn es das zweite Zeichen nach einem ist ^, z . B. [^]]alles andere als ]. (Bemerkenswerte Ausnahme: ECMAScript-Geschmack!)

  • [muss überhaupt nicht entkommen. Zusammen mit dem obigen Tipp bedeutet dies, dass Sie beide Klammern der fürchterlich kontraintuitiven Zeichenklasse zuordnen können [][].

  • ^Es muss nicht maskiert werden, wenn es nicht das erste Zeichen in einem Zeichensatz ist, z [ab^c].

  • -nicht entkommen nicht brauchen , wenn es entweder das erste (zweite nach einem ^) oder letztes Zeichen in einem Zeichensatz, zum Beispiel [-abc], [^-abc]oder [abc-].

  • Es müssen keine anderen Zeichen innerhalb einer Zeichenklasse maskiert werden, auch wenn es sich um Metazeichen außerhalb von Zeichenklassen handelt (mit Ausnahme des umgekehrten Schrägstrichs \).

Auch in einigen Geschmacksrichtungen ^und $werden buchstäblich abgeglichen, wenn sie sich nicht am Anfang bzw. Ende des regulären Ausdrucks befinden.

(Danke an @ MartinBüttner für das Ausfüllen einiger Details)

Sp3000
quelle
Einige bevorzugen es, den tatsächlichen Punkt zu maskieren, indem sie ihn in eine Zeichenklasse einschließen, in der kein Maskieren erforderlich ist (z. B. [.]). Ein normaler Escape-Vorgang würde in diesem Fall 1 Byte sparen\.
CSᵠ
Beachten Sie, dass [in Java ein Escapezeichen gesetzt werden muss. Ich bin mir jedoch nicht sicher, ob es sich um eine Intensivstation (für Android und iOS) oder um .NET handelt.
n̴̖̋h̷͉̃a̷̭̿h̷̭̿d̸̡̅ẗ̵̨́
18

Ein einfacher regulärer Ausdruck, der allen druckbaren Zeichen in der ASCII- Tabelle entspricht.

[ -~]
hwnd
quelle
1
pure Großartigkeit, alle Zeichen einer US-Standardtastatur! Hinweis: Die Standard-ASCII-Tabelle (ohne den erweiterten Bereich 127-255
CSᵠ
Ich benutze es oft, aber es fehlt ein allgemeines "normales" Zeichen: TAB. Und es wird davon ausgegangen, dass Sie LC_ALL = "C" (oder ähnliches) verwenden, da einige andere Gebietsschemas fehlschlagen.
Olivier Dulac
Kann der Bindestrich so verwendet werden, um einen beliebigen Zeichenbereich in der ASCII-Tabelle anzugeben? Funktioniert das für alle Arten von Regex?
Josh Withee
14

Kennen Sie Ihre Regex-Aromen

Es gibt eine überraschende Anzahl von Menschen, die glauben, dass reguläre Ausdrücke im Wesentlichen sprachunabhängig sind. Tatsächlich gibt es jedoch erhebliche Unterschiede zwischen den Geschmacksrichtungen, und besonders für Codegolf ist es gut, einige davon und ihre interessanten Merkmale zu kennen, damit Sie für jede Aufgabe die beste auswählen können. Hier finden Sie eine Übersicht über einige wichtige Geschmacksrichtungen und was sie von anderen unterscheidet. (Diese Liste kann nicht wirklich vollständig sein, aber lassen Sie mich wissen, wenn ich etwas wirklich Auffälliges verpasst habe.)

Perl und PCRE

Ich werfe diese in einen Topf, da ich mit dem Perl-Geschmack nicht allzu vertraut bin und sie größtenteils gleichwertig sind (PCRE ist schließlich für Perl-kompatible reguläre Ausdrücke). Der Hauptvorteil der Perl-Variante besteht darin, dass Sie Perl-Code tatsächlich aus dem regulären Ausdruck und der Substitution aufrufen können.

  • Rekursion / Unterprogramme . Wahrscheinlich das wichtigste Merkmal zum Golfen (das es nur in wenigen Geschmacksrichtungen gibt).
  • Bedingte Muster (?(group)yes|no).
  • Unterstützt von Fall zu ändern in der Ersatzzeichenfolge mit \l, \u, \Lund \U.
  • PCRE ermöglicht den Wechsel in Lookbehinds, wobei jede Alternative eine andere (aber feste) Länge haben kann. (Die meisten Aromen, einschließlich Perl, erfordern Lookbehinds mit einer festen Gesamtlänge.)
  • \G um eine Übereinstimmung mit dem Ende der vorherigen Übereinstimmung zu verankern.
  • \K um den Beginn des Spiels zurückzusetzen
  • PCRE unterstützt sowohl Unicode-Zeicheneigenschaften als auch Skripte .
  • \Q...\Elängere Serien von Charakteren zu entkommen. Nützlich, wenn Sie versuchen, eine Zeichenfolge zu finden, die viele Metazeichen enthält.

.NETZ

Dies ist wahrscheinlich der stärkste Geschmack mit nur sehr wenigen Nachteilen.

Ein wichtiges Manko beim Golfen ist, dass es keine Possessive Quantifiers wie einige andere Flavours unterstützt. Stattdessen .?+musst du schreiben (?>.?).

Java

  • Aufgrund eines Fehlers (siehe Anhang) unterstützt Java eine begrenzte Art von Lookbehind mit variabler Länge: Sie können bis zum Anfang der Zeichenfolge mit Lookbehind schauen, .*von wo aus Sie jetzt einen Lookahead wie starten können (?<=(?=lookahead).*).
  • Unterstützt Vereinigung und Schnittmenge von Zeichenklassen.
  • Bietet die umfassendste Unterstützung für Unicode mit Zeichenklassen für "Unicode-Skripte, -Blöcke, -Kategorien und -Binäreigenschaften" .
  • \Q...\E wie in Perl / PCRE.

Rubin

In neueren Versionen ist diese Variante ähnlich leistungsfähig wie PCRE, einschließlich der Unterstützung von Unterprogrammaufrufen. Wie Java unterstützt es auch die Vereinigung und Überschneidung von Zeichenklassen. Eine Besonderheit ist die eingebaute Zeichenklasse für hexadezimale Ziffern: \h(und die negierte \H).

Die nützlichste Funktion zum Golfen ist jedoch, wie Ruby mit Quantifizierern umgeht. Insbesondere ist es möglich, Quantifizierer ohne Klammern zu verschachteln. .{5,7}+funktioniert und funktioniert auch .{3}?. Im Gegensatz zu den meisten anderen Geschmacksrichtungen kann auf die untere Grenze eines Quantifizierers 0verzichtet werden, z . B. .{,5}äquivalent zu .{0,5}.

Wie für Subroutinen, ist der große Unterschied zwischen PCRE der Subroutinen und Rubys Subroutinen, dass Rubys Syntax ein Byte länger (?n)vs \g<n>, aber Rubys Subroutinen können für die Aufnahme verwendet werden, während PCRE Captures nach Unterprogramm beendet zurücksetzt.

Schließlich hat Ruby eine andere Semantik für zeilenbezogene Modifikatoren als die meisten anderen Varianten. Der Modifikator, der normalerweise min anderen Geschmacksrichtungen verwendet wird, ist in Ruby immer aktiviert. Also ^und $passen Sie immer den Anfang und das Ende einer Zeile an, nicht nur den Anfang und das Ende der Zeichenfolge. Dies kann Ihnen ein Byte ersparen, wenn Sie dieses Verhalten benötigen, aber es kostet Sie zusätzliche Bytes, wenn Sie dies nicht tun, da Sie jeweils ^und $durch \Aund ersetzen müssen \z. Außerdem wird der normalerweise aufgerufene Modifikator s(der .Zeilenvorschübe erstellt) min Ruby aufgerufen . Dies wirkt sich nicht auf die Anzahl der Bytes aus, sollte jedoch beachtet werden, um Verwirrung zu vermeiden.

Python

Python hat einen soliden Geschmack, aber mir sind keine besonders nützlichen Funktionen bekannt, die Sie sonst nirgendwo finden würden.

Es gibt jedoch eine alternative Variante , die das reModul irgendwann ersetzen soll und viele interessante Funktionen enthält. Zusätzlich zur Unterstützung für Rekursion, Lookbehinds variabler Länge und Zeichenklassen-Kombinationsoperatoren verfügt es über die einzigartige Funktion des Fuzzy Matching . Im Wesentlichen können Sie eine Reihe von Fehlern (Einfügungen, Löschungen, Ersetzungen) angeben, die zulässig sind, und die Engine gibt Ihnen auch ungefähre Übereinstimmungen.

ECMAScript

Das ECMAScript-Aroma ist sehr begrenzt und daher zum Golfen selten sehr nützlich. Das Einzige, was es zu tun hat, ist die negierte leere Zeichenklasse [^] , die mit einem beliebigen Zeichen übereinstimmt, sowie die bedingungslos fehlerhafte leere Zeichenklasse [](im Gegensatz zu der üblichen (?!)). Leider weist der Geschmack keine Merkmale auf, was letzteres für normale Probleme nützlich macht.

Lua

Lua hat seinen eigenen, ziemlich einzigartigen Geschmack, der ziemlich begrenzt ist (z. B. kann man nicht einmal Gruppen quantifizieren), aber eine Handvoll nützlicher und interessanter Funktionen enthält.

  • Es gibt eine große Anzahl von Abkürzungen für integrierte Zeichenklassen , einschließlich Interpunktion, Groß- / Kleinschreibung und Hexadezimalziffern.
  • Damit %bwird eine sehr kompakte Syntax unterstützt, um ausgewogene Zeichenfolgen abzugleichen. ZB %b()entspricht a (und dann alles bis zu einem Matching )(korrektes Überspringen innerer Matching- Paare). (und )kann hier zwei beliebige Zeichen sein.

Boost

Boosts Regex-Geschmack ist im Wesentlichen Perls. Es hat jedoch einige nette neue Funktionen für die Ersetzung von Regex, einschließlich Falländerungen und Bedingungen . Letzteres gibt es meines Wissens nur bei Boost.

Martin Ender
quelle
Beachten Sie, dass der Look-Ahead im Look-Behind die Begrenzung im Look-Behind überschreitet. Getestet in Java und PCRE.
n̴̖̋h̷͉̃a̷̭̿h̷̭̿d̷̰̀ĥ̷̳
Ist nicht .?+gleichbedeutend mit .*?
CalculatorFeline
@CalculatorFeline Ersteres ist ein besitzergreifender 0-or-1-Quantifizierer (in Geschmacksrichtungen, die besitzergreifende Quantifizierer unterstützen), letzteres ist ein 0-or-more-Quantifizierer.
Martin Ender
@ CalculatorFeline ah Ich verstehe die Verwirrung. Es gab einen Tippfehler.
Martin Ender
13

Kenne deine Charakterklassen

Die meisten Regex-Varianten haben vordefinierte Zeichenklassen. Stimmt beispielsweise \dmit einer Dezimalstelle überein, die drei Byte kürzer ist als [0-9]. Ja, sie können geringfügig voneinander abweichen, da sie \din einigen Varianten auch mit Unicode-Ziffern übereinstimmen. Bei den meisten Herausforderungen macht dies jedoch keinen Unterschied.

Hier sind einige Zeichenklassen, die in den meisten Regex-Varianten vorkommen:

\d      Match a decimal digit character
\s      Match a whitespace character
\w      Match a word character (typically [a-zA-Z0-9_])

Darüber hinaus haben wir auch:

\D \S \W

Das sind negierte Versionen der oben genannten.

Achten Sie darauf, Ihren Geschmack für zusätzliche Zeichenklassen zu überprüfen, die es möglicherweise hat. Zum Beispiel hat PCRE \Rfür Zeilenumbrüche und Lua sogar Klassen wie Klein- und Großbuchstaben.

(Danke an @HamZa und @ MartinBüttner für diesen Hinweis)

Sp3000
quelle
3
\Rfür Zeilenumbrüche in PCRE.
HamZa
12

Kümmern Sie sich nicht um Gruppen, die nicht erfassen (außer ...)

Dieser Tipp gilt (zumindest) für alle gängigen Perl-inspirierten Aromen.

Dies mag offensichtlich sein, aber (wenn Sie nicht Golf spielen) ist es empfehlenswert, (?:...)wenn immer möglich Gruppen zu verwenden, die keine Eroberungsgruppen sind . Diese beiden zusätzlichen Charaktere ?:sind beim Golfen jedoch verschwenderisch. Verwenden Sie daher einfach Erfassungsgruppen, auch wenn Sie sie nicht rückbeziehen möchten.

Es gibt jedoch eine (seltene) Ausnahme: Wenn Sie 10mindestens dreimal hintereinander auf eine Gruppe verweisen , können Sie tatsächlich Bytes sparen, indem Sie eine frühere Gruppe in eine nicht erfassende Gruppe umwandeln , sodass alle diese zu \10s werden \9. (Ähnliche Tricks gelten, wenn Sie die Gruppe 11mindestens fünfmal verwenden.)

Martin Ender
quelle
Warum braucht 11 5 Mal, um es wert zu sein, wenn 10 3 Mal benötigt?
Nic Hartley
1
Wenn @QPaysTaxes $9anstelle von $10oder $11einmal verwendet werden kann, wird ein Byte gespeichert . Das Verwandeln $10in $9erfordert eins ?:, also zwei Bytes, sodass Sie drei Sekunden benötigen $10, um etwas zu speichern. Das Umwandeln $11in $9erfordert zwei ?:Sekunden, was vier Bytes entspricht. Sie benötigen also fünf $11Sekunden, um etwas zu speichern (oder fünf von $10und $11kombiniert).
Martin Ender
10

Rekursion für die Wiederverwendung von Mustern

Eine Handvoll Aromen unterstützen die Rekursion ( meines Wissens Perl, PCRE und Ruby). Selbst wenn Sie nicht versuchen, rekursive Probleme zu lösen, kann diese Funktion viele Bytes in komplizierteren Mustern einsparen . Es ist nicht erforderlich, eine andere (benannte oder nummerierte) Gruppe innerhalb dieser Gruppe selbst anzurufen. Wenn Sie ein bestimmtes Muster haben, das mehrmals in Ihrem regulären Ausdruck vorkommt, gruppieren Sie es einfach und verweisen Sie auf dieses Muster außerhalb dieser Gruppe. Dies unterscheidet sich nicht von einem Unterprogrammaufruf in normalen Programmiersprachen. Also statt

...someComplexPatternHere...someComplexPatternHere...someComplexPatternHere... 

In Perl / PCRE können Sie Folgendes tun:

...(someComplexPatternHere)...(?1)...(?1)...

oder in Ruby:

...(someComplexPatternHere)...\g<1>...\g<1>...

vorausgesetzt, dies ist die erste Gruppe (natürlich können Sie im rekursiven Aufruf eine beliebige Nummer verwenden).

Beachten Sie, dass dies nicht mit einer Rückverweisung ( \1) identisch ist . Rückverweise stimmen mit genau der Zeichenfolge überein, mit der die Gruppe zuletzt übereinstimmte. Diese Unterprogrammaufrufe werten das Muster tatsächlich erneut aus. Als Beispiel für someComplexPatternHereeine längere Zeichenklasse:

a[0_B!$]b[0_B!$]c[0_B!$]d

Das würde sowas passen

aBb0c!d

Beachten Sie, dass Sie hier keine Rückverweise verwenden können, während das Verhalten beibehalten wird. Ein Rückverweis auf die obige Zeichenfolge schlägt fehl, da Bund 0und !nicht identisch sind. Bei Unterprogrammaufrufen wird das Muster jedoch tatsächlich neu bewertet. Das obige Muster ist völlig äquivalent zu

a([0_B!$])b(?1)c(?1)d

Erfassung in Unterprogrammaufrufen

Ein Hinweis zur Vorsicht für Perl und PCRE: Wenn die Gruppe 1in den obigen Beispielen weitere Gruppen enthält, werden sich die Unterprogrammaufrufe nicht an ihre Erfassungen erinnern. Betrachten Sie dieses Beispiel:

(\w(\d):)\2 (?1)\2 (?1)\2

Dies wird nicht übereinstimmen

x1:1 y2:2 z3:3

da nach der Rückkehr der Unterprogrammaufrufe die neue Erfassung der Gruppe 2verworfen wird. Stattdessen würde dieses Muster mit dieser Zeichenfolge übereinstimmen:

x1:1 y2:1 z3:1

Dies unterscheidet sich von Ruby, wo Subroutinenaufrufe tun ihre Aufnahmen behalten, so das Äquivalent Ruby - regex (\w(\d):)\2 \g<1>\2 \g<1>\2die erste der oben genannten Beispielen entsprechen würde.

Martin Ender
quelle
Sie können \1für Javascript verwenden. Und PHP auch (denke ich).
Ismael Miguel
5
@IsmaelMiguel Dies ist kein Rückverweis. Dies wertet das Muster tatsächlich erneut aus. Zum Beispiel (..)\1würde passen, abababer scheitern, abbawährend (..)(?1)letztere passen. Tatsächlich handelt es sich um einen Unterprogrammaufruf in dem Sinne, dass der Ausdruck erneut angewendet wird, anstatt buchstäblich mit dem übereinzustimmen, mit dem er beim letzten Mal übereinstimmte.
Martin Ender
Wow, ich hatte keine Ahnung! Jeden Tag etwas Neues lernen
Ismael Miguel
In .NET (oder anderen (?=a.b.c)(.[0_B!$]){3}d
Versionen
@ user23013 das scheint sehr spezifisch für dieses Beispiel. Ich bin nicht sicher, ob dies zutrifft, wenn ich ein bestimmtes Untermuster in verschiedenen Lookarounds wiederverwende.
Martin Ender
9

Ein Match scheitern lassen

Wenn Sie Regex verwenden, um Rechenprobleme zu lösen oder stark unregelmäßige Sprachen abzugleichen, ist es manchmal erforderlich, dass eine Verzweigung des Musters fehlschlägt, unabhängig davon, wo Sie sich in der Zeichenfolge befinden. Der naive Ansatz besteht darin, einen leeren negativen Lookahead zu verwenden:

(?!)

Der Inhalt (das leere Muster) stimmt immer überein, sodass der negative Lookahead immer fehlschlägt. Meistens gibt es jedoch eine viel einfachere Option: Verwenden Sie einfach ein Zeichen, von dem Sie wissen, dass es niemals in der Eingabe erscheint. Wenn Sie beispielsweise wissen, dass Ihre Eingabe immer nur aus Ziffern besteht, können Sie diese einfach verwenden

!

oder jedes andere nicht-stellige Nicht-Meta-Zeichen, das einen Fehler verursacht.

Auch wenn Ihre Eingabe möglicherweise Unterzeichenfolgen enthält, gibt es kürzere Wege als (?!). Jede Variante, bei der Anker im Gegensatz zum Ende innerhalb eines Musters erscheinen, kann eine der folgenden 2-Zeichen-Lösungen verwenden:

a^
$a

Beachten Sie jedoch , dass einige Aromen behandeln werden ^und $als wörtliche Zeichen in diesen Positionen, weil sie offensichtlich nicht wirklich Sinn als Anker machen.

In der ECMAScript-Variante gibt es auch die eher elegante 2-Zeichen-Lösung

[]

Dies ist eine leere Zeichenklasse, mit der versucht wird, sicherzustellen, dass das nächste Zeichen eines der Zeichen in der Klasse ist. Die Klasse enthält jedoch keine Zeichen, sodass dies immer fehlschlägt. Beachten Sie, dass dies in keiner anderen Variante funktioniert, da Zeichenklassen normalerweise nicht leer sein können.

Martin Ender
quelle
8

Optimieren Sie Ihre OPs

Wann immer Sie 3 oder mehr Alternativen in Ihrem RegEx haben:

/aliceblue|antiquewhite|aquamarine|azure/

Überprüfen Sie, ob es einen gemeinsamen Start gibt:

/a(liceblue|ntiquewhite|quamarine|zure)/

Und vielleicht sogar ein gemeinsames Ende?

/a(liceblu|ntiquewhit|quamarin|zur)e/

Hinweis: 3 ist nur der Anfang und würde die gleiche Länge ausmachen, 4+ würde einen Unterschied machen


Aber was ist, wenn nicht alle ein gemeinsames Präfix haben? (Leerzeichen nur zur Verdeutlichung hinzugefügt)

/aliceblue|antiquewhite|aqua|aquamarine|azure
|beige|bisque|black|blanchedalmond|blue|blueviolet|brown|burlywood
|cadetblue|chartreuse|chocolate|coral|cornflowerblue|cornsilk|crimson|cyan/

Gruppiere sie, solange die 3+ Regel Sinn macht:

/a(liceblue|ntiquewhite|qua|quamarine|zure)
|b(eige|isque|lack|lanchedalmond|lue|lueviolet|rown|urlywood)
|c(adetblue|hartreuse|hocolate|oral|ornflowerblue|ornsilk|rimson|yan)/

Oder verallgemeinern Sie, ob die Entropie Ihren Verwendungszweck erfüllt:

/\w(liceblue|ntiquewhite|qua|quamarine|zure
|eige|isque|lack|lanchedalmond|lue|lueviolet|rown|urlywood
|adetblue|hartreuse|hocolate|oral|ornflowerblue|ornsilk|rimson|yan)/

^ In diesem Fall sind wir sicher, dass wir keine clueoder bekommencrown slack Ryan

Dies "nach einigen Tests" verbessert auch die Leistung, da es einen Anker bietet , bei dem man beginnen kann.

CSᵠ
quelle
1
Wenn der gemeinsame Anfang oder das gemeinsame Ende länger als ein Zeichen ist, kann bereits die Gruppierung von zwei Zeichen einen Unterschied bewirken. Wie aqua|aquamarineaqua(|marine)oder aqua(marine)?.
Paŭlo Ebermann
6

Dieser ist ziemlich einfach, aber es lohnt sich zu erwähnen:

Wenn Sie feststellen, dass Sie die Zeichenklasse wiederholen [a-zA-Z], können Sie [a-z]den i( case- i nsensitive modifier) wahrscheinlich einfach verwenden und an Ihren regulären Ausdruck anhängen .

In Ruby sind beispielsweise die folgenden zwei regulären Ausdrücke gleichbedeutend:

/[a-zA-Z]+\d{3}[a-zA-Z]+/
/[a-z]+\d{3}[a-z]/i - 7 Bytes kürzer

In diesem Fall können die anderen Modifikatoren auch Ihre Gesamtlänge verkürzen. Anstatt dies zu tun:

/(.|\n)/

die jedes Zeichen (weil Punkt nicht Newline überein), verwenden Sie die s ingle-line - Modifikator s, das Punktspiel newlines macht.

/./s - 3 Bytes kürzer


In Ruby gibt es eine Menge eingebauter Zeichenklassen für Regex. Sehen Sie sich diese Seite an und suchen Sie nach "Character Properties".
Ein gutes Beispiel ist das "Währungssymbol". Laut Wikipedia gibt es eine Menge möglicher Währungssymbole, und es wäre sehr teuer, sie in eine Zeichenklasse einzuteilen ( [$฿¢₡Ð₫€.....]), während Sie jedes davon in 6 Bytes abgleichen können:\p{Sc}

Devon Parsons
quelle
1
Ausgenommen JavaScript, wo der sModifikator nicht unterstützt wird. :( Aber dort können Sie JavaScript proprietären /[^]/Trick verwenden.
Manatwork
Beachten Sie, dass (.|\n)dies in einigen Geschmacksrichtungen nicht funktioniert, da es .häufig auch nicht zu anderen Arten von Zeilentrennzeichen passt. Die übliche Möglichkeit, dies (ohne s) zu tun [\s\S], sind die gleichen Bytes wie (.|\n).
Martin Ender
@ Martinbüttner, meine idee war es zusammen mit den anderen leitungsenden tipps zu halten. Aber wenn Sie der Meinung sind, dass sich diese Antwort mehr auf Modifikatoren bezieht, habe ich keine Einwände, wenn Sie sie erneut veröffentlichen.
Manatwork
@manatwork erledigt (und fügte einen verwandten nicht-ES spezifischen Trick hinzu)
Martin Ender
6

Ein einfacher Sprachparser

Sie können einen sehr einfachen Parser mit einem RE wie erstellen \d+|\w+|".*?"|\n|\S. Die zuzuordnenden Token sind durch das RE- oder das RE-Zeichen getrennt.

Jedes Mal, wenn die RE-Engine versucht, an der aktuellen Position im Text eine Übereinstimmung zu finden, versucht sie das erste Muster, dann das zweite usw. Wenn dies fehlschlägt (z. B. bei einem Leerzeichen hier), fährt sie fort und versucht die Übereinstimmungen erneut . Ordnung ist wichtig. Wenn wir den \SBegriff vor dem \d+Begriff platzieren, \Swürde der zuerst auf ein Nicht-Leerzeichen passen, was unseren Parser beschädigen würde.

Der ".*?"String-Matcher verwendet einen nicht gierigen Modifikator, sodass immer nur ein String abgeglichen wird. Wenn Ihr RE keine nicht gierigen Funktionen hat, können Sie "[^"]*"die entsprechenden Funktionen verwenden.

Python-Beispiel:

text = 'd="dogfinder"\nx=sum(ord(c)*872 for c in "fish"+d[3:])'
pat = r'\d+|\w+|".*?"|\n|\S'
print re.findall(pat, text)

['d', '=', '"dogfinder"', '\n', 'x', '=', 'sum', '(', 'ord', '(', 'c', ')',
    '*', '872', 'for', 'c', 'in', '"fish"', '+', 'd', '[', '3', ':', ']', ')']

Golfed Python Beispiel:

# assume we have language text in A, and a token processing function P
map(P,findall(r'\d+|\w+|".*?"|\n|\S',A))

Sie können die Muster und ihre Reihenfolge für die Sprache anpassen, die Sie abgleichen möchten. Diese Technik eignet sich gut für JSON, einfaches HTML und numerische Ausdrücke. Es wurde schon oft mit Python 2 erfolgreich verwendet, sollte aber allgemein genug sein, um in anderen Umgebungen zu funktionieren.

Logik-Ritter
quelle
6

\K anstatt positiv auszusehen

PCRE und Perl unterstützen die Escape-Sequenz \K, die den Beginn des Spiels zurücksetzt. Dies ab\Kcderfordert, dass Ihre Eingabezeichenfolge enthält abcd, die gemeldete Übereinstimmung jedoch nur cd.

Wenn Sie zu Beginn Ihres Musters einen positiven Lookbehind verwenden (was wahrscheinlich der wahrscheinlichste Ort ist), können Sie in den meisten Fällen \Kstattdessen 3 Bytes verwenden und sparen:

(?<=abc)def
abc\Kdef

Dies ist für die meisten Zwecke äquivalent , jedoch nicht vollständig. Die Unterschiede bringen sowohl Vor- als auch Nachteile mit sich:

  • Vorteil: PCRE und Perl unterstützen keine Lookbehinds beliebiger Länge (nur .NET). Das heißt, Sie können so etwas nicht tun (?<=ab*). Aber mit können \KSie jede Art von Muster davor stellen! Funktioniert also ab*\K. Dies macht diese Technik in den Fällen, in denen sie anwendbar ist, erheblich leistungsfähiger.
  • Nach oben: Lookarounds ziehen sich nicht zurück. Dies ist relevant, wenn Sie etwas im Look erfassen möchten, um später einen Rückverweis zu erstellen. Es gibt jedoch mehrere mögliche Erfassungen, die alle zu gültigen Übereinstimmungen führen. In diesem Fall würde die Regex-Engine immer nur eine dieser Möglichkeiten ausprobieren. Bei Verwendung \Kdieses Teils wird der reguläre Ausdruck wie alles andere zurückverfolgt.
  • Nachteil: Wie Sie wahrscheinlich wissen, können sich mehrere Übereinstimmungen einer Regex nicht überschneiden. Häufig werden Lookarounds verwendet, um diese Einschränkung teilweise zu umgehen, da der Lookahead einen Teil der Zeichenfolge überprüfen kann, der bereits von einer früheren Übereinstimmung verwendet wurde. Also , wenn Sie wollten alle die Zeichen übereinstimmen, gefolgt ab Sie verwenden könnten (?<=ab).. Angesichts der Eingabe

    ababc
    

    das würde zum zweiten aund zum zweiten passen c. Dies kann nicht mit reproduziert werden \K. Wenn Sie verwendet haben ab\K., würden Sie nur das erste Match erhalten, da sich das jetzt abnicht in einem Lookaround befindet.

Martin Ender
quelle
Wenn ein Muster die \KEscape-Sequenz innerhalb einer positiven Zusicherung verwendet, kann der gemeldete Beginn einer erfolgreichen Übereinstimmung größer sein als das Ende der Übereinstimmung.
Hwnd
@hwnd Mein Punkt ist, dass ababces keine Möglichkeit gibt, sowohl die zweite aals auch die cmit zu vergleichen \K. Sie erhalten nur eine Übereinstimmung.
Martin Ender
Sie haben Recht, nicht mit der Funktion selbst. Sie müssten mit\G
hwnd
@hwnd Ah, ich verstehe deinen Standpunkt jetzt. Aber ich denke, an diesem Punkt (aus der Sicht des Golfspiels) sind Sie besser dran mit einem negativen Lookbehind, denn Sie könnten es tatsächlich sogar brauchen, da Sie nicht sicher sein können, ob das .Spiel vom letzten Match tatsächlich eines war a.
Martin Ender
1
Interessante Verwendung von \ K =)
hwnd
5

Passend zu jedem Charakter

In der ECMAScript- Variante fehlen die sModifikatoren, mit denen .jedes Zeichen (einschließlich Zeilenumbrüchen) übereinstimmt. Dies bedeutet, dass es keine Einzelzeichenlösung gibt, um vollständig beliebige Zeichen abzugleichen. Die Standardlösung in anderen Geschmacksrichtungen (wenn man saus irgendeinem Grund nicht verwenden möchte ) ist [\s\S]. Allerdings ist ECMAScript der einzige Geschmack (meines Wissens) , die Klassen leer Zeichen unterstützt, und hat daher eine viel kürzere Alternative: [^]. Dies ist eine negierte leere Zeichenklasse - das heißt, sie stimmt mit jedem beliebigen Zeichen überein.

Auch für andere Geschmacksrichtungen können wir aus dieser Technik lernen: Wenn wir nicht verwenden möchten s(z. B. weil wir immer noch die übliche Bedeutung von .an anderen Stellen benötigen ), kann es immer noch einen kürzeren Weg geben, um sowohl Zeilenvorschub- als auch druckbare Zeichen abzugleichen. vorausgesetzt, es gibt ein Zeichen, von dem wir wissen, dass es nicht in der Eingabe erscheint. Angenommen, wir verarbeiten Zahlen, die durch Zeilenumbrüche begrenzt sind. Dann können wir jedes Zeichen mit abgleichen [^!], da wir wissen, dass !das niemals Teil der Zeichenkette sein wird. Dies spart zwei Bytes gegenüber dem naiven [\s\S]oder [\d\n].

Martin Ender
quelle
4
In Perl \Nbedeutet dies genau, was .außerhalb des /sModus bedeutet, es sei denn, es wird nicht von einem Modus beeinflusst.
Konrad Borowski
4

Verwenden Sie Atomgruppen und Possessivquantifikatoren

Ich fand Atomgruppen ( (?>...)) und possessive Quantoren ( ?+, *+, ++, {m,n}+) manchmal sehr nützlich für den Golfsport. Es stimmt mit einer Zeichenfolge überein und lässt später kein Zurückverfolgen zu. Es wird also nur die erste übereinstimmende Zeichenfolge gefunden, die von der Regex-Engine gefunden wird.

Beispiel: Um eine Zeichenfolge mit einer ungeraden Anzahl von aZeichen am Anfang abzugleichen, auf die keine weiteren folgen a, können Sie Folgendes verwenden:

^(aa)*+a
^(?>(aa)*)a

Auf diese Weise können Sie Dinge wie .*frei verwenden, und wenn es eine offensichtliche Übereinstimmung gibt, wird es keine andere Möglichkeit geben, zu viele oder zu wenige Zeichen zu finden, wodurch Ihr Muster möglicherweise beschädigt wird.

In .NET Regex (das keine besitzergreifenden Quantifizierer hat) können Sie dies verwenden, um Gruppe 1 das größte Vielfache von 3 (mit maximal 30) Malen (nicht sehr gut golfen) zu platzieren:

(?>((?<-1>){3}|){10})
jimmy23013
quelle
1
ECMAscript fehlen auch Possessivquantifikatoren oder Atomgruppen :(
CSᵠ
4

Vergessen Sie eine erfasste Gruppe nach einem Unterausdruck (PCRE)

Für diesen Regex:

^((a)(?=\2))(?!\2)

Wenn Sie \ 2 nach Gruppe 1 löschen möchten, können Sie die Rekursion verwenden:

^((a)(?=\2)){0}(?1)(?!\2)

Es wird passen, aawährend das vorherige nicht passt. Manchmal können Sie auch ??oder sogar ?anstelle von verwenden {0}.

Dies kann hilfreich sein, wenn Sie häufig Rekursionen verwendet haben und einige der Rückverweise oder bedingten Gruppen an verschiedenen Stellen in Ihrem regulären Ausdruck vorkamen.

Beachten Sie auch, dass Atomgruppen für Rekursionen in PCRE angenommen werden. Das passt also nicht zu einem Buchstaben a:

^(a?){0}(?1)a

Ich habe es noch nicht in anderen Geschmacksrichtungen probiert.

Für Lookaheads können Sie zu diesem Zweck auch Doppel-Negative verwenden:

^(?!(?!(a)(?=\1))).(?!\1)
jimmy23013
quelle
4

Optionale Ausdrücke

Es ist manchmal nützlich, sich daran zu erinnern

(abc)?

ist meistens das gleiche wie

(abc|)

Es gibt jedoch einen kleinen Unterschied: Im ersten Fall erfasst die Gruppe entweder abcoder sie erfasst überhaupt nicht. Der letztere Fall würde einen Rückverweis bedingungslos zum Scheitern bringen. Im zweiten Ausdruck, die Gruppe wird entweder Capture abcoder eine leere Zeichenfolge, wobei letztere Fall eine Rückreferenzierung machen würde Spiel bedingungslos. Um das letztere Verhalten zu emulieren, ?müssten Sie alles in eine andere Gruppe einschließen, was zwei Bytes kosten würde:

((abc)?)

Die Version, die verwendet |wird , ist auch nützlich, wenn Sie den Ausdruck trotzdem in eine andere Form von Gruppe einschließen möchten und sich nicht um die Erfassung kümmern:

(?=(abc)?)
(?=abc|)

(?>(abc)?)
(?>abc|)

Schließlich kann dieser Trick auch auf Unreedy angewendet werden, ?wo ein Byte sogar in seiner Rohform gespeichert wird (und folglich 3 Bytes, wenn es mit anderen Gruppenformen kombiniert wird):

(abc)??
(|abc)
Martin Ender
quelle
1

Mehrere Lookaheads, die immer übereinstimmen (.NET)

Wenn Sie 3 oder mehr Lookahead-Konstrukte haben, die immer übereinstimmen (um Unterausdrücke zu erfassen), oder wenn ein Quantifizierer auf einem Lookahead von etwas anderem gefolgt wird, sollten sie sich in einer nicht unbedingt erfassten Gruppe befinden:

(?=a)(?=b)(?=c)
((?=a)b){...}

Diese sind kürzer:

(?(?(?(a)b)c))
(?(a)b){...}

wo asollte nicht der Name einer erfassten Gruppe sein. Sie können nicht |das Übliche in bund cohne ein weiteres Klammerpaar bedeuten .

Leider schienen die Bilanzkreise in den Bedingungen fehlerhaft zu sein, was sie in vielen Fällen unbrauchbar machte.

jimmy23013
quelle