Seperti judulnya, saya menghabiskan beberapa jam akhir pekan lalu mencoba untuk menyelesaikan pikiran saya tentang kelas bahasa yang cocok dengan ekspresi reguler yang kompatibel dengan Perl, tidak termasuk operator yang cocok yang memungkinkan untuk mengeksekusi kode arbitrer di dalam pola .
Jika Anda tidak tahu apa itu PCRE, baca ini dan ini .
Masalahnya adalah, sumber daya yang tersedia di internet cukup banyak berhenti pada bahasa bebas konteks, dan PCRE dapat mencocokkan lebih dari itu (lihat di bawah); tapi aku benar-benar tidak tahu di mana menemukan teorema atau makalah tentang hal semacam ini.
Khususnya: PCRE jelas merupakan superset dari bahasa reguler (karena sintaks PCRE memiliki semua operator bahasa reguler).
CFG apa pun dapat diletakkan dalam bentuk normal Greibach, yang menghilangkan rekursi kiri. Saya pikir ini dapat digunakan dengan cara (?(DEFINE)...)kelompok untuk "menerjemahkan" tata bahasa ke dalam subrutin yang cocok, menghindari tersedak rekursi kiri, dengan menerjemahkan:
- non-terminal di kepala setiap produksi menjadi subrutin
(?<HEAD>...) - tubuh setiap produksi dimasukkan ke dalam subrutin; terminal dibiarkan apa adanya, non-terminal menjadi prosedur doa (yaitu
(?&NONTERMINAL)); - semua produksi dengan nonterminal yang sama dengan head di ORed bersama oleh
|operator (ditambah pengelompokan tambahan dengan(?:...), jika perlu) - polanya kemudian menjadi
(?(DEFINE)...)grup yang berisi semua produksi "yang diterjemahkan", dan doa untuk prosedur simbol awal, untuk mencocokkan seluruh string, yaitu^(?(DEFINE)...)(?&START)$
Ini harus berurusan dengan CFG apa pun. Oleh karena itu, PCRE harus dapat mencocokkan CFL apa pun.
Masih ada lagi: mari kita ambil bahasa yang sederhana yaitu bahasa string diulang dua kali. Bahasa ini bukan CFL - lemma pemompaan untuk CFL gagal. (Berikan perhatian khusus yang harus dipegang | v x w | ≤ p , sehingga Anda tidak bisa hanya memompa awal atau akhir dari dua string yang berulang.)
Namun, bahasa ini mudah cocok dengan PCRE sebuah: ^(.*)\1$. Karena itu, kami benar-benar di atas CFL.
Berapa banyak di atas? Seperti yang saya katakan, saya tidak tahu. Saya tidak dapat menemukan sumber daya tentang CSL atau semua kelas lain di antaranya untuk mengambil keputusan. Adakah pakar yang bersedia membahas hal ini?
Tambahan: Saya diminta untuk menentukan subset sintaks PCRE mana yang harus diizinkan. Seperti yang saya tulis di awal posting, saya ingin mengecualikan operator yang memungkinkan untuk mengeksekusi kode arbitrer di dalam pola, seperti ??{}.
Demi argumen itu, saya pikir kita bisa tetap dengan sintaks yang ditentukan oleh halaman manual pcresyntax (3) , yang merupakan subset wajar dari apa yang ditawarkan Perl 5.10-5.12, dikurangi info (karena tidak ada di dalam pola). Saya tidak yakin bahwa menambah atau menghapus kata kerja kontrol penelusuran ulang mengubah bahasa yang dapat kita kenali; jika demikian, akan menyenangkan untuk mencari tahu kelas mana yang kita dapatkan dan yang tidak.
Jawaban:
Saya juga menemukan posting blog ini sangat menarik http://nikic.github.io/2012/06/15/The-true-power-of- Regular-expressions.html . Ini memberikan bukti yang sama yang saya berikan sebelumnya tentang fakta bahwa regexps mengenali CFL (dengan menulis ulang tata bahasa melalui
DEFINEblok), dan bahkan beberapa CSL (seperti bahasa string berulang); itu dibangun di atas itu dan terus berjalan, memberikan bukti bahwa regexps dengan referensi-balik adalah NP-hard (dengan mengurangi 3-SAT ke regexp).sumber
Mereka paling banyak memutuskan bahasa konteks-sensitif (yang, seperti yang Anda tunjukkan, adalah superset dari bahasa bebas konteks). Lihat posting biksu perl ini .
Wawasan dasar adalah bahwa "memori" mesin adalah jumlah kelompok tangkap, yang dibatasi secara linear.
sumber