0
\$\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\$
  • 1
    \$\begingroup\$ @Abigail You right, my typo. Edited post \$\endgroup\$ – nonForgivingJesus Aug 10 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 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\$ – Peter Taylor Aug 11 at 7:48
  • \$\begingroup\$ Could you specify example program input and output? \$\endgroup\$ – Krzysztof Szewczyk Aug 12 at 17:57
  • \$\begingroup\$ @KrzysztofSzewczyk edited \$\endgroup\$ – nonForgivingJesus Aug 12 at 18:04
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\$
  • \$\begingroup\$ Reason for downvote? \$\endgroup\$ – Jo King Aug 11 at 0:20
  • \$\begingroup\$ Fails for this \$\endgroup\$ – wastl Aug 11 at 0:25
  • \$\begingroup\$ Oh, didn't see your comment. I'm not the downvoter. \$\endgroup\$ – wastl Aug 11 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 at 2:28
  • \$\begingroup\$ Well, rules say ., ^, $ and * should be special (with usual meaning), and everything else is literal. \$\endgroup\$ – wastl Aug 11 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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