Ein DFA ist ein deterministischer finiter Automat, manchmal auch deterministischer endlicher Automat genannt. Um zu erfahren, was ein Automat oder ein regulärer Ausdruck ist, empfehle ich, mal im Internet zu suchen oder bei genügend Interesse gleich die passenden Bücher zu kaufen (Reguläre Ausdrücke von O'Reilly und Compilerbau Teil 1 im Oldenbourgverlag, das "Drachenbuch").
Dieses Projekt erzeugt Zustände für einen DFA in VB. Der DFA-Code liegt dem Projekt bei, es ist die Funktion Test_DFA im Modul DFAs. Um einen eigenen DFA zu erstellen, muss man die Funktion nur kopieren und ggf. anpassen, u.a. den Pfad der Übergangstabelle.
Diese DFAs hier können im Prinzip nur sagen, ob ein übergebener String ab einer angegebenen Position einem regulären Ausdruck entspricht, also akzeptiert wird. Die Automaten geben die letzte Stelle des längsten gefundenen Musters zurück. Ein Beispiel für den Einsatz eines DFAs ist der Scanner, welcher praktischerweise mit dem Programm selber erstellt wurde.
Das Projekt besteht aus drei Teilen, dem Scanner, dem LR(1)-Parser und dem Konstruktor. Der Scanner wandelt den Eingabestring, welcher einen korrekten regulären Ausdruck beinhaltet, in einen Symbolstrom um. Der Parser konstruiert einen Syntaxbaum und der Konstruktor bildet die verschiedenen Mengen und schließlich die Zustände.
Ein Erfassen von Teilmengen mit Klammern ist auf Grund der Natur der DFAs nicht möglich (siehe "Reguläre Ausdrücke", O'Reilly). Dafür benötigt man einen NFA (Nichtdeterministischen finiten Automaten) oder einen hybriden Automaten. Wer Spaß dran hat - die Menge Followpos ist nichts anderes als ein NFA.
Der Vorteil eines DFAs ist die Geschwindigkeit. DFAs sind textorientiert, ihre Laufzeit entspricht O(n) wenn die Eingabe n Zeichen hat. Die Laufzeit von NFAs entspricht O(r*n) wenn r die Länge des regulären Ausdrucks ist. Der Nachteil eines DFAs ist der Platzbedarf im Vergleich zu einem NFA. Dieser beträgt beim DFA O(2^r) während er beim NFA nur O(r) beträgt (siehe hierzu das "Drachenbuch" s.o.).
Der vorliegende Code hat einige Einschränkungen bei den regulären Ausdrücken. Er unterstützt nicht alle Konstrukte, die man aus Sprachen wie Perl oder PHP kennt.
Ihm sind einfache Zeichenklassen \w, \d, \s, \W, \D, \S, "." und [] bekannt. Unterstütze Metazeichen sind \n für vbLf, \r für vbCr und \t für vbTab. Beliebige ASCII-Zeichen können durch \xFF angegeben werden, wobei die beiden Fs durch den hexadezimalen ASCII-Code des Zeichens zu ersetzen sind. Die Metazeichen sowie die Zeichenklassen bis auf den Punkt werden auch innerhalb von Zeichenklassen [] selber unterstützt. Ein Bindestrich kann hier einen Bereich angeben, dies funktioniert aber nur zwischen Buchstaben, Zahlen und dem Metazeichen \xFF. Z.B. repräsentiert [a-f] eine Zeichenklasse mit allen Kleinbuchstaben von a bis f. Hier werden alle ASCII-Zeichen zwischen dem ersten Zeichen und dem zweiten Zeichen eingefügt! Der Backslash dient als Escapezeichen, muss daher auch selbst escaped werden. Durch ein Dach ^ als erstes Zeichen wird die Zeichenklasse invertiert.
Die Metaoperationen *, + und ? sind verfügbar, alle jedoch gierig. Da DFAs erstellt werden, welche textgesteuert sind, sind nicht-gierige Ausdrücke nicht ohne weiteres möglich. Dies den DFAs beizubringen ist meist unsauber - ein NFA könnte das von Haus aus.
Der Backslash kann die besondere Bedeutung beliebiger Zeichen innerhalb und ausserhalb von Zeichenklassen aufheben. Ausdrücke können beliebig durch Klammern verschachtelt werden. Die Alternation mit "|" wird unterstützt.
Bei fehlerhaften regulären Ausdrücken als Eingabe kann es vorkommen, dass kein Fehler gemeldet wird oder der Automat sich seltsam verhält. Sollten Fehler entdeckt werden, bitte ich darum, mir eine Email zu schicken.
History
05.10.2003 Hinzugefügt
Autor: Dominik Auras <Dominik_auf_vbInside.de>
