Notasi apa yang bagus untuk bahasa deterministik bebas konteks dan jelas pushdown yang ada?

Bahasa bebas konteks deterministik (DCFL) dan bahasa pushdown tampak (VPL) keduanya set bahasa formal antara bahasa bebas konteks (CFL) dan bahasa biasa (REG). Apakah ada notasi yang dapat dibaca yang dapat diekspresikan dalam ASCII sederhana seperti Backus-Naur-Form untuk CFL dan ekspresi reguler untuk REG?

fl.formal-languages Jakob
sumber

Mungkin bermanfaat untuk memperjelas arti "baik" dalam judul pertanyaan. Apa yang salah dengan menggunakan BNF untuk menggambarkan DCFL?

Tsuyoshi Ito

Maksud saya adalah mudah dibaca dan ditulis untuk manusia, jadi harus berdasarkan ASCII. BNF hebat - ekspresi reguler adalah bagian kecil dari BNF. Tetapi bagian mana dari BNF yang mendefinisikan DCFL dan yang mendefinisikan VPL?

Jakob

Jawaban:

Mengenai DCFL, saya tidak melihat notasi yang lebih baik daripada fungsi transisi dari automaton pushdown deterministik, yaitu menulis secara eksplisit aturan bentuk dengan menyatakan dalam , tumpukan simbol, urutan simbol stack, dan simbol input atau string kosong. Notasi itu sendiri tidak memaksakan determinisme, tetapi mudah diperiksa. Dengan menggunakan jenis notasi tata bahasa bebas konteks (seperti BNF), Anda akan mengalami masalah karena DCFL adalah subkelas CFL yang tepat, dan seperti dicatat oleh DaniCL, Anda tidak dapat memutuskan secara umum diberi CFG apakah bahasanya ditentukan deterministik. $q,z,a\to q',\gamma$ $q,q'$ $Q$ $z$ $\gamma$ $a$

Mengenai VPLS, sebuah tanda kurung / kurung-gaya untuk CFGs akan cukup baik, dengan aturan bentuk di mana adalah non-terminal, simbol panggilan, simbol kembali, dan suatu ~~urutan~~ yang teratur ekspresi lebih dari simbol dan nonterminals internal campuran. Karena setiap VPL juga merupakan (D) CFL, Anda juga dapat menggunakan kembali notasi di atas untuk pushdown automata dan memeriksa apakah operasi stack cocok dengan panggilan dan pengembalian, atau menuliskan hubungan transisi dari automaton kata bersarang (yang akan kurang redundan) . $A\to a\alpha b$ $A$ $a$ $b$ $\alpha$

Sunting: kalau dipikir-pikir itu, notasi untuk skema XML, seperti sintaks kompak RelaxNG --- yang merupakan notasi ASCII ---, dapat dengan mudah digunakan untuk VPL. Anda akan hanya perlu untuk menegakkan beberapa konvensi penamaan untuk tag, misalnya tag pembuka "<ab>" untuk panggilan simbol pencocokan tag penutup "</ ab>" untuk simbol kembali . $a$ $b$

Sylvain
sumber

Terima kasih! Mengenai DCFL saya pikir ini adalah arah yang benar. Sintaks konkret akan memiliki beberapa singkatan berguna untuk himpunan bagian yang diuraikan oleh ekspresi reguler. Mengenai VPL saya belum yakin, karena VLP diizinkan untuk memiliki panggilan dan mengembalikan simbol yang berbeda dengan model pohon seperti XML. Anda dapat membandingkannya dengan lebih baik dengan sub-urutan SAX-peristiwa yang sewenang-wenang dari pohon XML sewenang-wenang. Saya ragu bahwa RelaxNG dapat menggambarkan ini.

Jakob

Pernyataan Menggunakan ... bersifat deterministik. di luar intinya - ia tidak mengatakan apa-apa tentang apakah ada subkelas CFG yang sangat jelas menggambarkan semua DCFL dan tidak ada yang lain. Seperti tata bahasa LR (k).

reinierpost

@reinerpost: true, tetapi (dalam pembelaan saya) saya tidak akan mempertimbangkan LR (1) tata bahasa untuk memberikan notasi sintaksis , karena orang perlu memeriksa kondisi LR (1).

Sylvain

Untuk menemukan representasi kanonik, pertimbangkan hal berikut: kelas DCFL setara dengan kelas bahasa yang dihasilkan oleh tata bahasa LR (k), yang lagi-lagi setara dengan LR (1). Ini berarti Anda dapat menemukan tata bahasa LR (1) untuk setiap DCFL. Tentu saja, tata bahasa LR (1) masih merupakan tata bahasa bebas konteks, tetapi dengan properti khusus: dari tata bahasa LR (1), kita dapat dengan mudah membangun tabel parse untuk memandu parser deterministik (dengan lookahead dari 1 simbol, karenanya LR (1)). Tabel parse ini akan menjadi representasi lain, meskipun agak kurang dapat dibaca.

Omong-omong, ingatlah bahwa tidak dapat diputuskan apakah bahasa bebas konteks tertentu bersifat deterministik (Teorema Greibach).

Saya harus mengakui bahwa saya belum pernah mendengar tentang VPL.

DaniCL
sumber

Nah, representasi kanonik jarang mudah dibaca, tetapi terima kasih atas arahannya. Jika Teorema Greibach menyatakan bahwa ada bahasa dalam CFL yang tidak dapat diputuskan berada di DCFL - bagaimana Anda menentukan bahasa ini? Jika Anda memiliki tata bahasa, Anda bisa mengekspresikannya dalam Backus Naur Form (BNF), jadi Teorema Greibach tampaknya menyiratkan bahwa tidak ada subset dari BNF yang secara tepat mengekspresikan DCFL? Bahasa pushdown yang tampak juga dikenal sebagai "kata-kata bersarang". Kelas bahasa ini relatif baru tetapi relevan untuk penguraian pohon tertata dan struktur serupa.

Jakob

Tentang masalah ketidakpastian: bahasa adalah CFL jika ada tata bahasa bebas konteks (CFG) yang menghasilkannya. Jika Anda diberikan CFG, Anda dapat memutuskan apakah tata bahasa ini adalah LR (k), karenanya deterministik. (Hal yang sama berlaku untuk pushdown automata - mudah untuk memeriksa apakah PDA yang diberikan bersifat deterministik atau tidak.) Namun, misalkan Anda memiliki CFG yang bukan LR (k) - ini tidak berarti bahwa bahasa tersebut bukan DCFL ; Anda mungkin tidak dapat menemukan tata bahasa LR (k) untuk itu.

DaniCL

"Anda dapat memutuskan apakah tata bahasa ini LR (k)" untuk k tetap.

Sylvain

@Jakob: Teorema Greibach tidak menyatakan itu, dan bahkan jika itu terjadi, itu hanya berarti bahwa CFG sewenang - wenang bukanlah formalisme notasi yang cocok untuk DCFG, sama seperti mereka bukan formalisme notasi yang baik untuk bahasa reguler (apakah suatu CFG menjelaskan bahasa biasa juga tidak dapat dipastikan). Namun tidak ada yang salah dengan memilih subkelas CFG (misalnya tata bahasa reguler untuk bahasa reguler).

reinierpost

Ada tradisi kata-kata ceroboh dalam buku teks di sini: mereka cenderung membuat pernyataan seperti "itu tidak dapat diputuskan apakah CFL biasa / deterministik" ketika apa yang mereka maksudkan dengan itu adalah "tidak dapat dipastikan apakah CFG menggambarkan reguler / deterministik bahasa".

reinierpost