Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A regular expression matcher using Brzozowski derivatives.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment