Apakah ada cara untuk membedakan antara tata bahasa LL (k) dan LR (k)?

Saya baru-baru ini mempelajari tentang perancangan Compiler. Saya jadi tahu tentang dua jenis tata bahasa satu adalah tata bahasa LL dan lainnya adalah tata bahasa LR.

Kita juga tahu fakta bahwa setiap tata bahasa LL adalah LR yang tata bahasa LL adalah bagian yang tepat dari tata bahasa LR. Yang pertama digunakan dalam parsing top-down dan yang kedua digunakan dalam parsing bottom-up.

Tetapi adakah cara lain agar kita dapat mengatakan bahwa tata bahasa yang diberikan adalah LL atau LR?

L R ( k ) L L ( k ) L R ( k $LL(k)$Tata bahasa dan bagus bukan hanya karena mereka dapat diuraikan secara efisien, tetapi juga karena kita dapat memeriksa apakah tata bahasa adalah atau , dan karena kita dapat membuat tabel untuk mereka ( tabel parse digunakan untuk mengurai string input). Perhatikan bahwa untuk dua kelas ini, memiliki tabel parse segera memungkinkan Anda untuk memeriksa apakah tata bahasa di kelas, karena ini adalah jika dan hanya jika tabel tidak mengandung kesalahan. Juga, ya, ada kelas tata bahasa yang dapat kita parse secara efisien jika kita memiliki tabel parse, tetapi untuk itu kita tidak dapat membuat tabel jika ada.$LR(k)$$LL(k)$$LR(k)$

Buku teks tentang metode parsing akan mengajarkan Anda cara membuat tabel untuk metode dan mungkin juga untuk (meskipun lebih umum). Buku teks seperti Parsing Theory oleh Sippu dan Soisalon-Soininen juga memperlakukan generasi tabel parse untuk tata bahasa dan .$LL(1)$$LR(1)$$SLR(1)$$LL(k)$$LR(k)$

Sayangnya, untuk tata bahasa yang sangat aneh, tabel parse untuk dan (meskipun tidak untuk ) dapat meledak dan menjadi besar; mereka akan melakukan ini bahkan untuk tata bahasa normal jika cukup tinggi. Ada tes yang tersedia yang dapat memeriksa apakah tata bahasa adalah atau atau tidak yang berjalan dalam waktu polinomial (pembuatan tabel adalah eksponensial). Untuk detailnya, baca buku teks di atas. Perhatikan bahwa dalam banyak kasus, tabel berukuran cukup, sehingga tes tidak diperlukan.$LL(k)$$LR(k)$$LL(1)$$k$$LL(k)$$LR(k)$

Jika Anda tidak ingin mencoba nilai untuk melihat apakah program Anda berfungsi, tetapi sebaliknya ingin komputer Anda mengetahui apakah ada nilai sehingga tata bahasa Anda adalah atau , Anda sayangnya kurang beruntung, karena ini tidak dapat dipastikan. Jika tata bahasa Anda adalah untuk beberapa , Anda dapat memutuskan apakah tata bahasa Anda adalah untuk beberapa , mungkin berbeda dari (lihat di sini untuk detailnya).k L L ( k ) L R ( k ) L R ( k ) k L L ( c ) c $k$$k$$LL(k)$$LR(k)$$LR(k)$$k$$LL(c)$$c$$k$

Kita harus memeriksa hanya bahwa tata bahasa adalah LL atau tidak karena setiap tata bahasa LL adalah LR yang LL adalah subset LR yang tepat. Jadi, jika tata bahasa adalah LL maka harus LR tetapi setiap LR bukan LL.

Tata bahasa G ada di LL iff setiap kali A-> C | D, kondisi berikut ini berlaku:

1. First (C) dan First (D) adalah himpunan terpisah.
2. Jika kosong di First (D), First (C) dan Follow (A) adalah set yang terpisah juga kosong di First (C).