En esta tarea, debe escribir un programa que lea una expresión regular y genere otro programa que muestre si esa expresión regular acepta una cadena de entrada. El resultado debe ser un programa escrito en el mismo idioma que su envío.

Entrada

La entrada es una expresión regular r que coincide con el siguiente ABNF (la regla de producción inicial es REGEX):

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

Si la entrada no coincide con esta gramática, el comportamiento de su programa no está definido.

Interpretación

Interprete la entrada como una expresión regular, donde *está la estrella de Kleene (es decir, repita el argumento izquierdo cero o más veces ), |es una alternativa, (y el )grupo y ningún operador están concatenados. La agrupación tiene prioridad sobre la estrella, la estrella tiene prioridad sobre la concatenación, la concatenación tiene prioridad sobre la alternativa.

Se dice que se acepta una cadena si la expresión regular coincide con la cadena completa.

Salida

La salida del programa es otro programa escrito en el mismo lenguaje que su envío que lee una cadena s de una manera definida por la implementación en tiempo de ejecución, emite si r acepta sy luego termina. La salida se puede realizar de una manera definida por el usuario, aunque solo debe haber dos salidas distintas para los programas aceptados y rechazados.

Puede suponer que la entrada de su programa de salida nunca supera los 2 ¹⁶ -1 Bytes.

Restricciones

Ni su envío ni ningún programa generado por su envío pueden utilizar la funcionalidad integrada o las bibliotecas que

• coincide con expresiones regulares
• transformar expresiones regulares
• compilar expresiones regulares
• generar analizadores a partir de una gramática
• simplifique el problema de manera que su presentación se vuelva trivial

Puntuación

El puntaje de su presentación es la cantidad de caracteres que contiene. La presentación con la puntuación más baja gana.

Casos de prueba

Todos los casos de prueba contienen una expresión regular, un conjunto de cadenas aceptadas, un conjunto de cadenas rechazadas y un programa de ejemplo en C99 que es una salida válida de un envío C99 (hipotético).

(expresión regular vacía)

Cadenas aceptadas

1. (entrada vacía)

Cadenas rechazadas

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

Programa de ejemplo

#include <stdio.h>

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

    return input[0] != 0;
}

(b|)(ab)*(a|)( ay balternando)

cadenas aceptadas

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

cadenas rechazadas

1. afba
2. foo
3. babba

programa de ejemplo

#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) (números binarios de coma flotante)

cadenas aceptadas

1. 10110100
2. 0 0
3. 1A00001

cadenas rechazadas

1. 011
2. 10 A
3. 1A00
4. 100A010

Ruby, 641 651 543 caracteres

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}]!=[]"

Esta versión rubí se hizo bastante larga debido a varios casos de esquina en el analizador de expresiones regulares (tal vez debería intentar un enfoque diferente). Espera la expresión regular en STDIN y genera el código ruby ​​correspondiente para el emparejador en STDOUT.

El programa genera directamente código para un NFA-ε que luego se ejecuta en el emparejador.

Caso de prueba 1: (la salida incluye nuevas líneas adicionales y sangría)

>>>

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

Caso de prueba 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]!=[]

Otro ejemplo:

>>> 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]!=[]

Editar: se agregó una transición para corregir el error. PleaseStand se indica en los comentarios. También cambió la inicialización del estado.

C, 627 caracteres

Este programa trata su primer argumento de línea de comandos como la entrada y genera el código C como su salida.

#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]));}");}

Aquí está su salida para (0|1(0|1)*)(|A(0|1)*1)(con nuevas líneas agregadas):

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]));}

Si proporciona una entrada válida como su primer argumento de línea de comandos, devuelve el estado de salida 1. De lo contrario, devuelve el estado de salida 0.

$ ./regexcompiler '(0 | 1 (0 | 1) *) (| A (0 | 1) * 1)'> floatprog.c
$ gcc -o floatprog floatprog.c
floatprog.c: En la función 'main':
floatprog.c: 1: 519: advertencia: declaración implícita incompatible de la función incorporada 'salida' [habilitada por defecto]
$ ./floatprog '1A00001' && echo inválido || echo válido
válido
$ ./floatprog '100A010' && echo inválido || echo válido
inválido

Cualquiera de los dos programas, si no proporciona el argumento de la línea de comandos, elimina la referencia de un puntero nulo, lo que provoca un error de segmentación. Una expresión regular suficientemente larga desbordará las memorias intermedias de este envío, y el tamaño de la entrada a un programa generado está limitado por el tamaño de la pila. Sin embargo, todos los casos de prueba funcionan.

Tenga en cuenta que e(g=h++,C=h++,0,0);introduce un comportamiento indefinido. Si, por ejemplo, los programas generados no se compilan, puede intentar reemplazar la declaración con h+=2;e(g=h-1,C=h-2,0,0);, que tiene cinco caracteres más.