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*
matchesabbbbb
, while(ab)*
matchesabababab
).
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 orimport
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 ofuses dos; uses crt;
. With the rule as given, both would add 10 points. (Of course, bothdos
andcrt
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
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\$