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

[Sicro]

RegEx-Engine-Modul für PureBasic

• GitHub-Projektseite: Klick

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. Im Gegensatz zu einem NFA wird bei einem DFA nichts ausprobiert, d. h. der DFA liest direkt "y".

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.

[STARGÅTE]

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?

[Sicro]

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.).

Ja, ebenfalls ein interessantes Projekt.

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.

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.

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.

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.

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.

Ich werde dein Module mal die nächste Tage mit meinem Lexer verknüpfen und ein paar Performance und Bug-Tests machen.

Danke, bin gespannt auf dein Feedback.

Allerdings verwendet mein Lexer oft "nicht gefräßig" Quantitäten, also x*? oder x+?
So brauch ich nicht '[^']+' definieren, sondern einfach '.+?'

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 '[^']+'
  

Meine Engine ist keine Backtracking-Engine und unterstützt "nicht gefräßige" Quantitäten daher nicht.

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?

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.

Edit: Erster Punkt in der Auflistung mit "oder zu anderen Tricks greifen" ergänzt.

[Nino]

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.

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.

[...]

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.:

Code: Alles auswählen

(get|get-value)[\s.,;]

[Sicro]

Hallo Nino,

klar, "\b" macht nur seinen Job.

Code: Alles auswählen

(get|get-value)[\s.,;]

Dann sind aber auch unerwünschte Zeichen im Match.
Ok, so geht es:

Code: Alles auswählen

(get|get-value)(?=$|[\s.,;])

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".

[STARGÅTE]

Ich bin noch nicht zum testen gekommen, wollte aber noch ein paar deine Kommentare kommentieren:

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.

Ä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.

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.

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)

Du meinst also ein Array($FFFF) = *charCountStartAddress und ein Memory "charCount, char1, char2, charCount, char1, charCount, ..."?

Ja genau.

Allerdings verwendet mein Lexer oft "nicht gefräßig" Quantitäten, also x*? oder x+?
So brauch ich nicht '[^']+' definieren, sondern einfach '.+?'

Ja, das ist bequem zu schreiben, aber oft langsamer, weil die Engine dann viel backtracken muss:

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?
So '(\\'|[^'])+' ?

Ach und danke auch für die vielen Referenzen in deinem Post

[Sicro]

Ä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.

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>'[^']+')")

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).

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

Zu dem Zeitpunkt fiel die Wahl auf die Variante mit dem geringeren RAM-Verbrauch.

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).

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.

Code: Alles auswählen

Global NewMap caseUnfold.caseUnfoldStruc(8192)

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.

Aber wie würdest du dann das Escape-Zeichen \' erlauben?
So '(\\'|[^'])+' ?

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.

[Nino]

Code: Alles auswählen

(get|get-value)[\s.,;]

Dann sind aber auch unerwünschte Zeichen im Match.

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

meine Engine kommt auch damit klar, wenn es keine Trennzeichen gibt, also RegEx "get|get-value" und String "get-valuegetget-value".

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

[Sicro]

Das war von mir nur ein Beispiel ...

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.

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.

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:

wenn man solche Tricks nicht anwenden muss, ist es doch schöner.

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.

[STARGÅTE]

Jetzt muss ich da noch mal nachhaken.

Mit gleichzeitig meine ich, dass alle Alternativen parallel sofort ausprobiert werden:

Code: Alles auswählen

CreateThread("(?P<Zahl>\d+\.?\d*)")
CreateThread("(?P<String>'[^']+')")

Ja gut, das ist ja dann parallel mit mehrere Threads, aber das wird doch auch in deinem Modul gar nicht gemacht?
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.

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:

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)

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).

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).