Di mana sebagian besar implementasi REGEX berada pada skala kompleksitas?

Kebanyakan implementasi modern dari ekspresi reguler, seperti yang ada di perl atau .NET, melampaui definisi ilmu komputer klasik dari REGEX dengan fitur-fitur seperti lookahead dan lookbehind. Apakah fitur-fitur ini membuat mereka menguraikan pernyataan yang tidak dapat dijelaskan dengan otomat terbatas, non-pushdown? Seberapa jauh lebih dekat dengan turing menyelesaikan ini membuat mereka jika mereka bisa?

Saya tidak berpikir bahwa masalah sebenarnya adalah pertanyaan tentang apa artinya tidak terikat; ini tidak lebih buruk daripada situasi lain dalam penguraian.

Masalahnya terletak pada karakteristik backreferences, yang keduanya sangat kuat dan sangat terbatas: mereka memungkinkan deskripsi beberapa bahasa bebas-konteks, tanpa mengizinkan beberapa bahasa bebas konteks. Misalnya, regex (a*)b\1b\1cocok dengan string dari bentuk , dan Anda dapat menggunakan lemma pemompaan untuk menunjukkan ini bukan bahasa bebas konteks. Namun, di sisi lain, regex dengan backreferences tampaknya tidak cukup untuk mencocokkan bahasa kurung yang seimbang, yang merupakan bahasa bebas konteks-prototipikal.$a^n \cdot b \cdot a^n \cdot b \cdot a^n$

Cukup mudah untuk memberikan semantik denotasional yang mengatakan string apa yang ada dalam bahasa untuk regex, tetapi memberikan karakterisasi automata-teoritik yang baik tampaknya jauh lebih menantang. Ini seperti mesin register, ke register mana Anda dapat menyalin substring dari input Anda, dan yang dapat Anda gunakan untuk menguji string Anda saat ini, tetapi Anda tidak memiliki kemampuan untuk memodifikasi register ini.

Orang yang melakukan teori model hingga memiliki banyak model mesin yang funky, dan akan menarik untuk mengetahui apakah ini sesuai dengan salah satu model mereka.

/(.*)\1/$L = \{ ww | w \in \Sigma^*\}$$w$$K$$L_K = \{ ww | w \in \Sigma^*, \mid w \mid \le K\}$$K$

Tetapi pada prinsipnya, regexps sebagaimana ditentukan lebih kuat daripada bahasa biasa, karena pertanyaan terkait ini membahas lebih detail (dengan contoh bagus juga).

Satu hasil menarik, diambil dari pertanyaan lain ini , juga dihubungkan oleh Suresh Venkat, adalah bahwa regexps "Praktis" adalah NP-lengkap, dan dengan demikian mereka harus setara berkuasa untuk SAT.

Menjadi non-ahli, sementara saya setuju bahwa secara intuitif "regex dengan backreferences tampaknya tidak cukup untuk mencocokkan bahasa kurung yang seimbang", ada sesuatu yang aneh terjadi. Kelengkapan NP menyiratkan bahwa setiap masalah NP dapat direduksi secara polinomi menjadi sebuah regexp, jadi mungkin hanya ada pengurangan polinomial dari bahasa "kurung seimbang" ke bahasa yang dikenali dengan regexps. Tetapi sekali lagi, mungkin ada beberapa regexp yang tidak masuk akal untuk mem-parsing CFL, karena mereka bahkan dapat mem-parsing nomor unary yang tidak utama!

Mungkin, pelajarannya adalah bahwa kelas kompleksitas dan kelas bahasa tidak sebanding, secara umum. Yang juga menyarankan untuk mengulangi pertanyaan Anda, untuk merujuk hierarki Chomsky daripada "skala kompleksitas" (bahkan jika, agar adil, saya tidak bingung dengan itu).

Charles Stewart menulis:

Aho, 1990, "Algoritma untuk menemukan pola dalam string" menunjukkan bahwa masalah keanggotaan untuk bahasa reguler dengan backtracking adalah NP lengkap.

Pratinjau sebagian (setidaknya pernyataan) dapat ditemukan di Google Buku , di halaman 289, dan referensi bibliografi ke makalah dapat ditemukan di sini . Perhatikan bahwa di koran, rewbr adalah singkatan dari Regular Expression With BackReferences.

PCRE, implementasi "ekspresi reguler" yang paling populer juga menerapkan pola rekursif, yang melampaui referensi balik. Sebuah pertanyaan tentang kompleksitasnya baru saja diajukan di Stackoverflow. Menurut jawaban praktis-mendalam-oleh Perl guru brian d foy, ini membuat PCRE sekuat tata bahasa bebas konteks. Namun sintaksnya mengerikan dibandingkan dengan Formulir Backus-Naur.