Der Algorithmus wurde zuerst beschrieben von Janusz A. Brzozowski; Derivatives of Regular Expressions; Journal of the ACM, Volume 11, Issue 4, 1964.
Informell beschrieben geht es bei diesem Algorithmus darum, einen regulären Ausdruck auf eine Zeichenkette anzuwenden und den verbliebenen regulären Ausdruck zu prüfen, ob dieser auf die leere Zeichenkette ableitbar ist. Kann der verbliebene reguläre Ausdruck auf eine leere Zeichenkette abgeleitet werden, passt der reguläre Ausdruck auf die Zeichenkette, andernfalls nicht.
Beispiele:
Der reguläre Ausdruck foobar soll bezüglich der Zeichenkette "foo" abgeleitet werden. Nach Anwendung des regulären Ausdrucks auf diese Zeichenkette bleibt der reguläre Ausdruck bar übrig. Dieser kann nicht auf eine leere Zeichenkette abgeleitet werden, da dieser Ausdruck noch die Zeichen 'b', 'a' und 'r' erwartet. Der reguläre Ausdruck passt also nicht auf die Zeichenkette. (Kurzschreibweise: foo\foobar = bar)
Der reguläre Ausdruck a* soll bezüglich der Zeichenkette "aa" abgeleitet werden. Nach der Ableitung bleibt der reguläre Ausdruck a* übrig. Dieser Ausdruck kann auf die leere Zeichenkette abgeleitet werden, da der *-Operator anzeigt, dass kein oder beliebig viele 'a'-Zeichen erwartet werden. Der reguläre Ausdruck passt somit auf die Zeichenkette. (Kurzschreibweise: aa\a* = a*)
Formale Beschreibung:
Begriffe:
Definition eines Datentyps für reguläre Ausdrücke
data RE a =
Regulärer Ausdruck für die leere Menge (symbolisiert Fehlerfall)
RE_ZERO -- L(0) = {}
Regulärer Ausdruck für die leere Zeichenfolge
| RE_UNIT -- L(1) = { [] }
Regulärer Ausdruck für ein Symbol
| RE_SYM a -- L(x) = { [x] }
Regulärer Ausdruck zur optionalen Wiederholung (*) eines anderen regulären Ausdrucks e
| RE_REP (RE a) -- L(e*) = { [] } `union` L(e+)
Regulärer Ausdruck zur Wiederholung (+) eines anderen regulären Ausdrucks e
| RE_PLUS (RE a) -- L(e+) = { x ++ y | x <- L(e), y <- L(e*) }
Regulärer Ausdruck e ist eine Option (?)
| RE_OPT (RE a) -- L(e?) = L(e) `union` { [] }
Sequenz (,) zweier regulärer Ausdrücke e und f
| RE_SEQ (RE a) (RE a) -- L(e,f) = { x ++ y | x <- L(e), y <- L(f) }
Alternative (|) zweier regulärer Ausdrücke e und f
| RE_ALT (RE a) (RE a) -- L(e|f) = L(e) `union` L(f) deriving (Show, Eq)
Mit Hilfe der Konstruktor-Funktionen können die regulären Ausdrücke bei ihrer Erzeugung gleich minimiert werden. So ist z.B. die optionale Wiederholung (*) einer leeren Zeichenfolge einfach nur die leere Zeichenfolge. Analog ergibt die Sequenz (,) einer leeren Zeichenfolge und eines regulären Ausdrucks e nur den regulären Ausdruck e.
re_unit, re_zero :: RE a re_sym :: a -> RE a re_rep, re_plus, re_opt :: RE a -> RE a re_seq, re_alt :: RE a -> RE a -> RE a re_unit = RE_UNIT re_zero = RE_ZERO re_sym x = RE_SYM x re_rep RE_UNIT = RE_UNIT re_rep RE_ZERO = RE_UNIT re_rep e = RE_REP e re_plus RE_UNIT = RE_UNIT re_plus RE_ZERO = RE_ZERO re_plus e = RE_PLUS e re_opt RE_UNIT = RE_UNIT re_opt RE_ZERO = RE_UNIT re_opt e = RE_OPT e re_seq RE_ZERO f = RE_ZERO re_seq RE_UNIT f = f re_seq e RE_ZERO = RE_ZERO re_seq e RE_UNIT = e re_seq e f = RE_SEQ e f re_alt RE_ZERO f = f re_alt e RE_ZERO = e re_alt e f = RE_ALT e f
Die Berechnung, ob sich regulärer Ausdruck auf eine leere Zeichenfolge ableiten lässt geschieht durch die Funktion nullable.
nullable :: RE sym -> Bool
Die leere Menge ist nicht auf leeren Zeichenfolge ableitbar
nullable RE_ZERO = False
Die leere Zeichenfolge ist auf eine leere Zeichenfolge ableitbar
nullable RE_UNIT = True
Ein Zeichen ist nicht auf eine leere Zeichenfolge ableitbar
nullable (RE_SYM s) = False
Die optionale Wiederholung (*) eines regulären Ausdrucks e ist auf eine leere Zeichenfolge ableitbar
nullable (RE_REP e) = True
Die Wiederholung (+) eines regulären Ausdrucks e ist auf eine leere Zeichenfolge ableitbar, wenn der wiederholte reguläre Ausdruck e auf eine leere Zeichenfolge ableitbar ist
nullable (RE_PLUS e) = nullable e --
Die Option (?) eines regulären Ausdrucks e ist auf eine leere Zeichenfolge ableitbar
nullable (RE_OPT e) = True
Die Sequenz (,) zweier regulärer Ausdrücke e und f ist auf eine leere Zeichenfolge ableitbar, wenn e und f auf eine leere Zeichenfolge ableitbar sind.
nullable (RE_SEQ e f) = nullable e && nullable f
Die Alternative (|) zweier regulärer Ausdrücke e und f ist auf eine leere Zeichenfolge ableitbar, wenn e oder f auf eine leere Zeichenfolge ableitbar ist.
nullable (RE_ALT e f) = nullable e || nullable f
Die Ableitung des regulären Ausdrucks bezüglich eines Zeichens geschieht durch die Funktion delta. Die Funktion erhält als Parameter einen regulären Ausdruck und ein Zeichen. Sie reduziert den regulären Ausdruck um dieses Zeichen. Rückgabewert ist der reduzierte reguläre Ausdruck.
delta :: (Eq a) => RE a -> a -> RE a delta re x = case re of
Die leere Menge kann nicht weiter reduziert werden.
RE_ZERO -> re_zero
Die leere Zeichenfolge kann nicht um ein Zeichen reduziert werden.
RE_UNIT -> re_zero
Ein Symbol kann erfolgreich reduziert werden, wenn es dem Zeichen entspricht.
RE_SYM sym | x == sym -> re_unit | otherwise -> re_zero
Die optionale Wiederholung (*) wird in eine Sequenz aus dem reduzierten regulären Ausdruck e und dem ursprünglichen regulären Ausdruck e überführt. Der ursprüngliche reguläre Ausdruck e wird optional wiederholt.
RE_REP e -> re_seq (delta e x) (re_rep e)
Die Wiederholung (+) wird in eine Sequenz aus dem reduzierten regulären Ausdruck e und dem ursprünglichen regulären Ausdruck e überführt. Der ursprüngliche reguläre Ausdruck e wird optional wiederholt.
RE_PLUS e -> re_seq (delta e x) (re_rep e)
Bei der Option (?) wird der enthaltene reguläre Ausdruck e auf das Zeichen angewendet.
RE_OPT e -> delta e x
Bei der Sequenz (,) wird geprüft, ob der erste enthaltene reguläre Ausdruck e auf eine leere Zeichenfolge ableitbar ist. Ist dies der Fall, müssen die beiden regulären Ausdrücke e und f der Sequenz auf das Zeichen angewendet werden. Ansonsten genügt es, der ersten regulären Ausdrück e bezüglich des Zeichens abzuleiten.
RE_SEQ e f | nullable e -> re_alt (re_seq (delta e x) f) (delta f x) | otherwise -> re_seq (delta e x) f
Bei der Alternative (|) wird eine Alternative mit den Ableitungen von beiden enthaltenen regulären Ausdrücken e und f erzeugt.
RE_ALT e f -> re_alt (delta e x) (delta f x)
Die Funktion matches dient zum Prüfen, ob eine Zeichenfolge durch einen regulären Ausdruck definiert wird. Sie nimmt als Parameter einen regulären Ausdruck und eine Zeichenfolge entgegen. Als Ergebnis liefert sie True zurück, wenn der reguläre Ausdruck auf die Zeichenfolge passt, andernfalls False.
matches :: (Eq a) => RE a -> [a] -> Bool matches e = nullable . foldl delta e
foldlmatches ist sehr kompakt geschrieben. Kern der Funktion ist die higher-order function foldl, welche als Parameter die Funktion delta, den regulären Ausdruck und die Zeichenfolge entgegennimmt.
Die Funktionen foldl nimmt als Parameter eine Funktion, einen Startwert und eine Liste von Werten entgegen. Sie ist in der Haskell Standard-Prelude wie folgt definiert:
foldl :: (a -> b -> a) -> a -> [b] -> a foldl f st [] = st foldl f st (x:xs) = foldl f (f st x) xs
Beispiel - Addition einer Liste von Zahlen mit foldl:
foldl (+) 0 [1..4] 1. foldl (+) (0 + 1) [2..4] 2. foldl (+) ((0 + 1) + 2) [3..4] 3. foldl (+) (((0 + 1) + 2) + 3) [4] 4. foldl (+) ((((0 + 1) + 2) + 3) + 4) [] 5. ((((0 + 1) + 2) + 3) + 4) 6. 10
Der reguläre Ausdruck wird zunächst mit Hilfe der beschriebenen Konstruktor-Funktionen erzeugt:
(a , b) | (a , c) = re_alt (re_seq (re_sym "a") (re_sym "b")) (re_seq (re_sym "a") (re_sym "c"))
Dieser reguläre Ausdruck wird nun zusammen mit der Zeichenfolge "ab" der Funktion matches übergeben:
matches re_alt(...) ["a","b"]
matches demonstriert.Die bereits beschriebene higher-order function foldl wird mit der delta Funktion, dem regulären Ausdruck und der Zeichenfolge aufgerufen. Dabei wird die delta Funktion für jedes Zeichen der Zeichenfolge aufgerufen, siehe Additions-Beispiel.
foldl delta re_alt(...) ["a","b"] 1. foldl delta (delta re_alt(...) "a") ["b"] 2. foldl delta (delta (delta re_alt(...) "a") "b") []
Ist die Liste der Zeichenfolge leer, fangen die ineinander geschachtelten delta Funktionen an zu arbeiten. Zunächst wird der eingegebene reguläre Ausdruck (a , b) | (a , c) auf das Zeichen 'a' angewendet. Da es sich um eine Alternative (|) handelt, werden die beiden enthaltenen regulären Ausdrücke der Alternative (|) um das Zeichen 'a' reduziert.
delta re_alt(...) "a" 1. re_alt (delta re_seq(...) "a") (delta re_seq(...) "a")
Die enthaltenen regulären Ausdrücke der Alternative sind Sequenzen (,). Da der erste reguläre Ausdruck der Sequenzen nicht auf eine leere Zeichenfolge ableitbar ist, werden die ersten regulären Ausdrücke der Sequenzen nach dem Zeichen 'a' abgeleitet.
delta re_seq(...) "a" 2.1 re_seq (delta re_sym "a" "a") re_sym "b" 2.2 re_seq (delta re_sym "a" "a") re_sym "c"
Beide reguläre Ausdrücke der Sequenzen akzeptieren das Zeichen 'a' und liefern als neuen regulären Ausdruck die leere Zeichenfolge.
delta (re_sym "a") "a" => re_unit
Durch die Konstruktor-Funktionen verbleibt folgender regulärer Ausdruck nach Ableitung des ursprünglichen regulären Ausdrucks (a, b) | (a,c) bezüglich 'a':
(b | c) = re_alt (re_sym "b") (re_sym "c")
Der verbliebene reguläre Ausdruck wird nun auf das Zeichen 'b' angewendet. Da es sich bei dem regulären Ausdruck (b | c) um eine Alternative (|) handelt, werden die beiden enthaltenen regulären Ausdrücke auf 'b' angewendet.
delta (re_alt (re_sym "b") (re_sym "c")) "b" 1. re_alt (delta (re_sym "b") "b") (delta (re_sym "c") "b") 2.1 delta (re_sym "b") "b" => re_unit 2.2 delta (re_sym "c") "b" => re_zero
Nur der reguläre Ausdruck für das Zeichen 'b' kann auf 'b' angewendet werden. Durch die Konstruktor-Funktionen wird der reguläre Ausdruck (b | c) auf den regulären Ausdruck für die leere Zeichenfolge reduziert. Da dieser reguläre Ausdruck auf die leere Zeichenfolge ableitbar ist, passt der reguläre Ausdruck (a, b) | (a, c) auf die Zeichenfolge "ab".
re_alt (re_unit) (re_zero) => re_unit nullable re_unit => True
| #PCDATA | re_opt (re_sym "#PCDATA") |
| EMPTY | re_unit |
| ANY | (PCDATA | elem_1 | ... | elem_n)* |
| children / mixed content |
regulärer Ausdruck der DTD |
Bei der Implementierung des zweiten Ansatzes müsste die vorhandene Baumstruktur in eine Liste umgewandelt werden. Da für jedes erkannte Element sofort dessen Kinder verarbeitet werden, ist die Liste entsprechend einer Preorder-Traversierung des Baumes aufzubauen.
Beim Erkennen eines Elements in der delta Funktion würde nun nicht mehr der reguläre Ausdruck für eine leere Zeichenfolge, bzw. Elementfolge, zurückgegeben werden, sondern der reguläre Ausdruck für dessen Inhaltsmodell.
delta re x = case re of
...
RE_SYM sym
| expectedNode x sym -> getContentModel (...)
| otherwise -> re_zero
...
Der beschriebene Algorithmus stellt einen sehr eleganten Ansatz zur XML-Validierung dar. Statt das Inhaltsmodell in Endliche Automaten zu transformieren, kann mit dessen regulären Ausdrücken gearbeitet werden.
Es muss jedoch ein Weg gefunden werden, um aussagekräftige Fehlermeldungen zu erzeugen, die dem User informieren an welcher Stelle im XML-Dokument ein Fehler aufgetreten ist. Die dargestellte Implementierung dieses Algorithmus unterstützt aussagekräftige Fehlermeldungen in keinster Weise, sondern meldet lediglich nach der Abarbeitung aller Zeichen, bzw. Elemente, ob eine Zeichenkette, bzw. ein XML-Dokument, einen regulären Ausdruck entspricht.