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 [] = []
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
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"])]
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.