![[*]](crossref.png)
type Parse = String -> Tree
Ein Parser besteht aus einer Vielzahl von vielen elementar Parsern die wiederrum durch kombinatoren verbunden sind, wobei jede dieser Kombinationen immer nur eine Teilstruktur des gesamten Systems verarbeiten. Das Problem hierbei ist, die Zwischenspeicherung der Teilergebnisse ( die Teilbäume ) und die noch zu verarbeitenden Symbole. Es gibt keine Möglichkeit die Daten in einer globalen Datenstruktur zu speichern (auf die Verwendung von Monaden sei hier verzichtet). Daher müssen die ermittelten Resultate im Funktionsergebnis zwischengespeichert werden. Eine verfeinerte Version der Implementierung kann so aussehen:
type Parse = String -> ( Tree, String )
Betrachtet man den Aspekt des gegenseitigen Aufrufs der einzelnen Parser erneut, so wird der Fall eintreten, dass ein Parser kein, ein oder sogar mehrere Ergebnisse liefert. Bei der bisherigen Betrachtung ist immer nur ein Ergebnis vorgesehen. Ein String zum Beispiel könnte mehrere Interpretationswege zulassen oder es kann der Fall eintreten, dass kein Ergebnis gefunden wird. Hierfür ist es notwendig, eine Liste von Ergebnissen in Parse zuzulassen. Eine Möglichkeit ist, dass das Ergebnis als Liste von Ergebnissen gespeichert wird. Jedes Element der Liste enthält den Teilbaum und die noch zu verarbeitenden Symbole. Wird eine leere Liste zurückgeliefert, so wurde kein Ergebnis erziehlt.
type Parse = String -> [ ( Tree, String ) ]
Wenn nur das erste Ergebnis der Liste benötigt wird, so ist lediglich der Kopf der Liste zu verwenden. Aufgrund von Lazy evaluation wird es keine Effizientsverluste geben. Die nicht verwendeten Ergebnisse werden erst bei Gebrauch berechnet.
Der Datentyp Parse wird im Tree den erzeugten Syntaxbaum und im String die noch zu verarbeitenden Symbole speichern. Die Struktur des Syntaxbaumes ist allerding von Anwendungsfall zu Anwendungsfall unterschiedlich. Als Beispiel wird eine Baumstruktur für arithmetische Ausdrücke oder in einem anderen Fall für eine XML-Datenstruktur benötigt. Damit die Baumstruktur so flexibel und unabhängig vom Anwendungsfall ist, muss ein weiterer Abstraktionsprozess durchgeführt werden.
type Parse a = String -> [ ( a, String ) ]
Bislang ist der Parser auf Strings beschrängt. Strings werden in Haskell als eine Liste von Characters implementiert. Es ist allerdings denkbar, dass es zu einem späteren Zeitpunkt anstatt einer Zeichenkette Tokens von einem Lexer als Eingabe gibt. Für diesen Fall ist der Typ ein letztes mal zu modifizieren.
type Parse b a = [b] -> [ ( a, [b] ) ]
oder etwas lesbarer auch so:
type Parse symbol result = [symbol] -> [ ( result, [symbol] ) ]
Dieser Datentyp wird in diesem Kapitel und in den folgenden Beispielen verwendet.
> symbola :: Parse Char Char > symbola [] = [] > symbola (x:xs) > | x== a = [ ( a ,xs) ] > | otherwise = []
Im Hugs aufgerufen, sieht das Ergebnis wie folgt aus. Im ersten Beispiel wurde das Symbol a erkannt und als Ergebnis abgelegt. Im zweiten Aufruf, entspricht das erste Symbol dem Zeichen b, entsprechend wurde die leere Liste zurückgegeben.
? symbola "abc" [( a ,"bc")] ? symbola "bcd" []
Die Funktion ist wie erwartet.
Damit nicht für jedes verwendete Symbol ein eigener Parser implementiert werden muss, ist dieser zu verallgemeinern. Hierfür ist der Parser symbol abgebildet.
> symbol :: Eq a => a -> Parse a a > symbol s [] = [] > symbol s (x:xs) > | s==x = [ (x,xs) ] > | otherwise = []
Bei dem Parser symbol wird das zu überprüfende Symbol als Parameter übergeben. Zusätzlich wurde eine Verallgemeinerung des Symboltyps vorgenommen. Es muss sich hierbei nicht mehr wie im vorherigen Beispiel um ein Character handeln. Es muss lediglich sichergestellt sein, dass für den Typ eine Instanz der Klasse Equality vorliegt.
> spot :: (a-> Bool) -> Parse a a > spot f [] = [] > spot f (x:xs) > | f x = [(x,xs)] > | otherwise = []
Durch die Implementierung von spot ist es jetzt möglich eine wesentlich elegantere Version von symbol zu schreiben.
> symbol :: Eq a => a -> Parse a a
> symbol t = spot (==t)
? symbol 'a' "abc"
[('a',"bc")]
> dig :: Parse Char Char > input = (spot isDigit) input
> succeed :: b -> Parse a b > succeed val inp = [(val,inp)]
Diese Funktion kann zum Beispiel als ``epsilon-'' Funktion verwendet werden. Die Funktion liefert immer einen leeren Programmbaum und die übergebenen Symbole zurück. Verwendet wird diese Funktion später bei den Parser kombinatoren.
über elementar Parser sind
nur Parser für terminal Symbole entwickelt worden. Viel interessanter sind jedoch Parser,
die terminal Symbole und nichtterminal Symbole verarbeiten. Hierfür werden
sogenannte Parser kombinatoren benötigt. Im folgenden werden einige Kombinatoren behandelt. Zum
Beispiel ein Parser zum Sequentialisieren zweier Parser (erst P1 dann P2) oder
eine Alternative (P1 oder P2).
> infixr 4 <|> > (<|>) :: Parse a b -> Parse a b -> Parse a b > (p1 <|> p2) input = (p1 input) ++ (p2 input)
Die Alternative ist hier als <|> Operator mit der 4. Prioritätsstufe und einer rechts Assoziativität implementiert. Grund für die Implementierung als Operator ist die bessere lesbarkeit des Quellcodes. Der Parser hätte natürlich auch als normale Funktion implementiert werden können. Betrachtet man zunächst die Funktionsimplementierung. Im Funktionsrumpf werden lediglich die beiden Parser p1 und p2 auf den input angewendet. Die Ergebnisse der beiden Parser werden durch den Listenkonkatenationsoperator ++ verbunden. Zum Beispiel:
? (dig <|> symbol 'a') "abc"
-- [] ++ [('a',"bc")]
[('a',"bc")]
In dem Beispiel schlägt der Parser dig fehl aber der Parser symbol 'a' liefert ein Ergebnis.
? (dig <|> symbol 'a') "123"
-- [('1',"23")] ++ []
[('1',"23")]
? (symbol 'a' <|> symbol 'b') "123"
-- [] ++ []
[]
> infixr 6 <*> > (<*>) :: Parse a b -> Parse a c -> Parse a (b,c) > (p1 <*> p2) input = [( (x1, x2), xs2 ) > | (x1, xs1) <- p1 input > , (x2, xs2) <- p2 xs1 > ]
Die Funktions- und Arbeitsweise der Sequenz ist durch die folgenden Beispiele verdeutlicht.
? (symbol 'a' <*> symbol 'b') "123"
[]
? (symbol 'a' <*> symbol 'b') "abc"
[(('a','b'),"c")]
? (symbol 'a' <*> symbol 'b' <*> symbol 'c') "abcd"
[(('a',('b','c')),"d")]
Bei dem ersten Beispiel ist das Ergebnis des ersten Parsers symbol 'a' eine leere Liste. Im zweiten Beispiel sind beide Parser erfolgreich. Näher betrachtet wird das letzte Beispiel. Das Ergebnis ist ein Baum mit Tupeln vom Typ [((Char,(Char,Char)),[Char])].
? ( symbol 'a' <*> ( symbol 'b' <*> symbol 'c') ) "abcd"
~ [ ( ('a', ('b','c') ), "d" ) ]
= [( (x1, x2), xs2 )
| (x1, xs1) <- [ ('a', "bcd") ]
, (x2, xs2) <- [ ('b', 'c'), "d" ) ]
]
? ( symbol 'b' <*> symbol 'c' ) "bcd"
~ [ ('b', 'c'), "d" ) ]
= [( (x1, x2), xs2 )
| (x1, xs1) <- [ ('b', "cd") ]
, (x2, xs2) <- [ ('c', "d" ) ]
]
> infixr 5 <@ > (<@) :: Parse a b -> ( b -> c ) -> Parse a c > (p <@ f) input = [ (f x,xs) > | (x,xs) <- p input > ]
Zunächst wird als Parameter ein Parser p und eine Funktion f erwartet. Der Parser p wird auf den input angewendet, die Funktion f wird auf das Resultat x angewendet. Das Ergebnis ist ein neuer Parser vom Typ Parse a c. Der Typ c ist hierbei der Resultattyp von der Funktion f.
> digit :: Parse Char Int > digit = spot isDigit <@ f > where f c = ord c - ord '0' ? digit "123" [(1,"23")]
Wie Eingangs erwähnt, kann durch den Operator <@ eine Ziffer in ein Integer umgewandelt werden. Die Funktion digit stellt eine mögliche Verwendung des Umwandlers dar.
> many :: Parse a b -> Parse a [b] > many p = (p <*> many p <@ list) > <|> > (succeed []) > where list (x,xs) = x:xs
Es gibt zwei unterschiedliche Funktionsergebnisse:
In den folgenden Beispielen wird deutlich, dass jede gültige Kombination in der Liste gespeichert wird. Der Parser many liefert somit mehr als ein Ergebnis. Dieses ist unbedingt bei bei der Verarbeitung zu beachten.
? many (spot isDigit) "123abc"
[("123","abc"),("12","3abc"),("1","23abc"),("","123abc")]
? many (spot isAlpha) "test"
[("test",""),("tes","t"),("te","st"),("t","est"),("","test")]
> option :: Parse a b -> Parse a [b] > option p input = ( ( p <@ (:[]) ) > <|> > ( succeed [] ) ) input
Die option wendet jeweils zwei Parser auf den input an. Zum einen den Parser p und den Umwandler <@. Zum anderen den Parser succeed []. Durch diese Alternative Verknüpfung werden bei Erfolg mehr als ein Ergebnis geliefert. Siehe dazu das folgende Beispiel:
? option (symbol '-') "-123"
[("-","123"),("","-123")]
? option (symbol '-') "123"
[("","123")]
Expr ::= const | '(' Expr Op Expr ')'
Op ::= '+' | '-' | '*' | '/' | '%'
In Hakell ist die Grammatik als einfacher arithmetischer Datentyp implementiert. Ein Ausdruck kann aus einer natürlichen Zahl Lit oder einem Ausdruck Bin bestehen. Bin ist aber wiederrum ein Operator und zwei Zahlen.
data Expr = Lit Int | Bin Op Expr Expr data Op = Add | Sub | Mul | Div | Mod
Der Ausdruck ``(14+-2)'' wird dann wie folgt dargestellt ``Bin Add Lit 14 Lit (-2)''. Ein etwas kompliziertere Ausdruck ist zum Beispiel ``(120*(20/2))'' und wird so dargestellt: ``Bin Mul Lit 120 (Bin Div Lit 20 Lit 2)''.
> parser :: Parse Char Expr > parser = litParse <|> opExprParse
Der parser beschreibt eine Expression. Die Expression besteht aus einem Literal Parser oder einer opExpr Parser.
> litParse :: Parse Char Expr > litParse > = ( > option (symbol '-') <*> many1 (spot isDigit) > ) <@ charListToExpr.join > where join = uncurry (++) ? litParse "14" [(Lit 14,""),(Lit 1,"4")] ? litParse "-4" [(Lit (-4),"")]
Der Parser litParse erstellt aus der übergebenen Symbolliste die möglichen Literals.
> opExprParse :: Parse Char Expr
> opExprParse = (symbol '('<*>
> parser <*>
> spot isOp <*>
> parser <*>
> symbol ')'
> ) <@ makeExpr
> where
> makeExpr :: (a,(Expr,(Char,(Expr,b)))) -> Expr
> makeExpr (_,(e1,(bop,(e2,_)))) = Op (charToOp bop) e1 e2
Durch den Parser opExprParse werden rekursiv die Ausdrücke zusammengebaut.
Beispiele:
? parser "(14+-2)" [(Bin Add (Lit 14) (Lit (-2)),"")] ? parser "(14-2)+a" [(Bin Sub (Lit 14) (Lit 2),"+a")]
Wie das letzte Beispiel zeigt, werden noch keine Fehler abgefangen. Es müsste in einem nächsten Entwicklungsschritt überprüft werden, ob die Menge der noch zu püfenden Symbole leer ist. Dann würde der letzte Fehler auch endeckt werden.