Perbedaan utama antara penguraian top down dan bottom up adalah bahwa penguraian atas ke bawah melakukan penguraian dari simbol menatap ke string input sementara penguraian bawah ke bawah melakukan penguraian dari string input ke simbol awal. Selanjutnya, perbedaan penting lainnya antara penguraian top down dan bottom up adalah bahwa penguraian top down menggunakan derivasi paling kiri dan penguraian bottom down menggunakan derivasi paling kanan.
Bahasa tingkat tinggi membantu menulis program komputer. Mereka lebih mudah dipahami oleh programmer tetapi tidak oleh komputer. Oleh karena itu, program tingkat tinggi dikonversi ke kode mesin. Tugas kompiler adalah mengubah kode sumber yang dapat dibaca manusia menjadi kode mesin yang dapat dibaca mesin. Sebuah program melewati beberapa langkah untuk mengkonversi ke kode mesin. Keseluruhan proses ini disebut Sistem Pemrosesan Bahasa. Salah satunya adalah kompilasi. Penganalisis sintaks atau pengurai ada di dalam kompiler, dan ia melakukan tugas penguraian.
ISI
1. Ikhtisar dan Perbedaan Utama
2. Apa itu Parsing Top Down?
3. Apa itu Parsing Bawah?
4. Perbandingan Berdampingan - Parsing Top Down vs Bottom Up dalam Bentuk Tabular
5. Ringkasan
Apa itu Parsing Top Down?
Setiap bahasa pemrograman memiliki seperangkat aturan untuk mewakili bahasa tersebut. Penganalisis sintaks atau parse mengambil string input dan memeriksa apakah itu sesuai dengan produksi tata bahasa. Dengan kata lain, tata bahasa harus menghasilkan string itu menggunakan pohon parse.
Dalam penguraian top down, penguraian terjadi dari simbol awal dan akan mencapai string input yang diberikan. Pertimbangkan aturan produksi tata bahasa berikut. String input (w) adalah cad.
S -> cAd
A -> ab /a
Pohon parse setelah melakukan parsing top down adalah sebagai berikut.
Gambar 01: Parse Tree 1 dengan Top Down Parsing
S menghasilkan c A d dan A menghasilkan a b. String adalah cabd. Ini bukan string yang diperlukan. Sehingga perlu dilakukan backtracking, yaitu menggunakan alternatif lain.
Demikian pula, S menghasilkan c A d. Menerapkan opsi lain untuk A akan memberikan a. Sekarang ia memberikan string yang diperlukan. Oleh karena itu, parser menerima string input ini. Pohon parse setelah melakukan parsing top down adalah sebagai berikut.
Gambar 02: Parse Tree 2 dengan Top Down Parsing
Ketika string input (w) adalah abcde
Pertimbangkan aturan produksi tata bahasa berikut.
S -> aABe
A -> Abc/b
B -> d
Dalam penguraian atas ke bawah,
S -> aABe (Mengganti A -> Abc)
S -> aAbcBe (Mengganti A -> b)
S -> abbcBe (Mengganti B ->d)
S -> abcde
Pergantian dimulai dengan variabel paling kiri terlebih dahulu dan kemudian ke posisi kanan berikutnya dan seterusnya. Oleh karena itu, ia mengikuti metode derivasi paling kiri. Selanjutnya, penting untuk memutuskan aturan produksi apa yang harus dipilih ketika ada variabel.
Apa itu Penguraian Bawah ke Atas?
Di bottom up parsing terjadi dengan cara lain. Penguraian terjadi dari string input ke simbol awal. Pertimbangkan aturan produksi tata bahasa berikut dan biarkan string input menjadi w cad
S -> cAd
A -> ab /a
Pohon parse setelah melakukan parsing bottom up adalah sebagai berikut.
Gambar 03: Pohon Parse dengan Parsing Bottom Up
String yang diberikan adalah cad. A dihasilkan oleh A. C, A dan d bergabung untuk mendapatkan simbol awal S.
Ketika string input (w) adalah abcde
Pertimbangkan aturan produksi tata bahasa berikut.
S -> aABe
A -> Abc/b
B -> d
Dalam penguraian dari bawah ke atas,
S -> aABe (Mengganti B ->d)
S -> aAde (Mengganti A -> Abc)
S -> aAbcde (Mengganti A -> b)
S -> abcde
Pergantian dimulai dengan variabel paling kanan terlebih dahulu dan kemudian pindah ke posisi kiri berikutnya dan seterusnya. Oleh karena itu, ia mengikuti metode derivasi gerak kiri.
Apa Perbedaan Antara Parsing Top Down dan Bottom Up?
Parsing top-down adalah strategi parsing yang pertama kali melihat level tertinggi dari parse tree dan bekerja menuruni parse tree dengan menggunakan aturan tata bahasa formal. Penguraian bottom up adalah strategi penguraian yang pertama kali melihat level terendah dari pohon penguraian dan mengerjakan pohon penguraian dengan menggunakan aturan tata bahasa formal. Penguraian terjadi dari simbol awal ke string input, dalam penguraian top down. Di sisi lain, penguraian terjadi dari string input ke simbol awal, di penguraian bawah ke atas.
Selanjutnya, keputusan utama dalam parsing top down adalah memilih aturan produksi apa yang akan digunakan untuk membangun string sedangkan keputusan utama dalam parsing bottom down adalah memilih kapan menggunakan aturan produksi untuk mengurangi string untuk mendapatkan simbol awal. Selain itu, parsing top down menggunakan derivasi paling kiri dan parsing bottom down menggunakan derivasi paling kanan.
Ringkasan – Parsing Top Down vs Bottom Up
Perbedaan antara penguraian atas ke bawah dan penguraian bawah ke atas adalah bahwa penguraian atas ke bawah melakukan penguraian dari simbol menatap ke string input sementara penguraian bawah ke bawah melakukan penguraian dari string input ke simbol awal.
Referensi:
1.“Kuliah Desain Kompilator 5 — Pengantar Parser dan LL(1) Parsing.” Kuliah Desain Penyusun 5 — Pengantar Parser dan Parsing LL(1) , Kuliah Gerbang oleh Ravindrababu Ravula, 22 Mei 2014. Tersedia di sini
