Convert Regexes

Question

Suppose you have existing regexes you wish to compile using one of the submissions to Compile Regexes.

In as few characters as possible, write a program that:

• accepts an existing regex as input, as either (a) one line from standard input; or (b) one argument from the command line; or (c) the contents of a textbox in a dialog box; then
• converts the regex into one that works with the compiler (see "Equivalent constructs"); then
• prints the new regex either (a) on standard output; or (b) in a dialog box.

Equivalent constructs

You can convert...

• ... the anchors ^ and $ to the empty string. If ^ is not at the beginning (and/or if $ is not at the end), prepend (and/or append) .*. (You may assume any ^ anchor is the first character of the regex and any $ anchor is the last character of the regex.)
• ... non-capturing groups to normal groups; replace (?:x) with (x).
• ... character classes; replace . with [0-9A-Za-z], \d with [0-9], and \D with [A-Za-z]. No character class will occur inside a bracket expression.
• ... bracket expressions to groups containing alternation. For example, [0-9A-FZ] can become (0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|Z), and [^0A-Za-z] can become (1|2|3|4|5|6|7|8|9).
• ... the plus operator: + to {1,}.

• ... braces (x is the nearest character or group to the left):

  • x{m} to m × x.
  • x{m,} to m × x followed by x*.

  • x{m,n} to m × x followed by either of:

    • (n-m) × x?
    • (n-m) × (|x then (n-m) × )

• ... the question mark operator: x? to (|x) or (x|).

Special rules

• You may assume all non-alphanumeric characters are metacharacters.
• Do not use general-purpose or Unicode algorithms to compress your code.
• Methods of input and output are implementation defined yet may not trivialize the solution.
• Using a special-purpose regex parsing library is prohibited. However, using one or more regexes as a tool for parsing the regex is OK (see below Scoring section).
• The input will never be longer than 1000 bytes.

Scoring

Generally, the score is the number of characters in your submission. However, you must double your score if you use a find-and-replace function and double it again if you use any regex or pattern matching function. When writing your program, carefully consider whether to use regex and/or pattern matching functions, as using one just once quadruples your score.

Test cases

Infinitely many valid outputs exist for each input case; thus, I have chosen a single example of possible output for each. The final test case is perhaps the trickiest.

Begins with "A"

 Input: ^A
Output: A(0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*

• Valid: Abra, Absol, Aerodactyl, Aipom, Alakazam
• Invalid: abra, absol, Bayleef, Beedrill

Contains "sex"

 Input: sex
Output: (0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*sex(0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*

• Valid: partsexpress, sextet, middlesex
• Invalid: partSEXpress, SEXtet, middleSEX

Any decimal integer

 Input: ^\d+$
Output: (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*

• Valid: 0, 7, 51, 370, 1040, 65536, 007, 051, 0000370, 001040, 065536
• Invalid: (the empty string), football, 10NIS

Decimal integer without leading zeroes

 Input: ^(0|[1-9]\d*)$
Output: (0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)

• Valid: 0, 7, 51, 370, 1040, 65536
• Invalid: 007, 051, 0000370, 001040, 065536, football, 10NIS

Lowercase Q without U word

 Input: ^[a-tv-z]*q[a-tv-z]*$
Output: (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|v|w|x|y|z)*q(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|v|w|x|y|z)*

• Valid: faqir, faqirs, qaid, qaids, qanat, qanats, qat, qats, qi, qindar, qindarka, qindars, qintar, qintars, qoph, qophs, qwerty, qwertys, sheqalim, sheqel, tranq, tranqs
• Invalid: Faqir, qAid, quid, liquefy

Ends in a vowel then three or more consonants

 Input: [AEIOUaeiou][^0-9AEIOUaeiou]{3,}$
Output: (0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*(A|E|I|O|U|a|e|i|o|u)(B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)(B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)(B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)(B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)*

• Valid: Bouncy, bouncy, erhythm
• Invalid: Noisy, noisy, Dodge, rhythm

Exception to I before E, except after C

 Input: ^\D*([^Cc][Ee][Ii]|[Cc][Ii][Ee])\D*$
Output: (A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*((0|1|2|3|4|5|6|7|8|9|A|B|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)(E|e)(I|i)|(C|c)(I|i)(E|e))(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*

• Valid (and incorrectly spelled): AIRFEILD, AIRfeild, eyepeice, reciept, veiwer, zeitgiest
• Valid (yet correctly spelled): forfeit, glacier, science, zeitgeist
• Invalid (and correctly spelled): AIRFIELD, AIRfield, eyepiece, receipt, viewer
• Invalid (yet incorrectly spelled): 6AIRFIELD, AIRFIELD0, forfiet, glaceir, sceince, zietgiest

U.S. amateur radio callsign

(Note that the FCC has reserved some of these (e.g. callsigns containing "SOS"), so not all of the matched callsigns could be legitimate callsigns used by U.S. amateur radio operators. 1x1 "special event" callsigns are not included.)

 Input: ^(?:[KNW]\d[A-Z]{2,3}|(?:A[A-L]|[KNW][A-Z])\d[A-Z]{1,2}|[KW][A-Z]\d[A-Z]{3})$
Output: ((K|N|W)(0|1|2|3|4|5|6|7|8|9)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(|(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z))|(A(A|B|C|D|E|F|G|H|I|J|K|L)|(K|N|W)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z))(0|1|2|3|4|5|6|7|8|9)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(|(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z))|(K|W)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(0|1|2|3|4|5|6|7|8|9)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z))

• Valid: W1AW, AB0C, AB2MH, NZ9WA, K9DOG, KL5CD, KA2DOG, KN0WCW
• Invalid: WWVB, AB00, AM8ER, NZ99A, L9DOG, KNOWCW, KN0WCWW, kn0wcw

Answer 1

perl, 1111 916 bytes

There is more golfing to do, but under 1000 bytes seemed like a good stopping point, especially as no one else has answered this question yet =)

@l=("A".."Z","a".."z");@h=(0..9,@l);sub g{join"|",@_}sub p{length$_[0]>1&&substr($_[0],0,1)ne"("?"($_[0])":$_[0]}sub e{$e=$_[0];for(split//,$_[1]){return if$i[$e++]ne$_}1}sub x{push@o,$l=p g @_}$w=c("^.*\$");sub N{++$n}sub I{$i[$n]}sub c{@i=split//,shift;$f=$t=0;shift@i,$f=1 if$i[0]eq"^";pop@i,$t=1 if$i[-1]eq"\$";@o=();for($n=0;$n<@i;N){if(e$n,"(?:"){push@o,"(";N;N}elsif(e$n,"."){x@h}elsif(e$n,"\\d"){x 0..9;N}elsif(e$n,"\\D"){x@l;N}elsif(e$n,"["){N;my($v,@c);$v=1,N if"^"eq I;while(I ne"]"){push@c,$i[$n+1]eq"-"?I..$i[$n+=2]:I;N}@c=grep{$d=$_;!grep{$_ eq$d}@c}@h if$v;x @c}elsif(e$n,"?"){splice@o,-1,1,"(|$l)"}elsif(e$n,"+"){$l=p$l;splice@o,-1,1,"$l$l*"}elsif(e$n,"{"){N;my($j,$k,$h);$j.=$i[$n++]until","eq I||"}"eq I;if(","eq I){$h=1;$k.=I until$i[N]eq"}"}$l=p$l;@r=$l x$j;push@r,defined$k?"(|$l)"x($k-$j):"$l*"if$h;splice@o,-1,1,@r}else{x I}}push@o,$w if!$t;join"",$f?@o:($w,@o)}while(<>){chomp;print c($_).$/}

And here's a still-pretty-obfuscated, but at-least-it's-indented version:

use strict;
use warnings;

my @let = ('A'..'Z','a'..'z');
my @chars = (0..9,@let);

sub g { join('|',@_) }
sub p { length $_[0] > 1 && substr($_[0],0,1) ne '(' ? "($_[0])" : $_[0] };

sub comp {
  my @i = split//,shift;
  my ($front_anchor, $tail_anchor);
  if($i[0] eq '^') { shift @i; $front_anchor=1 }
  if($i[-1] eq '$') { pop @i; $tail_anchor=1 }
  my @out;
  my $last;
  for(my $n=0;$n<@i;++$n) {
    if($i[$n] eq '(' && $i[$n+1] eq '?' && $i[$n+2] eq ':') {
      push @out, '(';
      $n+=2;
    } elsif($i[$n] eq '.') {
      $last = g @chars;
      push @out, p $last;
    } elsif($i[$n] eq '\\' && $i[$n+1] eq 'd') {
      $last = g 0..9;
      push @out, p $last;
      ++$n;
    } elsif($i[$n] eq '\\' && $i[$n+1] eq 'D') {
      $last = g @let;
      push @out, p $last;
      ++$n;
    } elsif($i[$n] eq '[') {
      ++$n;
      my $invert=0;
      if($i[$n] eq '^') {
        $invert=1;
        ++$n;
      }
      my @c;
      do {
        if($i[$n+1] eq '-') {
          push @c, $i[$n]..$i[$n+2];
          $n+=2;
        } else {
          push @c, $i[$n];
        }
        ++$n;
      } while($i[$n] ne ']');
      @c = grep { my $c=$_; !grep { $_ eq $c } @c } @chars if $invert;
      $last = g @c;
      push @out, p $last;
    } elsif($i[$n] eq '?') {
      $last = "(|$last)";
      splice @out, -1, 1, $last;
    } elsif($i[$n] eq '+') {
      $last = p $last;
      $last = "$last$last*";
      splice @out, -1, 1, $last;
    } elsif($i[$n] eq '{') {
      ++$n;
      my ($bm, $bn, $hc);
      $bm .= $i[$n++] until $i[$n] eq ',' || $i[$n] eq '}';
      if($i[$n] eq ',') {
        $hc=1;
        $bn .= $i[$n] until $i[++$n] eq '}';
      }
      my @r;
      push @r, p $last for 1..$bm;
      push @r, p($last).'*' if $hc && !defined $bn;
      if($hc && defined $bn) {
        my $y = $bn - $bm;
        push @r, '(|'.p($last).')' for 1..$y;
      }
      splice @out, -1, 1, @r;
      undef $last; #no nested quantifiers
    } else {
      $last = $i[$n];
      push @out, $last;
    }
  }
  @out = (comp('^.*$'),@out) unless $front_anchor;
  @out = (@out,comp('^.*$')) unless $tail_anchor;
  return wantarray?@out:join"",@out;
}

while(<>) {
  chomp;
  print comp($_)."\n";
}