ParseLib.lhs Library functions for parsing Note that this is not a monadic approach to parsing. (c) Simon Thompson, 1995,1998. > module ParseLib where > infixr 5 >*> The type of parsers. > type Parse a b = [a] -> [(b,[a])] Some basic parsers Fail on any input. > none :: Parse a b > none inp = [] Succeed, returning the value supplied. > succeed :: b -> Parse a b > succeed val inp = [(val,inp)] token t recognises t as the first value in the input. > token :: Eq a => a -> Parse a a > token t (x:xs) > | t==x = [(t,xs)] > | otherwise = [] > token t [] = [] spot whether an element with a particular property is the first element of input. > spot :: (a -> Bool) -> Parse a a > spot p (x:xs) > | p x = [(x,xs)] > | otherwise = [] > spot p [] = [] Examples. > bracket = token '(' > dig = spot isDigit Succeeds with value given when the input is empty. > endOfInput :: b -> Parse a b > endOfInput x [] = [(x,[])] > endOfInput x _ = [] Combining parsers alt p1 p2 recognises anything recogniseed by p1 or by p2. > alt :: Parse a b -> Parse a b -> Parse a b > alt p1 p2 inp = p1 inp ++ p2 inp > exam1 = (bracket `alt` dig) "234" Apply one parser then the second to the result(s) of the first. > (>*>) :: Parse a b -> Parse a c -> Parse a (b,c) > (>*>) p1 p2 inp > = [((y,z),rem2) | (y,rem1) <- p1 inp , (z,rem2) <- p2 rem1 ] Transform the results of the parses according to the function. > build :: Parse a b -> (b -> c) -> Parse a c > build p f inp = [ (f x,rem) | (x,rem) <- p inp ] Recognise a list of objects. > list :: Parse a b -> Parse a [b] > list p = (succeed []) > `alt` > ((p >*> list p) `build` convert) > where > convert = uncurry (:) Some variants... A non-empty list of objects. > neList :: Parse a b -> Parse a [b] > neList p = (p `build` (:[])) > `alt` > ((p >*> list p) `build` (uncurry (:))) Zero or one object. > optional :: Parse a b -> Parse a [b] > optional p = (succeed []) > `alt` > (p `build` (:[])) A given number of objects. > nTimes :: Int -> Parse a b -> Parse a [b] > nTimes 0 p = succeed [] > nTimes (n+1) p = (p >*> nTimes n p) `build` (uncurry (:))