RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet

Anwendungen, Tools, Userlibs und anderes nützliches.
Benutzeravatar
Sicro
Beiträge: 955
Registriert: 11.08.2005 19:08
Kontaktdaten:

Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet

Beitrag von Sicro »

STARGÅTE hat geschrieben: 15.09.2022 21:20Ja gut, das ist ja dann parallel mit mehrere Threads, aber das wird doch auch in deinem Modul gar nicht gemacht?
Sollte auch nur ein Pseudo-Code sein, wie man sich die Verarbeitung vorstellen kann.
STARGÅTE hat geschrieben: 15.09.2022 21:20Was du meinst, bzw. so wie ich das verstanden habe, wird der Regex für die Zahl und für den String "gleichzeitig" im DFA hinterlegt. Dass heißt, wenn der String geprüft wird, springt der DFA bei einer Zahl zu einem entsprechenden Zustand und bei einem ' zu einem entsprechenden anderen Zustand.
Hier hast du natürlich recht, dass das dann wirklich "gleichzeitig" verarbeitet wird, wohingegen mein Gruppen-Regex erst den einen CharacterSet prüft und erst beim Fehlschlag zum anderen geht.
Genau, so funktioniert das.
STARGÅTE hat geschrieben: 15.09.2022 21:20Ja gut, so "einfach" geht das natürlich nicht, denn du erzeugst ja dann logischerweise 65370 Linked Lists mit ihrem ganzen Overhead.
Du würdest wenn dann ein Pointer-Array benötigen (~65kB) und ein Datenpuffer [...]
Genau, leere Listen brauchen auch Speicher. Mit einer kleinen Änderung war es also nicht getan. Deshalb habe ich es vorerst bei den Maps belassen bis mir eine bessere Datenstruktur einfällt. Wie geschrieben, ich werde deinen Vorschlag ausprobieren. :allright:
Bild
Warum OpenSource eine Lizenz haben sollte :: PB-CodeArchiv-Rebirth :: Pleasant-Dark (Syntax-Farbschema) :: RegEx-Engine (kompiliert RegExes zu NFA/DFA)
Manjaro Xfce x64 (Hauptsystem) :: Windows 10 Home (VirtualBox) :: Neueste PureBasic-Version
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet

Beitrag von STARGÅTE »

Hallo Sicro,

habe jetzt mal ein bisschen rumgetestet.

Was mir zuerst auffällt ist, dass der NFA Modus sehr sehr langsam ist. Ich weiß nicht genau warum, vielleicht mache ich ja was falsch, aber ich habe z.B. einfach den Regex "\w+" erstellt und deine RegExEngine.pbi geparst.
Der NFA modus braucht hier 8 Sekunden, während DFA praktisch 0 Sekunden braucht. (ohne Debugger logischerweise)
Ein anderes "Problem" ist, dass die Erstellungszeit des DFA ziemlich schnell steigt, je mehr Platzhalterzeichen vorkommen:
".2" brauch 200ms, "..DE" braucht 8000ms und <...> stolze 16 sekunden.
Ähnliches bei Charaktersets:
"<\w+>" braucht 6 s (132 kB), "<\w+>.+" braucht 14 s (261 kB) und "<\w+>.+</\w+>" braucht 37 s (393 kB).
Mir ist durchaus klar, dass sowas ja nur einmal gemacht werden muss. Aber ich meine, eine Sprachen-Syntax ist ja durchaus größer/komplexer.

Ansonsten ist der DFA beim parsen schön schnell. Bei verschiedenen Testdateien (XML oder PB Quellcodes) bis zu 2 MB ist der DFA etwa genauso schnell wie ExamineRegularExpression von PureBasic. Wenn der Regex komplizierter wird, ist dein DFA deutlich schneller. Mein eigenes Include ist leider 20 mal langsamer, hier werde ich selbst auch noch mal etwas optimieren. Den NFA musste ich aber immer auskommentieren, weil er nicht fertig wurde.

Falsches matching habe ich aktuell noch nicht gefunden (im Rahmen deines aktuell noch begrenzten Syntax).
So wird bei dir der Stting "1234abcdefgh" mit dem Regex "\d*(34abc|a)" anders gematched als "üblich". Bei dir wird "1234abc" gefunden (längster Ausdrück), bei anderen Engines hingegen nur "1234a" weil \d* solange "frisst" bis es nicht mehr passt. Daher wurde dort ja das \d*? eingeführt.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
Sicro
Beiträge: 955
Registriert: 11.08.2005 19:08
Kontaktdaten:

Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet

Beitrag von Sicro »

Danke STARGÅTE :allright:
STARGÅTE hat geschrieben: 17.09.2022 12:36Was mir zuerst auffällt ist, dass der NFA Modus sehr sehr langsam ist. Ich weiß nicht genau warum, vielleicht mache ich ja was falsch, aber ich habe z.B. einfach den Regex "\w+" erstellt und deine RegExEngine.pbi geparst.
Der NFA modus braucht hier 8 Sekunden, während DFA praktisch 0 Sekunden braucht. (ohne Debugger logischerweise)
Der NFA-Matcher ist aktuell nur vollständigkeitshalber eingebaut. Normalerweise sollte man immer ein DFA erstellen oder den NFA-Matcher nur bei einfachen regulären Ausdrücken verwenden. Der Grund, warum der NFA-Matcher so langsam ist, ist, weil im Thompson-NFA schnell viele Epsilon-Übergänge existieren, denen gefolgt werden muss (z. B. bei "\w+" gibt es bis zu 608 Epsilon-Übergänge hintereinander). Die Auflösung der Epsilon-Übergänge wird derzeit nicht zwischengespeichert und muss bei jedem Aufruf von Match() wiederholt werden.
STARGÅTE hat geschrieben: 17.09.2022 12:36Ein anderes "Problem" ist, dass die Erstellungszeit des DFA ziemlich schnell steigt, je mehr Platzhalterzeichen vorkommen:
".2" brauch 200ms, "..DE" braucht 8000ms und <...> stolze 16 sekunden.
Ähnliches bei Charaktersets:
"<\w+>" braucht 6 s (132 kB), "<\w+>.+" braucht 14 s (261 kB) und "<\w+>.+</\w+>" braucht 37 s (393 kB).
Das sind alles komplexe reguläre Ausdrücke. Die Zeichenklasse "Punkt" generiert bereits einen NFA mit 262.386 Zuständen. Der "NFA zu DFA"-Algorithmus hat da sehr viel zu tun. Am Ende kommt ein DFA mit nur noch 259 Zuständen heraus.
STARGÅTE hat geschrieben: 17.09.2022 12:36Mir ist durchaus klar, dass sowas ja nur einmal gemacht werden muss. Aber ich meine, eine Sprachen-Syntax ist ja durchaus größer/komplexer.
Ich habe testweise einen Lexer erstellt, der die PureBasic-Sprache lexen kann: 1.315.347 NFA-Zustände danach 2.713 DFA-Zustände, was 31 Sekunden gedauert hat.

Ja, es dauert zu lange. Ich werde die NFA-Struktur umschreiben, damit sie bei den Übergängen Byte-Bereiche (min. Byte-Wert und max. Byte-Wert) unterstützt anstatt nur ein Byte-Wert. Das sollte die Anzahl der Epsilon-Zustände stark reduzieren. Der NFA-Matcher und die DFA-Erstellung sollten dann schneller sein.

Deinen Vorschlag, eine andere Datenstruktur für die Simple Case Unfolding Tabelle zu verwenden, habe ich ausprobiert. Folgendermaßen habe ich es umgesetzt:

Code: Alles auswählen

Structure CaseUnfoldStruc
  charsCount.a
  chars.l[0]
EndStructure

Global Dim *caseUnfold.CaseUnfoldStruc($10FFFF)

*caseUnfold($000041) = ?caseUnfoldTable + $000000
*caseUnfold($000061) = ?caseUnfoldTable + $000003
...

DataSection
  caseUnfoldTable:
  Data.a 0
  Data.l $000041
  Data.a 0
  Data.l $000042
  ...
EndDataSection
Ja, aktuell unterstützte ich nur UCS-2, wodurch nur ein Array($FFFF) erforderlich wäre, aber da ich bald UTF-16 unterstützen will, wäre später ein Array($10FFFF) erforderlich. Extrem viele Array-Indexe bleiben mit dieser Datenstruktur leider unbelegt (*caseUnfold() = 0):

Code: Alles auswählen

Anzahl der Array-Indexes:            1.114.111 (8.912.888 bytes für die Pointer (64-bit))
Anzahl der Array-Indexes ohne Daten: 1.111.234 (8.889.872 bytes für die Pointer (64-bit))
Eine Map hat hingegen nur die Einträge, die erforderlich sind.

Ich habe noch einen Fehler gefunden, der in der nächsten Beta-Version behoben ist:
  • Escapen von öffnenden eckigen Klammern war nicht möglich innerhalb einer Zeichenklasse: "[\[]"
Bild
Warum OpenSource eine Lizenz haben sollte :: PB-CodeArchiv-Rebirth :: Pleasant-Dark (Syntax-Farbschema) :: RegEx-Engine (kompiliert RegExes zu NFA/DFA)
Manjaro Xfce x64 (Hauptsystem) :: Windows 10 Home (VirtualBox) :: Neueste PureBasic-Version
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet

Beitrag von STARGÅTE »

Hallo Sicro,

ich muss mich hinsichtlich dieses Posts korrigieren. Natürlich braucht ein Pointer-Array mit $FFFF Einträgen nicht nur 65 kB sondern 530 kB, weil ein Pointer ja 8 Byte braucht.
Somit brauch ein volles Unicode-Pointer-Array tatsächlich 9 MB, wo einfach nur Leere ist.
Wenn du nun aber weißt, dass die eigentlichen Daten sich eh nur über ~3000 Einträge erstrecken, dann könntest du natürlich auch von einem Pointer-Array zu einem Offset-Array wechseln und weil du dort vermutlich mit einem maximalen Offset von 65000 auskommst, würde es reichen "Global Dim caseUnfoldOffset.u($10FFFF)" zu definieren (beachte das .u) und die "Startadresse" einfach addieren.
So wären es nur knapp 2 MB, weil du statt 8 Byte nur 2 Byte brauchst.

Allerdings wäge ich bei meinen Codes immer diese drei Punkte ab: Geschwindigkeit, Speicherplatz und "Bequemlichkeit".
  • Aus Speicherplatz-Sicht würde man vermutlich gar keine Sprungtabelle machen (weder Array noch Map) sondern einfach die 3000 Fälle durchspazieren bis der passende dabei ist.
  • Aus Geschwindigkeits-Sicht würde man definitiv eine Pointer-Array-Sprungtabelle nutzen, und die einmaligen 9MB in Kauf nehmen.
  • Aus Bequemlichkeit könnte man vermutlich bei einer Map bleiben, aber hier bist du weder Speicherplatz-effizient noch Geschwindigkeits-effizient, Stichwort Slot-Anzahl.
    Ich selbst hätte selbst aus Bequemlichkeit ein Array genutzt, um diese String-Konvertierung zu vermeiden
Klar kann man nun auch argumentieren, dass wenn man "sowas" öffter braucht, sich das schnell addiert und zu sehr große EXEn oder DLLs führt.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
Sicro
Beiträge: 955
Registriert: 11.08.2005 19:08
Kontaktdaten:

Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet

Beitrag von Sicro »

1.0.0-beta.2 veröffentlicht

Download: Klick

Verbessert
  • Die Unicode Case Unfolding Tabelle wurde neu geschrieben, was zu 44 % kleineren ausführbaren Dateien führt.
  • Zeichenklassen produzieren nun viel kompaktere NFAs, was zu schnellerem NFA-Matching, schnellerer DFA-Erstellung und weniger Speicherverbrauch führt.
  • Die kompakteren NFAs kommen auch den DFAs zugute, da sie nun ebenfalls viel kleiner sind.
Behoben
  • Es war nicht möglich, öffnende eckige Klammern innerhalb von Zeichenklassen zu escapen.
-------------------------------------
STARGÅTE hat geschrieben: 21.09.2022 18:42 Wenn du nun aber weißt, dass die eigentlichen Daten sich eh nur über ~3000 Einträge erstrecken, dann könntest du natürlich auch von einem Pointer-Array zu einem Offset-Array wechseln
Eine gute Idee. Das Problem ist nur, dass die Tabelle "CaseFolding" kontinuierlich weiterentwickelt wird. Kürzlich ist die Version 15 erschienen, die keine für mein Projekt relevanten Änderungen gebracht hat, aber wer weiß, was zukünftige Versionen bringen. Dann kann ich vielleicht nicht mehr mit solchen Tricks arbeiten.
STARGÅTE hat geschrieben: 21.09.2022 18:42 Aus Geschwindigkeits-Sicht würde man definitiv eine Pointer-Array-Sprungtabelle nutzen, und die einmaligen 9MB in Kauf nehmen.
Du hast recht, 9 MB ist heutzutage nichts mehr. Geschwindigkeitsprobleme gibt es in dem Bereich noch nicht, aber das könnte sich vielleicht ändern, wenn ich die Unterstützung für UTF-16 hinzufüge. Ich habe deinen Vorschlag in der neuen Beta 2 übernommen :)
Bild
Warum OpenSource eine Lizenz haben sollte :: PB-CodeArchiv-Rebirth :: Pleasant-Dark (Syntax-Farbschema) :: RegEx-Engine (kompiliert RegExes zu NFA/DFA)
Manjaro Xfce x64 (Hauptsystem) :: Windows 10 Home (VirtualBox) :: Neueste PureBasic-Version
Benutzeravatar
Sicro
Beiträge: 955
Registriert: 11.08.2005 19:08
Kontaktdaten:

Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet

Beitrag von Sicro »

1.0.0-beta.2 wurde nochmal neu veröffentlicht.

Die SimpleCaseUnfolding-Tabelle war etwas fehlerhaft. Dafür wollte ich keine neue Beta-Versionsnummer veröffentlichen.

Beta 3 ist schon in Arbeit und wird vermutlich die letzte Beta-Version sein.
Bild
Warum OpenSource eine Lizenz haben sollte :: PB-CodeArchiv-Rebirth :: Pleasant-Dark (Syntax-Farbschema) :: RegEx-Engine (kompiliert RegExes zu NFA/DFA)
Manjaro Xfce x64 (Hauptsystem) :: Windows 10 Home (VirtualBox) :: Neueste PureBasic-Version
Benutzeravatar
Sicro
Beiträge: 955
Registriert: 11.08.2005 19:08
Kontaktdaten:

Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet

Beitrag von Sicro »

Finale 1.0.0 veröffentlicht

Nach einigen Tests und Verbesserungen habe ich mich nun dazu entschieden, die Finale-Version 1.0.0 zu veröffentlichen.

Download: Klick

Neu
  • ASCII-Modus hinzugefügt, der die vordefinierten Zeichenklassen auf ASCII-Zeichen beschränkt (Kodierung ist immer noch UCS-2) und den Groß-/Kleinschreibung-unabhängigen Modus nur auf Groß- und Kleinbuchstaben beschränkt, anstatt Case-Folding anzuwenden.
  • Entwicklerwerkzeuge hinzugefügt.
Verbessert
  • Weitere Fehlerbehandlungen hinzugefügt.
Behoben
  • Verarbeitung von RegExes wie (a*)* oder (a*)+ löste eine Endlosschleife aus.
  • Parsen der RegEx-Modi wurde korrigiert.
  • Speicherlecks wurden behoben.
Bild
Warum OpenSource eine Lizenz haben sollte :: PB-CodeArchiv-Rebirth :: Pleasant-Dark (Syntax-Farbschema) :: RegEx-Engine (kompiliert RegExes zu NFA/DFA)
Manjaro Xfce x64 (Hauptsystem) :: Windows 10 Home (VirtualBox) :: Neueste PureBasic-Version
Antworten