Apa perbedaan antara parser LR, SLR, dan LALR?

Apa perbedaan sebenarnya antara pengurai LR, SLR, dan LALR? Saya tahu bahwa SLR dan LALR adalah jenis parser LR, tetapi apa perbedaan sebenarnya sejauh menyangkut tabel parsing mereka?

Dan bagaimana cara menunjukkan apakah sebuah tata bahasa adalah LR, SLR, atau LALR? Untuk tata bahasa LL kita hanya perlu menunjukkan bahwa sel tabel parsing tidak boleh berisi beberapa aturan produksi. Adakah aturan serupa untuk LALR, SLR, dan LR?

Misalnya, bagaimana kita bisa menunjukkan tata bahasa itu

S --> Aa | bAc | dc | bda
A --> d

itu LALR (1) tapi bukan SLR (1)?

EDIT (ybungalobill) : Saya tidak mendapatkan jawaban yang memuaskan untuk apa perbedaan antara LALR dan LR. Jadi tabel LALR berukuran lebih kecil tetapi hanya dapat mengenali subset dari tata bahasa LR. Bisakah seseorang menjelaskan lebih lanjut tentang perbedaan antara LALR dan LR? LALR (1) dan LR (1) akan cukup untuk sebuah jawaban. Keduanya menggunakan 1 token di depan dan keduanya digerakkan oleh tabel! Bagaimana mereka berbeda?

Parser SLR, LALR dan LR semuanya dapat diimplementasikan menggunakan mesin berbasis tabel yang sama persis.

Pada dasarnya, algoritme parsing mengumpulkan token input T berikutnya, dan berkonsultasi dengan status S saat ini (dan tabel lookahead, GOTO, dan reduksi terkait) untuk memutuskan apa yang harus dilakukan:

• SHIFT: Jika tabel saat ini mengatakan untuk SHIFT pada token T, pasangan (S, T) didorong ke tumpukan parse, status diubah sesuai dengan apa yang tabel GOTO katakan untuk token saat ini (misalnya, GOTO (T) ), token masukan lain T 'diambil, dan prosesnya berulang
• MENGURANGI: Setiap negara bagian memiliki 0, 1, atau banyak kemungkinan pengurangan yang mungkin terjadi di negara bagian tersebut. Jika parser adalah LR atau LALR, token akan diperiksa terhadap kumpulan lookahead untuk semua pengurangan yang valid untuk status tersebut. Jika token cocok dengan lookahead yang ditetapkan untuk pengurangan aturan tata bahasa G = R1 R2 .. Rn, pengurangan tumpukan dan pergeseran terjadi: tindakan semantik untuk G dipanggil, tumpukan muncul n (dari Rn) kali, pasangan ( S, G) didorong ke tumpukan, status baru S 'diatur ke GOTO (G), dan siklus berulang dengan token yang sama T.Jika pengurai adalah pengurai SLR, paling banyak ada satu aturan pengurangan untuk keadaan dan tindakan reduksi dapat dilakukan secara membabi buta tanpa mencari untuk melihat pengurangan mana yang berlaku. Hal ini berguna untuk parser SLR tahu apakah ada yangpengurangan atau tidak; ini mudah untuk mengetahui apakah setiap negara bagian secara eksplisit mencatat jumlah pengurangan yang terkait dengannya, dan penghitungan itu diperlukan untuk versi L (AL) R dalam praktiknya.
• EROR: Jika SHIFT atau REDUCE tidak dimungkinkan, kesalahan sintaksis dideklarasikan.

Jadi, jika mereka semua menggunakan mesin yang sama, apa gunanya?

Nilai yang diklaim dalam SLR adalah kesederhanaannya dalam implementasi; Anda tidak perlu memindai melalui kemungkinan pengurangan memeriksa kumpulan lookahead karena paling banyak ada satu, dan ini adalah satu-satunya tindakan yang dapat dilakukan jika tidak ada SHIFT keluar dari status. Pengurangan mana yang berlaku dapat dilampirkan secara khusus ke status, sehingga mesin pengurai SLR tidak perlu memburunya. Dalam praktiknya, parser L (AL) R menangani sekumpulan bahasa yang lebih besar dan berguna, dan sangat sedikit pekerjaan tambahan untuk diterapkan sehingga tidak ada yang mengimplementasikan SLR kecuali sebagai latihan akademis.

Perbedaan antara LALR dan LR berkaitan dengan generator tabel. Generator parser LR melacak semua kemungkinan pengurangan dari status tertentu dan set lookahead yang tepat; Anda berakhir dengan status di mana setiap pengurangan dikaitkan dengan lookahead persisnya yang ditetapkan dari konteks kirinya. Ini cenderung membangun kumpulan negara bagian yang agak besar. Generator parser LALR bersedia menggabungkan status jika tabel GOTO dan set lookhead untuk pengurangan kompatibel dan tidak bertentangan; ini menghasilkan jumlah status yang jauh lebih kecil, dengan harga tidak dapat membedakan rangkaian simbol tertentu yang dapat dibedakan oleh LR. Jadi, pengurai LR dapat mengurai sekumpulan bahasa yang lebih besar daripada pengurai LALR, tetapi memiliki tabel parser yang jauh lebih besar. Dalam praktiknya, seseorang dapat menemukan tata bahasa LALR yang cukup dekat dengan bahasa target sehingga ukuran mesin status layak untuk dioptimalkan;

Jadi: Ketiganya menggunakan mesin yang sama. SLR adalah "mudah" dalam arti bahwa Anda dapat mengabaikan sedikit mesin tetapi itu tidak sebanding dengan masalahnya. LR mem-parsing serangkaian bahasa yang lebih luas tetapi tabel status cenderung cukup besar. Itu membuat LALR sebagai pilihan praktis.

Setelah mengatakan semua ini, perlu diketahui bahwa pengurai GLR dapat mengurai bahasa bebas konteks apa pun, menggunakan mesin yang lebih rumit tetapi tabel yang persis sama (termasuk versi yang lebih kecil yang digunakan oleh LALR). Ini berarti GLR benar-benar lebih bertenaga daripada LR, LALR dan SLR; cukup banyak jika Anda dapat menulis tata bahasa BNF standar, GLR akan mengurai sesuai dengan itu. Perbedaan dalam permesinan adalah GLR bersedia untuk mencoba beberapa parse ketika ada konflik antara tabel GOTO dan atau set lookahead. (Bagaimana GLR melakukan ini secara efisien adalah jenius belaka [bukan milik saya] tetapi tidak akan muat dalam posting SO ini).

Bagi saya itu adalah fakta yang sangat berguna. Saya membangun penganalisis program dan transformator kode dan parser diperlukan tetapi "tidak menarik"; pekerjaan yang menarik adalah apa yang Anda lakukan dengan hasil parsing sehingga fokusnya adalah melakukan pekerjaan pasca parsing. Menggunakan GLR berarti saya dapat dengan mudah membangun tata bahasa yang berfungsi, dibandingkan dengan meretas tata bahasa untuk masuk ke bentuk yang dapat digunakan LALR. Ini sangat penting ketika mencoba berurusan dengan bahasa non-akademis seperti C ++ atau Fortran, di mana Anda benar-benar membutuhkan ribuan aturan untuk menangani seluruh bahasa dengan baik, dan Anda tidak ingin menghabiskan hidup Anda mencoba meretas aturan tata bahasa ke memenuhi batasan LALR (atau bahkan LR).

Sebagai contoh terkenal, C ++ dianggap sangat sulit untuk diurai ... oleh orang yang melakukan penguraian LALR. C ++ mudah diurai menggunakan mesin GLR menggunakan hampir semua aturan yang disediakan di bagian belakang manual referensi C ++. (Saya memiliki parser seperti itu, dan tidak hanya menangani vanilla C ++, tetapi juga berbagai dialek vendor. Ini hanya mungkin dalam praktiknya karena kami menggunakan pengurai GLR, IMHO).

[EDIT November 2011: Kami telah memperluas parser kami untuk menangani semua C ++ 11. GLR membuatnya jauh lebih mudah untuk dilakukan. EDIT Agustus 2014: Sekarang menangani semua C ++ 17. Tidak ada yang rusak atau bertambah buruk, GLR tetaplah mengeong kucing.]

Parser LALR menggabungkan status yang sama dalam tata bahasa LR untuk menghasilkan tabel status parser yang berukuran persis sama dengan tata bahasa SLR yang setara, yang biasanya urutan besarnya lebih kecil daripada tabel parsing LR murni. Namun, untuk tata bahasa LR yang terlalu kompleks untuk menjadi LALR, status gabungan ini mengakibatkan konflik parser, atau menghasilkan parser yang tidak sepenuhnya mengenali tata bahasa LR asli.

BTW, saya menyebutkan beberapa hal tentang ini dalam algoritma tabel parsing MLR (k) saya di sini .

Tambahan

Jawaban singkatnya adalah bahwa tabel penguraian LALR lebih kecil, tetapi mesin pengurai sama. Tata bahasa LALR tertentu akan menghasilkan tabel parsing yang jauh lebih besar jika semua status LR dihasilkan, dengan banyak status redundan (hampir identik).

Tabel LALR lebih kecil karena status yang mirip (redundan) digabungkan bersama, secara efektif membuang info konteks / lookahead yang dikodekan oleh status terpisah. Keuntungannya adalah Anda mendapatkan tabel parsing yang jauh lebih kecil untuk tata bahasa yang sama.

Kekurangannya adalah tidak semua tata bahasa LR dapat dienkode sebagai tabel LALR karena tata bahasa yang lebih kompleks memiliki lookahead yang lebih rumit, yang menghasilkan dua atau lebih status daripada satu status gabungan.

Perbedaan utamanya adalah bahwa algoritma untuk menghasilkan tabel LR membawa lebih banyak informasi antara transisi dari satu negara bagian ke negara bagian lain sedangkan algoritma LALR tidak. Jadi, algoritme LALR tidak dapat mengetahui apakah status gabungan tertentu benar-benar harus dibiarkan sebagai dua atau lebih status terpisah.

Namun jawaban lain (YAA).

Algoritma parsing untuk SLR (1), LALR (1) dan LR (1) identik seperti yang dikatakan Ira Baxter,
namun, tabel parser mungkin berbeda karena algoritma generasi parser.

Generator parser SLR membuat mesin status LR (0) dan menghitung pandangan ke depan dari tata bahasa (set FIRST dan FOLLOW). Ini adalah pendekatan yang disederhanakan dan mungkin melaporkan konflik yang tidak benar-benar ada di mesin status LR (0).

Generator parser LALR membuat mesin status LR (0) dan menghitung pandangan ke depan dari mesin status LR (0) (melalui transisi terminal). Ini adalah pendekatan yang benar, tetapi terkadang melaporkan konflik yang tidak akan ada di mesin status LR (1).

Generator parser LR Canonical menghitung mesin status LR (1) dan pandangan ke depan sudah menjadi bagian dari mesin status LR (1). Tabel parser ini bisa sangat besar.

Generator parser LR Minimal menghitung mesin status LR (1), tetapi menggabungkan status yang kompatibel selama proses, dan kemudian menghitung pandangan ke depan dari mesin status LR minimal (1). Tabel parser ini berukuran sama atau sedikit lebih besar dari tabel parser LALR, memberikan solusi terbaik.

LRSTAR 10.0 dapat menghasilkan parser LALR (1), LR (1), CLR (1) atau LR (*) dalam C ++, apa pun yang diperlukan untuk tata bahasa Anda. Lihat diagram ini yang menunjukkan perbedaan antara pengurai LR.

[Pengungkapan penuh: LRSTAR adalah produk saya]

Misalkan seorang parser tanpa lookahead dengan senang hati mengurai string untuk tata bahasa Anda.

Menggunakan contoh yang Anda berikan, ia menemukan sebuah string dc, apa fungsinya? Apakah itu menguranginya menjadi S, karena dcapakah string valid dihasilkan oleh tata bahasa ini? ATAU mungkin kami mencoba mengurai bdckarena bahkan itu adalah string yang dapat diterima?

Sebagai manusia kita tahu jawabannya sederhana, kita hanya perlu mengingat apakah kita baru saja mengurai batau belum. Tapi komputer itu bodoh :)

Karena parser SLR (1) memiliki kekuatan tambahan atas LR (0) untuk melakukan lookahead, kita tahu bahwa sejumlah lookahead tidak dapat memberi tahu kita apa yang harus dilakukan dalam kasus ini; sebaliknya, kita perlu melihat kembali masa lalu kita. Jadi datang pengurai LR kanonik untuk menyelamatkan. Ini mengingat konteks masa lalu.

Cara mengingat konteks ini adalah bahwa ia mendisiplinkan dirinya sendiri, bahwa setiap kali ia menemukan a b, ia akan mulai berjalan di jalur menuju membaca bdc, sebagai salah satu kemungkinan. Jadi ketika ia melihat a dia tahu apakah ia sudah berjalan di jalan setapak. Jadi parser CLR (1) dapat melakukan hal-hal yang tidak dapat dilakukan oleh parser SLR (1)!

Tapi sekarang, karena kami harus mendefinisikan begitu banyak jalur, status mesin menjadi sangat besar!

Jadi kami menggabungkan jalur yang tampak sama, tetapi seperti yang diharapkan itu bisa menimbulkan masalah kebingungan. Namun, kami bersedia mengambil risiko dengan biaya mengurangi ukuran.

Ini adalah parser LALR (1) Anda.

Sekarang bagaimana melakukannya secara algoritmik.

Saat Anda menggambar set konfigurasi untuk bahasa di atas, Anda akan melihat konflik shift-kurangi dalam dua kondisi. Untuk menghapusnya, Anda mungkin ingin mempertimbangkan SLR (1), yang mengambil keputusan berdasarkan mengikuti, tetapi Anda akan mengamati bahwa itu masih tidak dapat melakukannya. Jadi Anda akan, menggambar set konfigurasi lagi tetapi kali ini dengan batasan bahwa setiap kali Anda menghitung penutupan, produksi tambahan yang ditambahkan harus mengikuti secara ketat. Rujuk buku teks apa pun tentang apa yang harus diikuti berikut ini.

Perbedaan mendasar antara tabel parser yang dihasilkan dengan SLR vs LR, adalah bahwa tindakan pengurangan didasarkan pada set berikut untuk tabel SLR. Ini bisa menjadi terlalu membatasi, pada akhirnya menyebabkan konflik pengurangan-shift.

Di sisi lain, parser LR basis mengurangi keputusan hanya pada set terminal yang benar-benar dapat mengikuti pengurangan non-terminal. Rangkaian terminal ini sering kali merupakan subset yang tepat dari himpunan Follows dari non-terminal semacam itu, dan oleh karena itu memiliki peluang konflik yang lebih kecil dengan tindakan shift.

Pengurai LR lebih kuat karena alasan ini. Namun, tabel penguraian LR bisa sangat besar.

Pengurai LALR dimulai dengan ide untuk membuat tabel penguraian LR, tetapi menggabungkan status yang dihasilkan sedemikian rupa sehingga ukuran tabel jauh lebih kecil. Sisi negatifnya adalah bahwa kemungkinan kecil konflik akan diperkenalkan untuk beberapa tata bahasa yang seharusnya dihindari oleh tabel LR.

Pengurai LALR sedikit kurang bertenaga dibandingkan pengurai LR, tetapi masih lebih bertenaga daripada pengurai SLR. YACC dan generator parser lainnya cenderung menggunakan LALR karena alasan ini.

PS Untuk singkatnya, SLR, LALR dan LR di atas benar-benar berarti SLR (1), LALR (1), dan LR (1), jadi tersirat satu token lookahead.

Parser SLR mengenali subset tata bahasa yang tepat yang dapat dikenali oleh parser LALR (1), yang kemudian mengenali subset tata bahasa yang tepat yang dapat dikenali oleh parser LR (1).

Masing-masing dibangun sebagai mesin negara, dengan setiap negara bagian mewakili beberapa set aturan produksi tata bahasa (dan posisi di masing-masing) saat mengurai input.

Contoh Dragon Book dari tata bahasa LALR (1) yang bukan SLR adalah ini:

S → L = R | R
L → * R | id
R → L

Berikut adalah salah satu kondisi untuk tata bahasa ini:

S → L•= R
R → L•

The •menunjukkan posisi parser di masing-masing produksi mungkin. Ia tidak tahu di mana produksi itu sebenarnya sampai mencapai akhir dan mencoba untuk mengurangi.

Di sini, pengurai dapat menggeser =atau mengurangi R → L.

SLR (alias LR (0)) parser akan menentukan apakah itu bisa mengurangi dengan memeriksa jika simbol input berikutnya adalah di follow set dari R(yaitu, himpunan semua terminal dalam tata bahasa yang dapat mengikuti R). Karena =juga dalam set ini, pengurai SLR mengalami konflik pengurangan-pergeseran.

Namun, parser LALR (1) akan menggunakan himpunan semua terminal yang dapat mengikuti produksi khusus R ini, yang hanya $(yaitu, akhir input). Jadi, tidak ada konflik.

Seperti yang telah dicatat oleh pemberi komentar sebelumnya, pengurai LALR (1) memiliki jumlah status yang sama dengan pengurai SLR. Algoritme propagasi lookahead digunakan untuk menangani lookahead ke produksi status SLR dari status LR (1) yang sesuai. Pengurai LALR (1) yang dihasilkan dapat menyebabkan konflik pengurangan-pengurangan yang tidak ada dalam pengurai LR (1), tetapi tidak dapat menyebabkan konflik pengurangan-pengurangan.

Dalam contoh Anda , status LALR (1) berikut ini menyebabkan konflik pengurangan-shift dalam implementasi SLR:

S → b d•a / $
A → d• / c

Simbol setelah /adalah set berikut untuk setiap produksi di parser LALR (1). Dalam SLR, follow ( A) termasuk a, yang juga bisa digeser.

Selain jawaban di atas, diagram ini menunjukkan bagaimana pengurai yang berbeda berhubungan:

Satu jawaban sederhana adalah bahwa semua tata bahasa LR (1) adalah tata bahasa LALR (1). Dibandingkan dengan LALR (1), LR (1) memiliki lebih banyak status dalam mesin kondisi hingga terkait (lebih dari dua kali lipat status). Dan itulah alasan utama tata bahasa LALR (1) membutuhkan lebih banyak kode untuk mendeteksi kesalahan sintaks daripada tata bahasa LR (1). Dan satu hal lagi yang penting untuk diketahui tentang kedua tata bahasa ini adalah bahwa dalam tata bahasa LR (1) kita mungkin memiliki lebih sedikit pengurangan / pengurangan konflik. Namun dalam LALR (1) lebih banyak kemungkinan untuk mengurangi / mengurangi konflik.