Antonius Tirta Surya – 1501166213
Question:Mengapa dalam top down parsing tidak boleh terdapat left recursion dan left factoring?
Metoda Parsing
Ada 2 metoda parsing : top-down dan bottom-up.
*A parser is a top down if it discovers a parse tree top to bottom.
*A top down parse corresponds to a preorder traversal of the parse tree
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.
Parsing bottom-up : Diberikan kalimat x sebagai input. Parsing dimulai dari kalimat x
yang nyata dari pembacaan semua leaf pohon parsing dari kiri ke
kanan sampai tiba di simbol awal S (atau tidak sampai di S jika
kalimat x memang tidak bisa diturunkan dari S)
Metode Top-Down Parsing ini meliputi :
- Backtrack/ Backup : Brute Force
- No Backtrack : Recursive Descent Parser
Metoda Brute-Force tidak dapat menggunakan grammar rekursi kiri, yaitu grammar yang
mengandung produksi rekursi kiri (left recursion) :
Problems:
- Left Recursion
- Left factoring
Sebuah grammar dikatakan bersifat left recursion apabila grammar tersebut mengandung suatu nonterminal dan derivasinya.
Contoh : A → Aα
Contoh 2:
A → Aα|β
Maka, A → βA’
A’ → αA’ | ε
Metode Top-Down Parsing tidak bisa menangani grammar yang mengandung left recursive, sehingga left recursive perlu dihilangkan.. Produksi rekursi kiri akan
menyebabkan parsing mengalami looping tak hingga.
Grammar dapat dikatakan left factoring apabila terdapat produksi yang berbentuk seperti di bawah ini :
Contoh :
A → αβ1 | αβ2
Grammar tersebut diubah menjadi :
A → αA’
A’ → β1 |β2
Adanya left factoring ini menyebabkan grammar menjadi ambigu karena tidak jelas yang mana dari dua produksi alternatif yang bisa digunakan untuk memperluas nonterminal A. Dari contoh soal di atas, kita tidak tahu mau menelusuri A ke αβ1 atau ke αβ2.
Sumber lain:pdf1