Ekspresi reguler tidak

Tanyakan bahkan kepada seseorang dengan latar belakang dalam ilmu komputer apa ekspresi reguler itu, dan jawabannya cenderung melampaui batasan berada dalam jangkauan robot kondisi-terbatas.

Misalnya, "ekspresi reguler"

/^1?$|^(11+?)\1+$/

dibuat oleh kepribadian Perl yang terkenal Abigail (dan bagian dari rangkaian uji Perl sejak 2002) menggambarkan sebuah mesin yang hanya menerima bilangan unary gabungan, tetapi latihan 4.5 (b) dalam edisi ketiga Peter Pengantar An Pengantar Bahasa Resmi dan Automata digunakan pembaca. yang lemma memompa untuk membuktikan bahwa

$\mathcal{L} = \left\{ a^n : n\ \mathrm{is\ not\ a\ prime\ number} \right\}$

bukan bahasa biasa.

Dalam konteks di mana perbedaan itu penting, apa yang harus kita sebut ungkapan yang lebih kuat?

Larry Wall mengusulkan agar kami menggunakan "ekspresi reguler" untuk formalisme yang diusulkan Kleene, dan "regex" untuk ekspresi untuk ekstensi yang banyak digunakan. Itu adalah konvensi yang cukup diikuti. Jika Anda ingin memperjelas bahwa Anda berbicara tentang ekspresi reguler dalam pengertian bahasa formal, biasanya tidak sulit untuk diterjemahkan ke dalam pembicaraan tentang bahasa biasa.

Kekuatan regex berasal dari backtracking, dan telah ada pekerjaan yang dilakukan pada automata untuk bahasa reguler dengan backtracking. Lihat, khususnya, Becchi & Crowley, 2008, Memperluas Finata Automata hingga Mencocokkan Ekspresi Reguler Kompatibel yang Efisien secara Efisien .

Ungkapan-ungkapan ini telah diperiksa oleh Aho (Buku Pegangan Ilmu Komputer Teoritis, Vol. A, Chp. 5) dan Campeanu, Salomaa, Yu ("Sebuah studi formal ekspresi reguler praktis", International Journal of Foundations of Computer Science, 14: 1007 –1018, 2003), serta beberapa makalah tindak lanjut.

Aho menyebut ungkapan yang lebih kuat "rewbr" (ekspresi reguler dengan referensi-ulang), Campeanu et al. gunakan "ekspresi reguler yang diperluas" serta "ekspresi reguler yang praktis". Seperti kelihatannya, "extended regular expression" adalah istilah yang paling umum digunakan dalam literatur terbaru.

Mengembangkan istilah "ekspresi rasional" dari sekolah Perancis, dan mengingat fakta bahwa ungkapan-ungkapan itu digunakan di dunia nyata, saya sendiri suka "ekspresi nyata".

Tambahan: Sebuah bab dalam tesis PhD saya membahas kelas bahasa formal ini (makalah yang sesuai akan muncul di STACS 2011). Saat menulis bab dan makalah itu, saya bereksperimen dengan berbagai istilah. Akhirnya, saya memutuskan untuk menggunakan ekspresi reguler yang diperluas untuk model dengan backreferences, dan ekspresi reguler yang tepat untuk ekspresi reguler yang bagus dan normal. Karena cukup menjengkelkan untuk mengubah terminologi dalam makalah yang sudah sepenuhnya (atau sebagian besar) ditulis, saya berpikir bahwa beberapa mungkin tertarik pada pengalaman yang mengarah pada pilihan saya:

Pertama, regex dan rewbr tidak benar-benar menggulung lidah, dan menggunakannya berulang kali dalam keseluruhan makalah menjadi sangat melelahkan untuk menulis dan membaca, khususnya ketika menggunakan salah satu bentuk jamak yang mungkin. Ekspresi reguler seperti PERL juga cukup sulit. Tentu saja, saya bukan penutur asli, jadi YMMV.

Kedua, segera setelah seseorang ingin berbicara tentang kedua model, akan lebih mudah untuk menggunakan istilah yang merupakan variasi dari ekspresi reguler , karena ini memungkinkan seseorang untuk menekankan kesamaan atau perbedaan sesuai kebutuhan (misalnya, "ekspresi reguler, apakah itu tepat atau diperpanjang "). Lebih jauh, ini memungkinkan seseorang untuk dengan mudah menekankan kasus khusus "ekspresi reguler yang diperluas tanpa referensi belakang", ketika berbicara tentang kasus khusus di seluruh kelas, daripada membandingkan model yang berbeda.

Ketiga, saya lebih suka menggunakan istilah yang sudah digunakan dalam literatur daripada istilah yang baru diciptakan, yang membuat saya pilihan ekspresi reguler yang diperluas dan ekspresi reguler yang praktis . Pilihan kedua menyiratkan (setidaknya secara implisit) bahwa ekspresi reguler yang tepat entah bagaimana tidak praktis, yang terasa agak aneh (terutama karena RE2 Google tidak menggunakan backrefs, dan tampaknya cukup praktis).

Tentu saja, pilihan ini hanya "maksimum lokal pribadi" saya, dan tergantung pada kebutuhannya, pilihan lain mungkin lebih tepat.

Diketahui bahwa reg's perl disebut cukup kuat untuk menjadi Turing lengkap; bahkan ada kompiler dari program biasa ke perl regexp.

Oleh karena itu saya ragu masuk akal untuk mencari nama untuk "regexps" semacam ini.

Lihat misalnya di http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm

Saya pikir istilah terbaik untuk "ekspresi reguler dalam konteks automata" adalah "ekspresi rasional", seperti yang digunakan, katakanlah, dalam Elements of Automata Theory Sakarovitch, atau Handbook of Weighted Automata.

Dengan jawaban yang lain, saya akan menyarankan bahwa "bahasa biasa" aman, dan setelah singkat berkomentar perbedaannya, untuk berbicara tentang "ekspresi reguler praktis" untuk regexs (dengan backtracking).

Juga perhatikan bahwa regexp yang sama, sebagai ekspresi reguler dan sebagai yang praktis, dapat memiliki semantik yang berbeda, karena dalam kasus yang terakhir semantik didefinisikan dalam hal pengulangan, dengan hasil yang berbeda. Detail akan di luar topik, tetapi saya akan menjawab jika Anda mengajukan pertanyaan lain tentang hal itu (mungkin pada SO daripada di sini, tidak tahu) dan memberi tahu saya melalui komentar.

Kita bisa menyebutnya ekspresi pola . Ini mungkin menimbulkan kebingungan dengan bahasa pola, tetapi setidaknya ini kurang umum.