Parsing Sudut Kiri (Left Corner Parsing)
Definisi
Parsing sudut kiri (Left Corner Parsing) adalah teknik parsing topdown yang memanfaatkan informasi dari sisi kiri (left corner) dari sebuah aturan produksi untuk memandu proses analisis sintaks. Ide dasarnya adalah menggabungkan karakteristik parsing topdown (predictive) dan bottomup (shiftreduce) sehingga parser dapat membuat prediksi yang lebih akurat dan mengurangi backtracking.
Prinsip Kerja
Setiap produksi dalam tata bahasa bentuk A memiliki left corner yaitu simbol pertama . Saat parser menemukan simbol di input, ia dapat menebak bahwa produksi A mungkin sedang dibangun, meskipun belum melihat seluruh . Dengan memanfaatkan tabel leftcorner, parser dapat:
- Mengidentifikasi candidate nonterminals yang dapat menghasilkan simbol yang sedang dibaca.
- Menghindari prediksi yang tidak mungkin dengan memeriksa kecocokan left corner terlebih dahulu.
- Menjaga struktur parsial yang sudah terbentuk (seperti pada bottomup) sambil tetap melakukan prediksi (seperti pada topdown).
Contoh Tata Bahasa dan Tabel Left Corner
Misalkan kita memiliki tata bahasa sederhana untuk ekspresi aritmatika:
E T E'E' + T E' | T F T'T' * F T' | F ( E ) | id
Tabel leftcorner dapat dibangun dengan mengisi sel (A, a) bila a adalah left corner dari produksi A . Hasilnya:
id ( + * )E E' T T' F
Jika token selanjutnya adalah id, parser melihat bahwa E, T, F semuanya mungkin, sehingga ia menambah statestate yang diperlukan untuk mengecek produksi selanjutnya.
Perbandingan dengan Metode Lain
Berikut perbandingan singkat antara leftcorner, LL(k), dan LR(k):
| Aspek | LL(k) | LR(k) | Left Corner |
|---|---|---|---|
| Strategi | Topdown murni | Bottomup murni | Hybrid topdown & bottomup |
| Backtracking | Sering diperlukan | Jarang | Minim, karena leftcorner pruned |
| Ukuran tabel | Relatif kecil | Relatif besar | Menengah, tergantung banyaknya left corners |
| Kemampuan menangani ambigu | Terbatas | Baik | Lebih baik daripada LL, hampir setara LR |
Kelebihan & Kekurangan
Kelebihan
- Mengurangi jumlah prediksi yang tidak relevan.
- Mendukung grammar yang tidak cocok untuk parsing LL(k) tanpa harus mengubahnya menjadi bentuk yang sangat terstruktur.
- Dapat diintegrasikan dengan algoritma chart parsing untuk meningkatkan efisiensi.
Kekurangan
- Membutuhkan tabel leftcorner tambahan, sehingga memakan memori lebih banyak daripada LL(k) sederhana.
- Implementasinya lebih kompleks dibanding parser topdown konvensional.
- Jika grammar sangat ambigu, keuntungan pruning dapat berkurang.
Implementasi Dasar
Berikut contoh pseudocode singkat untuk parser leftcorner berbasis agenda:
initialize agenda with start symbol Swhile agenda not empty: state = agenda.pop() if state expects terminal t and next token == t: advance input else if state expects nonterminal A: for each production A : if leftCorner() matches next token: push new state with production A else if state is completed: for each parent state that was waiting for A: push parent state advanced past A
Pseudocode ini menekankan dua operasi utama: mencocokkan left corner sebelum membuat prediksi, dan menggabungkan kembali state yang selesai (seperti pada bottomup).
