1
\$\begingroup\$

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
\$\endgroup\$
7
  • 1
    \$\begingroup\$ @Abigail You right, my typo. Edited post \$\endgroup\$ Aug 10, 2019 at 19:01
  • \$\begingroup\$ What is the range of any char? Is it any character apart from the special characters? \$\endgroup\$
    – Jo King
    Aug 11, 2019 at 3:19
  • \$\begingroup\$ 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). \$\endgroup\$ Aug 11, 2019 at 7:48
  • \$\begingroup\$ Could you specify example program input and output? \$\endgroup\$ Aug 12, 2019 at 17:57
  • \$\begingroup\$ @KrzysztofSzewczyk edited \$\endgroup\$ Aug 12, 2019 at 18:04

1 Answer 1

1
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.