title: Code Golf: Regex parser
body: <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>&gt; myregex easy easy Easy hard
  true
  false
  false
  
  &gt; myregex ab*a aa abba abab b
  true
  true
  false
  false
  
  &gt; myregex 0*1|10 1 10 0110 00001
  true
  true
  false
  true
  
  &gt; myregex 0*(1|1+0) 1 10 0110 00001
  true
  true
  true
  true
  
  &gt; 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>