Bagaimana cara mensimulasikan backreferences, lookaheads, dan lookbehinds di automata state yang terbatas?

Saya membuat ekspresi reguler sederhana lexer dan parser untuk mengambil ekspresi reguler dan menghasilkan pohon parsenya. Membuat otomat keadaan terbatas non-deterministik dari pohon parse ini relatif sederhana untuk ekspresi reguler dasar. Namun sepertinya saya tidak bisa membungkus kepala saya di sekitar bagaimana mensimulasikan referensi, melihat ke depan, dan melihat ke belakang.

Dari apa yang saya baca di buku naga ungu saya mengerti bahwa untuk mensimulasikan lookahead dimana ekspresi reguler cocok jika dan hanya jika pertandingan dilanjutkan dengan pertandingan biasa ekspresi , Anda membuat terbatas non-deterministik status otomat di mana digantikan oleh . Apakah mungkin untuk membuat otomat keadaan terbatas deterministik yang melakukan hal yang sama?$r/s$$r$$s$$/$$\varepsilon$

Bagaimana dengan mensimulasikan tampilan kepala negatif dan tampilan belakang? Saya akan sangat menghargai jika Anda menautkan saya ke sumber daya yang menjelaskan cara melakukan ini secara rinci.

Pertama-tama, referensi-ulang tidak dapat disimulasikan oleh automata terbatas karena memungkinkan Anda untuk mendeskripsikan bahasa-bahasa non-reguler. Misalnya, ([ab]^*)\1cocok dengan , yang bahkan tidak bebas konteks.$\{ww \mid w \in \{a,b\}^*\}$

Melihat ke depan dan melihat ke belakang bukanlah hal yang istimewa di dunia automata terbatas karena kami hanya mencocokkan seluruh input di sini. Oleh karena itu, semantik khusus "hanya periksa tapi jangan konsumsi" tidak ada artinya; Anda baru saja menggabungkan dan / atau memotong ekspresi dan mengkonsumsi ekspresi dan menggunakan automata yang dihasilkan. Idenya adalah untuk memeriksa ekspresi lihat-depan atau lihat-belakang saat Anda "mengkonsumsi" input dan menyimpan hasilnya dalam keadaan.

Saat menerapkan regexps, Anda ingin menjalankan input melalui otomat dan memulai kembali dan mengakhiri indeks kecocokan. Itu adalah tugas yang sangat berbeda, sehingga sebenarnya tidak ada konstruksi untuk automata terbatas. Anda membangun automaton Anda seolah-olah ekspresi lihat-depan atau lihat-belakang memakan, dan mengubah indeks Anda menyimpan resp. pelaporan yang sesuai.

Ambil, misalnya, lihat ke belakang. Kita dapat meniru semantik regexp dengan menjalankan regexp pengecekan bersamaan dengan regexp "match-all" yang mengkonsumsi secara implisit. hanya dari kondisi di mana otomat ekspresi ekspresi di belakang berada dalam kondisi akhir, otomat ekspresi dijaga dapat dimasukkan. Misalnya, regexp /(?=c)[ab]+/(dengan asumsi adalah alfabet lengkap) - perhatikan bahwa ia menerjemahkan ke ekspresi reguler - dapat dicocokkan dengan$\{a,b,c\}$$\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$

^{[ sumber ]}

dan Anda harus melakukannya

• simpan indeks saat ini sebagai$i$$q_2$$q_2$
• $i$$-1$$q_2$

Perhatikan bagaimana bagian kiri dari otomat adalah otomat paralel dari automata kanonik untuk [abc]*dan c(iterasi) masing-masing.

$i$$j$$i$$j$

Perhatikan bahwa non-determinisme melekat pada ini: otomat utama dan lihat-depan / di belakang mungkin tumpang tindih, jadi Anda harus menyimpan semua transisi di antara mereka untuk melaporkan yang cocok nanti, atau mundur.

Referensi otoritatif tentang masalah pragmatis di balik penerapan mesin regex adalah serangkaian tiga posting blog oleh Russ Cox . Seperti yang dijelaskan di sana, karena backreferences membuat bahasa Anda tidak biasa, mereka diimplementasikan menggunakan backtracking .

Mencari dan melihat ke belakang, seperti banyak fitur dari mesin pencocokan pola regex, tidak cukup cocok dengan paradigma memutuskan apakah string adalah anggota suatu bahasa atau tidak. Alih-alih dengan regex kita biasanya mencari substring dalam string yang lebih besar. "Match" adalah substring yang merupakan anggota bahasa, dan nilai kembali adalah titik awal dan akhir substring dalam string yang lebih besar.

Titik lookaheads dan lookbehinds bukanlah untuk memperkenalkan kemampuan untuk mencocokkan bahasa yang tidak biasa, melainkan untuk menyesuaikan di mana mesin melaporkan titik awal dan akhir dari substring yang cocok.

Saya mengandalkan deskripsi di http : //www . regular-expressions.info/lookaround.html . Mesin regex yang mendukung fitur ini (Perl, TCL, Python, Ruby, ...) semua tampaknya didasarkan pada pengulangan (yaitu, mereka mendukung serangkaian bahasa yang jauh lebih besar daripada hanya bahasa biasa). Mereka tampaknya menerapkan fitur ini sebagai perpanjangan backtracking yang relatif "sederhana", daripada mencoba untuk membangun automata terbatas nyata untuk melakukan tugas.

Penampilan positif

Sintaks untuk lookahead positif adalah (?=regex) . Jadi misalnya q(?=u)cocok qhanya jika diikuti oleh u, tetapi tidak cocok dengan u. Saya membayangkan mereka menerapkan ini dengan variasi pada backtracking. Buat FSM untuk ekspresi sebelum tampilan positif. Ketika yang cocok ingat di mana itu berakhir dan mulai FSM baru yang mewakili ekspresi di dalam lookahead positif. Jika itu cocok maka Anda memiliki "pertandingan", tetapi pertandingan "berakhir" tepat sebelum posisi di mana pertandingan pencarian kepala positif dimulai.

Satu-satunya bagian dari ini yang akan sulit tanpa mundur adalah bahwa Anda perlu mengingat titik di input di mana lookahead dimulai dan pindahkan tape input Anda kembali ke posisi ini setelah Anda selesai dengan pertandingan.

Lookahead negatif

Sintaks untuk lookahead negatif adalah (?!regex) . Jadi misalnya q(?!u)cocok qhanya jika tidak diikuti oleh u. Ini bisa berupa qdiikuti oleh beberapa karakter lain, atau qdi akhir string. Saya membayangkan ini diimplementasikan dengan membuat NFA untuk ekspresi lookahead, kemudian berhasil hanya jika NFA gagal mencocokkan string berikutnya.

Jika Anda ingin melakukannya tanpa mengandalkan kemunduran, Anda bisa meniadakan NFA dari ekspresi lookahead, lalu perlakukan seperti cara Anda memperlakukan lookahead positif.

Terlihat Positif di Belakang

(?<=)(?=q)uuqq$n$$n$$n$

Anda mungkin dapat mengimplementasikan ini tanpa mundur dengan mengambil persimpangan "string yang berakhir dengan regex " dengan bagian regex apa pun yang datang sebelum operator yang melihat ke belakang. Ini akan menjadi meskipun rumit, karena lookbehind regex mungkin perlu melihat kembali lebih jauh dari awal saat input.

Terlihat Negatif di belakang

Sintaks untuk tampilan negatif di belakang adalah (?<!regex) . Jadi, misalnya, (?<!q)ucocok u, tetapi hanya jika tidak didahului oleh q. Jadi itu akan cocok dengan uin umbrelladan uin doubt, tetapi tidak uin quick. Sekali lagi, ini tampaknya dilakukan dengan menghitung panjang regex , mendukung banyak karakter, menguji pertandingan dengan regex , tetapi sekarang gagal seluruh pertandingan jika tampilan di belakang cocok.

Anda mungkin dapat menerapkan ini tanpa mundur dengan mengambil negasi regex dan kemudian melakukan hal yang sama seperti yang Anda lakukan untuk tampilan positif.

Setidaknya untuk referensi kembali, ini tidak mungkin. Misalnya, regex (.*)\1mewakili bahasa yang tidak teratur. Artinya adalah bahwa tidak mungkin untuk membuat otomat terbatas (deterministik atau tidak) yang akan mengenali bahasa ini. Jika Anda ingin membuktikan ini secara formal, Anda dapat menggunakan lemma pemompaan .

Saya telah melihat ini sendiri, dan Anda harus dapat mengimplementasikan lookahead menggunakan Alternating Finite Automaton . Ketika Anda menemukan lookahead, Anda menjalankan kedua lookahead dan sisanya dari ekspresi, menerima hanya jika kedua jalur menerima. Anda dapat mengonversi AFA ke NFA dengan blowup yang wajar (dan dengan demikian menjadi DFA), meskipun saya belum memverifikasi bahwa konstruksi yang jelas cocok dengan kelompok tangkapan.

Tampilan dengan lebar tetap harus sangat mungkin dilakukan tanpa mundur. Biarkan n menjadi lebarnya. Mulai dari titik di NFA Anda di mana tampilan dimulai, Anda akan membagi status yang melihat ke belakang sehingga setiap jalur ke tampilan tersebut berakhir dengan n karakter senilai status yang hanya masuk ke tampilan di belakang. Kemudian, tambahkan lookahead ke awal negara-negara (dan segera kompilasi subgraph dari AFA ke NFA jika diinginkan).

Referensi, seperti yang telah disebutkan orang lain, tidak teratur, sehingga tidak dapat diimplementasikan oleh robot yang terbatas. Bahkan, mereka NP-lengkap. Dalam implementasi yang sedang saya kerjakan, pencocokan cepat ya / tidak adalah yang terpenting, jadi saya memilih untuk tidak menerapkan referensi sama sekali.