Skip to content

Instantly share code, notes, and snippets.

@petermarks
Created November 16, 2010 22:45
Show Gist options
  • Save petermarks/702671 to your computer and use it in GitHub Desktop.
Save petermarks/702671 to your computer and use it in GitHub Desktop.
Expression parser
import Data.Maybe
import Text.Printf
import Data.Char
import Control.Monad
data Expr = Term Int | Op Operator Expr Expr | Var String
deriving (Show, Eq)
data Operator = Sum | Mult | Sub | Div
deriving (Show, Eq)
sampleStr = "2 + a * 4 - b"
newtype Parser a = Parser {runParser :: String -> Maybe (a, String)}
predP :: (Char -> Bool) -> Parser Char
predP pred = Parser p
where
p (x : xs) | pred x = Just (x, xs)
p _ = Nothing
anyCharP :: Parser Char
anyCharP = predP (const True)
charP :: Char -> Parser Char
charP c = predP (==c)
combP :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
combP f pa pb = do
a <- pa
b <- pb
return $ f a b
instance Monad Parser where
return x = Parser $ \s -> Just (x, s)
(Parser a) >>= f = Parser $ \s -> do
(x, s') <- a s
runParser (f x) s'
-- or:
-- (Parser a) >>= f = Parser $ maybe Nothing (\(x, s') -> runParser (f x) s') . a
instance MonadPlus Parser where
mzero = Parser $ \s -> Nothing
(Parser a) `mplus` (Parser b) = Parser $ \s -> a s `mplus` b s
digitP :: Parser Char
digitP = predP isDigit
symbolCharP :: Parser Char
symbolCharP = predP isAlphaNum
operatorP :: Parser Operator
operatorP = msum
[ charP '*' >> return Mult
, charP '/' >> return Div
, charP '+' >> return Sum
, charP '-' >> return Sub
]
some :: Parser a -> Parser [a]
some pa = do
a <- pa
as <- some pa `mplus` return []
return $ a : as
termP :: Parser Expr
termP = some digitP >>= return . Term . read
varP :: Parser Expr
varP = some symbolCharP >>= return . Var
opP :: Parser Expr
opP = do
charP '('
a <- exprP
o <- operatorP
b <- exprP
charP ')'
return $ Op o a b
exprP :: Parser Expr
exprP = msum [termP, varP, opP]
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