Desain Penyusun - Parser Bottom-Up

Penguraian bottom-up dimulai dari simpul daun pohon dan bekerja ke arah atas hingga mencapai simpul akar. Di sini, kita mulai dari sebuah kalimat dan kemudian menerapkan aturan produksi secara terbalik untuk mencapai simbol awal. Gambar yang diberikan di bawah ini menggambarkan parser bottom-up yang tersedia.

Shift-Reduce Parsing

Penguraian pengurangan-shift menggunakan dua langkah unik untuk penguraian dari bawah ke atas. Langkah-langkah ini disebut shift-step dan reduce-step.

• Shift step: Langkah shift mengacu pada kemajuan penunjuk masukan ke simbol masukan berikutnya, yang disebut simbol bergeser. Simbol ini didorong ke tumpukan. Simbol yang digeser diperlakukan sebagai simpul tunggal dari pohon parse.

• Reduce step: Jika parser menemukan aturan tata bahasa lengkap (RHS) dan menggantinya ke (LHS), ini dikenal sebagai langkah reduksi. Ini terjadi ketika bagian atas tumpukan berisi pegangan. Untuk mengurangi, fungsi POP dilakukan pada tumpukan yang keluar dari pegangan dan menggantikannya dengan simbol non-terminal LHS.

LR Parser

Parser LR adalah parser non-rekursif, shift-reduce, dan bottom-up. Ini menggunakan kelas luas dari tata bahasa bebas konteks yang menjadikannya teknik analisis sintaks yang paling efisien. Pengurai LR juga dikenal sebagai pengurai LR (k), di mana L adalah singkatan dari pemindaian kiri-ke-kanan dari aliran input; R berarti konstruksi derivasi paling kanan secara terbalik, dan k menunjukkan jumlah simbol lookahead untuk membuat keputusan.

Ada tiga algoritme yang banyak digunakan yang tersedia untuk membangun parser LR:

• SLR (1) - Parser LR Sederhana:
  • Bekerja pada kelas tata bahasa terkecil
  • Sedikit jumlah negara bagian, maka tabelnya sangat kecil
  • Konstruksi sederhana dan cepat
• LR (1) - Parser LR:
  • Bekerja pada set lengkap Tata Bahasa LR (1)
  • Menghasilkan tabel besar dan sejumlah besar status
  • Konstruksi lambat
• LALR (1) - Parser LR Look-Ahead:
  • Bekerja pada ukuran tata bahasa menengah
  • Jumlah negara bagian sama seperti di SLR (1)

Algoritma Parsing LR

Di sini kami menjelaskan algoritme kerangka dari pengurai LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL vs. LR

LL	LR
Melakukan derivasi paling kiri.	Melakukan derivasi paling kanan secara terbalik.
Mulailah dengan root nonterminal di stack.	Akhiri dengan akar nonterminal di tumpukan.
Berakhir saat tumpukan kosong.	Dimulai dengan tumpukan kosong.
Menggunakan tumpukan untuk menentukan apa yang masih diharapkan.	Menggunakan tumpukan untuk menunjukkan apa yang sudah terlihat.
Membangun pohon parse dari atas ke bawah.	Membangun pohon parse dari bawah ke atas.
Secara terus menerus mengeluarkan nonterminal dari tumpukan, dan mendorong sisi kanan yang sesuai.	Mencoba mengenali sisi kanan pada tumpukan, meletuskannya, dan mendorong nonterminal yang sesuai.
Perluas non-terminal.	Mengurangi non-terminal.
Membaca terminal saat meletuskan salah satu dari tumpukan.	Membaca terminal saat mendorongnya ke tumpukan.
Praorder traversal dari pohon parse.	Traversal pasca-pesanan dari pohon parse.