Regex vs. Eigenbau (Effizienz vs. Lesbarkeit?)

[theo]

Aber mal eine ganz "menschliche" Frage: Gibt es eigentlich jemanden, der das wirklich "kann" oder schreiben da einfach alle voneinander ab oder hangeln sich durch ein cheat sheet, bis das "Gebastel" funktioniert?
Ich meine nur schon eine "Quick Reference" schlägt einen ja tot. Und man möchte es irgendwie auch gar nicht lernen...

[Warf]

Im grunde ist regex ganz einfach, es gibt eigentlich nur 3 grundsätzliche matchings:
1. Literal matching, das ist wenn du was hinschreibst wirds genau gematched also der ausdruck "a" machted genau den charakter "a"
2. Set Matching, [a-z] matched alle charaktere von a bis z. Oder um alphanumerisch mit _ und - zu matchen hat man [A-Za-z0-9_-], also ganz trivial. Eine ausnahme ist man kann das Komplement bilden mit einem ^ am anfang, dann matched [^a-z] alles was nicht in dem set ist.
3. Sonderzeichen und escape sequenzen wie $ für ende vom string und ^ für anfang vom string. Um die Sonderzeichen als literale zu verwenden müssen sie mit \ escaped werden (\$ z.b.)

Nur beim 3. muss ich ab und an mal nachschauen für spezielle sachen. Dann gibt es noch abkürzungen und makros. \d z.b. ist einfach ne kurzversion von [0-9], \b ist der beginn von nem wort, also space, tab, newline, start vom string, etc., und "." ist das set was alle charaktere enthält. Aber wenn man die sets selbst baun kann braucht man die nicht zu wissen, und ich muss zugeben außer \d und "." benutz ich die wenigsten davon

Damit kann man einzelne charaktere matchen, dann gibt es noch 3 möglichkeiten die zu kombinieren.
1. Konkatination durch simples hintereinander schreiben: ab matched zu erst den char a danach den char b
2. Optional durch |: a|b matched den char a oder b.
3. Klenee stern ist beliebig oft wiederholbar: a* ist eine wiederholung von 0-n mal der charakter a (also sowohl sowohl der leere string, als auch "a", "aa", "aaa", etc.).

Als hilfstool gibts dann oft noch + was einmal oder mehrfach ist, und ist nichts anderes als eine konkatination und ein Klenee stern. a+ ist im nichts anderes als "aa*" also ein "a" und danach 0-n viele "a"s. Sowie ? was ein kein oder einmal ist (also a? ist equivalent zu ()|a). Sowie exakte anzahlen (a{2} ist equivalent zu aa und a{1,2} ist equivalent zu a|aa). Das sind aber alles nur komfortfunktionen die die als makros für die oben genannten operationen gelten

Außerdem gibt es operator priorität * > concat > |. Wie in der Algebra potenzieren eine höhre priorität hat als multiplizieren was höhere priorität hat als addieren
beispiel ab*|ba ist equivalent zu (a(b*))|(ba)

Und zu guter letzt gibts noch klammern die genau wie in der algebra die höchste operator priorität haben und subausdrücke zusammen fassen können. Also (ab)*sagt beliebig viele wiederholoungen von ab, im gegensatz zu ab* was ein a und beliebig viele bs ist.

Wenn man diese 7 simplen regeln verstanden hat kann man regex. Alles drum herum sind nur comfortfunktionen, die ganz nützlich sein können (wie \d statt [0-9]) man aber nicht zwangsläufig braucht.

Das einzige was evtl noch wichtig ist ist standardmäßig ist regex immer greedy, d.h. sobald ein match gefunden wurde ist das das ergebnis, das ist auch die effizienteste weise. Das heist bei ".*Welt" würde bei "Hallo Welt Welt" der Matcher nach dem ersten "Welt" aufhören weil der Text wurde ja gefunden. Alternativ dazu gibt es longest match, was dann so lange weiter geht bis kein match gefunden werden kann, also in dem Fall bis zum ende des strings wo dann tatsächlich ein zweites Welt steht. Das bedeutet aber in worst case muss der matcher hier bis zum ende des strings durchlaufen obwohl er am anfang schon stoppen könnte.
Aber bisher brauchte ich in 99% aller Fälle nur greedy matching, was standardeisntellung normalerweise ist.

[theo]

Danke für die Zusammenfassung.
Aber es ist schon noch mehr, es benötigt eine gewisse Denkweise, die einem "normalen" Programmierer nicht direkt "angeboren" ist.
Ich habe hier mal ein Beispiel, das vielleicht ganz gut für Regex geeignet ist und auch nicht zu unübersichtlich wird.
Finde in diesem Text alle URLS zu "jquery-X.min.js"

test "https://code.jquery.com/jquery-3.5.0.min.js" test "https://code.jquery.com/jquery-3.5.1.min.js"

Ein Lösung ist (Aus dem Web kopiert).

([^"']*jquery[\-\d.]*\.min\.js[^"']*)

Der mittlere Bereich ist einigermassen einleuchtend, aber wie "denkt" man das als gesuchten "Match" / Einheit?
Wozu dient die Runde Klammer hier?
Warum suche ich nach "kein Hochkomma" oder bedeutet das ^ hier etwas anderes?

Vielleicht ist mein Problem, dass ich das eher schrittweise denke und nicht als gesamten Ausdruck.

[kupferstecher]

Es gibt den unterschied zwischen dem Matchen und dem Finden, beim Matchen (die Frage ob ein string in gänze eine bestimmte form hat) braucht man kein backtracking, da ist die Laufzeit O(n). Beim suchen wo das pattern irgendwo auftauchen kann muss man backtracken und braucht O(n*m) [...]

Ich hab jetzt mal ein bisschen danach gesucht, habe aber die dahintersteckenden Algorithmen noch nicht richtig verstanden. Ein Stichwort ist wohl der Thompson Algorithmus. Wenn jemand mit einfachen Worten beschreiben kann, was der 'Trick' dahinter ist, gerne!

https://swtch.com/~rsc/regexp/regexp1.html

[Warf]

([^"']*jquery[\-\d.]*\.min\.js[^"']*)

Der mittlere Bereich ist einigermassen einleuchtend, aber wie "denkt" man das als gesuchten "Match" / Einheit?
Wozu dient die Runde Klammer hier?
Warum suche ich nach "kein Hochkomma" oder bedeutet das ^ hier etwas anderes?

Vielleicht ist mein Problem, dass ich das eher schrittweise denke und nicht als gesamten Ausdruck.

DIe Runde Klammer ist vermutlich weil mache Regex implementationen dir nur das matching ergebnis ausgeben wenn es ne gruppe gibt, aber ist sonst theoretisch unnötig (für TRegExpr soweit ich weis z.b. nicht benötigt). Und genau das [^"'] bedeitet weder " noch ' beliebig oft. Vermutlich um nicht zufällige string erwähnungen zu matchen.

Ich hab jetzt mal ein bisschen danach gesucht, habe aber die dahintersteckenden Algorithmen noch nicht richtig verstanden. Ein Stichwort ist wohl der Thompson Algorithmus. Wenn jemand mit einfachen Worten beschreiben kann, was der 'Trick' dahinter ist, gerne!

Das ist im grunde automaten theorie. Beginnen wir mal ganz einfach ein DFA (Deterministic Finite Automata, DEA in deutsch) ist ein Automat der verschiedene states hat und mit eingaben zwischen den states wechseln kann. Kann man als graphen darstellen.

Z.B. ein Automat
Start->State1 mit input a
Start->State2 mit input b
State1->Endstate mit input c
State2->Endstate mit input c

Der automat startet immer im Start State. Geben wir dem automaten jetzt den charakter a wechselt er in den State 1, mit dem Charakter b in State2. Von State1 oder State2 geht es jeweils mit "c" in den Endstate.
Der automat hat ein match wenn er den endstate erreicht. Wird was anderes übergeben als einer der definierten übergänge endet man im sink/error state, aus dem man nicht mehr raus kommt.

Also bei dem wort "ac" geht der automat Start->State1->Endstate und ist damit erfolgreich. Bei dem wort "bc" geht es Start->State1->Endstate. Bei dem wort cc geht es Start->Sink->Sink und ist damit nicht erfolgreich. Bei den worten "a" oder "b" geht es zwar in einen validen State, aber kein endstate und damit ist es auch nicht erfolgreich.
Dieser automat hat also nur zwei pfade die in einem endstate landen und beschreibt damit den regex (ac)|(bc)

Um nun Regex zu implementieren nimmt man den Regex und Kompiliert diesen zu einem solchen DFA (der im grunde nix anderes ist als eine Map die States und Inputs auf Zielstates mappt). Dann lässt man den DFA laufen und wenn er in einem endstate steht findest du den match und wenn nicht dann nicht.
Daher ist Regex auch so effizient, du musst jeden charakter nur einmal nehmen, in den DFA werfen und wenn du an einem Endstate angekommen bist hast du ein match, wenn nicht dann nicht.
Vor allem geht das auch auf streams, das du jeden char einzeln auslesen kannst reinwerfen kannst und danach wieder vergessen kannst.

Stichwort für den Konvertierungsalgorithmus ist Kleenes Theorem, hier habe ich eine (englische) veranschauung gefunden: https://www.cs.cornell.edu/courses/cs28 ... leene.html
Grundsätzlich ists ein bischen komplizierter, man muss den Regex erst zu einem eps-NFA baun, den dann zu einem NFA reduzieren und den dann über die so genannten powerset (Potenzmengen) Konstruktion zu einem DFA umwandeln. Den kann man dann noch reduzieren um nicht so viel speicher zu fressen und man hat einen optimalen DFA

Wenn man jetzt nicht matched sondern sucht, muss man einen so genannten backtracking DFA bauen, bei dem man alle möglichen matches innerhalb eines strings sucht. Man fängt also praktisch mit dem ersten character des Strings an, und lässt den DFA laufen, findet er was: merkt man es sich. Dann geht man zum zweiten charakter und lässt den DFA über den kompletten rest string laufen, und so weiter.
Man muss also im worst case (wenn kein match gefunden wird) für jeden charakter über den ganzen rest string laufen. Daher ist das dann in O(n^2).
Das ganze heist backtracking da man nach jedem durchlauf zum anfang wieder backtracked und von vorne anfängt

PS: Es ist übrigens immer ne ganz nette übung automaten mal selbst zu implementieren. Ist tatsächlich was was ich ganz gerne mache wenn ich eine neue sprache lerne da es was ist was man einfach testen kann ohne große bibliotheken lernen zu müssen.
Dann aber ohne das ursprüngliche regex parsing sondern einfach als funktionen. Dann baut man z.b. sowas für den Regex (ab*|c*d)

Code: Alles auswählen

regex := OrExpr(ConcatExpr([LiteralExpr('a'), KleeneExpr(LiteralExpr('b)')]), ConcatExpr([KleeneExpr(LiteralExpr('c')), LiteralExpr('d')])
for c in input do
  regex.step(c);
if Regex.Endstate then
  WriteLn('Match');

Und sowas benutze ich dann auch tatsächlich öfters mal in projekten, z.B. aus meinen TermUtils:

Code: Alles auswählen

  // Special Keys (Arrows, F-Keys, Insert, Delete, whatever)
  manager.AddAutomaton(TEnclosedSequenceAutomaton.Create(csi,
    ['A'..'D', 'H', 'F', 'P'..'S', '~'], Ord(stCSI)));
  // F1-F4
  manager.AddAutomaton(TSingleLetterSequenceAutomaton.Create(ss3,
    ['P'..'S'], Ord(stSS3)));
  // Alt + key
  manager.AddAutomaton(TPrefixAutomaton.Create(#27, TUTF8CharAutomaton.Create(0),
    Ord(stModifiedChar)));
  // Char keys and Ctrl Keys
  manager.AddAutomaton(TUTF8CharAutomaton.Create(Ord(stChar)));

Mit z.b. einem Automaten der UTF8 chars matcht:

Code: Alles auswählen

procedure TUTF8CharAutomaton.DoStep(c: char);
begin
  if FSink then
    Exit;
  if Count = 1 then
  begin
    if Ord(c) and 128 = 0 then
      MakeFinal
    else if Ord(c) and $E0 = $C0 then
      FExpectedLength := 2
    else if Ord(c) and $F0 = $E0 then
      FExpectedLength := 3
    else if Ord(c) and $F8 = $F0 then
      FExpectedLength := 4
    else
      FSink := True;
  end
  else if (Count > FExpectedLength) or (ord(c) and $C0 <> 128) then
    FSink := True
  else if Count = FExpectedLength then
    MakeFinal;
end;

[theo]

([^"']*jquery[\-\d.]*\.min\.js[^"']*)

Der mittlere Bereich ist einigermassen einleuchtend, aber wie "denkt" man das als gesuchten "Match" / Einheit?
Wozu dient die Runde Klammer hier?
Warum suche ich nach "kein Hochkomma" oder bedeutet das ^ hier etwas anderes?

Vielleicht ist mein Problem, dass ich das eher schrittweise denke und nicht als gesamten Ausdruck.

DIe Runde Klammer ist vermutlich weil mache Regex implementationen dir nur das matching ergebnis ausgeben wenn es ne gruppe gibt, aber ist sonst theoretisch unnötig (für TRegExpr soweit ich weis z.b. nicht benötigt). Und genau das [^"'] bedeitet weder " noch ' beliebig oft. Vermutlich um nicht zufällige string erwähnungen zu matchen.

Nicht ganz. Das [^"'] wird offenbar benötigt, um den "Match-Bereich" auszudehnen auf die gesamte URL.
Das ist genau mein Problem: Wo fängt man hier mit Denken an?
Es sieht ja irgendwie so aus, als würde er nach "jquery"etc. suchen und dann zurück bis zum vorangehenden Anführungszeichen.
Wenn ich das [^"'] weg mache, matcht gar nichts mehr und wenn ich das * auch noch entferne, matcht nur noch das Dokument ohne Host-Teil.
Aber so richtig geheuer ist mir das nicht.
https://regex101.com/r/HQFyK6/1

[Warf]

Ah stimmt das matcht ja alles bis auf ' oder ". Da hatte ich selbst das inverse set nicht richtig gesehen. Es ist halt ein kleiner trick um sachen zwischen anführungszeichen zu matchen ohne die anführungszeichen selbst zu matchen. Z.B.

Code: Alles auswählen

(["'].*jquery[\-\d.]*\.min\.js.*["'])

Würde die Anführungszeichen mit matchen. Was sogar tatsächlich in dem Fall besser wäre, da man ja noch überprüfen muss das das erste und letzte anführungszeichen identisch sind (wobei man das auch mit einer regex bauen kann).

Gleichzeitig ist das ganze allerdings auch noch sehr faul, denn es matched sachen die nicht in einer URL vorkommen dürfen. korrekt wäre sowas:

Code: Alles auswählen

([A-Za-z0-9+.-]+:)?\/\/[A-Za-z0-9_~-]+(\.[A-Za-z0-9_~-]+)*(:\d+)?(\/[A-Za-z0-9_~-]+)*\/jquery[\-\d.]*\.min\.js(\?[A-Za-z0-9_~%.-]+=[A-Za-z0-9_~%.-]+(&[A-Za-z0-9_~%.-]+)*)?(#[A-Za-z0-9_~%.-]+)?

Das habe ich jetzt nicht akribisch selbst zusammen gebaut, sondern den regex lasse ich mir generieren:

Code: Alles auswählen

const
  DomainCharset = '[A-Za-z0-9_~-]';
  PathCharset = '[A-Za-z0-9_~%.-]';
  SchemeExpr = '([A-Za-z][A-Za-z0-9+.-]*:)?\/\/'; 
  HostExpr = DomainCharset + '+(\.' + DomainCharset + '+)*';
  PortExpr = '(:\d+)?';
  PathExpr = '(\/' + DomainCharset + '+)*';
  JQueryFileExpr = 'jquery[\-\d.]*\.min\.js';
  QueryExpr = '(\?' + PathCharset + '+=' + PathCharset  +'+(&' + PathCharset  + '+)*)?';
  FragmentExpr = '(#' + PathCharset + '+)?';

  JQueryURLExpr = SchemeExpr + HostExpr + PortExpr + PathExpr + '\/' + JQueryFileExpr + QueryExpr + FragmentExpr;

Und das ist übrigens extrem einfach zu bauen und debuggen, denn man kann jeden teil einzeln betrachten, und die meisten spezifikationen beschreiben syntax normalerweise in regulären ausdrücken. Z.b. aus dem RFC 3986:

Code: Alles auswählen

scheme      = ALPHA *( ALPHA / DIGIT / "+" / "-" / "." )

was sich 1-1 auf den ausdruck "[A-Za-z][A-Za-z0-9+.-]*" übertragen lässt.
Von daher, auch wenn das ein sehr komplizierter audruck ist, die teilausdrücke sind sehr einfach, und lassen sich direkt verifizeiren.

Tatsächlich habe ich mir schon öfter mal überlegt eine bibliothek für regex ausdrücke zu baun damit das einfacher geht. Sowas wie:

Code: Alles auswählen

  HostExpr = DomainCharset * OneOrMore + ('.' + DomainCharset * OneOrMore) * ZeroOrMore;

[theo]

Das Generieren des Ausdrucks könnte auch ein Anwendungsfall für die KI sein!
Das könnte ich mir gut vorstellen.

[af0815]

Das Generieren des Ausdrucks könnte auch ein Anwendungsfall für die KI sein!

[sarkasmus on]Ich glaube, das ist eines der wenigen Gebiete wo KI scheitern könnte[sarkasmus off]

[kupferstecher]

Beginnen wir mal ganz einfach ein DFA [...]

Warf, vielen Dank!

Die Idee mit dem Automaten ist mir jetzt klar, das Backtracking auch. Wo es noch klemmt, ist, wie man das Backtracking bei mehreren Pfaden vermeidet. Aber das ist schon mal eine gute Motivation das Thema weiter zu verfolgen~

[Warf]

Die Idee mit dem Automaten ist mir jetzt klar, das Backtracking auch. Wo es noch klemmt, ist, wie man das Backtracking bei mehreren Pfaden vermeidet. Aber das ist schon mal eine gute Motivation das Thema weiter zu verfolgen~

Das ist der Komplizierteste Teil an dem ganzen system, die Umwandlung von NFA zu DFA, denn ein DFA hat per definition in jedem input nur einen weg den er laufen kann, während der NFA mehrere haben kann. Das funktioniert durch die Potenzmengenkonstruktion, im grunde bläht man dabei den Automaten massiv auf, sodass es praktisch für jeden mögliche kombination an wegen zu einem zustand ein neuer State erzeugt (sehr übersimplifiziert). Damit wird der DFA ziemlich groß, aber wie gesagt dafür kenn er danach nochmal reduziert werden

[Joh]

Ich möchte mich hier auch mal als non-Regexer outen.

OK, als ich programmieren gelernt habe, gab es (für DOS) noch kein Regex...
(War übrigens Turbo Pascal 5; PC mit 2 Diskettenlaufwerken ohne Festplatte)

Danach kam Regex für mich immer nur in der (seltenen) Linux-Konsole an einem Server bei irgendwelchen Log-Files oder so zum Einsatz.
=> Suche nach einem String; OH je, da gibts ganz viele von; mit Regex durchackern.
Das ging, aber müühhhssseeellliiiggggg...

Dann ist mir der 100-Zeiler wesentlich lieber.
Und wenn dann in Zeile 17 steht:

Code: Alles auswählen

// Achtung, Wert xy kann hin und wieder einen Zusatzstring enthalten

dann verstehe ich auch nach 2 Jahren, warum diese komische if-Bedingung oder Schleife in Zeile 18 steht

Bei regex verstehe ich schon am nächsten Tag nicht mehr, was ich da tat.

[BeniBela]

Abgesehen von der Regex-Theorie gibt es auch noch die Praxis

RegExpr scheint gar nichts mit DFA/NFA zu machen, sondern nur Zeichen für Zeichen den String abzusuchen und bei Alternativen Backtracking zu machen.

Dann gibt es da noch eine Optimierung, dass in manchen Fällen Pos aufgerufen wird.


Deshalb verwende ich FLRE für regex. Das macht die Automaten und hat in Assembler geschriebene eigene Pos-Varianten, die noch schneller sein sollen.

Allerdings sind diese Assemblervarianten häufig abgestürzt. Und in Benchmarks habe ich gesehen, dass es mehr Zeit damit verbringt, diesen Automaten zu bauen, als Pos brauchen würde, um die Strings zu finden.

Deshalb verwende ich nun wenn möglich einen Eigenbau

[theo]

dann verstehe ich auch nach 2 Jahren, warum diese komische if-Bedingung oder Schleife in Zeile 18 steht
Bei regex verstehe ich schon am nächsten Tag nicht mehr, was ich da tat.

Genau so sehe ich das auch und bisher konnte mich niemand umstimmen.
Regex innerhalb von Pascal ist ein bisschen wie Assembler innerhalb von Pascal.
Es mag Fälle geben, wo man damit einen Code-Abschnitt optimieren kann, aber dafür muss es sehr, sehr gute Gründe geben.
Im Normalfall sollte man Kryptisches umschiffen.

[Winni]

dann verstehe ich auch nach 2 Jahren, warum diese komische if-Bedingung oder Schleife in Zeile 18 steht
Bei regex verstehe ich schon am nächsten Tag nicht mehr, was ich da tat.

Genau so sehe ich das auch und bisher konnte mich niemand umstimmen.
Regex innerhalb von Pascal ist ein bisschen wie Assembler innerhalb von Pascal.
Es mag Fälle geben, wo man damit einen Code-Abschnitt optimieren kann, aber dafür muss es sehr, sehr gute Gründe geben.
Im Normalfall sollte man Kryptisches umschiffen.

Yes Sir!

Für das bischen Parsen braucht man kein RegEx.

Das ist mit Kanonen auf Spatzen schießen.

Winni