17
\$\begingroup\$

In this task you have to write a program that reads a regular expression and generates another program that outputs whether an input string is accepted by that regular expression. The output must be a program written in the same language as your submission.

Input

The input is a regular expression r matching the following ABNF (the initial production rule is REGEX):

REGEX       = *( STAR / GROUP / LITERAL / ALTERNATIVE )
STAR        = REGEX '*'
GROUP       = '(' REGEX ')'
LITERAL     = ALPHA / DIGIT
ALTERNATIVE = REGEX '|' REGEX

If the input does not match this grammar, the behavior of your program is undefined.

Interpretation

Interprete the input as a regular expression, where * is the Kleene-star (meaning repeat left argument zero or more times), | is an alternative, ( and ) group and no operator at all concatenated. Grouping takes precedence over star, star takes precedence over concatenation, concatenation takes precedence over alternative.

A string is said to be accepted if the regex matches the whole string.

Output

The program's output is another program written in the same language as your submission that reads a string s in an implementation defined way at runtime, outputs whether r accepts s and then terminates. Output may be done in a user-defined way although there must be only two distinct outputs for accepted and rejected programs.

You may assume that the input of your output program is never longer than 216-1 Bytes.

Restrictions

Neither your submission nor any program generated by your submission may use builtin functionality or libraries that

  • match regexes
  • transform regular expressions
  • compile regular expressions
  • generate parsers from a grammar
  • simplify the problem in a way that your submission becomes trivial

Scoring

The score of your submission is the number of characters it. The submission with the lowest score wins.

Testcases

All testcases contain a regular expression, a set of accepted strings, a set of rejected strings and an example program in C99 which is a valid output of a (hyptothetical) C99 submission.

(empty regular expression)

Accepted strings

  1. (empty input)

Rejected strings

  1. foo
  2. bar
  3. baz
  4. quux

Example program

#include <stdio.h>

int main() {
    char input[65536];
    gets(input);

    return input[0] != 0;
}

(b|)(ab)*(a|) (a and b alternating)

accepted strings

  1. a
  2. ba
  3. abababababa
  4. abab

rejected strings

  1. afba
  2. foo
  3. babba

example program

#include <stdio.h>

int main() {
  char input[65536];
  int state = 0;

  for (;;) switch (state) {
    case 0: switch (getchar()) {
      case 'a': state = 1; break;
      case 'b': state = 2; break;
      case EOF: return 0;
      default:  return 1;
    } break;
    case 1: switch (getchar()) {
      case 'b': state = 2; break;
      case EOF: return 0;
      default:  return 1;
    } break;
    case 2: switch (getchar()) {
      case 'a': state = 1; break;
      case EOF: return 0;
      default:  return 1;
    } break;
}

(0|1(0|1)*)(|A(0|1)*1) (binary floating point numbers)

accepted strings

  1. 10110100
  2. 0
  3. 1A00001

rejected strings

  1. 011
  2. 10A
  3. 1A00
  4. 100A010
\$\endgroup\$
  • 1
    \$\begingroup\$ I presume that having a program like return (regex.match(stdin) is not null) is not allowed. \$\endgroup\$ – beary605 Aug 18 '12 at 23:25
  • 1
    \$\begingroup\$ You say that "The output must be a program written in the same language as the input", but the input is a regex. And the grammar you provide doesn't include the rule GROUP, which presumably defines literal brackets. \$\endgroup\$ – Peter Taylor Aug 19 '12 at 7:24
  • \$\begingroup\$ @Peter Sorry, I meant to write they same language as the submission. \$\endgroup\$ – FUZxxl Aug 19 '12 at 10:04
  • \$\begingroup\$ @beary605 Yeah, you're right. See the section Restrictions: Neither your submission nor any program generated by your submission may use builtin functionality or libraries that match regexes (...). \$\endgroup\$ – FUZxxl Aug 19 '12 at 10:13
  • \$\begingroup\$ I think your second example program is incorrect, it's missing a loop around the outer switch \$\endgroup\$ – Hasturkun Aug 21 '12 at 11:09
8
\$\begingroup\$

Ruby, 641 651 543 characters

H=Hash.new{|h,k|[k]}
d=[[i=0,0,[]]]
o=[?(]
L="t,u,v=d.pop;q,r,s=d.pop;o.pop<?|&&(H[r]<<=t)||(H[q]<<=t;H[r]<<=u);d<<[q,u,s+v]"
gets.chop.chars.map{|c|c==?*&&(q,r,s=d.pop;H[r]|=[q,i+=1];d<<=[r,i,s];next)
eval(L)while/[|)]/=~c ?o[-1]>?(:o[-1]==?.
/[|(]/=~c&&d<<[i+=1,i,o<<c&&[]]||c!=?)&&d<<[i+=1,i+1,["s==#{o<<?.;i}&&c=='#{c}'&&#{i+=1}"]]||o[-1]=?.}
eval(L)while o.size>1
H.map{H.map{|k,v|v.map{|v|H[k]|=H[v]}}}
t,u,v=d[0]
$><<"s=#{H[t]};gets.chop.chars.map{|c|s=s.map{|s|#{v*'||'}}-[!0];#{H.map{|k,v|"s&[#{k}]!=[]&&s|=#{v}"}*?;}};p s&[#{u}]!=[]"

This ruby version became quite long because of several corner cases in the regex parser (maybe I should try a different approach). It expects the regular expression on STDIN and outputs the corresponding ruby code for the matcher to STDOUT.

The program directly generates code for a NFA-ε which is then executed in the matcher.

Test case 1: (output includes additional newlines and indentation)

>>>

s=[0];
gets.chop.chars.map{|c|
  s=s.map{|s|}-[!0];
};
p s&[0]!=[]

Test case 2:

>>> (b|)(ab)*(a|)

s=[0, 1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
gets.chop.chars.map{|c|
  s=s.map{|s|s==2&&c=='b'&&3||s==6&&c=='a'&&7||s==8&&c=='b'&&9||s==12&&c=='a'&&13}-[!0];
  s&[1]!=[]&&s|=[1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[3]!=[]&&s|=[3, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[0]!=[]&&s|=[0, 1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[5]!=[]&&s|=[5, 6];
  s&[7]!=[]&&s|=[7, 8];
  s&[9]!=[]&&s|=[9, 5, 10, 6, 11, 12, 14];
  s&[4]!=[]&&s|=[4, 9, 5, 10, 6, 11, 12, 14];
  s&[11]!=[]&&s|=[11, 12, 14];
  s&[13]!=[]&&s|=[13, 14];
  s&[10]!=[]&&s|=[10, 11, 12, 14]
};
p s&[14]!=[]

Another example:

>>> a|bc

s=[0, 1, 3, 4];
gets.chop.chars.map{|c|
  s=s.map{|s|s==1&&c=='a'&&2||s==4&&c=='b'&&5||s==6&&c=='c'&&7}-[!0];
  s&[0]!=[]&&s|=[0, 1, 3, 4];
  s&[3]!=[]&&s|=[3, 4];
  s&[5]!=[]&&s|=[5, 6];
  s&[2]!=[]&&s|=[2, 7]
};
p s&[7]!=[]

Edit: Added a transition to fix the bug PleaseStand noted in the comments. Also changed initialisation of state.

\$\endgroup\$
  • \$\begingroup\$ Input 011 for regex (0|1(0|1)*)(|A(0|1)*1) results in true - it should be false. \$\endgroup\$ – PleaseStand Aug 23 '12 at 2:23
  • \$\begingroup\$ @PleaseStand Fixed. Please see my edit. \$\endgroup\$ – Howard Aug 25 '12 at 7:10
12
\$\begingroup\$

C, 627 characters

This program treats its first command-line argument as the input and generates C code as its output.

#define A(v) F[v]+strlen(F[v])
#define S sprintf
char*B="&&f%d(s)||f%d(s)",*J="&&f%d(s+%d)",*r,F[256][65536];h=2;e(f,n,o,R,C,O,t,g){for(C=O=f;*r;++r)switch(*r){case 40:r++;e(g=h++,C=h++,0,0);r[1]^42?t=g:(t=C,S(A(t),B,g,C=h++),r++);o=!S(A(O),J,t,o);O=C;break;case 41:goto L;case'|':S(A(C),J,n,o);o=!S(A(O=f),"||1");break;default:r[1]^42?S(A(C),"&&s[%d]==%d",o++,*r,O^f||R++):(o=!S(A(O),J,t=h++,o),O=C=h++,g=h++,S(A(g),"&&*s==%d&&f%d(s+1)",*r++,t),S(A(t),B,g,C));}L:S(A(C),J,n,o);}main(int c,char**v){r=v[1];for(e(1,!S(*F,"&&!*s"),0,0);h--;)printf("f%d(char*s){return 1%s;}",h,F[h]);puts("main(int c,char**v){exit(f1(v[1]));}");}

Here is its output for (0|1(0|1)*)(|A(0|1)*1) (with newlines added):

f11(char*s){return 1&&s[0]==49&&f7(s+1);}
f10(char*s){return 1&&s[0]==48&&f9(s+1)||1&&s[0]==49&&f9(s+1);}
f9(char*s){return 1&&f10(s)||f11(s);}
f8(char*s){return 1&&f7(s+0)||1&&s[0]==65&&f9(s+1);}
f7(char*s){return 1&&f0(s+0);}
f6(char*s){return 1&&f2(s+0);}
f5(char*s){return 1&&s[0]==48&&f4(s+1)||1&&s[0]==49&&f4(s+1);}
f4(char*s){return 1&&f5(s)||f6(s);}
f3(char*s){return 1&&s[0]==48&&f2(s+1)||1&&s[0]==49&&f4(s+1);}
f2(char*s){return 1&&f8(s+0);}
f1(char*s){return 1&&f3(s+0);}
f0(char*s){return 1&&!*s;}
main(int c,char**v){exit(f1(v[1]));}

If you provide valid input as its first command-line argument, it returns exit status 1. Otherwise, it returns exit status 0.

$ ./regexcompiler '(0|1(0|1)*)(|A(0|1)*1)' > floatprog.c
$ gcc -o floatprog floatprog.c
floatprog.c: In function ‘main’:
floatprog.c:1:519: warning: incompatible implicit declaration of built-in function ‘exit’ [enabled by default]
$ ./floatprog '1A00001' && echo invalid || echo valid
valid
$ ./floatprog '100A010' && echo invalid || echo valid
invalid

Either program, if you fail to provide the command-line argument, dereferences a null pointer, causing a segmentation fault. A sufficiently long regex will overflow the buffers of this submission, and the size of input to a generated program is limited by the size of the stack. However, all the test cases work.

Note that e(g=h++,C=h++,0,0); introduces undefined behavior. If, for example, generated programs do not compile, you can try replacing the statement with h+=2;e(g=h-1,C=h-2,0,0);, which is five characters longer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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