Codegolf — Компиляция Регулярных Выражений

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

Вход

Входные данные представляют собой регулярное выражение р соответствующее следующему ABNF (исходное производственное правило

 
 
 (0|1(0|1)*)(|A(0|1)*1) 
 
 

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

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

Интерпретируйте ввод как регулярное выражение, где babba is the Kleene-star (meaning повторить левый аргумент ноль или более раз), foo is an alternative, afba и abab group and no operator at all concatenated. Grouping takes precedence over star, star takes precedence over concatenation, concatenation takes precedence over alternative.

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

Выход

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

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

Ограничения

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

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

Подсчет очков

Оценка вашего представления — это количество символов в нем. Побеждает работа с наименьшим количеством баллов.

Тестовые случаи

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

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

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

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

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

1. фу
2. бар
3. Баз
4. Quux

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

ba ( a и b alternating)

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

1. a
2. (b|)(ab)*(a|)
3. #include <stdio.h> int main() { char input[65536]; gets(input); return input[0] != 0; }
4. )

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

1. (
2. |
3. *

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

REGEX (binary floating point numbers)

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

1. 10110100
2. 0
3. 1A00001

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

1. 011
2. 10А
3. 1А00
4. 100А010

#код-гольф #регулярное выражение #генерация кода #генерация

С, 627 символов

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

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

Вот его вывод для >>> (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]!=[] (with newlines added):

Если вы предоставляете действительные входные данные в качестве первого аргумента командной строки, он возвращает статус выхода 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' && неверный вывод || эхо действительно
действительный
$ ./floatprog '100A010' && неверный вывод || эхо действительно
неверный

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

Обратите внимание, что 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}]!=[]" 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); , что на пять символов длиннее.

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

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

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

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

Тестовый пример 2:

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

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