RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
RegEx-Engine-Modul für PureBasic
Ich arbeite seit einer Weile an einem "RegEx-Engine"-Modul für PureBasic. Die Engine kompiliert einen regulären Ausdruck in einen NFA (Nichtdeterministischer endlicher Automat), optional auch in einen sehr schnellen DFA (Deterministischer endlicher Automat), und kann den NFA/DFA gegen eine Zeichenkette ausführen.
Beim Abgleich wählt die Engine immer die längste Übereinstimmung unter mehreren möglichen Übereinstimmungen. Während dieses Prozesses ist kein Backtracking erforderlich, da alle Alternativen gleichzeitig geprüft werden. Also bei einem regulären Ausdruck "0123x|0123y" und der Zeichenkette "0123y" startet die Engine nach dem Fehlschlag bei "x" nicht wieder von Vorne bei "0", sondern befindet sich hinter "3" und die Engine muss nur "y" lesen.
Es ist auch möglich, der Engine mehrere reguläre Ausdrücke zu übergeben und für diese eindeutige ID-Nummern festzulegen, um bei einer Übereinstimmung ermitteln zu können, welcher reguläre Ausdruck übereingestimmt hat. Mit dieser Funktionalität können auf einfache Weise Lexer erstellt werden. Dies ist auch die eigentliche Motivation, die zu diesem Projekt geführt hat. Die Engine ist aber flexibel in der Verwendung gehalten und kann auch einfach für andere Zwecke verwendet werden, weshalb ich sie nicht ausschließlich als Lexer-Engine betrachte und sie deshalb auch nicht so benannt habe.
Ein paar Code-Beispiele, die Auflistung der unterstützten Syntax für die regulären Ausdrücke, weitere Informationen und das Modul selbst findet ihr auf GitHub.
Aktuell befindet sich das Projekt in der Beta-Phase, deshalb wäre ich sehr dankbar für Feedback von euch.
Features die in kommenden Versionen aktuell geplant sind: Klick
Diese Features werden nicht mehr in der aktuellen Beta-Phase von Version 1.0.0 eingebaut, sondern erst in den nächsten Nebenversionen, z. B. 1.1.0, 1.2.0 usw.
Beachtet, dass dieses Projekt keine RegEx-Engine vorhat, die als Ersatz für funktionsreichere Engines wie die in PureBasic nativ integrierte PCRE dienen soll. Es wird also keine Unterstützung für Capturing Groups, Backreferences, Word Boundaries und Anchors geben.
Ich arbeite seit einer Weile an einem "RegEx-Engine"-Modul für PureBasic. Die Engine kompiliert einen regulären Ausdruck in einen NFA (Nichtdeterministischer endlicher Automat), optional auch in einen sehr schnellen DFA (Deterministischer endlicher Automat), und kann den NFA/DFA gegen eine Zeichenkette ausführen.
Beim Abgleich wählt die Engine immer die längste Übereinstimmung unter mehreren möglichen Übereinstimmungen. Während dieses Prozesses ist kein Backtracking erforderlich, da alle Alternativen gleichzeitig geprüft werden. Also bei einem regulären Ausdruck "0123x|0123y" und der Zeichenkette "0123y" startet die Engine nach dem Fehlschlag bei "x" nicht wieder von Vorne bei "0", sondern befindet sich hinter "3" und die Engine muss nur "y" lesen.
Es ist auch möglich, der Engine mehrere reguläre Ausdrücke zu übergeben und für diese eindeutige ID-Nummern festzulegen, um bei einer Übereinstimmung ermitteln zu können, welcher reguläre Ausdruck übereingestimmt hat. Mit dieser Funktionalität können auf einfache Weise Lexer erstellt werden. Dies ist auch die eigentliche Motivation, die zu diesem Projekt geführt hat. Die Engine ist aber flexibel in der Verwendung gehalten und kann auch einfach für andere Zwecke verwendet werden, weshalb ich sie nicht ausschließlich als Lexer-Engine betrachte und sie deshalb auch nicht so benannt habe.
Ein paar Code-Beispiele, die Auflistung der unterstützten Syntax für die regulären Ausdrücke, weitere Informationen und das Modul selbst findet ihr auf GitHub.
Aktuell befindet sich das Projekt in der Beta-Phase, deshalb wäre ich sehr dankbar für Feedback von euch.
Features die in kommenden Versionen aktuell geplant sind: Klick
Diese Features werden nicht mehr in der aktuellen Beta-Phase von Version 1.0.0 eingebaut, sondern erst in den nächsten Nebenversionen, z. B. 1.1.0, 1.2.0 usw.
Beachtet, dass dieses Projekt keine RegEx-Engine vorhat, die als Ersatz für funktionsreichere Engines wie die in PureBasic nativ integrierte PCRE dienen soll. Es wird also keine Unterstützung für Capturing Groups, Backreferences, Word Boundaries und Anchors geben.
Zuletzt geändert von Sicro am 01.01.2023 20:46, insgesamt 2-mal geändert.
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
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Sehr interessantes Projekt. Gerade die Schlagwörter: "Lexer" und "NFA/DFA" triggern mich gerade, da ich für meine Scriptsprache ja auch extra n eigenes RegEx-Include gebaut habe (hier), u.a. weil das Regex von PB zu unflexibel war (keine Callbacks, keine Backreferences bei Ersetzungen usw.).
Beim schnellen drüber gucken habe ich mich zwar gewundert, dass du mit Maps arbeitest, die (weil sie Strings nutzten) "sehr langsam" sind. Aber beim eigentlichen Matching wird ja dann der NFA/DFA genutzt, wenn ich das richtig überblicke.
Trotzdem ist diese caseUnfold map natürlich ziemlich sperrig. Das könntest du auch mit einer binären HashTable umsetzen: Ein array mit $FFFF Feldern zu Start-Adressen wo die Anzahl der chars liegt und die chars selbst.
Nur so n Idee.
Ich werde dein Module mal die nächste Tage mit meinem Lexer verknüpfen und ein paar Performance und Bug-Tests machen. Allerdings verwendet mein Lexer oft "nicht gefräßig" Quantitäten, also x*? oder x+?
So brauch ich nicht '[^']+' definieren, sondern einfach '.+?'
Ich finde es allerdings schade, dass du gleich vorweg schreibst "Es wird also keine Unterstützung für Capturing Groups, Backreferences, Word Boundaries und Anchors geben."
Klar, die brauchst man nicht unbedingt für einen Lexer, aber wenn du eh schon dabei bist n eigenes Regex zu schreiben?
Beim schnellen drüber gucken habe ich mich zwar gewundert, dass du mit Maps arbeitest, die (weil sie Strings nutzten) "sehr langsam" sind. Aber beim eigentlichen Matching wird ja dann der NFA/DFA genutzt, wenn ich das richtig überblicke.
Trotzdem ist diese caseUnfold map natürlich ziemlich sperrig. Das könntest du auch mit einer binären HashTable umsetzen: Ein array mit $FFFF Feldern zu Start-Adressen wo die Anzahl der chars liegt und die chars selbst.
Nur so n Idee.
Ich werde dein Module mal die nächste Tage mit meinem Lexer verknüpfen und ein paar Performance und Bug-Tests machen. Allerdings verwendet mein Lexer oft "nicht gefräßig" Quantitäten, also x*? oder x+?
So brauch ich nicht '[^']+' definieren, sondern einfach '.+?'
Ich finde es allerdings schade, dass du gleich vorweg schreibst "Es wird also keine Unterstützung für Capturing Groups, Backreferences, Word Boundaries und Anchors geben."
Klar, die brauchst man nicht unbedingt für einen Lexer, aber wenn du eh schon dabei bist n eigenes Regex zu schreiben?
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
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Ja, ebenfalls ein interessantes Projekt.STARGÅTE hat geschrieben: ↑12.09.2022 23:14Sehr interessantes Projekt. Gerade die Schlagwörter: "Lexer" und "NFA/DFA" triggern mich gerade, da ich für meine Scriptsprache ja auch extra n eigenes RegEx-Include gebaut habe (hier), u.a. weil das Regex von PB zu unflexibel war (keine Callbacks, keine Backreferences bei Ersetzungen usw.).
Die Gründe, warum ich mich dazu entschieden habe, eine eigene RegEx-Engine zu schreiben und nicht mehr die in PureBasic integrierte RegEx-Engine-Implementation für einen Lexer zu verwenden, sind:
- Sie bietet keine Funktion, immer die längste mögliche Übereinstimmung zurückzugeben. Der Trick mit einem Word Boundary "(Enumeration|EnumerationBinary)\b" funktioniert nicht immer. Zum Beispiel funktioniert er bei solchen Schlüsselwörtern nicht: "(get|get-value)\b" würde bei dem String "get-value" nur "get" zurückgeben. Klar, anstatt dem Word Boundary Trick könnte man die Schlüsselwörter der Länge nach sortieren (von lang zu kürzer) oder zu anderen Tricks greifen, aber wenn man solche Tricks nicht anwenden muss, ist es doch schöner.
- ExamineRegularExpression() keinen Parameter besitzt, um die Startposition festzulegen (Feature-Request). Meine alte Lexer-Include muss deshalb den String immer wieder am Anfang abschneiden, was ziemlich die Performance bremst. Mit einer Krücke, die maximale Token-Länge zu beschränken, konnte die Performance etwas verbessert werden.
- ExamineRegularExpression() keinen Pointer zu einem String akzeptiert und der String beim Aufrufen der Funktion immer wieder kopiert werden muss, was wieder eine Performance-Bremse ist.
- Es keine Möglichkeit gibt, mehrere reguläre Ausdrücke gleichzeitig auszuführen und später bestimmen zu können, welcher reguläre Ausdruck zu einer Übereinstimmung geführt hat. Stattdessen muss jeder reguläre Ausdruck nacheinander ausgeführt werden.
Richtig, ich verwende Maps nur beim Erstellen der NFA/DFA und die haben nur mit MapKeys der länge von einem Zeichen zu tun, daher sind sie sehr schnell. Ich verwende sie, um doppelte Einträge zu vermeiden. Zudem wäre mit Arrays der Speicherverbrauch wahrscheinlich höher, weil sie immer einen maximalen Index von $FFFF haben müssten. Zudem kann ich bei Arrays im Gegensatz zu Maps nicht einfach feststellen, welcher Array-Index wirklich Daten hat. Bei den Maps habe ich keine Einträge ohne Daten.
Ja, mit der caseUnfold-Map bin ich auch noch nicht zufrieden. Du meinst also ein Array($FFFF) = *charCountStartAddress und ein Memory "charCount, char1, char2, charCount, char1, charCount, ..."? Sobald ich wieder genug Zeit habe, werde ich mir das nochmal ansehen. Der Code für die caseUnfold-Map wird natürlich automatisch generiert, so kann ich einfach und schnell andere Datenstrukturen ausprobieren.
Danke, bin gespannt auf dein Feedback.
Ja, das ist bequem zu schreiben, aber oft langsamer, weil die Engine dann viel backtracken muss:
- String 'Example text' mit RegEx '.+?'
- String 'Example text' mit RegEx '[^']+'
Das ist eine Einschränkung von RegEx-Engines, die intern mit einem DFA arbeiten, anstatt mit einer Backtracking-Engine. Es gibt eine Erweiterung von DFA namens Tagged DFA, die Teile dieser Einschränkung aufhebt. Vielleicht blicke ich da auch noch durch und kann das in einer zukünftigen Version einbauen. Moderne RegEx-Engines können einfach zu viel und sind deshalb langsam.STARGÅTE hat geschrieben: ↑12.09.2022 23:14Ich finde es allerdings schade, dass du gleich vorweg schreibst "Es wird also keine Unterstützung für Capturing Groups, Backreferences, Word Boundaries und Anchors geben."
Klar, die brauchst man nicht unbedingt für einen Lexer, aber wenn du eh schon dabei bist n eigenes Regex zu schreiben?
Edit: Erster Punkt in der Auflistung mit "oder zu anderen Tricks greifen" ergänzt.
Zuletzt geändert von Sicro am 15.09.2022 19:35, insgesamt 1-mal geändert.
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
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Hallo Sicro,
ich verstehe deine ausführliche Begründung, warum du eine eigene RegEx-Engine geschrieben hast.
Nur einen Punkt möchte ich hier gerade rücken, denn ganz so schlecht wie du die in PB eingebaute RegEx-Engine darstellst, ist sie nicht.
ich verstehe deine ausführliche Begründung, warum du eine eigene RegEx-Engine geschrieben hast.
Nur einen Punkt möchte ich hier gerade rücken, denn ganz so schlecht wie du die in PB eingebaute RegEx-Engine darstellst, ist sie nicht.
Das spricht nicht gegen die eingebaute RegEx-Engine, sondern zeigt lediglich, dass \b nicht immer geeignet ist, die Wort-Grenzen zu erkennen, wie sie im jeweiligen Kontext festgelegt sind. Es kommt auf die Art des zu untersuchenden Textes an, ob "-" eine Wortgrenze darstellt oder nicht. Natürlich ist der Anker \b nicht immer zum Erkennen der gewünschten Wortgrenzen geeignet – z.B. auch nicht, wenn man Unicode-Text untersucht. Man kann aber leicht selbst definieren, welche Zeichen eine Wortgrenze kennzeichnen sollen, z.B.:Sicro hat geschrieben: ↑14.09.2022 13:15 Die Gründe, warum ich mich dazu entschieden habe, eine eigene RegEx-Engine zu schreiben und nicht mehr die in PureBasic integrierte RegEx-Engine-Implementation für einen Lexer zu verwenden, sind:[...]
- Sie bietet keine Funktion, immer die längste mögliche Übereinstimmung zurückzugeben. Der Trick mit einem Word Boundary "(Enumeration|EnumerationBinary)\b" funktioniert nicht immer. Zum Beispiel funktioniert er bei solchen Schlüsselwörtern nicht: "(get|get-value)\b" würde bei dem String "get-value" nur "get" zurückgeben. Klar, anstatt dem Word Boundary Trick könnte man die Schlüsselwörter der Länge nach sortieren (von lang zu kürzer), aber wenn man solche Tricks nicht anwenden muss, ist es doch schöner.
Code: Alles auswählen
(get|get-value)[\s.,;]
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Hallo Nino,
klar, "\b" macht nur seinen Job.
Ok, so geht es:
Ist zwar unüblich, aber meine Engine kommt auch damit klar, wenn es keine Trennzeichen gibt, also RegEx "get|get-value" und String "get-valuegetget-value".
klar, "\b" macht nur seinen Job.
Dann sind aber auch unerwünschte Zeichen im Match.
Ok, so geht es:
Code: Alles auswählen
(get|get-value)(?=$|[\s.,;])
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
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Ich bin noch nicht zum testen gekommen, wollte aber noch ein paar deine Kommentare kommentieren:
So bekommst du doch bei jedem Match den jeweiligen Token-Typ (Gruppenbezeichnung) und die gesamte Syntax wird praktisch "gleichzeitig" getestet.
Hinzu kommt, dass eine Map standardmäßig in PureBasic nur 512 Slots hat, es also notwendigerweise bei deiner caseUnfold() map mit grob 3000 Einträgen zu massiven Kollisionen kommt. Hier könntest du zumindest die Slots erhöhen. Aber ein Array mit 65k Feldern ist wohl das schnellste und einfachste.
So '(\\'|[^'])+' ?
Ach und danke auch für die vielen Referenzen in deinem Post
Äh, ist das nicht gerade die Aufgabe von Gruppen, also z.B. "(?P<Zahl>\d+\.?\d*)|(?P<String>'[^']+')|..."
So bekommst du doch bei jedem Match den jeweiligen Token-Typ (Gruppenbezeichnung) und die gesamte Syntax wird praktisch "gleichzeitig" getestet.
Es ist ja nicht unbedingt die Länge des Strings das "Problem". Allein der Umweg von einem Unicode-Wert zu einem Unicode-Zeichen und wieder zurück zu einem Hash-Wert ist eigentlich totaler quatsch (hinsichtlich Effizienz).
Hinzu kommt, dass eine Map standardmäßig in PureBasic nur 512 Slots hat, es also notwendigerweise bei deiner caseUnfold() map mit grob 3000 Einträgen zu massiven Kollisionen kommt. Hier könntest du zumindest die Slots erhöhen. Aber ein Array mit 65k Feldern ist wohl das schnellste und einfachste.
Code: Alles auswählen
Global NewMap caseUnfold.caseUnfoldStruc(8192)
Ja genau.
Da gebe ich dir recht. Hier ständig zu das Ende des Strings zu testen, obwohl in viel mehr fällen der String weitergeht ist ineffizient. Aber wie würdest du dann das Escape-Zeichen \' erlauben?Sicro hat geschrieben: ↑14.09.2022 13:15Ja, das ist bequem zu schreiben, aber oft langsamer, weil die Engine dann viel backtracken muss:STARGÅTE hat geschrieben:Allerdings verwendet mein Lexer oft "nicht gefräßig" Quantitäten, also x*? oder x+?
So brauch ich nicht '[^']+' definieren, sondern einfach '.+?'
So '(\\'|[^'])+' ?
Ach und danke auch für die vielen Referenzen in deinem Post
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
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Kann man so sehen, aber innerhalb der Engine werden die Alternativen in deinem Beispiel-RegEx nacheinander getestet: Wenn "(?P<Zahl>\d+\.?\d*)" fehlschlägt, wird "(?P<String>'[^']+')" ausprobiert usw.
Mit gleichzeitig meine ich, dass alle Alternativen parallel sofort ausprobiert werden:
Code: Alles auswählen
CreateThread("(?P<Zahl>\d+\.?\d*)")
CreateThread("(?P<String>'[^']+')")
Das ist mir bewusst. Manchmal nimmt man dieses Übel in Kauf, weil es keine Maps in PB gibt, die Zahlen als Schlüssel entgegennimmt. Der Gedanke mit den unnötigen Umwandlungen hatte ich auch schon einmal und habe die Map durch ein Array($FF5A) ersetzt (Struktur belassen). Danach habe ich Testprogramme beider Varianten kompiliert und verglichen:
Code: Alles auswählen
Program Size RAM
--------------------------------
test_array 145 KiB 35,0 MiB
test_map 235 KiB 27,5 MiB
Für eine der nächsten Versionen des Moduls möchte ich volle Unicode-Unterstützung (UTF-16-Surrogates) hinzufügen, in der ich dann für Simple Case Folding ein Array($1E943) bräuchte, wobei 122.374 Array-Indexes dann ohne Daten wären (entsprechend aktueller CaseFolding.txt, Version 14.0.0).
Für gute Slot-Anzahlen habe ich noch kein Gefühl. Normalerweise würde ich einfach mal ein paar Slot-Anzahlen ausprobieren und schauen, wie sie sich auswirken, aber da ich, wie zuvor schon erwähnt, keine Geschwindigkeitsprobleme mit der caseUnfold-Map feststellen konnte, kam mir keine Geschwindigkeitsoptimierung in den Sinn.STARGÅTE hat geschrieben: ↑14.09.2022 22:49Hinzu kommt, dass eine Map standardmäßig in PureBasic nur 512 Slots hat, es also notwendigerweise bei deiner caseUnfold() map mit grob 3000 Einträgen zu massiven Kollisionen kommt. Hier könntest du zumindest die Slots erhöhen.Code: Alles auswählen
Global NewMap caseUnfold.caseUnfoldStruc(8192)
Ja, sieht gut aus. Ich habe ein paar andere Varianten ausprobiert, aber diese hat am wenigsten Backtrackings erfordert, obwohl es leider trotzdem viel Backtracking erfordert, aber das geht wahrscheinlich nicht besser bei einer Backtracking-Engine:
Edit: Letztes Bild im Text in eine neue Zeile verschoben.
Zuletzt geändert von Sicro am 15.09.2022 19:17, insgesamt 1-mal geändert.
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
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Das war von mir nur ein Beispiel ...
Wie gesagt hängt es vom zu parsenden Text ab, welche Zeichen als Worttrennzeichen interpretiert werden sollen, und welche nicht. Es gibt da keine allgemeine Regel, die immer passt. Daher ist \b auch nur für „quick and dirty“-Code geeignet. Dieser Anker kann seine Funktion als Wortgrenze schon dann nicht korrekt erfüllen, wenn im Text z.B. deutsche Umlaute vorkommen:
Code: Alles auswählen
CreateRegularExpression(0, "\b.+?\b")
If ExamineRegularExpression(0, "Ralf Meier")
While NextRegularExpressionMatch(0)
Debug "Match: " + RegularExpressionMatchString(0)
Debug " Position: " + Str(RegularExpressionMatchPosition(0))
Wend
EndIf
Debug "------------------"
If ExamineRegularExpression(0, "Jörg Müller")
While NextRegularExpressionMatch(0)
Debug "Match: " + RegularExpressionMatchString(0)
Debug " Position: " + Str(RegularExpressionMatchPosition(0))
Wend
EndIf
PutreBasic kommt damit auch klar. Es kommt halt darauf an ob man nur nach ganzen Wörtern sucht oder nicht.
Code: Alles auswählen
If CreateRegularExpression(0, "get(?:-value)?")
If ExamineRegularExpression(0, "get-valuegetget-value")
While NextRegularExpressionMatch(0)
Debug "Match: " + RegularExpressionMatchString(0)
Debug " Position: " + Str(RegularExpressionMatchPosition(0))
Wend
EndIf
Else
Debug RegularExpressionError()
EndIf
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Das habe ich auch so verstanden.
Mich hat da nur die Experimentierlust gepackt und habe ein weiteres Beispiel genannt, dass das Problem nicht mehr hat.
Deshalb habe ich in der Auflistung oben ja auch noch einen weiteren Trick erwähnt, die Alternativen nach Länge zu sortieren. Ich habe den Punkt oben nun mit "oder zu anderen Tricks greifen" ergänzt, um klarzustellen, dass ich nicht ausschließe, dass es noch weitere (bessere) Tricks gibt. Die Kernaussage des Punktes bleibt aber, wenn man immer die längste Übereinstimmung haben will:
Das Verhalten von der RegEx-Engine in PB ist beliebter als das Verhalten immer die längste Übereinstimmung zurückzugeben, weil der RegEx-Schreiber mehr Kontrolle hat, wie die RegEx verarbeitet wird. Aber in manchen Fällen, wie bei einem Lexer, will man in der Regel eben doch das unbeliebtere Verhalten.
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
Re: RegEx-Engine-Modul, das NFA/DFA baut und zum Abgleich verwendet
Jetzt muss ich da noch mal nachhaken.
Was 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.
Du würdest wenn dann ein Pointer-Array benötigen (~65kB) und ein Datenpuffer mit (wie oben erwähnt) Zeichenanzahl und Zeichen selbst, was bei 1600 Fällen oder so, mit im Schnitt nur ein Zeichen gerade mal 5 kB (1 Byte count, 2 Byte Zeichen, 1600 Fälle) wären. Summa summarum also weniger nur "echte" 70 kB und keine 27 MB wie du es jetzt bei der Map brauchst.
(Bitte nicht falsch verstehen, dass ich dich da jetzt irgendwie Kritisiere würde. Ich möchte hier nur das Optimierungspotential zeigen. Natürlich ist das für die Nutzung deines Moduls völlig wurscht, weil es sich ja vor der eigentlichen Prüfung abspielt und du den einfachen Weg gegangen bist)
Ja gut, das ist ja dann parallel mit mehrere Threads, aber das wird doch auch in deinem Modul gar nicht gemacht?Sicro hat geschrieben: ↑15.09.2022 15:46 Mit gleichzeitig meine ich, dass alle Alternativen parallel sofort ausprobiert werden:Code: Alles auswählen
CreateThread("(?P<Zahl>\d+\.?\d*)") CreateThread("(?P<String>'[^']+')")
Was 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.
Ja 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 mit (wie oben erwähnt) Zeichenanzahl und Zeichen selbst, was bei 1600 Fällen oder so, mit im Schnitt nur ein Zeichen gerade mal 5 kB (1 Byte count, 2 Byte Zeichen, 1600 Fälle) wären. Summa summarum also weniger nur "echte" 70 kB und keine 27 MB wie du es jetzt bei der Map brauchst.
(Bitte nicht falsch verstehen, dass ich dich da jetzt irgendwie Kritisiere würde. Ich möchte hier nur das Optimierungspotential zeigen. Natürlich ist das für die Nutzung deines Moduls völlig wurscht, weil es sich ja vor der eigentlichen Prüfung abspielt und du den einfachen Weg gegangen bist)
Code: Alles auswählen
Structure caseUnfoldStruc
CharacterCount.a
Character.u[0]
EndStructure
Dim *caseUnfold.caseUnfoldStruc($FFFF)
Oh sehr gut! Das war auch immer etwas was mir in PureBasic hin und wieder Kopfschmerzen bereitet hat, wenn ich mit Zeichen über $FFFF gearbeitet habe. Weil dann Len() oder Mid() einfach nicht richtig funktionierten. Hatte da dann auch Unicode-Versionen geschrieben (hier).Sicro hat geschrieben: ↑15.09.2022 15:46 Für eine der nächsten Versionen des Moduls möchte ich volle Unicode-Unterstützung (UTF-16-Surrogates) hinzufügen, in der ich dann für Simple Case Folding ein Array($1E943) bräuchte, wobei 122.374 Array-Indexes dann ohne Daten wären (entsprechend aktueller CaseFolding.txt, Version 14.0.0).
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
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr