Top-down Parsing

1. Pastikan tidak ada left recursion dan left factoring pada grammar
2. Tentukan nilai First (karakter pertama pada setiap hasil produksi)
3. Tentukan nilai Follow
4. Buatlah tabel parsing
   1. Lihat nilai First
   2. Jika ada empty di first maka lihat follow
5. Parsing

Left Factoring

A  --> Ba | Bcd | ef
    B (a | cd) | ef
A  --> B A’ | ef
A’ --> a | cd

---

B  --> abc | ad | eq
       a (bc | d) | eq
B  --> aB’ | eq
B’ --> bc | d

---

D  --> abd | bc | abc
       ab (d | c) | bc
D  --> abD’ | bc
D’ --> d | c

---

E   --> bad | bac | b
        b (ad | ac | ε)
E   --> bE’
E’  --> ad | ac | ε
        A (d | c) | ε
E’  --> AE’’ | ε
E’’ --> d | c
Conclusion
E   --> bE’
E’’  --> AE’’ | ε
E’’ --> d | c

Left Recursion

A --> Ab | cd
A  --> cdA’
A’ --> bA’ | ε

---

D  --> bd | De | ba
       β     α   β
D  --> bdD’ | baD’
D’ --> eD’ | ε

---

F  --> aFc | Fde | a
        β     α    β
F  --> aFcF’ | aF’
F’ --> deF’ | ε

Follow

Algoritma:

1. if (S -> ab | c) and (S is start) then $ is the follow
2. if (A -> αBβ) then first of β is the follow of B, excluding the empty first
3. a. if (A -> αB) then the follow of A is the follow of B
   b. if (A -> αBβ) and (first β is empty) then the follow of A is the follow of B

note:

• β is the rest of the grammar
• if there is only one character then pad left with ε

Cheat
Cari dari semua hasil produksi yang berada di belakang (kanan) X dan bukan variabel.

Ex