Automaten für reguläre Ausdrücke erstellen
Zum Code
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>

Code aus Form1.frm
Option Explicit

Private Sub cmdCreate_Click()
Dim x() As Symbol, i As Long, xNode As Node, root As Long
Dim positions() As Long, followpos() As Menge, s As String
Dim eingabezeichen() As Long, match() As Menge, zustaende() As Zustand
Dim listitem As listitem, n As Long, col As ColumnHeader
Dim leer As Boolean, e As Long, endsymptr As Long

'regulärer Ausdruck für den Scanner
'\\.[\da-fA-F]*|\.|\[.*(\\.+)*\]
'Test x, Meta, "\\", Meta, ".", Meta_Or, "|", Meta, "\.", _
Meta_Or, "|", Meta, "\[", Meta, ".", MetaOp, "*", BR_Open, _
"(", Meta, "\\", Meta, ".", MetaOp, "+", BR_Close, ")", _
MetaOp, "*", Meta, "\]"
', Meta_Or, "|", Meta, "\|", Meta_Or, "|", Meta, "\*", _
Meta_Or, "|", Meta, "\+", Meta_Or, "|", Meta, "\?", _
Meta_Or, "|", Meta, "\(", Meta_Or, "|", Meta, "\)", _
Meta_Or, "|", Meta, "."
'Debug.Print lexcat(x, 0, UBound(x))

Scanner.Scan txtRegEx.Text, x
root = LR_Parser.Parse(x, endsymptr)
Konstruktor.BildeMengen x, root, endsymptr, positions, _
followpos, eingabezeichen, match, zustaende

Debug.Print lexcat(x, 0, UBound(x))

If txtFilepath.Text <> "" Then
If Dir(txtFilepath.Text) <> "" Then
Kill txtFilepath.Text: DoEvents
End If
Open txtFilepath.Text For Binary As #1
Put #1, , UBound(zustaende)
For i = 1 To UBound(zustaende)
Put #1, , zustaende(i).acc
Put #1, , zustaende(i).tran
Next i
Close #1
End If

On Error Resume Next

TreeView1.Nodes.Clear
List1.Clear
List2.Clear
ListView1.ListItems.Clear

Set xNode = TreeView1.Nodes.Add(, , , x(root).lexeme)
xNode.Expanded = True

If chkAttributes.Value = vbChecked Then
ShowAttributes x, xNode, root
End If

i = x(root).Child(0)
If Err.Number <> 0 Then
Err.Clear
ReDim x(root).Child(0)
x(root).Child(0) = -1
End If

For i = 0 To UBound(x(root).Child)
If x(root).Child(i) >= 0 Then
BuildNode x, xNode, x(root).Child(i)
End If
Next i

For i = 1 To UBound(zustaende)
List2.AddItem "Zustand " & CStr(i) & ": {" & _
CatElemente(zustaende(i).pos) & "}"
Next i

For i = 0 To UBound(positions)
If positions(i) >= 0 Then
List1.AddItem "Pos " & i & ": " & x(positions(i)).lexeme
End If
Next i

For i = 0 To UBound(followpos)
List1.AddItem "Followpos(" & i & ") = {" & _
CatElemente(followpos(i)) & "}"
Next i

For i = 0 To UBound(match)
List1.AddItem "Chr: " & _
IIf(InStr("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRST" & _
"UVWXYZäöüÄÖÜß0123456789.,-:;_#'+*~´`?\}][{!""§$%&/()=^°|" & _
"<>€", Chr$(i)) > 0, Chr$(i), CStr(i)) & " - {" & _
CatElemente(match(i)) & "}"
Next i

For i = 0 To UBound(eingabezeichen)
If eingabezeichen(i) >= 0 Then
List1.AddItem "Eingabe: " & x(eingabezeichen(i)).lexeme
End If
Next i

ListView1.ColumnHeaders.Clear
ListView1.ColumnHeaders.Add , , "Positionen"
s = _
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZäöüÄÖÜ" & _
"ß0123456789.,-:;_#'+*~´`?\}][{!""§$%&/()=^°|<>€"

For i = 1 To UBound(zustaende)
Set listitem = ListView1.ListItems.Add(, , "{" & _
CatElemente(zustaende(i).pos) & "}" & _
IIf(zustaende(i).acc, " acc", ""))
For n = 0 To 255
For e = 1 To UBound(zustaende)
leer = zustaende(e).tran(n) = 0
If Not leer Then
Exit For
End If
Next e
If Not leer Then
If i = 1 Then
Set col = ListView1.ColumnHeaders.Add(, , IIf(InStr(s, _
Chr$(n)) > 0, Chr$(n), CStr(n)), 20)
col.Alignment = lvwColumnCenter
End If
listitem.ListSubItems.Add , , IIf(zustaende(i).tran(n) _
<> -1, CStr(zustaende(i).tran(n)), "")
End If
Next n
Next i
End Sub

Private Sub BuildNode(ByRef Stream() As Symbol, par As Node, ptr _
As Long)
Dim xNode As Node, i As Long

Set xNode = TreeView1.Nodes.Add(par, tvwChild, , Stream(ptr).lexeme)
xNode.Expanded = True

If chkAttributes.Value = vbChecked Then
ShowAttributes Stream, xNode, ptr
End If

On Error Resume Next
i = Stream(ptr).Child(0)
If Err.Number <> 0 Then
Err.Clear
ReDim Stream(ptr).Child(0)
Stream(ptr).Child(0) = -1
End If

For i = 0 To UBound(Stream(ptr).Child)
If Stream(ptr).Child(i) >= 0 Then
BuildNode Stream, xNode, Stream(ptr).Child(i)
End If
Next i
End Sub

Private Sub ShowAttributes(ByRef Stream() As Symbol, xNode As _
Node, ptr As Long)
Dim sym As Symbol, attr As Sym_Attr, i As Long
Dim id As String, val As String, match() As Menge

sym = Stream(ptr)

On Error Resume Next
i = sym.attr(0).val
If Err.Number <> 0 Then
Err.Clear
ReDim sym.attr(0)
End If

For i = 0 To UBound(sym.attr)
If sym.attr(i).id > 0 Then
id = "Unbekannt": val = CStr(sym.attr(i).val)

Select Case sym.attr(i).id
Case Sym_Attr_ID.pos: id = "Position"
Case Sym_Attr_ID.nullable
id = "Nullable"
val = IIf(sym.attr(i).val = -1, "False", "True")
End Select

TreeView1.Nodes.Add xNode, tvwChild, , id & ": " & val
End If
Next i

i = sym.First(0)
If Err.Number <> 0 Then
Err.Clear
ReDim sym.First(0)
sym.First(0) = -1
End If

If sym.First(0) >= 0 Then
val = ""
For i = 0 To UBound(sym.First)
val = val & CStr(sym.First(i)) & ", "
Next i
val = Left$(val, Len(val) - 2)

TreeView1.Nodes.Add xNode, tvwChild, , "First: {" & val & "}"
End If

i = sym.Last(0)
If Err.Number <> 0 Then
Err.Clear
ReDim sym.Last(0)
sym.Last(0) = -1
End If

If sym.Last(0) >= 0 Then
val = ""
For i = 0 To UBound(sym.Last)
val = val & CStr(sym.Last(i)) & ", "
Next i
val = Left$(val, Len(val) - 2)

TreeView1.Nodes.Add xNode, tvwChild, , "Last: {" & val & "}"
End If
End Sub

Private Sub cmdBrowse_Click()
CommonDialog.ShowOpen
txtFilepath.Text = CommonDialog.FileName
End Sub