Check if simple regex matches string A simple regex is either:


_ (which matches the empty string)
Any lowercase letter a to z (which matches that letter)
r*, where r is a regex (which matches r any number of times)
(r|s), where r and s are regexes (which matches either r or s)
(r+s), where r and s are regexes (which matches r followed by s)


Note that due to the recursive definition, * can occur multiple times in a row.

Here are some examples of regexes and their matches:


(a+b) matches only ab
((a|_)+b*) matches , a, b, ab, bb, abb, but not baaa, aab
(c+(o+((l+(o+(u|_)))+r))) matches only color and colour
(a|b)* matches only strings containing letters a and b (so , ab, bab, but not abc)
(_***|(a+b***)) matches only the empty string or a followed by any number of bs.


Your task is to write a program that takes such a regex and a string of lowercase letters, and outputs whether or not the regex matches the entire string (output should be as described here).

The shortest code in bytes wins.
Haskell, 203 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 that is used to match a string against the input regex. 

The main function is (&amp;) :: String -&gt; String -&gt; 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 -&gt; ([String] -&gt; [String], String) takes a string representation of a regex and returns as the first element of a 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. The regex fully matches the string if the empty string is contained in the list of possible unmatched suffixes.



r&amp;s=elem""$fst(p r)[s]
p(c:t)|c&gt;'`'=t% \s-&gt;[t|h:t&lt;-s,c==h]|c&gt;'^'=t%id|(l,o:t)&lt;-p t,(r,_:u)&lt;-p t=u%last(r.l:[\s-&gt;r s++l s|o&gt;'+'])
m#s=s++filter(`notElem`s)(m s)
('*':t)%m=t%until(\s-&gt;s==m#s)(m#)
s%m=(m,s)


Try it online!

To get rid of one byte, I replaced import Data.List; m#s=nub$s++m s with m#s=s++filter(`notElem`s)(m s). These functions aren't equivalent if there are duplicate elements in either s of m s. The new function does, however, remove all elements from m s that already exist in s, so until still terminates once no new suffixes are discovered by the application of m.  

Ungolfed Code

import Data.List

match :: String -&gt; String -&gt; Bool
match r s =elem ""$(fst $ parseRegex r)[s]

parseRegex :: String -&gt; ([String] -&gt; [String], String)
parseRegex ('_':t) = parseKleene id t
parseRegex (c:t) | c &gt;= 'a' = parseKleene (&gt;&gt;=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-&gt; (r ss)++(l ss))) t''

parseKleene :: ([String] -&gt; [String]) -&gt; String -&gt; ([String] -&gt; [String], String)
parseKleene p ('*':t) = parseKleene p' t
  where
    p' ss
      | ss' &lt;- nub$ p ss,
        ss /= ss' = ss ++ (p' ss')
      | otherwise = ss
parseKleene p s = (p,s)




GolfScript, 198 bytes

I was able to beat my Haskell solution by implementing the first algorithm I tried in GolfScript instead of Haskell. I don't think it's interesting enough for a separate answer, so I'll just leave it here. There are likely some golfing opportunities since I learned GolfScript just for this.

This solution is in the form of a block that expects the test string on the top of the stack followed by the regex string.

{[.;]\1+{(.96&gt;{0[\]}{2%0{r\(\r\:s;[@]s(;\}i}{if}:i~\{(.3%}{;\2[\]\}until[.;]\+\}:r~\;{.{(.{.4%{2%{)@\m\)\;m}{)\;{.@.@m 1$|.@={\;}{\o}i}:o~}i}{;)@.@m@@\)\;m|}i}{;(:c;;{,},{(\;c=},{(;}%}i}{;}i}:m~""?}


Try it online!