Validierung mit Parser Kombinatoren



[ Informatik-Seminar 2002 ] ... [ Thema XML-Validierung mit Haskell ] ... [ Literaturverzeichnis ] ...

Übersicht:


Einführung

Häufig werden Werkzeuge wie Yacc zur automatischen Generierung von Parsern aus kontextfreien Grammatiken verwendet. Für Haskell existiert das Yacc-ähnliche Werkzeug Happy.
Yacc und Happy erzeugen beide Bottom-Up-Parser. Diese sind zwar sehr effizient implementierbar, haben jedoch den Nachteil, daß sie als Eingabe LALR-Grammatiken benötigen. Grammatiken dieser Klasse sind meistens schwer verständlich, außerdem müssen Grammatiken aus Sprachdefinitionen erst in einem komplexen, fehlerträchtigen Schritt in diese Form umgewandelt werden. Top-Down-Parser arbeiten mit den weitaus natürlicheren LL(k)-Grammatiken.

Parserkombinatoren bieten einen anderen, eleganten Weg zur Erzeugung von Parsern. Parserkombinatoren sind Funktionen höherer Ordnung, die die Erzeugung eines Parsers innerhalb des funktionalen Programms direkt aus einer BNF-Grammatik ermöglichen. Ein erheblicher Vorteil von Parserkombinatoren liegt in der Entwicklung der Grammatik. Durch Backtracking sind diese Parser in der Lage, kontextfreie Grammatiken zu parsen, an die keine weiteren Forderungen, wie z.B. LALR(1), gestellt werden.

Parserkombinatoren bieten darüber hinaus viele weitere Vorteile:

Kombinatoren zur XML-Validierung

Im folgenden werden die Basiskombinatoren für die kontextfreie Grammatik des Element-Inhaltsmodells vorgestellt.
Zunächst gilt es einen Datentyp für die Parserkombinatoren zu definieren. Der Datentyp heißt Parser und ist eine Funktion, die eine Liste von Symbolen als Parameter entgegennimmt und als Ergebnis eine Liste von Tupeln liefert. Eine leere Ergebnis-Liste singnalisiert einen Pars-Fehler. Mehrere Ergebnisse zeigen an, dass mehrere erfolgreiche Pars-Möglichkeiten existieren, auch list of success genannt.
Die Tupel der Ergebnisliste bestehen aus dem geparsten Ergebnis und der verbliebenen Liste der ungeparsten Symbole. Ist die Liste der verbliebenen Symbole leer, so wurden alle Symbole geparst.

type Parser sym res = [sym] -> [(res,[sym])]

Um die Parserkombinatoren in einer natürlichen Schreibweise darzustellen werden drei Infix-Operatoren definiert.

infixl 7 <$   -- Umwandeln eines Parsers in einen anderen
infixr 5 >*>  -- Sequenz zweier Parser
infixr 4 <|>  -- Alternative zweier Parser

Dieser Funktion nimmt einen Parser und eine Funktion entgegen und wendet diese Funktion auf das Ergebnis des Parsers an. Mit Hilfe dieser Funktion ist es Möglich, das Ergebnis eines Parsers zu transformieren.

(<$) :: Parser s a -> (a -> b) -> Parser s b
(p <$ f) inp = [(f y, ys) | (y, ys) <- p inp]

Sequenz (,)
Diese Funktion nimmt zwei Parser entgegen und liefert als Ergebnis einen Parser, welcher beide Parser hintereinander ausführt. Der zweite Parser arbeitet auf den nicht konsumierten Symbolen des ersten Parsers. Die Ergebnisse beider Parser werden in einem Tupel zusammengefasst.

(>*>) :: Parser s a -> Parser s b -> Parser s (a,b)
(p1 >*> p2) inp = [((y,z),rest2) | (y,rest1) <- p1 inp, (z,rest2) <- p2 rest1]

Alternative (|)
Diese Funktion verknüpft die Ergebnislisten zweier Parser. Da nur ein Parser bei einer Alternative ein Ergebnis liefert und der zweite eine leere Liste, ist dieses Vorgehen möglich.

(<|>) :: Parser s a -> Parser s a -> Parser s a
(p <|> q) inp = p inp ++ q inp

Optionale Wiederholung (*)
Diese Funktion nimmt einen Parser entgegen und liefert als Ergebnis eine Liste von dessen Ergebnissen. Die Funktion ruft den übergebenen Parser und anschließend sich selbst rekursiv auf. Da die Wiederholung optional ist, wird dieser Parser durch den Alternativ-Kombinator mit der leeren Ergebnisliste verknüpft.

many :: Parser s a -> Parser s [a]
many p = (p >*> many p) <$ toList
        <|> succeed []

Wiederholung (+)
Diese Funktion nimmt einen Parser entgegen und liefert als Ergebnis eine Liste von dessen Ergebnissen. Die Funktion ruft den Parser und anschließend many auf.

many1 :: Parser s a -> Parser s [a]
many1 p = (p >*> many p) <$ toList

Option (?)
Diese Funktion nimmt einen Parser entgegen und liefert als Ergebnis einen Parser, der eine leere Ergebnisliste oder die Ergebnisse des Parsers liefert.

optional :: Parser s a -> Parser s [a]
optional p = (succeed [])
            <|> (p  <$ (:[]))

Symbol
Diese Funktion nimmt ein Symbol entgegen und liefert als Ergebnis einen Parser, der dieses Symbol konsumiert.

sym :: Eq s => s -> Parser s s
sym a (x:xs) | x == a    = [(x,xs)]
             | otherwise = []
sym a []                 = []

Hilfsfunktionen

Diese Funktion liefert einen Parser, der ein als Parameter übergebenes Ergebnis liefert, ohne ein Eingabesymbol zu verarbeiten.

succeed :: a -> Parser s a
succeed r xs = [(r, xs)]

Wandelt ein Tupel in eine Liste um

toList (x,xs) = x:xs


Beispiele

Mit den folgenden Beispielen soll demonstriert werden, wie Parserkombinatoren arbeiten. Dabei werden vorgegebene reguläre Ausdrücke in entsprechende Parser transformiert. In den Beispielen werden nur Zeichenketten verwendet. Die Beispiele lassen sich jedoch leicht auf XML übertragen, indem man anstatt der Zeichen Elemente annimmt.

1. Dieses erste Beispiel ist dem vorherigen Abschnitt der Ableitung regulärer Ausdrücke entnommen. Der reguläre Ausdruck wird in einem Parser transformiert und dieser mit einer Zeichenkette aufgerufen. Das vom Parser gelieferte Resultat zeigt durch die leere Liste der noch zu konsumierenden Symbole an, dass der Parser die gesamte Eingabe verarbeiten konnte.

regulärer Ausdruck: (a, b) | (a, c)

Parser:
test1 = ((sym "a") >*> (sym "b")) <|> ((sym "a") >*> (sym "c"))

Aufruf:
test1 ["a","b"]

Ergebnis:
[(("a","b"),[])]



2. Bei diesem Beispiel liefert der Parser mehrere Ergebnisse. Der Parser kann eine Liste von a's konsumieren und wird mit vier a's aufgerufen. Da ein Parserkombinator nicht zwingend alle Symbole verarbeiten muss, liefert dieser Parser vier Ergebnisse. Zuerst das Ergebnis aller konsumierten a's, anschließend das Ergebnis, wenn nur drei a's konsumiert werden usw. Die Listen der noch zu konsumierenden Symbole zeigen an, wie viele a's nicht verarbeitet wurden. Entscheidend ist lediglich das erste Ergebnis, da die leere Symbolliste anzeigt, dass der Parser alle Symbole verarbeiten konnte.

regulärer Ausdruck: a+

Parser:
test2 = many1 (sym "a")

Aufruf:
test2 ["a","a","a","a"]

Ergebnis:
[(["a","a","a","a"],[]),(["a","a","a"],["a"]),(["a","a"],["a","a"]),(["a"],["a","a","a"])]

Wird die Liste der a's durch ein anderes Zeichen erweitert, kann der Parser dieses Zeichen nicht verarbeiten. Die nicht leeren Symbollisten im Ergebnis zeigen dies an. Das Zeichen 'c' konnte nicht verarbeitet werden.

Aufruf:
test2 ["a","a","c"]

Ergebnis
[(["a","a"],["c"]),(["a"],["a","c"])]



3. Dies ist ein Beispiel für einen etwas komplexeren regulären Ausdruck, bzw. Parser. In der Eingabezeichenkette sind nur die zwingend notwendigen Symbole angegeben. Alle anderen Parserkombinatoren liefern als Ergebnis eine leere Liste.

regulärer Ausdruck: a*, b, (c?, d*, e)+

Parser:
test3 = many (sym "a") >*> (sym "b") >*> many1 (optional (sym "c") >*> many (sym "d") >*> (sym "e"))

Aufruf:
test3 ["b","e"]

Ergebnis:
[(([],("b",[([],([],"e"))])),[])]

Ein weiterer Aufruf des obigen Parsers, wieder wird die gesamte Eingabe akzeptiert.

Aufruf:
test3 ["b","e","c","d","e"]

Ergebnis:
[(([],("b",[([],([],"e")),(["c"],(["d"],"e"))])),[]),(([],("b",[([],([],"e"))])),["c","d","e"])]



4. Dieses letzte Beispiel soll das nicht-deterministische Parsen veranschaulichen. Der Parser liefert insgesamt zwei erfolgreiche Resultate, da das Zeichen 'a' von beiden Teil-Parsern akzeptiert wird. Welches Ergebnis letztendlich genommen wird ist irrelevant.

regulärer Ausdruck: (a* | a*)

Parser:
test4 = (many (sym "a")) <|> (many (sym "a"))

Aufruf:
test4 ["a"]

Ergebnis:
[(["a"],[]),([],["a"]),(["a"],[]),([],["a"])]


Bewertung

Parserkombinatoren haben sich in vielen Anwendungen bewährt. Fehlererkennungen und Fehleranzeigen sind gut erforscht und lassen sich relativ einfach implementieren.

Es ist jedoch eine Kunst, die Kombinatoren so zu entwerfen, dass sie beliebig kombiniert werden können, da sich durch das Kombinieren ständig ihr Rückgabe-Typ ändert. So kann z.B. der reguläre Ausdruck (a* | (a+)?) nicht durch die obigen Kombinatoren nachgebildet werden, ohne den Parsertyp zusätzlich zu modifizieren. Ein weiteres Problem stellt der reguläre Ausdruck (a*)* dar, weil die Kombinatoren hierbei einen Stack-overflow erzeugen.


[ Informatik-Seminar 2002 ] ... [ Thema XML-Validierung mit Haskell ] ... [ Validierung mit Parser Kombinatoren ] ... [ Literaturverzeichnis ] ...