A regular expression matcher using Brzozowski derivatives.

regex-deriv.hs

data Regex
  = Empty
  | Single Char
  | Alt Regex
        Regex
  | Con Regex
        Regex
  | Star Regex
  deriving (Show)

eStr :: Regex
eStr = Star Empty

obs :: Regex -> Bool
obs Empty = False
obs (Single _) = False
obs (Alt r s) = obs r || obs s
obs (Con r s) = obs r && obs s
obs (Star _) = True

deriv :: Char -> Regex -> Regex
deriv _ Empty = Empty
deriv c (Single c') =
  if c == c'
    then eStr
    else Empty
deriv c (Alt r s) = Alt (deriv c r) (deriv c s)
deriv c (Con r s) = Alt (Con (deriv c r) s) (Con obsR (deriv c s))
  where
    obsR =
      if obs r
        then eStr
        else Empty
deriv c (Star r) = Con (deriv c r) (Star r)

derivStr :: String -> Regex -> Regex
derivStr [] r = r
derivStr (a:x) r = derivStr x (deriv a r)

match :: Regex -> String -> Bool
match r s = obs (derivStr s r)