Unterschiede zwischen zwei regulären Ausdrücken und Berechnung ihrer Schnittmenge

 (phylactery.org)
2 Punkte von GN⁺ 2023-09-12 | 1 Kommentare | Auf WhatsApp teilen
  • Wenn reguläre Ausdrücke wie Mengen von Zeichenketten verglichen werden sollen, berechnet antimirov auf einer Ansicht die Inklusionsbeziehung und Gleichheit zweier Ausdrücke α und β sowie Schnittmenge und Differenzmenge
  • Der Ergebnisbereich zeigt Komplement und Relationsausdrücke gemeinsam an; Operationen wie ~α, α < β, α = β, α & β, α ^ β, α - β können geprüft werden
  • Wird eine separate Zeichenkette s eingegeben, lässt sich mit s ∈ α und s ∈ β sofort überprüfen, ob die einzelnen regulären Ausdrücke matchen
  • Die Syntax unterstützt ., Konkatenation, Alternative |, Wiederholung *·+·?·{n}·{m,n}, Zeichengruppen, negierte Zeichengruppen, Escapes und UTF-16-Unicode-Escapes
  • Verhaltensändernde Funktionen wie Anker, Zero-Width Assertions, Backreferences, Extraktion von Untergruppen, Suche/partielle Matches oder Ignorieren der Groß-/Kleinschreibung werden nicht unterstützt

Vergleich regulärer Ausdrücke und Mengenoperationen

  • Der Eingabebereich nimmt zwei reguläre Ausdrücke α und β entgegen
  • Die Ausgabe zeigt das Komplement sowie Relationen und Mengenoperationen der beiden regulären Ausdrücke gemeinsam an
    • ~α, ~β: Komplement des jeweiligen regulären Ausdrucks
    • α < β, α = β, α > β: Inklusionsbeziehung und Gleichheit der beiden regulären Ausdrücke
    • α & β: Schnittmenge
    • α ^ β: symmetrische Differenz
    • α - β: Differenzmenge
  • Wenn die Zeichenkette s eingegeben wird, kann in der Form s ∈ α, s ∈ β geprüft werden, ob sie zu den jeweiligen regulären Ausdrücken gehört
  • Außerdem werden die Größe jedes regulären Ausdrucks und die Anzahl der DFA-Zustände angezeigt
    • Im Beispielbildschirm gilt |α| = 1, |β| = 1
    • Im Beispielbildschirm haben dfa(α) und dfa(β) jeweils 1 Zustand

Unterstützte Syntax für reguläre Ausdrücke

  • Die Grundoperatoren behandeln einzelnes Zeichen, Konkatenation, Alternative und Wiederholung
    • .: Match auf ein beliebiges einzelnes Zeichen
    • xy: Konkatenation, die y nach x matcht
    • x|y: Match auf x oder y
    • x*: Wiederholung 0-mal oder öfter
    • (xyz): Gruppierung
    • (): leerer regulärer Ausdruck, der die leere Zeichenkette matcht
  • Häufig verwendete Kurzschreibweisen für Wiederholung werden ebenfalls unterstützt
    • x+: Wiederholung 1-mal oder öfter, äquivalent zu xx*
    • x?: optionales Match, äquivalent zu (x|)
    • x{n}: Konkatenation von x genau n-mal
    • x{m,n}: Konkatenation von x mindestens m-mal und höchstens n-mal
  • Für Zeichensätze und Escapes können folgende Formen verwendet werden
    • [a-z0-9]: Match auf ein einzelnes Zeichen aus der Gruppe
    • [^a-z0-9]: Match auf ein einzelnes Zeichen, das nicht in der Gruppe enthalten ist
    • \\c: Escape des Sonderzeichens c
    • \\u001a: Match auf das entsprechende UTF-16-Zeichen
    • Andere Zeichen wie a, b, c matchen sich selbst

Nicht unterstützte Funktionen

  • antimirov konzentriert sich darauf, reguläre Ausdrücke als Ziel von Mengenoperationen zu behandeln; folgende Funktionen sind ausgeschlossen
    • Anker ^, $
      • Allerdings müssen ^ und $ weiterhin escaped werden
    • Zero-Width Assertions, z. B. (?=...), (?<=...)
    • Backreferences, z. B. \\1, \\2
    • Extraktion von Untergruppen
    • Suche oder partielle Matches
    • Andere Flags zur Verhaltensänderung wie das Ignorieren der Groß-/Kleinschreibung
  • Weitere Informationen finden sich unter non/antimirov

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-09-12
Meinungen auf Hacker News

  • Ich habe eine ähnliche Web-Demo gebaut, die zeigt, wie ein regulärer Ausdruck über Parsing → NFA → DFA → minimaler DFA umgewandelt wird, und aus dem minimalen DFA bis hin zu LLVM IR/Javascript/WebAssembly ausgibt
    http://compiler.org/reason-re-nfa/src/index.html

  • Diese Bibliothek lässt sich nutzen, um eine Hierarchie von String-Klassen aufzubauen, wodurch man typisierte Strings stärker einsetzen kann
    Zum Beispiel haben E-Mails und URLs spezielle Grammatiken; ihr Werteraum ist eine Teilmenge aller nichtleeren Strings, und nichtleere Strings sind wiederum eine Teilmenge aller Strings
    Wenn das Typsystem weiß, dass ein E-Mail-String ein Untertyp eines nichtleeren Strings ist, kann es es als gültig ansehen, eine E-Mail-Adresse an eine Funktion zu übergeben, die einen nichtleeren String verlangt
    Diese Bibliothek kann verwendet werden, um die Definitionen und Hierarchien solcher String-Typen zu verifizieren; die Implementierung der Hierarchie unterscheidet sich je nach Sprache, etwa über Subclassing, Trait-Bounds usw.

    • In Sprachen mit Tagged-Union-Typen verwendet man diesen Ansatz häufig. Haskell-artiger Pseudocode sähe ungefähr so aus
      Der Konstruktor Address wird nicht exportiert, nur der Typ; in fromString :: Text -> Maybe Address wird validiert, und bei einer ungültigen Adresse wird Nothing zurückgegeben
      Die Gültigkeit sollte nicht in die Daten hineingemischt werden, sondern über einen separaten Pfad signalisiert werden; wenn eine Ausgabe nötig ist, holt man den umschlossenen Wert mit toText :: Address -> Text wieder heraus
    • Für die Validierung von E-Mail-Adressen sollte man besser keine regulären Ausdrücke verwenden
      https://news.ycombinator.com/item?id=31092912
    • Es gibt kaum etwas Merkwürdigeres, als sich an einem Spätsommermorgen darin zu vertiefen, was links vom @ in einer E-Mail-Adresse erlaubt ist und was nicht
      Die einfache Heuristik, dass jeder reguläre Ausdruck, der versucht, eine „gültige E-Mail-Adresse“ zu beschreiben, falsch ist, ist ziemlich sicher, verdirbt aber den ganzen Spaß
    • Ich frage mich, was mit „Werteraum“ gemeint ist

  • Reguläre Ausdrücke sind ein gutes Beispiel dafür, wie man eine ziemlich elegante und komplexe mathematische Theorie in ein wertvolles Interface verpackt
    Lineare Algebra fühlt sich ähnlich an

    • Es erstaunt mich immer wieder, dass sich, wenn ein geeigneter Körper gegeben ist, sehr viel Mathematik in lineare Algebra überführen lässt
      Selbst eine Möbius-Transformation w=(az+b)/(cz+d) der komplexen Ebene lässt sich in lineare Algebra übersetzen
    • Normalerweise bedeutet das, dass die Darstellung der Wahrheit näherkommt
      Gute Interfaces haben einen intrinsischen Wert, den viele stark ergebnisorientierte Menschen nicht richtig anerkennen
    • Wenn ich mich richtig erinnere, kam bei Conway unter https://store.doverpublications.com/0486485838.html die Verbindung zur linearen Algebra vor. Ich habe es nur grob überflogen

  • Diese tolle Seite berechnet binäre Relationen zwischen Paaren regulärer Ausdrücke und zeigt den DFA als Graphen an
    Sie demonstriert wirklich eindrucksvoll ziemlich nichttriviale Operationen auf regulären Ausdrücken

    • Sehr cool, aber streng genommen ist es nicht überraschend, dass sie keine Features unterstützt, die das Ganze nicht mehr regulär machen
      Trotzdem hätte ich gedacht, dass die Anker ^ und $ unproblematisch wären

  • Als ich „regex filter numbers divisible by 3“ eingefügt habe, ist die Seite komplett eingefroren: https://stackoverflow.com/q/10992279/41948
    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$
    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
    Ich frage mich, ob es eine kürzere Darstellung gibt

    • Diese Webseite hängt sich bei regulären Ausdrücken auf, die DFAs mit vielen Zuständen erzeugen
      Beispiele wären (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog
    • Laut Beschreibung der Seite werden Anker ohnehin nicht unterstützt

  • Ich wollte die Schnittmenge syntaktisch gültiger URLs und E-Mail-Adressen sehen, aber schon die Eingabe des folgenden URL-Regex dauert auf der Seite zu lange
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    Quelle: https://stackoverflow.com/a/3809435/623763

    • Ausdrücke wie (...){1,256} sind sehr schwergewichtig, und der Scala-JS-Code läuft am Ende entweder in ein Timeout oder bringt den Browser um
      Wenn man das durch (...)+ ersetzt, funktioniert es zumindest in meiner Umgebung. Kleine Ausdrücke wie (...){1,6} dürften in Ordnung sein

  • Ich war zunächst überrascht, dass die durch Vereinigung und Schnittmenge erzeugten regulären Ausdrücke nicht besonders knapp sind, habe es dann aber schnell nachvollzogen
    Zum Beispiel lässt sich die Schnittmenge von "y.+" und ".+z" mit dem sehr einfachen Ausdruck "y.*z" schreiben, und die Seite bestätigt auch die Äquivalenz. Das Tool gibt jedoch yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz* aus
    Es wird Gründe für solche Ergebnisse geben, aber einen minimalen regulären Ausdruck nach Kriterien wie Zeichenzahl auszugeben, dürfte deutlich schwieriger sein

    • Einer der Gründe dürfte sein, dass ".+z" nach der Umwandlung in einen deterministischen Automaten größer und unübersichtlicher wird

  • Ich habe dieses Konzept früher einmal verwendet, um die Validierungslogik für eine „IP RegEx filter“-Einstellung zu schreiben
    Ziel war, Nutzer IP-Filter per regulärem Ausdruck konfigurieren zu lassen. Das Marketing verstand CIDR nicht, kannte aber wegen Google Analytics reguläre Ausdrücke
    Wie lässt sich ein gültiger regulärer Ausdruck definieren? Die Schnittmenge mit dem regulären Ausdruck für „alle IPv4-Adressen“ durfte nicht leer sein und zugleich durfte er nicht identisch mit dem regulären Ausdruck für „alle IPv4-Adressen“ sein
    Das hat viele Beschwerden verhindert, dass der Filter nichts tue, aber fehlerhafte Filtereingaben selbst hat es nicht verhindert

    • Wäre nicht auch eine einfachere Lösung möglich gewesen? Statt zu versuchen, den Filter-Regex zu validieren, könnte man Beispiel-IP-Adressen anzeigen oder Nutzer eine Gruppe von Adressen eingeben lassen und dann zeigen, welche Adressen matchen und welche nicht
      Das hilft auch beim Umgang mit fehlerhaften Filtern

  • Damit es auf Mobilgeräten besser nutzbar ist, sollte man die Autovervollständigung im Eingabefeld für reguläre Ausdrücke wohl abschalten
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • Ich habe die Seite mit zwei ähnlichen Regexes für durch 3 teilbare Zahlen getestet, und sie blieb auch hängen, nachdem ich das ^ und $ an den Enden entfernt hatte
    Regex 1: ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))*
    Regex 2: ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))*
    Bis direkt vor dem letzten * wird alles geparst, aber in dem Moment, in dem man das * anhängt, bleibt die ganze Seite hängen
    Ohne das * hat es einen gültigen Validator erzeugt, der Zahlenstücke parst, deren Quersumme durch 3 teilbar ist