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!
-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. 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.
_*(|)? \$\endgroup\$*in a row results in a valid simple regex; for example,qa***zshould matchqzandqaaz. Is this the definition we should stick to? If so, 8+ answers will need to be edited, as they are currently incorrect. \$\endgroup\$_*is also a valid "simple regex" that matches only an empty string. Deleting_would leave single*, which is a grammar error in most regex flavors (if not all). \$\endgroup\$