Check if simple regex matches string

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 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.

Answer 1

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 (&) :: 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!

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, 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!

Answer 2

APL (Dyalog Unicode), 39 bytes^SBCS

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! (output made easier to read by converting all output to JSON)

⍞ prompt stdin (for string)

⊢ on that, apply the following:

(…)⎕S⍬ PCRE Search 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 Replace runs of * with * and _ with ()

 '$^', prepend dollar sign and caret (indicating end and start)

 1⌽ rotate the first character ($) to the end

Answer 3

APL (Dyalog Unicode), ²⁹⁵ 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!

^{-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.

Answer 4

Python 3, _⁵⁸ 56 bytes

lambda r,s:re.match(re.sub('[_+]','',r)+'$',s)
import re

Try it online!

Simple - just convert it to ordinary regex, using ordinary regex!

-2 bytes thanks to Deadcode

---

Note from author: invalid due to chained repeats and repeats of nothing being allowed. Working on it.

Answer 5

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!

Or 43 bytes by returning either null or an object.

Answer 6

Retina, 38 35 bytes

*1A`
1G`
^
a`
_
()
\*+
*
"$-5"~`\+

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 7

R, 55 75 bytes

function(x,y)grepl(paste0("^",gsub("([+_]|(?<=\\*))\\**","",x,pe=T),"$"),y)

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 8

Java 8, 55 bytes

r->s->s.matches(r.replaceAll("\\+|(_|(\\*))\\**","$2"))

Try it online.

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 method implicitly adds a leading and trailing ^...$ to check the entire String.

Answer 9

PHP, 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!

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 10

Perl 5, 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 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 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!

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, 20 + -p flag = 21 bytes (looser, obsolete interpretation of question)

y/_+//d;$_=<>=~/^$_/

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 11

C# (Visual C# Interactive Compiler), 535 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?-1:0;q--;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.Remove(0,1);}while(w);}if(l==42&&a[j-2]==41||l<41&z[j-1]-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;}

Try it online!

Inspired by @ankh-morpork's solution, this is another simple regex engine. Unfortunately, it is nowhere as terse as that solution.

Answer 12

Japt -¡, 13 bytes

è^+'$iVr"_|%+

Try it

true

Answer 13

Perl 5, 47 + -alp flag = 50 bytes

$_=$F[0];s/[_+]/()/g;s/\*+/*/g;$_=$F[1]=~/^$_$/

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!