Created
November 16, 2010 22:45
-
-
Save petermarks/702671 to your computer and use it in GitHub Desktop.
Expression parser
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Data.Maybe | |
import Text.Printf | |
import Control.Applicative | |
data Expr = Term Int | Op Operator Expr Expr | Var String | |
deriving (Show, Eq) | |
data Operator = Sum | Mult | Sub | Div | |
deriving (Show, Eq) | |
newtype Parser a = Parser {runParser :: String -> Maybe (a, String)} | |
anyCharP :: Parser Char | |
anyCharP = Parser p | |
where | |
p [] = Nothing | |
p (x : xs) = Just (x, xs) | |
charP :: Char -> Parser Char | |
charP c = Parser $ \inp -> case inp of | |
(x:xs) | x == c -> Just (c, xs) | |
_ -> Nothing | |
combP :: (a -> b -> c) -> Parser a -> Parser b -> Parser c | |
combP f pa pb = f <$> pa <*> pb | |
instance Functor Parser where | |
fmap f (Parser pa) = Parser $ \s -> case pa s of | |
Nothing -> Nothing | |
Just (a, s') -> Just (f a, s') | |
instance Applicative Parser where | |
pure x = Parser $ \s -> Just (x, s) | |
(Parser pf) <*> (Parser pa) = Parser $ \s -> case pf s of | |
Nothing -> Nothing | |
Just (f, s') -> case pa s' of | |
Nothing -> Nothing | |
Just (a, s'') -> Just (f a, s'') | |
-- a monoid on applicative functors | |
instance Alternative Parser where | |
empty = Parser $ \s -> Nothing | |
(Parser pa) <|> (Parser pb) = Parser $ \s -> case pa s of | |
Just (a, s') -> Just (a, s') | |
Nothing -> pb s | |
digitP = foldr1 (<|>) (map charP ['0'..'9']) | |
symbolCharP = foldr1 (<|>) (map charP (['a'..'z'] ++ ['A'..'Z'])) <|> digitP | |
-- lift char into a String | |
str :: Char -> String | |
str = \x -> [x] | |
-- zero or many | |
manyP :: Parser String -> Parser String | |
manyP p = many1P p <|> pure "" | |
-- one or many | |
many1P :: Parser String -> Parser String | |
many1P p = (++) <$> p <*> manyP p | |
-- parse an int | |
intP :: Parser Int | |
intP = read <$> many1P (str <$> digitP) | |
-- parse a non-whitespace string | |
symbolP :: Parser String | |
symbolP = many1P (str <$> symbolCharP) | |
operatorP :: Parser Operator | |
operatorP = (const Sum) <$> charP '+' <|> | |
(const Mult) <$> charP '*' <|> | |
(const Sub) <$> charP '-' <|> | |
(const Div) <$> charP '/' | |
termP :: Parser Expr | |
termP = Term <$> intP | |
varP :: Parser Expr | |
varP = Var <$> symbolP | |
opP :: Parser Expr | |
opP = charP '(' *> ((\a o b -> Op o a b) <$> exprP <*> operatorP <*> exprP) <* charP ')' | |
exprP :: Parser Expr | |
exprP = termP <|> opP <|> varP | |
parseExpr :: String -> Maybe Expr | |
parseExpr s = maybe Nothing (Just . fst) (runParser exprP (filter (/=' ') s)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment