Personal tools

Embedding context free grammars

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
Current revision (00:07, 22 February 2010) (edit) (undo)
m
 
(3 intermediate revisions not shown.)
Line 14: Line 14:
infixl 6 :|
infixl 6 :|
-
infixl 6 :&
 
Line 42: Line 41:
else Nothing
else Nothing
parse x (Push c g) = parse (c:x) g
parse x (Push c g) = parse (c:x) g
-
parse x (FMap y f) =
+
parse x (FMap y f) = parse x y >>= f
-
let
+
-
r1 = parse x y
+
-
in
+
-
if isJust r1 then
+
-
let r2 = fromJust r1
+
-
in
+
-
Just (f r2) else Nothing
+
parse _ _ = Nothing
parse _ _ = Nothing
-
 
-
 
-
 
-
 
-
 
-
 
infixl 7 ~&
infixl 7 ~&
Line 80: Line 66:
(a :& b)
(a :& b)
(\((a,b,c,d,e),f) -> (a,b,c,d,e,f))
(\((a,b,c,d,e),f) -> (a,b,c,d,e,f))
 +
</haskell>
 +
and here's a lambda calculus parser
 +
 +
<haskell>
Line 89: Line 79:
app = term ~& term
app = term ~& term
-
 
-
</haskell>
 
-
 
-
And here's a lambda calculus parser:
 
-
 
-
<haskell>
 
term = FMap var Var :| abstraction :| parenedTerm
term = FMap var Var :| abstraction :| parenedTerm
Line 112: Line 96:
</haskell>
</haskell>
 +
 +
[[Category:Code]]

Current revision

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
Retrieved from "http://www.haskell.org/haskellwiki/Embedding_context_free_grammars"

Category: Code