TUGAS TBO : CONTEXT FREE GRAMMER & PARSING

PARSING TOP DOWN

Parsing top-down : Diberikan kalimat x sebagai input. Parsing dimulai dari simbol awal S sampai kalimat x nyata (atau tidak nyata jika kalimat x memang tidak bisa diturunkan dari S) dari pembacaan semua leaf dari pohon parsing jika dibaca dari kiri ke kanan.

Disini akar, dan daun pada pohon ini diketahui. Bentuk sisa dari Pohon Sintaks harus kita cari. Ada beberapa metode yang dapat digunakan untuk menyelesaikan konstruksi ini. Pertama, usahakan konstruksi Pohon dapat dimulai bermula dari akar dan dilanjutkan turun ke bawah menuju daun. Metode ini disebut Top-Down Parsing.

Alternative lain adalah dengan memulai pada daun, dan bergerak ke atas menuju akar. Metode ini disebut Bottom Up Parsing.

Pendekatan Top down dan Bottom Up dapat dikombinasikan untuk menghasilkan kemungkinan lain. Mari kita membicarakan secara singkat tentang Top Down Parsing. Pandang Identifier x2 yang dibentuk oleh Grammar G5 pada bagian yang lalu. Langkah pertama adalah mengkonstruksi derivasi langsung.

Pada setiap urutan langkah, nonterminal paling kiri α dari bentuk sentensial Q1αQ2, diganti dengan bagian kanan dari produksi A àψ, untuk membentuk bentuk sentensial berikutnya. Proses ini ditunjukkan, dalam menidentifikasikan x2 pada 5 buah Pohon.

Kita mungkin saja mempunyai beberapa pilihan produksi. Di sini kita dapat mengambil yang kita rasa sesuai. Jika langkah pertama dikerjakan derivasi langsung = = => , maka bagaimanapun langkah berikutnya tidak akan mungkin untuk menghasilkan  x2.

Secara umum Top Down Parsing memerlukan backup. Backup adalah pengulangan penggunaaan suatu produksi dengan alternative produksi yang lain, bila produksi yang digunakan tidak sesuai dengan symbol input. Top Down Parsing dapat digambarkan sebagai usaha untuk mendapatkan derivasi leftmose untuk suatu untai input. Derivasi leftmost adalah derivasi untuk mendapatkan untai tertentu, dengan melakukan derivasi terhadap nonterminal terkiri.

Dengan Aàβ adalah suatu produksi dari Grammar dan Q1 anggota VT *. Hubungan ini dapat diperluas menjadi =L+=> dan =L*=>. Disini ψ =L => σ boleh dibaca y memproduksi kiri s.

Secara umum, terdapat banyak barisan untai Q1, Q2,….Qn sedemikian sehingga

S ==> Q1 ==> Q2 ==> ...==>Qn ==>x

Disini, jika Q1 mengandung paling sedikit dua symbol nonterminal, maka kita membpunyai pilihan nonterminal man yang kan diganti. Relasi =L+=> menyatakan bahwa terdapat tepat hanya satu derivasi =L=>. Dapat dicatat bahwa pernyataan ini hanya berlaku untuk Grammar tidak ambiguous. Pengertian yang serupa dapat kita definisikan untuk derivasi kanonik rightmous =R=>, serta =R+=> dan =R*=>.

6.1.1 Parsing Top-Down

Ada 2 kelas metoda parsing top-down, yaitu kelas metoda dengan backup dan kelas metoda tanpa backup. Contoh metoda kelas dengan backup adalah metoda Brute-Force, sedangkan contoh metoda kelas tanpa backup adalah metoda recursive descent.

a. Metoda Brute-Force

Kelas metoda dengan backup, termasuk metoda Brute-Force, adalah kelas metoda parsing yang menggunakan produksi alternatif, jika ada, ketika hasil penggunaan sebuah produksi tidak sesuai dengan simbol input. Penggunaan produksi sesuai dengan nomor urut produksi.

b. Metoda Recursive-Descent

• Kelas metoda tanpa backup, termasuk metoda recursive descent, adalah kelas metoda

parsing yang tidak menggunakan produksi alternatif ketika hasil akibat penggunaan

sebuah produksi tidak sesuai dengan simbol input. Jika produksi A mempunyai dua

buah ruas kanan atau lebih maka produksi yang dipilih untuk digunakan adalah

produksi dengan simbol pertama ruas kanannya sama dengan input yang sedang

dibaca. Jika tidak ada produksi yang demikian maka dikatakan bahwa parsing tidak

dapat dilakukan.

• Ketentuan produksi yang digunakan metoda recursive descent adalah : Jika terdapat

dua atau lebih produksi dengan ruas kiri yang sama maka karakter pertama dari semua

ruas kanan produksi tersebut tidak boleh sama. Ketentuan ini tidak melarang adanya

produksi yang bersifat rekursi kiri.

Metode Parsing Recursive Descent tidak kita bahas secara mendalam. Disini pilihan produksi yang tepat, dideteksi dengan melihat hanya pada symbol pertam dari derivasinya. Sebagai contoh, diberikan produksi :

  ---> IF DO | WHILE DO | BEGIN END

Kata kunci IF, WHILE dan BEGIN menunjukkan satu pilihan yang pmungkin dapat berhasil untuk membentuk statement.

Pada teknik parsing yang tidak menggunakan backup, kikta dihadapkan pada masalah untuk menentukan produksi dari suatu nonterminal, yang akan digunakan untuk mendapatkan penguraian suatu kalimat dengan sukses.

 

Nama : Aristo Oktobrian (50407155)