Skip to content

Instantly share code, notes, and snippets.

@AlexeyRaga
Created December 28, 2016 00:05
Show Gist options
  • Select an option

  • Save AlexeyRaga/ac5393d4a49e1c3447362e769bcc816b to your computer and use it in GitHub Desktop.

Select an option

Save AlexeyRaga/ac5393d4a49e1c3447362e769bcc816b to your computer and use it in GitHub Desktop.
Simple naive regex matcher in Haskell
{-# LANGUAGE OverloadedStrings #-}
-- Code from https://www.schoolofhaskell.com/school/to-infinity-and-beyond/pick-of-the-week/a-regular-expression-matcher
import GHC.Exts (IsString(..))
data Regexp = Zero -- empty
| One -- epsilon
| Lit Char -- single character
| Plus Regexp Regexp -- union (+)
| Cat Regexp Regexp -- concatenation (.)
| Star Regexp -- repetition (*)
deriving Show
infixl 6 <+>
infixl 7 <>
(<+>) :: Regexp -> Regexp -> Regexp
Zero <+> e = e
e <+> Zero = e
e1 <+> e2 = Plus e1 e2
(<>) :: Regexp -> Regexp -> Regexp
Zero <> _ = Zero
_ <> Zero = Zero
One <> e = e
e <> One = e
e1 <> e2 = Cat e1 e2
star :: Regexp -> Regexp
star Zero = One
star One = One
star (Star e) = Star e
star e = Star e
type Cont= String -> Bool
accept :: Regexp -> String -> Cont -> Bool -- worker function
accept Zero cs k = False
accept One cs k = k cs
accept (Lit c) (c':cs) k = c==c' && k cs
accept (Lit c) [] k = False
accept (Cat e1 e2) cs k = accept e1 cs (\cs' -> accept e2 cs' k)
accept (Plus e1 e2) cs k = accept e1 cs k || accept e2 cs k
accept (Star e) cs k = accept_star e cs k
where
accept_star e cs k
= k cs || accept e cs (\cs' -> cs'/=cs && accept_star e cs' k)
match :: Regexp -> String -> Bool
match re s = accept re s null
instance IsString Regexp where
fromString cs = foldr ((<>) . Lit) One cs
-- Example use
main = let re = "ab" <> star "ba"
in print (match re "abbaba")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment