Danke STARGÅTE
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: "[\[]"