Perbedaan Antara Parsing Top Down dan Bottom Up
Share
Itu perbedaan utama antara parsing top down dan bottom up adalah bahwa Perintahkan ke bawah parsing melakukan parsing dari simbol menatap ke string input sedangkan parsing bawah ke bawah melakukan parsing 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 untuk mengubah kode sumber yang dapat dibaca manusia menjadi kode mesin yang dapat dibaca mesin. Suatu program melewati beberapa langkah untuk mengonversi ke kode mesin. Seluruh proses ini disebut Sistem pemrosesan Bahasa. Salah satunya adalah kompilasi. Penganalisis sintaks atau parser ada di kompiler, dan melakukan tugas parsing.
ISI
1. Ikhtisar dan Perbedaan Utama
2. Apa itu Parsing Top Down
3. Apa itu Bottom Up Parsing
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. Penganalisis sintaks atau parse mengambil string input dan memeriksa apakah itu sesuai dengan produksi tata bahasa. Dengan kata lain, tata bahasa harus menghasilkan string 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 ini. 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 Parsing Top Down
S menghasilkan c A d dan A menghasilkan a. String itu cabd. Ini bukan string yang diperlukan. Jadi, perlu dilakukan backtracking, yaitu menggunakan alternatif lain.
Demikian pula, S menghasilkan c A d. Menerapkan opsi lain untuk A akan memberikan a. Sekarang 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
Ketika string input (w) adalah abbcde
Pertimbangkan aturan produksi tata bahasa berikut ini.
S -> aABe
A -> Abc / b
B -> d
Di parsing top down,
S -> aABe (Mengganti A -> Abc)
S -> aAbcBe (Mengganti A -> b)
S -> abbcBe (Mengganti B -> d)
S -> abbcde
Pergantian dimulai dengan paling kiri variabel pertama dan kemudian ke posisi kanan berikutnya dan seterusnya. Oleh karena itu, ia mengikuti metode derivasi paling kiri. Lebih lanjut, penting untuk memutuskan aturan produksi apa yang harus dipilih ketika ada variabel.
Apa itu Parsing Bottom Up?
Dalam 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 be cad
S -> cAd
A -> ab / a
Pohon parse setelah melakukan penguraian dari bawah ke atas 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.
Ketika string input (w) adalah abbcde
Pertimbangkan aturan produksi tata bahasa berikut ini.
S -> aABe
A -> Abc / b
B -> d
Dalam penguraian bottom up,
S -> aABe (Mengganti B -> d)
S -> aAde (Mengganti A -> Abc)
S -> aAbcde (Mengganti A -> b)
S -> abbcde
Pergantian dimulai dengan variabel paling kanan pertama dan kemudian pindah ke posisi kiri berikutnya dan seterusnya. Oleh karena itu, ia mengikuti metode derivasi mot kiri.
Apa Perbedaan Antara Parsing Top Down dan Bottom Up?
Penguraian top-down adalah strategi penguraian yang pertama kali melihat tingkat tertinggi dari pohon parse dan bekerja di pohon parse dengan menggunakan aturan tata bahasa formal. Penguraian dari bawah ke atas adalah strategi penguraian yang pertama-tama melihat pada tingkat terendah dari pohon pengurai dan mengolah pohon pengurai dengan menggunakan aturan tata bahasa formal. Penguraian terjadi dari simbol awal ke string input, di penguraian top down. Di sisi lain, penguraian terjadi dari string input ke simbol awal, di penguraian dari bawah ke atas.
Selain itu, keputusan utama dalam penguraian top-down adalah memilih aturan produksi apa yang akan digunakan untuk membangun string, sedangkan keputusan utama dalam penguraian dari bawah ke bawah 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 top down dan bottom up adalah bahwa penguraian top down melakukan penguraian dari simbol menatap ke string input, sedangkan penguraian bottom down melakukan penguraian dari string input ke simbol awal..
Referensi:
1. "Kuliah Penyusun Desain Kompiler 5 - Pengantar Parsers dan LL (1) Parsing." Kuliah Desain Kompiler 5 - Pengantar Parsers dan LL (1) Parsing, Gate Lectures oleh Ravindrababu Ravula, 22 Mei 2014. Tersedia di sini
