В этой задаче вы должны написать программу, которая читает регулярное выражение и генерирует другую программу, которая выводит, принята ли входная строка этим регулярным выражением. Вывод должен быть программой, написанной на том же языке, что и ваша заявка.

вход

Ввода является регулярным выражением г соответствия следующей ABNF (начальное правило производства REGEX):

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

Если ввод не соответствует этой грамматике, поведение вашей программы не определено.

интерпретация

Интерпретировать входные данные как регулярное выражение, где *Kleene-star (имеется в виду повторение левого аргумента ноль или более раз ), |является альтернативой, (а )группа и ни один оператор вообще не объединены. Группировка имеет приоритет над звездой, звезда имеет приоритет над конкатенацией, конкатенация имеет приоритет над альтернативой.

Строка считается принятой, если регулярное выражение соответствует всей строке.

Выход

Вывод программы - это другая программа, написанная на том же языке, что и ваша заявка, которая читает строку s определенным для реализации способом во время выполнения, выводит, принимает ли r s, а затем завершает работу. Вывод может быть сделан пользовательским способом, хотя для принятых и отклоненных программ должно быть только два отдельных вывода.

Вы можете предположить, что ввод вашей выходной программы никогда не будет длиннее 2 ¹⁶ -1 байт.

ограничения

Ни ваша заявка, ни какая-либо программа, созданная вами, не могут использовать встроенные функции или библиотеки, которые

• соответствие регулярных выражений
• преобразовать регулярные выражения
• компилировать регулярные выражения
• генерировать парсеры из грамматики
• упростить задачу таким образом, чтобы ваше представление стало тривиальным

счет

Оценка вашего представления - это количество символов. Представление с самым низким счетом выигрывает.

Testcases

Все тестовые случаи содержат регулярное выражение, набор принятых строк, набор отклоненных строк и пример программы на C99, которая является действительным выводом (гипотетической) отправки C99.

(пустое регулярное выражение)

Принимаемые строки

1. (пустой ввод)

Отклоненные строки

1. Foo
2. бар
3. Baz
4. quux

Пример программы

#include <stdio.h>

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

    return input[0] != 0;
}

(b|)(ab)*(a|)( aи bчередующийся)

принятые строки

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

отклоненные строки

1. afba
2. foo
3. babba

пример программы

#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) (двоичные числа с плавающей точкой)

принятые строки

1. 10110100
2. 0
3. 1A00001

отклоненные строки

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

Рубин, 641 651 543 символов

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

Эта версия ruby ​​стала довольно длинной из-за нескольких угловых случаев в синтаксическом анализаторе регулярных выражений (возможно, я должен попробовать другой подход). Он ожидает регулярное выражение в STDIN и выводит соответствующий код ruby ​​для сопоставителя в STDOUT.

Программа непосредственно генерирует код для NFA-ε, который затем выполняется в средстве сопоставления.

Тестовый пример 1: (вывод включает в себя дополнительные переводы строки и отступы)

>>>

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

Контрольный пример 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]!=[]

Другой пример:

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

Редактировать: Добавлен переход для исправления ошибки, пожалуйста, отметьте в комментариях. Также изменилась инициализация состояния.

C 627 знаков

Эта программа обрабатывает свой первый аргумент командной строки как входные данные и генерирует C-код как свои выходные данные.

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

Вот его вывод для (0|1(0|1)*)(|A(0|1)*1)(с добавленными символами новой строки):

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

Если вы в качестве первого аргумента командной строки предоставите действительный ввод, он вернет статус выхода 1. В противном случае он вернет статус выхода 0.

$ ./regexcompiler '(0 | 1 (0 | 1) *) (| A (0 | 1) * 1)'> floatprog.c
$ gcc -o floatprog floatprog.c
floatprog.c: в функции 'main':
floatprog.c: 1: 519: предупреждение: несовместимое неявное объявление встроенной функции 'exit' [включено по умолчанию]
$ ./floatprog '1A00001' && echo invalid || echo valid
valid
$ ./floatprog '100A010' && echo invalid || эхо-код
недействителен

Любая из программ, если вы не предоставите аргумент командной строки, разыменовывает нулевой указатель, вызывая ошибку сегментации. Достаточно длинное регулярное выражение переполнит буферы этого представления, а размер ввода в сгенерированную программу ограничен размером стека. Тем не менее, все тесты работают.

Обратите внимание, что e(g=h++,C=h++,0,0);вводит неопределенное поведение. Если, например, сгенерированные программы не компилируются, вы можете попробовать заменить оператор на h+=2;e(g=h-1,C=h-2,0,0);пять символов длиннее.