Apa keuntungan dan kerugian utama dari penguraian LL dan LR?

Ketika membangun parser ke bahasa pemrograman apa yang saya peroleh dan apa yang saya kehilangan memilih satu atau yang lain?

Saya akan kontras LL dan LR parsing untuk sejumlah kriteria:

Kompleksitas

LL menang di sini, tangan ke bawah. Anda dapat dengan mudah menulis parser LL. Sebenarnya, ini biasa dilakukan: kompiler Microsoft C # adalah parser keturunan rekursif tulisan tangan (sumber di sini , cari komentar yang dibuat oleh Patrick Kristiansen - posting blog juga sangat menarik).

Penguraian LR menggunakan metode yang agak kontra-intuitif untuk mem-parsing teks. Ini bekerja, tetapi butuh beberapa waktu untuk membungkus kepala saya di sekitar cara kerjanya tepatnya. Oleh karena itu, menulis parser seperti itu dengan tangan adalah sulit: Anda akan kurang lebih mengimplementasikan generator parser LR.

Keumuman

LR menang di sini: semua bahasa LL adalah bahasa LR, tetapi ada lebih banyak bahasa LR daripada bahasa LL (bahasa adalah bahasa LL jika dapat diuraikan dengan parser LL, dan sebuah bahasa adalah bahasa LR jika dapat diurai dengan sebuah parser LR).

LL memiliki beberapa gangguan yang akan mengganggu Anda ketika mengimplementasikan hampir semua bahasa pemrograman. Lihat di sini untuk ikhtisar.

Ada bahasa yang tidak ambigu yang bukan bahasa LR, tetapi itu cukup langka. Anda hampir tidak pernah menemukan bahasa seperti itu. Namun, LALR memang memiliki beberapa masalah.

LALR kurang lebih merupakan peretas bagi pengurai LR untuk membuat tabel lebih kecil. Tabel untuk parser LR biasanya dapat tumbuh sangat besar. Parser LALR memberikan kemampuan untuk mem-parsing semua bahasa LR dengan imbalan tabel yang lebih kecil. Kebanyakan parser LR benar-benar menggunakan LALR (meskipun tidak secara diam-diam, Anda biasanya dapat menemukan apa yang diterapkannya).

LALR dapat mengeluh tentang konflik pengurangan-pengurangan dan pengurangan-pengurangan. Ini disebabkan oleh tabel hack: ini 'melipat' entri yang sama bersama-sama, yang berfungsi karena sebagian besar entri kosong, tetapi ketika mereka tidak kosong itu menghasilkan konflik. Jenis kesalahan ini tidak alami, sulit dipahami dan perbaikannya biasanya cukup aneh.

Kesalahan kompiler dan pemulihan kesalahan

LL menang di sini. Dalam parse LL, biasanya cukup mudah untuk memancarkan kesalahan kompiler yang berguna, khususnya parser yang ditulis tangan. Anda tahu apa yang Anda harapkan selanjutnya, jadi jika tidak muncul, Anda biasanya tahu apa yang salah dan kesalahan apa yang paling masuk akal.

Juga, dalam penguraian LL, pemulihan kesalahan jauh lebih mudah. Jika suatu input tidak diuraikan dengan benar, Anda dapat mencoba untuk melewatkan sedikit ke depan dan mencari tahu apakah sisa dari input tidak diurai dengan benar. Jika misalnya beberapa pernyataan pemrograman salah, Anda dapat langsung beralih dan menguraikan pernyataan berikutnya, sehingga Anda dapat menangkap lebih dari satu kesalahan.

Menggunakan parser LR ini jauh lebih sulit. Anda dapat mencoba menambah tata bahasa Anda sehingga menerima input yang salah dan mencetak kesalahan di area di mana terjadi kesalahan, tetapi ini biasanya cukup sulit dilakukan. Kemungkinan Anda berakhir dengan tata bahasa non-LR (atau non-LALR) juga naik.

Kecepatan

Kecepatan sebenarnya bukan masalah dengan cara Anda mengurai input Anda (LL atau LR), melainkan kualitas kode yang dihasilkan dan penggunaan tabel (Anda dapat menggunakan tabel untuk LL dan LR). LL dan LR karena itu sebanding dalam hal ini.

Tautan

Berikut ini tautan ke situs yang juga kontras dengan LL dan LR. Cari bagian dekat bagian bawah.

Di sini Anda dapat menemukan percakapan mengenai perbedaan. Bukan ide yang buruk untuk melihat secara kritis pendapat yang disuarakan di sana, ada sedikit perang suci yang terjadi di sana.

Untuk info lebih lanjut, di sini dan di sini adalah dua posting saya sendiri tentang parser, meskipun mereka tidak sepenuhnya tentang perbedaan antara LL dan LR.