Perbandingan teori bahasa tata bahasa LL dan LR

67

Orang sering mengatakan bahwa parser LR (k) lebih kuat daripada parser LL (k) . Pernyataan-pernyataan ini sebagian besar tidak jelas; khususnya, haruskah kita membandingkan kelas untuk tetap atau serikat atas semua ? Jadi bagaimana sebenarnya situasinya? Secara khusus, saya tertarik pada bagaimana LL (*) cocok.kk

Sejauh yang saya tahu, set tata bahasa masing-masing yang diterima oleh LL dan LR parser adalah ortogonal, jadi mari kita bicara tentang bahasa yang dihasilkan oleh masing-masing tata bahasa. Biarkan menunjukkan kelas bahasa yang dihasilkan oleh tata bahasa yang dapat diuraikan oleh pengurai , dan serupa untuk kelas lainnya.LR(k)LR(k)

Saya tertarik pada hubungan berikut:

  • LL(k)?LR(k)
  • i=1LL(k)?i=1LR(k)
  • i=1LL(k)=?LL()
  • LL()?i=1LR(k)

Beberapa di antaranya mungkin mudah; tujuan saya adalah mengumpulkan perbandingan "lengkap". Referensi dihargai.

Raphael
sumber
2
Mungkin ini bisa membantu Anda! Gambar Tata Bahasa Hirarki
Andrea Tucci
1
@ AndreaTucci: Ya, tapi itu hanya mencakup tata bahasa, bukan bahasa yang dihasilkan.
Raphael

Jawaban:

60

Ada banyak penahanan yang diketahui. Biarkan menunjukkan kontainmen dan kontainmen yang tepat. Biarkan menunjukkan ketidakterbandingan.×

Biarkan , .LL=kLL(k)LR=kLR(k)

Tingkat tata bahasa

Untuk LL

  • LL(0)LL(1)LL(2)LL(2)LL(k)LLLL()
  • SLL(1)=LL(1),SLL(k)LL(k),SLL(k+1)×LL(k)

Sebagian besar ini terbukti dalam Properties tata bahasa top-down deterministik oleh Rosenkrantz dan Stearns. adalah latihan yang agak sepele. Presentasi oleh Terence Parr ini menempatkan pada slide 13. Makalah Tata bahasa LL-regular oleh Jarzabek dan Krawczyk menunjukkan , dan buktinya secara sepele meluas keSLL(k+1)×LL(k)LL()LLLLRLLLL()

Untuk LR

  • LR(0)SLR(1)LALR(1)LR(1)
  • SLR(k)LALR(k)LR(k)
  • SLR(1)SLR(2)SLR(k)
  • LALR(1)LALR(2)LALR(k)
  • LR(0)LR(1)LR(2)LR(k)LR

Ini semua adalah latihan sederhana.

LL versus LR

  • LL(k)LR(k) ( Properti tata bahasa top-down deterministik ditambah tata bahasa rekursif kiri)
  • LL(k)×SLR(k),LALR(k),LR(k1) (latihan sederhana)
  • LLLR (tata bahasa rekursif kiri)
  • LL()×LR (rekursi kiri versus lookahead sewenang-wenang)

Tingkat bahasa

Untuk LL

  • LL(0)LL(1)LL(2)LL(k)LLLL()
  • SLL(k)=LL(k)

Sebagian besar ini terbukti dalam Properti tata bahasa top-down deterministik . Masalah kesetaraan untuk tata bahasa LL- dan LR-reguler oleh Nijholt membuat referensi ke makalah yang menunjukkan . Makalah tata bahasa LL-reguler oleh Jarzabek dan Krawczyk menunjukkan , dan bukti mereka sepele meluas keLL(k)LL()LLLLRLLLL()

Untuk LR

  • LR(0)SLR(1)=LALR(1)=LR(1)=SLR(k)=LALR(k)=LR(k)=LR

Beberapa di antaranya dibuktikan oleh Knuth dalam makalahnya. Pada Terjemahan Bahasa dari Kiri ke Kanan di mana ia memperkenalkan LR (k), sisanya terbukti dalam Mengubah LR (k) Tata Bahasa menjadi LR (1), SLR (1), dan (1,1) Tata Bahasa Konteks Kanan Terbatas oleh Mickunas et al.

LL versus LR

  • LLLR(1) (kontainmen mengikuti dari di atas, adalah contoh kanonik untuk kontainmen ketat){aibj|ij}
  • LL()×LR (bahasa menunjukkan separuh klaim, dan pengenalan masalah kesetaraan untuk tata bahasa biasa LL- dan LR oleh Nijholt membuat referensi ke makalah menunjukkan setengah lainnya){aibj|ij}
  • LR(1)=DCFL (lihat misalnya referensi di sini ).
Alex ten Brink
sumber
Namun jawaban yang sangat baik, saya sudah terbalik. Saya akan berpikir Frank deRemer membuktikan LALR <= LR dalam makalah LALR aslinya? (1969?)
user207421
@ EJP: langsung jika Anda mendefinisikan dengan menciutkan status . deRemer hanya membuktikan bahwa konstruksinya menciptakan parser yang sama. Kelas tata bahasa tidak sama, yang merupakan latihan yang bagus (atau bahkan pertanyaan yang bagus untuk situs ini). Kesetaraan kelas bahasa jauh lebih rumit: baca koran jika Anda benar-benar menginginkan detail;)LALR(k)LR(k)LALRLR
Alex ten Brink
1
@AlextenBrink Saya memang membaca koran, dan diajar oleh Frank de Remer, tapi sudah 30 tahun lebih ;-) Terima kasih atas semua detailnya.
user207421
Mungkin bagus untuk mengumpulkan contoh tata bahasa untuk setiap ketidaksetaraan.
o11c
1
@ o11c Saya pikir itu akan membebani satu jawaban. Kesan saya adalah bahwa Alex memberikan referensi yang baik jika perlu; ia menyatakan "olahraga ringan" untuk beberapa orang. Saya kira jika seorang pembaca tidak dapat membuat tata bahasa, mereka dapat memposting pertanyaan baru yang menanyakan kasus spesifik tersebut.
Raphael