[Question]
  [
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 `b`s.
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](https://codegolf.meta.stackexchange.com/a/12308/84442)).
The shortest code in bytes wins.
  
[Answer]
# [Haskell](https://www.haskell.org/), 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 `(&) :: 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 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&s=elem""$fst(p r)[s]
p(c:t)|c>'`'=t% \s->[t|h:t<-s,c==h]|c>'^'=t%id|(l,o:t)<-p t,(r,_:u)<-p t=u%last(r.l:[\s->r s++l s|o>'+'])
m#s=s++filter(`notElem`s)(m s)
('*':t)%m=t%until(\s->s==m#s)(m#)
s%m=(m,s)
```
[Try it online!](https://tio.run/##nZhRb5swEMff8yksui4GkvUdlTxMWqVJkyate@s6eqZug0ZChB21D2hfPbNJSKDBd@6iRgn5//y37zgflCWoP7Isd7v6o0plKVdB8OFJab5hdXin7icbnic6bPLF9GGa6kv2S80Xd7pZJvp6rmZ5mi7vrfjbisVjw8tZZfjr@YbpGa9nWbLdH6TbyxKMb/2pTO6sSc1UHJdMNdViGk/vw8nqQqXmp6ei1LLmD@tKfzHLeVAhXzEVTvg0mhrny5WZaLvWRcmti0pTM84gF@FEGY2vZircraBYsyRhX78zboztUcoeqwkzr81W3@r625oFtxpqXayfmZZKq6BV7dcf8lm@sgCC9v2z3soxSQTsBko1qnXSWy1rtTHHrO/4VuQQi9CuRowPPuqOJXW6IHQQOUHkQHrkFOGOsumiGA@y6YLAZGSBDRlkQwbZkEE2eJAGyMJYRKGzFAYIeDDCx8cHEn5OXlYAzmocuIFA6yEiCqLVScCuBoQHJdzRdRghk@MhB6x29gHlFJKf0nvWStyrzCL7QuR@EzmfO4oB3aCdTgMU4Qz/oAsKAACa8XAR7jzzrEHTcZBx1bmEzhzbHhneLrPe9I5NCHSPwU9pj8G3O5HxHuTFuM@KwQxjshe3F5xjk3Etv8UH8JEeuYLhKY8ztHgPo5GKijO0ZFD1uDZXQQ31saLf5wLff0cGvCBkp/cgTwrcJwbQ5nyQkRskIC4lR8DDA1kn3jKgwbtfA8MCcgCC0ikDtOucRelCCJkcD/0XzYo@7A4vOtyd@NMDWGB3doaPuWhEr16drWzA@nL@jl4RjgwS7x8l/neuQVZd/Xk4lScH/qDwXrAA8Y6UCGelAHYPdhABVykZ3zUHjD7VZ37CAxQDx/GreGTfxH9AHQNekCdFtJMB7bcVxtyFP09kK4vNH0RhhKVrCIEf5YsRGRviHilz@Yt3DBBnM5ye6twU60It5WP3VGcyOZklCTOUfeQzX/S@fa6q0n7uHxed8FoypWtmZ2gYr@VHcxSyNGWSpUbU23ptB1i10ktZvxRKjjxo4lwtqxfWDo5jFrC/7Cqw34y/Pb5i8nUjc23W3P68x2UYtjbHeXb/AA "Haskell – 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 -> 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)
```
---
# [GolfScript](http://www.golfscript.com/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>{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!](https://tio.run/##nZhtb5swEMff8ykstkg8dFnTTZMGapdX@wR7V1foTEmLlicBkToZ8tUzmwQCqu/MhhIR/P/d@e44G5SX3XpVpkW@r04n@TiPn/gilN78@7cHefvInxp5N7uVBfd4waMyflw@lV7Mm7yR@aqJ8iNX7JdZI2N@p2jeHLZVvm7dhLyJiiOP5Vwhcv51pjxJf8k33OfxppG@lpbz5YYtPtbz5b3kcSP5TrmOdkc9Qexrdbls@bod8aI0juVNcyM9Hqf3@hw3s1bSdpuj6/5oTtEGqvQ1dj6wKiurpMhesjd1kW/zKod1UlaQ/o5Y9rbP0ip7PkNlVbAW1L8UvMq3A3Szr/6wfMXKQ5pmZXnD0gLKVz2ygnztSIexqPMX64vOZ3vR@9VX/cV13jZcJX1aPFyjulcDjMnmfHL1PNlzxLjrdnYud9mRfXZ7j@5nN1TH/lCV2ixfOU10rUDsOLfRT1iXWewsol/FQZ0dV2VYVG0opasN1RC4TH81MSxgOy5c1rp4JxjGHTdphXeOEsSR43oQCl9PLwxmvWiKoRMFJYJIKTkF2jolZbNWdyEb0qm7iFENC6im06npdGo6nRpLR4lKTfxQBL75zo50sAHC6sFKiAk@7E4AzD018gNYy6p6BdQ9bkVa1RGAsCECyaVjKI22hBTQXjiHn5J6aiygWulIWEmgD0xD1rieLwgBX0@daFFJ2ZzmRRSkCgAWwGYvkDJ6SY2nfdEIyTxt5xNt64TYuRLzlP2aAcsGQNyoAUAsSqqgA8IOIBVXjAJUicJ2f@93AGO8LTsiTWj7qCCKGiZ4A17ssPYIE7wFcKkPxtgdqHhu2XPOxIrpAbAT2JIcEFMQQIoO@PZ40bB3CqB27161WWOBEasaamI7qgHthl4VpEia4lsCldBVpzTaEoaHBRRDEkkmuDzdJ6IjUqBvQAoOPVGLQduZN5kROAma6MueksFC/KOJ@K9ZRgU07pbjSaZAMJES04IUIKYWQJi7ANC3l4sChERqRPNfGMttfOdJ2CiB@eqelIH@Ui/8HQB2YgpCbQAjdEJHm/yKiTBVmCRUHwj8AK3MmIAJyCSGKs6YtVUH8yym0kR9nnfbbPivwukv "GolfScript – Try It Online")
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 39 [bytes](https://codegolf.meta.stackexchange.com/a/9429/43319 "When can APL characters be counted as 1 byte each?")[SBCS](https://github.com/abrudz/SBCS ".dyalog files using a single byte character set")
***Edit:*** now works with runs of `*` even after `_`
Full program. Prompts stdin for string and then for regex. Returns a list consisting of an empty list (by default, this prints as two spaces) for matches and an empty list (empty line) for non-matches.
```
(1⌽'$^','\*+' '_'⎕R'*' '()'⊢⍞~'+')⎕S⍬⊢⍞
```
[Try it online!](https://tio.run/##hZGxTsMwEEB3f0UHpLuz6cBHdGGAqhlYUKO7UKFKUR2ltFJFYASECGJhZWDmC5D4Gf9IuBQhSOuCB5/97tknn7nI@2crzv15Ex6fk4FOJwkMlpPZBfQQksl8PvWzYTlt93CYHB8BmTaEm6dLlTXovAb1@5UJd7dFgwfh4QP2xrAPp9bpsRTUGYHVJRKE@9dQv1yDA2pLhvrtizR6uOmtR2FYDLITMt/AIHKVkhP7wzgGJWpGqexw4zJztB7H78587kuDmUPvMHeoYUGVJ1cSda3F/5r2ohKyvx/eBbJlbBGJOMwRmG0ig6m1tmr/QyN1OiV/JHemRHgz9wk "APL (Dyalog Unicode) – Try It Online") (output made easier to read by converting all output to JSON)
`⍞` prompt stdin (for string)
`⊢` on that, apply the following:
`(`…`)⎕S⍬` PCRE **S**earch for the following, returning an empty list for each match
 `~'+'` remove all plusses from the following:
 `⍞` prompt stdin (for regex)
`⊢` on that, apply the following:
 `'\*+' '_'⎕R'*' '()'` PCRE **R**eplace runs of `*` with `*` and `_` with `()`
 `'$^',` prepend dollar sign and caret (indicating end and start)
 `1⌽` rotate the first character (`$`) to the end
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~295~~ 277 bytes
```
a←819⌶⎕A
E←{⍵{(⍺⊆⍨~⍵),⍺[⍸⍵]}(⍵∊'|+')∧0=+\-⌿'()'∘.=⍵}1↓¯1↓⊢
M←{c←⊃⌽⍵⋄c∊'0',a:0⋄c∊'_*':1⋄r s o←E⍵⋄o='|':∨/∇¨r s⋄∧/∇¨r s}
D←{c←⊃⌽⍵⋄c∊'0_':'0'⋄c=⍺:'_'⋄c∊a:'0'⋄c='*':1⌽∊')('(⍺∇¯1↓⍵)'+'⍵⋄r s o←E⍵⋄o='|':1⌽∊')('(⍺∇r)'|',⍺∇s⋄M r:1⌽∊')(('(⍺∇r)'+'s')|',⍺∇s⋄1⌽∊')('(⍺∇r)'+'s}
{M⊃D/(⌽⍵),⊂⍺}
```
[Try it online!](https://tio.run/##hVFLb9NAEL77V/g2u96U2uIClnJAtBI9REiUG1TWrvNqFcnIVQ8oaw6AgjFxBUJIXOFCbj0VoUoIKT9l/kiY9au2WojtzOw3883jy8oXs53hSzmLJpuNxMXHe959XP7E8y8PrH2Cc8wv5wzzK8wWmK9eEeQ9gs8w/0Xno4Ryl5hmoAVwTH@4ffF8B5d/gHHA9OudPqUTDxef1xfGYvbdGpi2IRnM3uDyt6n/8DY0PVzoSd@tUeCA7xGI7VM7Ivp@yYz6oMHHdLWL6bv1irIUpMkNTKy9f08IwKcxBtJmVz4EUKVkE4diLpURnzMoxFPrcn@SDwLKjrcudrMy5hTvlWez68COW6w2TcAp8A731m5ES6z5gMTt7bJSH91J9poIyWZsZOfndIEHj4mxvriLi0@EDp88JPv00cHhxrNdG99/s4FJoYprGq9XNkgFZEKwPPv6dRsukzrgQjnXBWCzHkjgxilyZQdVtCmsklIaQHGr2ywULBKMzQp3Ro05FzGZpncYzaIYSn9WH8iV0KqXq2RoxZ3WWtUipSBVKOqocMyv5nc0tJiBoE863NlKDRzzdOeHteJqrBk85JpN9AknR0@ox1wfc9HJOAYrPeJ6yiteDbcUVRluzjdmVS3@V1agGm4pahbkrb9dhcPReDI9PjFXPpQjNYVWUMFf "APL (Dyalog Unicode) – Try It Online")
-18 bytes thanks to @ngn.
This is a proof of concept that we can do a "simple regex matching" without any backtracking, thus avoiding possible infinite loops due to `_*` or `r**`. This is also a showcase that APL is a general-purpose programming language.
The anonymous function at the last line does the regex matching; use it as `(regex) f (input string)`. The return value is 1 if the match is successful, 0 otherwise.
### Concept
Given a simple regex `R` and the first character `c` of input string, we can construct (or *derive*) another simple regex `R'` that matches exactly the strings `s` where the original `R` matches `c+s`.
$$
\forall R \in \text{simple regex}, c \in \text{[a-z]}, s \in \text{[a-z]\*}, \\
\exists R' \in \text{simple regex}, R' =\sim s \iff R =\sim c+s
$$
Combine this with a tester which checks if `r` matches an empty string (epsilon), and we get a fully working simple regex matcher: given a regex \$ R\_0 \$ and string \$ s = c\_1 c\_2 \cdots c\_n \$, sequentially derive \$ R\_0, c\_1 \rightarrow R\_1, c\_2 \rightarrow R\_2 \cdots \rightarrow R\_n \$ and then test if \$ R\_n \$ matches epsilon.
My code uses the following algorithm for testing epsilon match (`MatchEps`) and computing `R'` from `R` and `c` (`Derive`).
```
T = True, F = False
0 = null regex (never matches)
_ = "empty string" regex
a = single-char regex
r, s = any (sub-)regex
MatchEps :: regex -> bool
MatchEps 0 = F    # Null regex can't match empty string
MatchEps _ = T    # Empty-string regex trivially matches empty string
MatchEps a = F    # Single-char can't match
MatchEps r* = T   # Kleene matches as zero iteration
MatchEps (r|s) = MatchEps r or MatchEps s
MatchEps (r+s) = MatchEps r and MatchEps s
Derive :: char -> regex -> regex
# No matching string at all
Derive c 0 = 0
# _ can't match any string that starts with c
Derive c _ = 0
# Single-char regex only matches itself followed by empty string
Derive c a = if c == 'a' then _ else 0
# r* matches either _ or (r+r*);
# _ can't start with c, so it must be first `r` of (r+r*) that starts with c
Derive c r* = ([Derive c r]+r*)
# r or s; simply derive from r or derive from s
Derive c (r|s) = ([Derive c r]|[Derive c s])
# r followed by s; it matters if r can match _
Derive c (r+s) =
  # if r matches _, either [r starts with c] or [r matches _ and s starts with c]
  if MatchEps r then (([Derive c r]+s)|[Derive c s])
  # otherwise, r always starts with c
  else ([Derive c r]+s)
```
### Ungolfed, with comments
```
⍝ Unwrap single layer of (...) and extract (r, s, op) from (r|s) or (r+s)
ExtractRS←{⍵{(⍺⊆⍨~⍵),⍺[⍸⍵]}(⍵∊'|+')∧0=+\-⌿'()'∘.=⍵}1↓¯1↓⊢
  ⍝ 1↓¯1↓⊢    Drop the outermost ()
  ⍝ {...}     Pass the result to the function as ⍵...
  ⍝   +\-⌿'()'∘.=⍵    Compute the layers of nested ()s
  ⍝   (⍵∊'|+')∧0=     Locate the operator (`|` or `+`) as bool vector
  ⍝   ⍵{...}          Pass to inner function again ⍵ as ⍺, above as ⍵
  ⍝     ⍺[⍸⍵]     Extract the operator
  ⍝     (⍺⊆⍨~⍵),  Prepend the left and right regexes
⍝ Tests if the given regex matches an empty string (epsilon, eps)
MatchEps←{
    c←⊃⌽⍵                 ⍝ Classify the regex by last char
    c∊'0',819⌶⎕A:0        ⍝ 0(no match) or lowercase: false
    c∊'_*':1              ⍝ _(empty) or Kleene: true
    r s op←ExtractRS ⍵    ⍝ The rest is (r|s) or (r+s); extract it
    op='|': ∨/∇¨r s       ⍝ (r|s): r =~ eps or s =~ eps
    ∧/∇¨r s               ⍝ (r+s): r =~ eps and s =~ eps
}
⍝ Derives regex `R'` from original regex `R` and first char `c`
Derive←{
    c←⊃⌽⍵             ⍝ Classify the regex by last char
    c∊'0_':,'0'       ⍝ 0 or _ doesn't start with any c
    c=⍺:,'_'          ⍝ Single char that matches
    c∊819⌶⎕A:'0'      ⍝ Single char that doesn't match
    c='*': '(',(⍺∇¯1↓⍵),'+',⍵,')'    ⍝ One char from Kleene: (R*)' = (R'+R*)
    r s op←ExtractRS ⍵               ⍝ Extract (r|s) or (r+s)
    op='|': '(',(⍺∇r),'|',(⍺∇s),')'  ⍝ (r|s): one char from either branch
    MatchEps r: '((',(⍺∇r),'+',s,')|',(⍺∇s),')'   ⍝ (r+s) and r =~ eps: ((r'+s)|s')
    '(',(⍺∇r),'+',s,')'                           ⍝ (r+s) but not r =~ eps: (r'+s)
}
⍝ Main function: Fold the string by Derive with initial regex,
⍝                and then test if the result matches eps
f←{MatchEps⊃Derive/(⌽⍵),⊂⍺}
```
### Final note
This is not an original idea of mine; it is part of [a series of exercises on a theorem proving textbook](https://softwarefoundations.cis.upenn.edu/lf-current/IndProp.html#lab245). I can claim that the algorithm is proven to work (because I did complete the correctness proofs), though I can't open the entire proof to public.
[Answer]
# [Python 3](https://docs.python.org/3/), 69 bytes
```
lambda r,s:re.match(re.sub('(?<=[_*])\*+|[_+]','',r)+'$',s)
import re
```
[Try it online!](https://tio.run/##nZDNasMwEITvfootFFYrmfTQW2jIKxR6TIJZOXIjkC0jyYSC391V/koCSQ7VYTWHmW@l6X/SznfvU7NYT45bvWUIZZwHM2s51TuRRRy0QLH8WKwquaG1VOOqUhssEctACl@xjFTYtvchQTBTMHFwKcICVpui8QEs2A5EdgPyYeijOk591hppXkA@5/CM@950W9HkxYLHipSWlK2W6BqpmY9E5keAzifQ3rt7JCrubKuV8Eo4JfI10OhJhew8LKm98wH/kxoexFhKeXo@3v7rr6rcjH5aTpURo@D8KSnpTkNXVfMzDo@a5Dn@rMKLL0NrPFRomwvuxO6D7ZLAT47RbIGdg2Riii9IhXHR3Ji@fGvSznbfsDddgn3wWc7fkKZf "Python 3 – Try It Online")
Simple - just convert it to ordinary regex, using ordinary regex!
[Answer]
# JavaScript (ES6), 45 bytes
Takes input as `(regex)(string)`. Returns a Boolean value.
Applies the straightforward method of removing `[_+]` from the simple regex to turn it into a standard regex.
```
r=>s=>!!s.match(`^${r.replace(/[_+]/g,"")}$`)
```
[Try it online!](https://tio.run/##fY9BDoIwEEX3ngIbFjMU4QRwEYIwrYCaSkkLbsSzI2A3YnQ1P5l5L3@udCcrzaXrD60@VVOdTCZJbZLu9za6US/PUB79h4lM1SmSFcRZwfO4CRnDp1/iJHVrtaoipRvIGAkWekwQy2e4A@slqVcDA@ICGYJFxN0nsdzTCq3pzbvsZLTuad5trEBjgVwEP9RSK20WdAmD2dKSg@agOMxjwFEjN7PjT0tXx5WTXz@OAgOHTy8 "JavaScript (Node.js) – Try It Online")
Or [43 bytes](https://tio.run/##fY9BDoIwEEX3ngIaFjMU4QR4EaIyrYCaSkmrbsSz14LdGNRkkvnJ5L38OdOdrDSn4bru9aFxbelMubF@8gtd5RHqXfIwuWkGRbKBotrzbdFljOEzqdFJ3VutmlzpDipGgmURE8S2Hh7ARuUmiuMWGBAXyBAsIq4@mYmgGZvT2xBy0NF8J39beIHGPXKR/pBLrbSZ4CnczJKXHDQHxcGvG44aufGWP01DpVBQfvl0FJgGgXsB) by returning either `null` or an object.
[Answer]
# [R](https://www.r-project.org/), ~~55~~ 75 bytes
```
function(x,y)grepl(paste0("^",gsub("([+_]|(?<=\\*))\\**","",x,pe=T),"$"),y)
```
[Try it online!](https://tio.run/##LYtBCsIwEEX3HmNwMZPMwgNYvIQ7qyUT2iKEpqQNVOjd40Q7i3mfz3@pDE0Z8uTXd5xw4w@NqZ8Dzm5Z@wvCC3hcsiDgw3bPHW/Xpm0NkT4DDMAbz31zJ4YzkNpl0Km3GC0Gi4pMeySbiAjYI/gYYk5q1nDQJSA6VbEz9XZ0Vmo4HF05J1Ih8uevUqt8AQ "R – Try It Online")
A function that takes a simple regex `x` and a vector of strings `y` and returns a vector of logical values the same length as `y` indicating whether `x` matches. 
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), ~~38~~ 35 bytes
```
*1A`
1G`
^
a`
_
()
\*+
*
"$-5"~`\+
```
[Try it online!](https://tio.run/##K0otycxLNPz/X8vQMYHL0D2BK44rMYErnktDkytGS5tLi0tJRddUqS4hRpvr/3@NZG2NfG2NHG0NIFWqWZOvqV2kqanJlZyfk19aBAA "Retina – Try It Online") Takes the simple regex on the first line and the string to match on the second. Explanation:
```
*1A`
```
Delete the first line, but don't actually change the working string. The string to match still gets stored in the history, which allows us to refer to it later.
```
1G`
```
Keep only the first line.
```
^
a`
```
Prefix the `a` modifier to anchor the pattern to the whole string.
```
_
()
```
Turn the `_`s into `()`s to match an empty string that can be "repeated" with `*`.
```
\*+
*
```
Reduces runs of `*` to a single `*`.
```
\+
```
Delete any `+`s.
```
"$-5"~`
```
Execute that as a stage, using the history as the working string.
[Answer]
# Java 8, 55 bytes
```
r->s->s.matches(r.replaceAll("\\+|(_|(\\*))\\**","$2"))
```
[Try it online.](https://tio.run/##lVKxTsMwEN37FacTUu04zcBYoBILG2LoSFB1dp2S4iaR4xSqpt8enNRVhSgSlRz7fO/53js7a9rSZL386JShuoZnyov9CKB25HIFa48mjctNkjWFcnlZJE8huJ87mxer@F@cF7nWys1mkMFDZyez2o9kQ06965rZxOrKkNKPxjBMU9GyRcvSNOLcTxHGeHOLnHd3I2@saqTxxoK/bZkvYeM9s6PS6xsQ7/0DOF07hiQxBmQkJEd@NwBZaQPbV7EwhUJ/wun4Hr0c@U/2az/JYzSERD1EPn/gQ62TDGPULriQEfdyvmqQCqASrBTMCOaXhrclF5bznomqNKXFa9iNvaKPo@ljA@qXZ2oljy74XUT9pQPixeziZ5pkFAB/R/JvjAJ2GJ3/ruH1Bmrow@qV/orh3FV4y/mudnqTlI1LKg85U7AxjoUnCEwRqFhCiiiG431mCiiyhKrK7NiQ5GHTlww2Dt03)
Removes all `+`; all `_` with zero or more trailing `*`; and changes all sequences of more than one subsequent `*` with a single `*`. Then it check if the String matches this modified regex. Note that in Java, the [`String#matches`](https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#matches-java.lang.String-) method implicitly adds a leading and trailing `^...$` to check the entire String.
[Answer]
# [PHP](https://php.net/), ~~983~~ ~~976~~ ~~954~~ ~~930~~ ~~910~~ ~~892~~ 838 bytes
```
<?php list(,$s,$i)=$argv;$p=0;$u=[2,[3,[2,[1,'('],$o=[2,[4,[2,&$u,[1,'|+']]],&$u],[1,')']],[1,'_'.join(range('a','z'))]],[5,[1,'*']]];m($o,$a);$s=$i;$p=0;echo m(o($a))&&$p==strlen($s);function m($m,&$a=[]){global$p,$s;$r=$p;$n=array_shift($m);foreach($m as$t){$b=[];if($n==1)if(($c=$s[$p]??0)&&strpos($t,$c)!==!1){$a[]=$c;$p++;return 1;}if($n==2){if(!m($t,$b)){$p=$r;return!1;}$a[]=$b;}if($n==3){if(m($t,$b)){$a[]=$b;return 1;}}if($n==4){k:$b=[];$r=$p;if(!m($t,$b)){$p=$r;return 1;}$a[]=$b;goto k;}if($n==5){if(m($t,$b))$a[]=$b;else{$a[]=[];$p=$r;}return 1;}if($n==6)return 1;}return $n==2?:$p!=$p=$r;}function o($a){$e=$b=u($a[1]);if($a[0]){$e=[2];foreach($a[0]as$u){$e[]=u($u[0]);$e[0]=$u[1][0]=='+'?2:3;}$e[]=$b;}return$e;}function u($u){$w=$u[0][0];$v=$w[0][0];$t=$v!='('?($v=='_'?[6,0]:[1,$v]):o($w[1]);return$u[1][0]==[]?$t:[4,$t];}
```
[Try it online!](https://tio.run/##dVPbjpswEP0VkEbBLqhKspcH3BEfgqzIQSShS7BlTLJtNt9Ox4ZcqqoSoLmcM2fGY8zBjOOPwhxM1Da9Yxn0GTQcQdn9SYDBpYABy3VWvmT@u8oSlsgMdIi9@tgChhD/ShMppXdl8Dm5wdgk33/qpmNWdfuaJSrJkt8J5z77FgDfPFEcGegMFBfQIzSTdl0ddHRkmlGcLxYUw97Ztu4Y9Fzshq5yje4IAUcSVlhKftm3eqtaMDSKAItgBHSorFW/Nv2h2TnCElXbWlUHsiPVg@MX2BJZNDtGYFxxMhhUCH0JRhbFksRJ2Oiegcug4jFivCKWKiVCRc2mqbC1G2wXrcR1LrPmF7LiY@BsOcENgp1xMeEm@vZOeAmEJ/ycf1S@IV/55SOfep5m/L9Q9CS0105HH3e9t7/1bqi67etJ25cPpa7/DPfOH6HZCjMXOZgYZ9Z9Q2GDF6ipPA5klyvJw2mrcilDolzLx1Z8lPYy@Ay1QYzB4wR5S2pxILo3MEmTYp2/0ID1fJJTK1A/aXs2FTpjKEKPgBPC@WY7hFOMdK0LRnGk61qU79lS5nQ14SR5Tr2fQ79z7bt6KQtwOf0F4KS4juP4mVapTlt62fC14akdPyvd6sH@AQ "PHP – Try It Online")
## Ungolfed
```
<?php
list($dummy,$string,$user_test)=$argv;
$pointer = 0;
//production rules
$unit = [];
$char = ['char','_abcdefghijklmnopqrstuvwxyz'];
$separator = ['char','|+'];
$unit_and_separator = ['and',&$unit,$separator];
$operators_list = ['list',$unit_and_separator];
$operators = ['and',$operators_list,&$unit];
$open_bracket = ['char','('];
$close_bracket = ['char',')'];
$brackets = ['and',$open_bracket,$operators,$close_bracket];
$atom = ['or',$brackets,$char];
$star = ['opt',['char','*']];
$unit = ['and',$atom,$star];
$ast = [];
match($operators, $ast);
$user_regex = buildoperators($ast);
$user_ast = [];
$string = $user_test;
$pointer = 0;
// answer here 1=matched blank=not matched
echo match($user_regex, $user_ast)&&($pointer==strlen($string));
// recursive descent parser 
function match($test_match, &$ast) {
    global $pointer,$string;
    $original_pointer = $pointer;
    foreach (array_slice($test_match,1) as $test) {
        switch ($test_match[0]) {
            case 'and':
                $sub_match = [];
                $pass = match($test,$sub_match);
                if (!$pass) {$pointer = $original_pointer;return false;}
                $ast[] = $sub_match;
                break;
            case 'or':
                $sub_match = [];
                $pass = match($test, $sub_match);
                if ($pass) {
                    $ast[] = $sub_match;
                    return true;
                }
                break;
            case 'list':
                do {
                    $sub_match = [];
                    $original_pointer=$pointer;
                    $pass = match($test, $sub_match);
                    if (!$pass) {
                        $pointer = $original_pointer;
                        return true;
                    }
                    $ast[] = $sub_match;
                } while (true);
                break;
            case 'char':
                $char = substr($string,$pointer,1);
                if ($char && @strpos($test,$char)!==false) {
                    $ast[]=substr($string,$pointer,1);
                    $pointer++;
                    return true;
                }
                break;
            case 'emptystring':
                return true;
                break;
            case 'opt':
                $pass = match($test, $sub_match);
                if ($pass) {$ast[] = $sub_match;} else {$ast[] = []; $pointer = $original_pointer;}
                return true;
                break;
        }
    }
    if ($test_match[0] == 'and') {
        return true;
    } else {
        $pointer = $original_pointer;
        return false;
    }
}
// build user production rules
function buildoperators($ast) {
    if ($ast[0]) {  
        $engine = ['and'];
        foreach ($ast[0] as $unit_and_separator) {
            $engine[] = buildunit($unit_and_separator[0]);
            switch ($unit_and_separator[1][0]) {
                case '+':
                    $engine[0]='and';
                    break;
                case '|':
                    $engine[0]='or';
                    break;
            }
        }
        $engine[] = buildunit($ast[1]);
    } else {
        $engine = buildunit($ast[1]);
    }
    return $engine;
}
function buildunit($unit) {
    $star = !empty($unit[1][0]);
    if ($star) {
        return ['list',buildatom($unit[0][0])];
    } else {
        return buildatom($unit[0][0]);
    }
}
function buildatom($atom) {
    if ($atom[0][0]=='(') {
        return buildoperators($atom[1]);
    } elseif ($atom[0][0]=='_') {
        return ['emptystring',''];
    } else {
        return ['char',$atom[0][0]];
    }
}
```
[Answer]
# [Perl 5](https://www.perl.org/), 34 + `-p` flag = 35 bytes
Full program. Takes the simple regex pattern, followed by string to match against, from stdin as two separate lines, then loops and does it again, until EOF is encountered. Prints `1` for a match or nothing for a non-match (with no newline in either case).
@ankh-morpork [has pointed out](https://codegolf.stackexchange.com/questions/197061/check-if-simple-regex-matches-string/197828#comment470601_197168) that technically, given the question's description of simple regexes, any number of `*` in a row makes a valid simple regex. @Bubbler [has pointed out](https://codegolf.stackexchange.com/questions/197061/check-if-simple-regex-matches-string/197828#comment470621_197061) that `_*` also needs to work (and be equivalent to `_`). The other answers haven't taken these things into account yet, but I will do so:
```
s/[_+]/()/g;s/\*+/*/g;$_=<>=~/^$_/
```
[Try it online!](https://tio.run/##K0gtyjH9/79YPzpeO1ZfQ1M/3bpYP0ZLW18LyFKJt7Wxs63Tj1OJ1///X0MjWVsjX1tDIwdMldbEa2lqamoXgYhCLS0tTa7k/Jz80qLCQq5/@QUlmfl5xf91CwA "Perl 5 – Try It Online")
To allow simple regexes such as `(_***+a)` to work, `_` is changed to `()` instead of . For golf reasons, `+` is also changed to `()`, although changing it to  would work.
This solution exploits the fact that valid input won't contain newlines, input can be assumed to be valid, and both the implicit `<>` (from `-p`) and the explicit `<>` include the terminating newline read from stdin, thus `$` doesn't need to be added at the end of the regex (as both the pattern and the string ), only `^` needs to be inserted at the beginning.
---
## [Perl 5](https://www.perl.org/), 20 + `-p` flag = 21 bytes (looser, obsolete interpretation of question)
```
y/_+//d;$_=<>=~/^$_/
```
[Try it online!](https://tio.run/##K0gtyjH9/79SP15bXz/FWiXe1sbOtk4/TiVe//9/jWRtjXxtDY0cMFVaE6@pqaldBCS4kvNz8kuLuP7lF5Rk5ucV/9ctAAA "Perl 5 – Try It Online")
Like most of the other solutions, deletes the `_` and `+` characters to turn the simple regex into a standard regex. This means that the simple regex `(_*+a)` will not work, as it becomes `(*a)` after the deletion. Anything containing `**` won't work either; in standard regex, an already-quantified expression cannot be quantified again.
[Answer]
# Perl 5, 47 + `-alp` flag = 50 bytes
```
$_=$F[0];s/[_+]/()/g;s/\*+/*/g;$_=$F[1]=~/^$_$/
```
[Try it online!](https://tio.run/##hY69DsIwDIT3PkWHDI4tFBiYUFdeopTIjiqEFJEqpVvFoxPMnwRTl7v7dDfc0Oe4LcX4xuzbdbcbXeupc2DdSfMByaGmd73pmps7Gm9cKR4RK2ASW7NUADx7S4JKvyDMf8zPbSBIBBBfNmllLWWVOqSY8kI/LQ1yr7dmsfgx/SDfyBKqexqu53QZy4rj8AA "Perl 5 – Try It Online")
---
# Perl 5, 41 + `-alp` flag = 44 bytes
Obsolete: it not supports `_***`-like regexes
```
$_=eval'$F[1]=~/^'.($F[0]=~y/_+//rd).'$/'
```
[Try it online!](https://tio.run/##hY6xCgIxEET7@4orAtnc4kULy2v9CdGwG1MIwYScJwjipxtXUdDqmp15zMBODiWua1VuCBeKWm22q91wt3vdg/il@Kt1aG05mF4rq2sFQjYtcQNAN2eQO6FfYKI/plfXIyQEiG@ZJDIGi5zWp5jKTD7NFUpo5B@b7iOygb@W2DePlM/HdBrrgmJ@Ag "Perl 5 – Try It Online")
[Answer]
# [C# (Visual C# Interactive Compiler)](http://www.mono-project.com/docs/about-mono/releases/5.0.0/#csc), 522 bytes
```
a=>b=>{int y=0,e=a.Length,k=0,o,q;var z=new int[e];for(;k<e;k++)if(a[k]<41){for(o=q=1;o>0;q++)o+=a[q+k]<41?1:a[q+k]>41?0:-1;z[k+--q]=k+1;z[k]=k+q+2;}void t(string s,int j){for(;j<e;){var l=a[j++];var w=j<e&&a[j]==42;if(j>1&&a[j-2]<41)for(int r=j,d=0;r<z[j-2]-1;)if(a[r++]>123&z.Take(r).Skip(j-2).Count(x=>x>0)%2>0)t(s,r);if(l>96&l<124)do{if(w)t(s,j+1);if(s==""||s[0]!=l)return;s=s[1..];}while(w);if(l==42&&a[j-2]==41||l<41&z[j-1]<=e&&a[z[j-1]-1]==42)t(s,z[j-1]);j=l>123?a.IndexOf(')',j)+1:j;}y=s==""?1:y;}t(b,0);return y;}
```
Saved 6 bytes thanks to ceilingcat
[Try it online!](https://tio.run/##bVPbjpswEH1evoIiNeuJCYJ0ValxzD5UqlRppZXaSn1AdGWIk3ApNIZsbvDt6dikaVQVJWY8Z86ZMwbSZpI22fnTtkrnTauyauXexotDJX5maRgu@VnwMOHhKata@8B9V3LhPclq1a7dAre1u2GvQtlHXsmdjUWRjNmyVoQVc8kKSiFbEhEV8fwhgJMGar7hAatDn20QrSkX0YYa/DGYDXGIsT@bBOwYFXQy2cS8oGajgw2dsv61zhZ2Swa7duNqd/mgz3JsDCdtqkTtnNLYONxxBEYjzMScP0wZ@srDwCQmU2NPs7WQ4rm74D5T86PB0MgwhUKtMJi@Gx29b6KQRIH3tch@ESwC72O9rVqy5@E@9OHtFBf05yrQjcrww/tROQ@mD7CoT5jYGTCngYEbzh2n65rIj9/wEpRst6piDW@iwPNi1u/WWSmRY6S0@T@uMQ66rkTzI201iOfcjDhs8KeLTashAyznpZ7gUXifq4XcPy/JPdy7OdBglrP@wI0VfBAH1rckcX1ggxsbE2dm6YNsZdPa3MbnHcUn6444RNAEHPeScUTi9OAagIjuBWgyvkExcoReEhOZNbnEw0YIg4sbnZSSmhJSmtsWNQGowuWvbFqXtdI0HWzVlSm6BMb/dL@0uTRNr7Uv4/G408PgHeB/JHF1qr1ZPbPwnZEiXRN9METJldy7Nr6VDeC3YE4KbDyj7ypr5VNWSeJ80TUz@@T3qGQIwKy7Wxmka/KgguRbNtKQG2gu4q69HHqC/hJAC/W3zTDRnwmOiH/o0oUE64e@LAvPWOc7ATjKkLxeFmZMhR7zNw "C# (Visual C# Interactive Compiler) – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt) [`-¡`](https://codegolf.meta.stackexchange.com/a/14339/), 13 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
è^+'$iVr"_|%+
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&flags=LaE&code=6F4rJyRpVnIiX3wlKw&input=ImNvbG91ciIKIihjKyhvKyhsKygobyt1KXxvKStyKSkpIg)
```
true
```
]