Perbedaan Antara Parsing Top Down dan Bottom Up

Perbedaan Antara Parsing Top Down dan Bottom Up

Perbedaan utama antara parsing top down dan bottom up adalah parsing top down melakukan parsing dari simbol menatap ke string input sedangkan parsing bottom down melakukan parsing dari string input ke simbol awal. Selain itu, perbedaan penting lainnya antara parsing top down dan bottom up adalah parsing top down menggunakan derivasi paling kiri dan parsing 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 diubah menjadi kode mesin. Tugas kompiler adalah mengubah kode sumber yang dapat dibaca manusia menjadi kode mesin yang dapat dibaca mesin. Suatu program melewati beberapa langkah untuk mengonversi ke kode mesin. Keseluruhan proses ini disebut Sistem Pemrosesan Bahasa. Salah satunya adalah kompilasi. Penganalisis sintaksis atau parser ada di kompiler, dan ia melakukan tugas parsing.

ISI

1. Ikhtisar dan Perbedaan Kunci
2. Apa itu Top Down Parsing
3. Apa itu Parsing Bawah ke Atas
4. Perbandingan Berdampingan – Penguraian Top Down vs Bottom Up dalam Bentuk Tabular
5. Ringkasan

Apa itu Top Down Parsing?

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 tersebut menggunakan parse tree.

Dalam parsing top down, parsing 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 Top Down Parsing

S menghasilkan c A d dan A menghasilkan a b. Talinya 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 ini memberikan string yang diperlukan. Oleh karena itu, parser menerima string input ini. Pohon parse setelah melakukan top down parsing adalah sebagai berikut.

Gambar 02: Parse Tree 2 dengan Top Down Parsing

Ketika string input (w) adalah abbcde

Pertimbangkan aturan produksi tata bahasa berikut.

S -> aABe

A -> Abc/b

B -> d

Dalam penguraian top down,

S -> aABe (Menggantikan A -> Abc)

S -> aAbcBe (Menggantikan A -> b)

S -> abbcBe (Menggantikan B ->d)

S -> abbcde

Pergantian dimulai dengan variabel paling kiri terlebih dahulu kemudian ke posisi kanan berikutnya dan seterusnya. Oleh karena itu, ini mengikuti metode derivasi paling kiri. Selanjutnya, penting untuk memutuskan aturan produksi apa yang akan dipilih ketika ada variabel.

Apa itu Penguraian Bawah ke Atas?

Dalam penguraian dari bawah ke atas terjadi sebaliknya. Penguraian terjadi dari string input ke simbol awal. Pertimbangkan aturan produksi tata bahasa berikut dan biarkan string masukan menjadi w ɛ cad

S -> cAd

A -> ab /a

Pohon parse setelah melakukan bottom up parsing adalah sebagai berikut.

Gambar 03: Parse Tree dengan Bottom Up Parsing

String yang diberikan adalah cad. A dihasilkan oleh A. Kombinasi c, A dan d menghasilkan simbol awal S.

Ketika string input (w) adalah abbcde

Pertimbangkan aturan produksi tata bahasa berikut.

S -> aABe

A -> Abc/b

B -> d

Dalam penguraian dari bawah ke atas,

S -> aABe (Menggantikan B ->d)

S -> aAde (Menggantikan A -> Abc)

S -> aAbcde (Menggantikan A -> b)

S -> abbcde

Pergantian dimulai dengan variabel paling kanan terlebih dahulu kemudian pindah ke posisi kiri berikutnya dan seterusnya. Oleh karena itu, ini mengikuti metode derivasi mot kiri.

Apa Perbedaan Antara Top Down dan Bottom Up Parsing?

Top-down parsing adalah strategi parse yang pertama kali melihat level tertinggi dari pohon parse dan bekerja ke bawah pohon parse dengan menggunakan aturan tata bahasa formal. Penguraian dari bawah ke atas adalah strategi penguraian yang pertama kali 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, penguraian terjadi dari string input ke simbol awal, di penguraian dari bawah ke atas.

Selain itu, 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 harus 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 – Top Down vs Bottom Up Parsing

Perbedaan antara parsing top down dan bottom up adalah parsing top down melakukan parsing dari simbol menatap ke string input sedangkan parsing bottom down melakukan parsing dari string input ke simbol awal.

Referensi:

1.“Kuliah Desain Kompiler 5 — Pengantar Parser dan LL(1) Parsing.” Kuliah Desain Kompiler 5 — Pengantar Parser dan LL(1) Parsing, Kuliah Gerbang oleh Ravindrababu Ravula, 22 Mei 2014. Tersedia disini

Leave a Comment