Dalam tugas ini Anda harus menulis sebuah program yang membaca ekspresi reguler dan menghasilkan program lain yang menampilkan apakah string input diterima oleh ekspresi reguler itu. Outputnya harus berupa program yang ditulis dalam bahasa yang sama dengan kiriman Anda.
Memasukkan
Input adalah ekspresi reguler r cocok dengan ABNF berikut (aturan produksi awal adalah REGEX
):
REGEX = *( STAR / GROUP / LITERAL / ALTERNATIVE )
STAR = REGEX '*'
GROUP = '(' REGEX ')'
LITERAL = ALPHA / DIGIT
ALTERNATIVE = REGEX '|' REGEX
Jika input tidak cocok dengan tata bahasa ini, perilaku program Anda tidak ditentukan.
Penafsiran
Menafsirkan input sebagai ekspresi reguler, di mana bintang *
-Kleene (artinya mengulangi argumen kiri nol kali atau lebih ), |
merupakan alternatif, (
dan )
grup dan tidak ada operator yang digabungkan. Pengelompokan lebih diutamakan daripada bintang, bintang lebih diutamakan daripada penggabungan, penggabungan lebih diutamakan daripada alternatif.
Suatu string dikatakan diterima jika regex cocok dengan keseluruhan string.
Keluaran
Output program ini adalah program lain yang ditulis dalam bahasa yang sama seperti kiriman Anda yang membaca string s dengan cara implementasi didefinisikan pada saat runtime, output apakah r menerima s dan kemudian berakhir. Output dapat dilakukan dengan cara yang ditentukan pengguna meskipun harus ada hanya dua output yang berbeda untuk program yang diterima dan ditolak.
Anda dapat mengasumsikan bahwa input dari program output Anda tidak pernah lebih dari 2 16 -1 Bytes.
Batasan
Baik kiriman Anda maupun program apa pun yang dihasilkan oleh kiriman Anda tidak dapat menggunakan fungsionalitas bawaan atau pustaka itu
- mencocokkan regex
- mengubah ekspresi reguler
- kompilasi ekspresi reguler
- menghasilkan parser dari tata bahasa
- sederhanakan masalahnya dengan cara agar pengiriman Anda menjadi sepele
Mencetak gol
Skor kiriman Anda adalah jumlah karakternya. Pengajuan dengan skor terendah akan menang.
Testcases
Semua testcases berisi ekspresi reguler, satu set string yang diterima, satu set string yang ditolak dan contoh program di C99 yang merupakan output yang valid dari pengiriman C99 (hyptothetical) C99.
(ekspresi reguler kosong)
String yang diterima
- (input kosong)
String yang ditolak
- foo
- batang
- baz
- quux
Contoh program
#include <stdio.h>
int main() {
char input[65536];
gets(input);
return input[0] != 0;
}
(b|)(ab)*(a|)
( a
dan b
berganti - ganti)
string yang diterima
a
ba
abababababa
abab
string yang ditolak
afba
foo
babba
contoh 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)
(angka titik mengambang biner)
string yang diterima
- 10110100
- 0
- 1A00001
string yang ditolak
- 011
- 10A
- 1A00
- 100A010
return (regex.match(stdin) is not null)
tidak diperbolehkan.Jawaban:
Ruby,
641651543 karakterVersi ruby ini menjadi cukup panjang karena beberapa kasus sudut di parser regex (mungkin saya harus mencoba pendekatan yang berbeda). Ia mengharapkan ekspresi reguler pada STDIN dan mengeluarkan kode ruby yang sesuai untuk korek api ke STDOUT.
Program ini secara langsung menghasilkan kode untuk NFA-ε yang kemudian dieksekusi dalam korek api.
Test case 1: (output termasuk baris baru dan lekukan)
Uji kasus 2:
Contoh lain:
Sunting: Menambahkan transisi untuk memperbaiki bug PleaseStand yang tercatat di komentar. Juga mengubah inisialisasi keadaan.
sumber
011
untuk(0|1(0|1)*)(|A(0|1)*1)
hasil regex ditrue
- seharusnyafalse
.C, 627 karakter
Program ini memperlakukan argumen baris perintah pertama sebagai input dan menghasilkan kode C sebagai hasilnya.
Ini adalah output untuk
(0|1(0|1)*)(|A(0|1)*1)
(dengan baris baru ditambahkan):Jika Anda memberikan input yang valid sebagai argumen baris perintah pertama, ia mengembalikan status keluar 1. Jika tidak, ia mengembalikan status keluar 0.
Program mana pun, jika Anda gagal memberikan argumen baris perintah, referensi referensi kosong, menyebabkan kesalahan segmentasi. Regex yang cukup panjang akan membanjiri buffer dari submission ini, dan ukuran input ke program yang dihasilkan dibatasi oleh ukuran stack. Namun, semua kasus uji berfungsi.
Perhatikan bahwa
e(g=h++,C=h++,0,0);
memperkenalkan perilaku yang tidak terdefinisi. Jika, misalnya, program yang dihasilkan tidak dikompilasi, Anda dapat mencoba mengganti pernyataan denganh+=2;e(g=h-1,C=h-2,0,0);
, yang lebih panjang lima karakter.sumber