Created
December 28, 2016 00:05
-
-
Save AlexeyRaga/ac5393d4a49e1c3447362e769bcc816b to your computer and use it in GitHub Desktop.
Simple naive regex matcher in Haskell
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| {-# 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