Perbedaan utama 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. 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 kompilator, dan ia melakukan tugas penguraian.
Apa itu Top Down Parsing?
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 top down parsing adalah sebagai berikut.
Gambar 01: Parse Tree 1 dengan Parsing Top Down
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 Parsing Top Down
Bila string input (w) adalah abbcde
Perhatikan aturan produksi tata bahasa berikut.
S -> aABe
A -> Abc/b
B -> d
Dalam penguraian top-down, S -> aABe (Mengganti A -> Abc)
S -> aAbcBe (Substitusi A -> b)
S -> abbcBe (Mengganti B ->d)
S -> abbcde
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 Bottom Up Parsing?
Dalam penguraian bottom up terjadi sebaliknya. 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: Parse Tree dengan Bottom Up Parsing
String yang diberikan adalah cad. A dihasilkan oleh A. C, A dan d bergabung untuk mendapatkan simbol awal S.
Bila string input(w) adalah abbcde
Perhatikan aturan produksi tata bahasa berikut.
S -> aABe
A -> Abc/b
B -> d
Dalam penguraian dari bawah ke atas, S -> aABe (Substitusi B ->d)
S -> aAde (Pengganti A -> Abc)
S -> aAbcde (Mengganti A -> b)
S -> abbcde
Pergantian dimulai dengan variabel paling kanan terlebih dahulu dan kemudian pindah ke posisi kiri berikutnya dan seterusnya. Oleh karena itu, ia mengikuti metode turunan mot kiri.
Apa Perbedaan Parsing Top Down dan Bottom Up?
Penguraian top-down adalah strategi penguraian yang pertama kali melihat tingkat tertinggi dari pohon penguraian dan bekerja ke bawah pohon penguraian dengan menggunakan aturan tata bahasa formal. Penguraian bottom up adalah strategi penguraian yang pertama-tama melihat tingkat 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, parsing terjadi dari string input ke simbol awal, di parsing bottom up.
Selanjutnya, keputusan utama dalam penguraian top-down adalah memilih aturan produksi apa yang akan digunakan untuk membangun string sedangkan keputusan utama dalam penguraian bawah-bawah adalah memilih kapan menggunakan aturan produksi untuk mereduksi string menjadi 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 top down dan bottom up parsing adalah bahwa top down parsing melakukan parsing dari simbol menatap ke string input sedangkan bottom down parsing melakukan parsing dari input string ke simbol awal.
