The Practice of Programming

At 1998, Brian Kernighan, while working on the book "The Practice of Programming", wanted to demonstrate realisation of regular expression engine. But struggled to find small engine, that cod could fit in the book.

So Brian Kernighan asked Rob Pike to write one for him, and Rob did it gracefully. Here is original source:

    /* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
if (regexp[0] == '^')
return matchhere(regexp+1, text);
do {    /* must look even if string is empty */
if (matchhere(regexp, text))
return 1;
} while (*text++ != '\0');
return 0;
}

/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
{
if (regexp[0] == '\0')
return 1;
if (regexp[1] == '*')
return matchstar(regexp[0], regexp+2, text);
if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0'; if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text)) return matchhere(regexp+1, text+1); return 0; } /* matchstar: search for c*regexp at beginning of text */ int matchstar(int c, char *regexp, char *text) { do { /* a * matches zero or more instances */ if (matchhere(regexp, text)) return 1; } while (*text != '\0' && (*text++ == c || c == '.')); return 0; }  Rules • Write regex engine that supports the same operations, as Rob's: • Any char (as symbol) • . to match any char • ^ to match start of the string • $ to match end of the string
• * to match any count of char from zero
• Auxiliary code do not count (to accept input, for example)
• Make the shortest solution and beat Rob Pike!

Input

Two strings: one for regex, one for match.

Output

• True (in your language), if regex matches string
• False (in your language), if regex do not match string
• @Abigail You right, my typo. Edited post Commented Aug 10, 2019 at 19:01
• What is the range of any char? Is it any character apart from the special characters?
– Jo King
Commented Aug 11, 2019 at 3:19
• Related: Match strings with wildcards, Regular expression parser, Compile regexes. (Also note that this set of features falls short of truly being a regex engine: there are regular languages which it can't match). Commented Aug 11, 2019 at 7:48
• @KrzysztofSzewczyk edited Commented Aug 12, 2019 at 18:04
• What does Any char (as symbol) mean?
– Jo King
Commented Aug 12, 2019 at 22:34

Perl 6, 39 bytes

->\a{&{?/<{a}>/}}o{S:g/<-[.*$^]>/'$/'/}


Try it online!

Simply evaluates the input as a regex, adding quotes to avoid any special characters Perl 6 uses. This takes input curried, as f(regex)(string), though it could be a lot shorter if I can just return a regex object.

• Reason for downvote?
– Jo King
Commented Aug 11, 2019 at 0:20
• Fails for this Commented Aug 11, 2019 at 0:25
• Oh, didn't see your comment. I'm not the downvoter. Commented Aug 11, 2019 at 0:50
• Oh okay. I'm not sure what chars are valid as matching, since clearly some are not meant to be matched literally
– Jo King
Commented Aug 11, 2019 at 2:28
• Well, rules say ., ^, \$ and * should be special (with usual meaning), and everything else is literal. Commented Aug 11, 2019 at 2:59