8
\$\begingroup\$

This task is a classic programming task: Implement a regular expression parser. That is, write a program or function which takes a string describing a regular expression and a candidate string, and test whether the complete candidate string matches the regular expression. You may assume that the regular expression passed is valid.

If your programming language offers regular expression matching or string parsing, you are not allowed to use that. Also you are not allowed to use libraries other than the standard library of your programming language. Also forbidden is to access an external tool to do the work (e.g. accessing a web server, or calling another executable). In addition, use of reflection or any other functionality that allows the program to access its own source code, the names of individual identifiers or similar information is explicitly forbidden to prevent gaming the scoring rules (thanks to ais523 in the comments for making me aware of the latter possibility).

This is an atomic code golf contest, it's not the character count that has to be minimized, but a modified token count (for details, see below).

Input

The regular expression is not enclosed in slashes (/), any slashes appearing in the regular expression string are part of the regular expression itself (that is, the string /.*/ denotes not the regular expression .*, but the regular expression /.*/ which will match the string /abc/, but not the string abc).

Both the regular expression string and the candidate string will consist solely of ASCII characters in the range 32 (space) to 126 (tilde).

The regular expression syntax

Your program only needs to parse the following minimal regular expression syntax:

  • Anything except the letters ., *, |, (, ) and \ matches literally.
  • A backslash (\) followed by any of the above characters literally matches the second character.
  • A dot (.) matches any character.
  • The star (*) matches zero or more consecutive strings each matching the regular expression preceding it. It cannot appear at the beginning.
  • The pipe (|) matches either the regular expression before it, or the regular expression following it.
  • Parentheses ((, )) themselves don't match anything, but are used to group expressions (e.g. ab* matches abbbbb, while (ab)* matches abababab).

Output

Your program or function must give one of two results, one indicating that the complete candidate string matches, one indicating that it doesn't. How the output is given (function return variable, global variable setting, text output, program status code, ...) is up to you (and the capabilities of your chosen programming language). Explain how the output is to be interpreted.

Scoring

Of course, this being a code golf, the minimal score wins. The score is calculated as follows:

  • Start with score 0.

  • Comments and whitespace characters that are not part of a token are ignored.

Rationale: I don't want to penalize pretty formatting. The token exception covers both spaces inside string and character constants, and special cases like the Whitespace language where each single whitespace character constitutes a token (so writing a program in Whitespace won't give you a score of 0).

  • For any statement/declaration/etc. which makes available a standard library component to the code (like #include in C, use in Perl or import in Java), add 5 point per imported standard library package.

Rationale: I don't want to make the scoring dependent on how verbose the import syntax of a language is. Also, there shall be a slight (but not too strong) discourage of using library components (direct code is preferred, unless the library makes a big difference; however note the restrictions on library use outlines above). The "per standard library package" part is so that you cannot reduce your point by combining several imports by one (e.g. in Turbo Pascal, you could write uses dos, crt; instead of uses dos; uses crt;. With the rule as given, both would add 10 points. (Of course, both dos and crt would be pointless for the given task.)

  • For any string, add one more than the number of characters in the string (that is, the empty string gets 1 point, a one character string gets 2 points, etc.). If the language has single-token literals for other complex types (like lists, dictionaries, etc.), it is one point per character in the literal. (thanks to ais523 in the comments for telling me about such complex literals).

Rationale: This is mainly to prevent tricks like eval("long program code") which is four tokens. With this rule, doing such a trick actually penalizes your code, because you're back to character counting instead of token counting.

  • For any number, add as many points as the minimal number of bytes needed to represent the number as either signed or unsigned two's-complement number. That is, numbers from -128 to 255 (including both values) get 1 point, otherwise numbers in the range -32768 to 65535 get 2 points, otherwise numbers in the range -8388608 to 16777215 get 3 points, and so on.

Rationale: This is to prevent similar tricks in languages supporting arbitrary large numbers, where the whole program might be encoded in a number that is then reinterpreted as a string and passed to eval or an equivalent function.

  • Any token not covered in the list above gives 1 point.

Rationale: This is to avoid penalizing verbose languages (e.g. Pascal with begin/end vs. C with {/}), and especially to avoid giving esoteric languages (Golfscript!) an advantage just for having one-character tokens. Also, it allows meaningful variable names without being penalized.

Note: This challenge was posted in the sandbox

\$\endgroup\$
3
  • \$\begingroup\$ I can see a few ways to exploit the scoring rules here; not sure if they'd actually save score, but they might. (For example, use a very long identifier name, then find the longest identifier in the program, shift the bytes in it, and eval it.) One thing you should probably deal with is literals for structures other than strings and integers; some languages have, e.g., a list literal or an XML literal that's only a single token. \$\endgroup\$
    – user62131
    Jun 9, 2017 at 23:13
  • \$\begingroup\$ You say that "\" followed by a special character matches that character literally. Is there defined behavior for "\" followed by a non-special character? Or is that just invalid syntax? \$\endgroup\$ Jun 10, 2017 at 12:48
  • \$\begingroup\$ @Tutleman: You don't need to handle that case, and if you do, you can do whatever seems advantageous for your code. \$\endgroup\$
    – celtschk
    Jun 11, 2017 at 21:09

1 Answer 1

5
\$\begingroup\$

Python 3, 445* points

This is a fairly straightforward approach: it uses a basic recursive descent parser, and a regex engine implemented using Brzozowski derivatives (which I just learned about, and which I think are super elegant); it takes two strings as input via STDIN – first a string representing the regex in question, then a string containing the text to match, and prints True to STDOUT if the regex matches and False if it doesn't.

class Nil:nullable,derive = False,lambda *self: Nil
class Empty(Nil):nullable = True
class And:
    def __init__(self, first, second=None):self.first,self.second = first,second
    nullable = property(lambda self: self.first.nullable and self.second.nullable)
    def derive(self, c):
        dxy = And(self.first.derive(c), self.second)
        return Or(dxy, self.second.derive(c)) if self.first.nullable else dxy
class Or(And):nullable,derive = property(lambda self: self.first.nullable or self.second.nullable),lambda self, c: Or(self.first.derive(c), self.second.derive(c))    
class Star(And):nullable,derive = True,lambda self, c: And(self.first, Star(self.first)).derive(c)
class Plus(Star):nullable = False
class Char(Plus):derive = lambda self, c: Empty if self.first in 'µ'+c else Nil
expr = input()
index = len(expr)
peek = lambda: index and expr[-index] or ''
def advance():
    global index
    item = peek()
    index -= True
    return item
def regex():
    factor = Empty
    while peek() not in ')|':
        current = advance()
        base = Char(current)
        if current == '(':
            base = regex()
            advance()
        elif current == '\\':base = Char(advance())
        elif current == '.':base = Char('µ')
        while '' < peek() in '*+':
            base = (Star if peek() == '*' else Plus)(base)
            advance()
        factor = And(factor, base)
    return Or(factor, regex()) if peek() == '|' == advance() else factor
derivative = regex()
for c in input(): derivative = derivative.derive(c)
print(derivative.nullable)

Try it online!


* I'll be honest: I'm not totally sure if I've scored this correctly, because the scoring rules for this submission are at once both rather complex and also imprecise. Their goals are certainly admirable, but I think the range of possible situations they try to cover is too vast.

As an example of what I mean: "Tokens" aren't necessarily a consistently defined concept in many programming languages, and this challenge doesn't clarify. In Python, for instance, they're implementation-defined.

Similarly, and among other such things, the challenge doesn't count whitespace against a score unless it's part of a token, but CPython generates tokens for certain non-meaningful whitespace, which leads to a contradiction with the scoring rule's stated intent of "avoiding penalizing pretty formatting."

Consequently, this could actually be anywhere from 407-533 points.

\$\endgroup\$
1
  • \$\begingroup\$ + is not included in the question's regex subset \$\endgroup\$ Nov 16, 2019 at 21:57

Your Answer

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

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