Nesta tarefa, você deve escrever um programa que leia uma expressão regular e gere outro programa que mostre se uma sequência de entrada é aceita por essa expressão regular. A saída deve ser um programa escrito no mesmo idioma que seu envio.

Entrada

A entrada é uma expressão regular r que corresponde ao seguinte ABNF (a regra de produção inicial é REGEX):

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

Se a entrada não corresponder a esta gramática, o comportamento do seu programa é indefinido.

Interpretação

Interprete a entrada como uma expressão regular, onde *está a estrela Kleene (significando repetir o argumento esquerdo zero ou mais vezes ), |é uma alternativa, (e o )grupo e nenhum operador são concatenados. O agrupamento tem precedência sobre a estrela, a estrela tem precedência sobre a concatenação, a concatenação tem precedência sobre a alternativa.

Diz-se que uma string é aceita se o regex corresponder à string inteira.

Resultado

A saída do programa é outro programa escrito na mesma língua que a sua apresentação que lê uma cadeia s de uma forma implementação definida em tempo de execução, as saídas se r aceita s e depois termina. A saída pode ser feita de maneira definida pelo usuário, embora deva haver apenas duas saídas distintas para programas aceitos e rejeitados.

Você pode supor que a entrada do seu programa de saída nunca seja maior que 2 ¹⁶ -1 bytes.

Restrições

Nem seu envio nem qualquer programa gerado por ele pode usar a funcionalidade interna ou bibliotecas que

• regexes de correspondência
• transformar expressões regulares
• compilar expressões regulares
• gerar analisadores a partir de uma gramática
• simplifique o problema de maneira que sua submissão se torne trivial

Pontuação

A pontuação do seu envio é o número de caracteres. A finalização com a menor pontuação vence.

Casos de teste

Todos os casos de teste contêm uma expressão regular, um conjunto de cadeias aceitas, um conjunto de cadeias rejeitadas e um programa de exemplo no C99, que é uma saída válida de um envio (hipotético) de C99.

(expressão regular vazia)

Strings aceitas

1. (entrada vazia)

Cadeias rejeitadas

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

Programa de exemplo

#include <stdio.h>

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

    return input[0] != 0;
}

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

cordas aceitas

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

cadeias rejeitadas

1. afba
2. foo
3. babba

programa de exemplo

#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 binários de ponto flutuante)

cordas aceitas

1. 10110100
2. 0 0
3. 1A00001

cadeias rejeitadas

1. 011
2. 10A
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}]!=[]"

Essa versão do ruby ​​se tornou bastante longa devido a vários casos de canto no analisador de expressões regulares (talvez eu devesse tentar uma abordagem diferente). Ele espera a expressão regular em STDIN e gera o código ruby ​​correspondente para o correspondente em STDOUT.

O programa gera código diretamente para um NFA-ε que é então executado no matcher.

Caso de teste 1: (a saída inclui novas linhas e recuo adicionais)

>>>

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

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

Outro exemplo:

>>> 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: Adicionada uma transição para corrigir o bug PleaseStand anotado nos comentários. Também mudou a inicialização do estado.

C, 627 caracteres

Este programa trata seu primeiro argumento de linha de comando como entrada e gera código C como saída.

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

Aqui está sua saída para (0|1(0|1)*)(|A(0|1)*1)(com novas linhas adicionadas):

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

Se você fornecer entrada válida como seu primeiro argumento de linha de comando, ele retornará o status de saída 1. Caso contrário, ele retornará o status de saída 0.

$ ./regexcompiler '(0 | 1 (0 | 1) *) (| A (0 | 1) * 1)'> floatprog.c
$ gcc -o floatprog floatprog.c
floatprog.c: Na função 'main':
floatprog.c: 1: 519: aviso: declaração implícita incompatível da função
interna ' exit' [ativada por padrão] $ ./floatprog '1A00001' && echo inválido || eco válido
válido
$ ./floatprog '100A010' && eco inválido || eco válido
inválido

Qualquer um dos programas, se você não fornecer o argumento da linha de comandos, desreferencia um ponteiro nulo, causando uma falha de segmentação. Uma regex suficientemente longa excederá os buffers desse envio e o tamanho da entrada para um programa gerado é limitado pelo tamanho da pilha. No entanto, todos os casos de teste funcionam.

Observe que e(g=h++,C=h++,0,0);apresenta um comportamento indefinido. Se, por exemplo, os programas gerados não forem compilados, você poderá tentar substituir a instrução por h+=2;e(g=h-1,C=h-2,0,0);cinco caracteres a mais.