Revision 2443d995-90e9-4b64-b96c-71c019bfd04f - Code Golf Stack Exchange

# [Haskell], 223 bytes

Nobody had done this by implementing a small regex engine yet, and I felt like it had to be done. This obviously won't win. but I'm hoping it will inspire someone to write an even more golfed regex engine.

I've rewritten my solution to avoid directly parsing the regular expression into its AST. Instead, the parsing process constructs a function used to match a string against the parsed regex. 

The main function is `(&) :: String -> String -> Bool` which takes a string representation of a regex and a string to test, returning a boolean value. This calls to the next function which handles most of the work in parsing the regex and matching the string. 

Function `p :: String -> ([String] -> [String], String)` takes a regex representation of a string and returns as the first element of the tuple a function that returns a list of all possible unmatched suffixes of strings in the input list after satisfying the regex parsed from the input string.

<!-- language-all: lang-hs -->

 import Data.List
 r&s=elem""$fst(p r)[s]
 (h:t)?c|c==h=[t]
 _?_=[]
 p(c:t)|c>'`'=(>>=(?c))%t|c>'^'=id%t|(l,o:t)<-p t,(r,_:u)<-p t=(if o<','then(r.l)else\s->r s++l s)%u
 m#s|t<-nub$m s,s/=t=s++m#t|1>0=s
 m%('*':t)=(m#)%t
 m%s=(m,s)

[Try it online!][TIO-k570i3e6]

[Haskell]: https://www.haskell.org/
[TIO-k570i3e6]: https://tio.run/##nZjfb5swEMff@Sss@iM2JOv2GtWpNE2VJlWatO6t69iZug0ahAg7ah/Q/vXOkJBAg8/uUKIA34/Pd8f5ICxB/ZF5/vqaFeuy0uQLaPhwkykdVOeKy1wWYXj6qDRdk4rdqfuALueaXaV1yvmS3@n7ILlK@N19sKapEep0Mfk94XSx4PQqZexMN2d@TXj2YHZpPi0NdDlbEz2l1TSZb7YHnGaPpLycTCd6KVe0@pAzmSv5U80WFVFxnBPFzjZBcaJqfTlbbcRpQdRUXXDNjVqc6PrT4iNXQXFGJ9HETMFpcWImNyeU2Z0q9lpAtiLzOfn6jVAWtEecPJQBMdt6o291dbMi4a2GSmerJ6Kl0ips1Wb3u3ySLySEsP3@qDZyTBIhuQbj95jWSW@1pNXGLCZ9i29FCrFgjTdifPBet7jU6cKhg0gdRApOG6mLsEdZd1GMB1l3QWAy4mDtDLJ2Blk7g6zxIA2QsFhEzFoKAwQ8GOFjxwcSfpa8TAFYq3FgDQRaD5GjIFrdCTTegPCghD26DnPIzvGQAlY724BSF5Ie0nvUSuxeJlGzIXK/iRzPHcWALtBOdwMuwhr@ThcuAADcjIcVYc8zTWo0HTsZV60udMax5ZHg7TLpTW9ZhODuMfgl7TH4cndkvAd5MfarYjDDmOzF7Q1n32Rs7rf4AN7TI3cwPOVxghbvbjRSUXGClgyq7n2zFdRQHyv6bS7w9bdnwAtCVnoP8qTAfmEAbc47GXlAAsetZA942ED8xFsG1Hj3q2FYQBZAuHSXAbTrHEVpQxyyczz0Nzcr@rA9vGj3dOJPD2CBPdkZPqaiFr16tbayAevL@Vv0inBkkHj/KPG/cw2yauvPw6k8OfAHhbfDAsQ7UiKslQLYM9hOBFx1yfiq2WHuS31kT3iAYmBx/C4eNV/HP6COAS/Ik3K0kwHttxTGrAt/3pGtJDYfiFiEpWsIgR/lizkyNsQ9UmazL94xQBzNcHirc52tMrWUD91bnSA4GJvPiaGaVz6zRW/vc1nmze/2ddEBryRRuiLNDDWhlTw3R4xwTiThRtSbatUMaNRSL2X1nCk58qKJUrUsn0k7OI5JSP6Si7DZM/ab4wsiX9Yy1cbn9vQWl4y1ZvbzvP4D "Haskell – Try It Online"

# Ungolfed Code

 import Data.List
 
 match :: String -> String -> Bool
 match r s =elem ""$(fst $ parseRegex r)[s]
 
 parseRegex :: String -> ([String] -> [String], String)
 parseRegex ('_':t) = parseKleene id t
 parseRegex (c:t) | c >= 'a' = parseKleene (>>=p) t
 where p (c':t')| c==c' = [t']
 p _ = []
 parseRegex ('(':t) =
 let (l, (o:t')) = parseRegex t in
 let (r, (_:t'')) = parseRegex t' in
 parseKleene (if o=='+' then (r.l) else (\ss-> (r ss)++(l ss))) t''
 
 parseKleene :: ([String] -> [String]) -> String -> ([String] -> [String], String)
 parseKleene p ('*':t) = parseKleene p' t
 where
 p' ss
 | ss' <- nub$ p ss,
 ss /= ss' = ss ++ (p' ss')
 | otherwise = ss
 parseKleene p s = (p,s)