Embedding context free grammars
Here's how to embed a context free grammar parser into haskell:
import Maybe
data Grammar a b where
NullParser :: Grammar a b
Check :: (a -> Bool) -> Grammar a a
(:|) :: (Grammar a b) -> (Grammar a b) -> Grammar a b
Push :: a -> (Grammar a b) -> Grammar a b
(:&) :: (Grammar a b) -> (Grammar a c) -> Grammar a (b,c)
FMap :: Grammar a c -> (c -> b) -> Grammar a b
infixl 6 :|
tok x = Check (x==)
parse :: [a] -> Grammar a b -> Maybe b
parse [c] (Check y) = if y c then Just c else Nothing
parse x (g :| g') =
let
r1 = parse x g
r2 = parse x g'
in
if isJust r1 then r1 else r2
parse (x:xs) (g :& g') =
let
r1 = parse xs ((Push x g) :& g')
r2 = parse [] g
r3 = parse (x:xs) g'
in
if isJust r1
then r1
else
if (isJust r2) && (isJust r3)
then Just (fromJust r2, fromJust r3)
else Nothing
parse x (Push c g) = parse (c:x) g
parse x (FMap y f) = parse x y >>= f
parse _ _ = Nothing
infixl 7 ~&
infixl 7 ~&&
infixl 7 ~&&&
infixl 7 ~&&&&
(~&) = (:&)
a ~&& b = FMap
(a :& b)
(\((a,b),c) -> (a,b,c))
a ~&&& b = FMap
(a :& b)
(\((a,b,c),d) -> (a,b,c,d))
a ~&&&& b = FMap
(a :& b)
(\((a,b,c,d),e) -> (a,b,c,d,e))
a ~&&&&& b = FMap
(a :& b)
(\((a,b,c,d,e),f) -> (a,b,c,d,e,f))
and here's a lambda calculus parser
data Term = Var Char | App Term Term | Abs Char Term deriving Show
var =
(Check (\x -> x <= 'z' && x >= 'a'))
app = term ~& term
term = FMap var Var :| abstraction :| parenedTerm
parenedTerm = FMap
(tok '(' ~& term ~&& tok ')')
(\(a,b,c) -> b)
abstraction = FMap
(tok '\\' ~& var ~&& tok '.' ~&&& term)
(\(a,b,c,d) -> Abs b d)
top = FMap
(term ~& tok ';')
fst
main = print $ parse "\\x.x;" top