Reguläre Ausdrücke[mittel bis schwer]

[CDW]

Eingereicht von 5830:

Aufgabe:
Schreibe einen Regex matcher in der Programmiersprache deiner Wahl.

Teilaufgabe a:
der matcher soll simple Ausdrücke wie [a-z0-9]
sowie Invertierungen [^a] unterstützen.

Teilaufgabe b:
erweitere die Funktionen des Matchers um
Anzahlangaben [a-z]{4} [a-z]{1, 4}

Teilaufgabe c:
erweitere den Matcher um "shortcuts" [a-z]*
[a-z]+ [a-z]? und Zeilenumbrüche \n \r

Teilaufgabe d:
füge "Intelligenz" zu deinem Matcher hinzu
(Operatorenpriorität, Klammern, etc.)

Dies kann natürlich zu einer vollständigen Unterstützung von Regex erweitert werden.

Zum testen: Online Regex Matcher

Also:
zuerst einen simplen RegEx Parser schreiben, der sowas akzeptiert:

abab
aaaa

und zumindest die Position aller Treffer ausgibt.

Dann: erweitern, so dass Klammern (), Stern * , ODER | akzeptiert werden:

a(a|b)b
(a|b)(a|b)*b

bedenke, dass Quantoren wie * + normalerweise greedy sind (größtmögliche Anzahl an Buchstaben "essen" - also ab*b sollte bei abbbb die komplette Eingabe akzeptieren/zurückgeben, nicht bloß ab, abb, abbbb)

Jetzt sollten sich die Teilaufgaben gut umsetzen lassen - in dem man z.B intern
[0-9] durch (0|1|2|3|4|5|6|7|8|9) ersetzt.
Besonders schick sollte es sein, wenn man die eigene, simple RegEx Implementierung dafür nutzt, um eben diese zu erweitern

Weitere Teilaufgaben:

Anzahl der Vergleiche pro konsumiertes Zeichen minimieren.
Beispiel:
einfache Implementierung für Ausdruck (a|b|c)b und Eingabe "cb"
c: vergleiche mit a, vergleiche mit b, vergleiche mit c =>OK
fortgeschrittene:
c: magic_vergleich: => OK (oder FAIL)

Unnötige Vergleiche vermeiden:
suche: abbcd in adddcddadabbcd
Einfache Implementierung:
a: vergleiche mit a => OK
d: vergleiche mit b => FAIL
d: vergleiche mit a => FAIL
d: vergleiche mit a=> FAIL
...

verbesserte:
c(at pos 5): vergleiche mit d|c|b|a=> OK (c)
d(at pos 4): vergleiche mit b => FAIL
a(at pos 10): vergleiche mit d|c|b|a => OK
b(at pos 11): vergleiche mit b => OK
b(at pos 12): vergleiche mit b => OK
c ...
d ... => MATCH!

Kann also beliebig kompliziert werden

Spoiler: Stichwörter

Stichwörter: NFA, DFA, Shifting, Regular Expression Matching Can Be Simple And Fast