Apa jenis parser yang paling kuat?

Sebagai proyek sampingan, saya menulis bahasa menggunakan Python. Saya mulai dengan menggunakan klon flex / bison yang disebut Ply, tetapi saya muncul di tepi dalam kekuatan apa yang dapat saya ungkapkan dengan gaya tata bahasa itu, dan saya tidak tertarik untuk meretas bahasa saya karena ketidakcocokan impedansi dengan alat. Karena itu, saya tidak segan untuk menulis sendiri.

Jadi apa jenis parser yang paling kuat? Kutipan untuk makalah (serta lebih banyak artikel pengantar) akan diterima.

(Saya tahu bahwa 'kuat' tidak didefinisikan secara tepat, tetapi mari kita sedikit longgar dengannya dan melihat ke mana jawabannya)

Tata bahasa biasanya didefinisikan sebagai tata bahasa Gratis Konteks - definisi yang tepat diberikan pada halaman Wikipedia, tetapi berfungsi sama seperti di PLY, yang didasarkan pada Bison , yang pada gilirannya didasarkan pada yacc .

Dikatakan di sini bahwa PLY menggunakan parser LALR . Ini pada dasarnya adalah parser LR di mana tabel pencarian dikondensasi, mungkin memperkenalkan konflik parsing, mengurangi beberapa ekspresifitas tata bahasa LR (yaitu, tata bahasa bebas konteks yang dapat diurai oleh parser LR). Jika Anda ingin tahu tentang batasan cabang parser khusus ini dan parser lain, tinjauan umum tentang semua jenis teknik penguraian (LL, LR dan lainnya) diberikan di sini .

Untuk menjawab pertanyaan Anda: ada algoritma penguraian yang mampu mem-parsing bahasa bebas konteks apa pun, meskipun bahasanya ambigu (yaitu, ada lebih dari satu cara untuk menginterpretasikan input):

Algoritma pertama seperti itu adalah algoritma CYK , yang sayangnya memiliki waktu operasi , di mana adalah panjang dari string input danadalah ukuran tata bahasa dan karenanya tidak praktis untuk bahasa parsing.n | G $O(n^3 |G|)$$n$$|G|$

Algoritma kedua adalah algoritma Earley . Algoritma ini juga mampu mengurai tata bahasa bebas konteks apa pun. Meskipun algoritma membutuhkan waktu untuk mengurai bahasa yang ambigu, itu hanya membutuhkan waktu untuk mem-parsing bahasa yang tidak ambigu. Selain itu, tampaknya bekerja dalam waktu linier untuk sebagian besar tata bahasa LR dan bekerja sangat baik pada tata bahasa kiri-rekursif.O ( n 2$O(n^3)$$O(n^2)$

Di sini Anda dapat menemukan makalah yang membahas implementasi praktis (adaptasi) algoritma Earley. Mereka menyimpulkan: "Mengingat generalisasi parsing Earley dibandingkan dengan LALR (1) parsing ((yang kira-kira seperti apa PLY)), dan mempertimbangkan bahwa bahkan PEP ((implementasi algoritma Earley) mereka) waktu terburuk tidak akan terlihat oleh pengguna, ini adalah hasil yang sangat baik ".

Jenis parser terakhir adalah parser GLR . Ini adalah versi umum dari parsing LR, yang mampu mem-parsing bahasa bebas konteks apa pun.

Implementasi GLR yang matang adalah ASF + SDF . Bison juga dapat menghasilkan parser GLR, meskipun implementasinya sedikit berbeda dari algoritma GLR 'standar'. The Algoritma Elkhound adalah algoritma hybrid GLR / LALR. Ini menggunakan LALR bila memungkinkan dan GLR bila diperlukan, agar keduanya cepat dan mampu mengurai tata bahasa apa pun.

Di luar tata bahasa bebas konteks ada tata bahasa konteks sensitif , tetapi ini pada umumnya sulit untuk diuraikan dan tidak menambahkan banyak ekspresif: Anda dapat berbuat lebih banyak dengan mereka, tetapi untuk sebagian besar aplikasi penggunaan tambahan tidak relevan, kecuali jika Anda mengurai bahasa alami.

Sebagai langkah terakhir ada tata bahasa tidak terbatas . Pada titik ini tata bahasa sudah selesai-Turing, jadi tidak ada batasan yang bisa diberikan oleh seseorang tentang berapa lama waktu yang diperlukan untuk menguraikan bahasa tertentu, yang tidak diinginkan untuk sebagian besar aplikasi penguraian. Kekuatan ekstra hampir tidak pernah dibutuhkan. Jika Anda ingin menggunakan semua kekuatan itu, ada mesin bahasa yang tersedia.

Terakhir, menerapkan parser-generator Anda sendiri bukanlah masalah sepele, khususnya untuk membuatnya menjadi cepat. Saya pribadi baru saja selesai membuat versi flex saya sendiri (generator lexer), dan walaupun ini tampak seperti latihan dalam masalah algoritmik yang relatif sederhana, menjadi cukup rumit untuk diperbaiki, khususnya ketika saya mencoba mendukung Unicode. Pertimbangkan untuk menggunakan implementasi yang sudah ada alih-alih menulis sendiri.

Sebuah makalah di ICFP 2010 tahun ini, Total Parser Combinators , menggambarkan parser combinator library yang dapat dihentikan dan juga menetapkan bahwa di pustaka ini "kombinator parser seekspresi mungkin" mengingat parser dijamin akan berakhir. Sayangnya saya tidak ingat penjelasan yang penulis berikan untuk arti "seekspresi mungkin", tetapi sepertinya relevan dengan pertanyaan Anda tentang "kekuatan."

Jika Anda ingin melampaui tata bahasa bebas konteks untuk parsing bahasa pemrograman, tetapi masih mengurai dalam waktu polinomial, Anda dapat menggunakan parsing tata bahasa ekspresi , atau tata bahasa boolean - yang terakhir juga tersedia dalam rasa LL dan LR (lihat di sini ). Dalam teori bahasa formal, juga bahasa Church-Rosser yang kuat namun waktu-linier dapat dipelajari, tetapi saya tidak mengetahui adanya generator parser yang diimplementasikan untuk hal ini.

Dalam pemrosesan bahasa alami, rasanya berbeda, misalnya, berurusan dengan ambiguitas (juga: ambiguitas inheren) dan urutan kata bebas memainkan peran yang sangat menonjol. Di sini, kata kunci dengan sedikit bahasa yang peka konteks dan mulai ulang automata mungkin membantu Anda untuk mulai membaca.

Alat Pembuat Parser:

ANTLR sangat bagus. Atau, Anda bisa melihat di JavaCC