Vorlesung: Praxis der Funktionalen Programmierung | Index

Die (einfache) Parser-Monade

ist eine Variante der Zustandsmonade. Jene war s -> (a, s). Als Zustand eines Parsers nehmen wir die noch nicht gelesene Eingaben (also vom Typ String). Wir müssen damit rechnen, daß ein Präfix mehrere Ableitungen (Parse-Bäume) besitzt, wir benötigen nicht ein Ergebnis (a, s), sondern eine Liste davon. Deswegen s -> [(a, s)].

module Parser_Type 

( Parser (..)
, parse
, MonadZero (zero), guard
, MonadPlus (plus)
)

where

import MonadZero
import MonadPlus

data Parser a = Parser ( String -> [ (a, String) ] )

parse :: Parser a -> String -> Either String a
parse (Parser p) input = 
   case p input of
	[(x, ""  )] -> Right x
	[(x, rest)] -> Left "kein vollständiger Parse"
        []	    -> Left "kein Parse"
	_	    -> Left "kein eindeutiger Parse"

instance Functor Parser where
    fmap f (Parser p) = Parser $ \ input ->
	 [ (f x, rest) | (x, rest) <- p input ]

instance Monad Parser where
    return x = Parser $ \ input -> [ (x, input) ]
    Parser p >>= f = Parser $ \ input ->
        [ (y, rest') 
	| (x, rest) <- p input
	, let Parser q = f x
	, (y, rest') <- q rest
	]

instance MonadZero Parser where
    zero = Parser $ \ input -> []

instance MonadPlus Parser where
    Parser p `plus` Parser q = Parser $ \ input ->
        p input ++ q input

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de