StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POCode Golf: Regex parser
text
Body
copied!<h3>The goal</h3> <p>Today's Code Golf challenge is to create a regex parser in as few characters as possible.</p> <h3>The syntax</h3> <p>No, I'm not asking you to match Perl-style regular expressions. There's already a very reliable interpreter for those, after all! :-)</p> <p>Here's all you need to know about regex syntax for this challenge:</p> <ul> <li>A <em>term</em> is defined as a single literal character, or a regular expression within grouping parentheses <code>()</code>.</li> <li>The <code>*</code> (asterisk) character represents a <em>Kleene star operation</em> on the previous TERM. This means zero or more of the previous term, concatenated together.</li> <li>The <code>+</code> (plus) character represents a convenient shortcut: <code>a+</code> is equivalent to <code>aa*</code>, meaning one or more of the previous term.</li> <li>The <code>?</code> (question mark) character represents zero or one of the previous term.</li> <li>The <code>|</code> (pipe) character represents an alternation, meaning that the REGULAR EXPRESSIONS on either side can be used in the match.</li> <li>All other characters are assumed to be literal. You may assume that all other characters are within <code>[0-9A-Za-z]</code> (i.e., all English alphanumerics).</li> </ul> <p>Or, put another way: <code>*</code>/<code>+</code>/<code>?</code> have highest precedence, then concatenation, then alternation. Since alternation has lower precedence than concatenation, its use within a regex without parentheses causes it to be bound to the full regex on each side. <code>*</code> and <code>+</code> and <code>?</code>, on the other hand, would just apply to the immediately preceding term.</p> <h3>The challenge</h3> <p>Your challenge is to write a program that will compile or interpret a regular expression (as defined above) and then test a number of strings against it.</p> <p>I'm leaving input up to you. My recommendation would be that the regex should probably come first, and then any number of strings to be tested against it; but if you want to make it last, that's fine. If you want to put everything in command-line arguments or into stdin, or the regex in command-line and the strings in stdin, or whatever, that's fine. Just show a usage example or two.</p> <p>Output should be <code>true</code> or <code>false</code>, one per line, to reflect whether or not the regex matches.</p> <p><b>Notes:</b></p> <ul> <li>I shouldn't need to say this... but don't use any regex libraries in your language! You need to compile or interpret the pattern yourself. (<b>Edit:</b> You may use regex if it's required for splitting or joining strings. You just can't use it to directly solve the problem, e.g., converting the input regex into a language regex and using that.)</li> <li>The regular expression must COMPLETELY match the input string for this challenge. (Equivalently, if you're familiar with Perl-like regex, assume that start- and end-of-string anchoring is in place for all matches)</li> <li>For this challenge, all of the special characters <code>()*+?|</code> are not expected to occur literally. If one comes up in the input, it is safe to assume that no pattern can match the string in question.</li> <li>Input strings to test should be evaluated in a case-sensitive manner.</li> </ul> <h3>The examples</h3> <p>For the examples, I'm assuming everything is done in command-line arguments, regex first. (As I said above, input is up to you.) <code>myregex</code> here represents your invocation of the program.</p> <pre><code>> myregex easy easy Easy hard true false false > myregex ab*a aa abba abab b true true false false > myregex 0*1|10 1 10 0110 00001 true true false true > myregex 0*(1|1+0) 1 10 0110 00001 true true true true > myregex a?b+|(a+b|b+a?)+ abb babab aaa aabba a b true true false true false true </code></pre> <p><b>NOTE:</b> Sorry, forgot to make community wiki! :-(</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload