Pushdown Automata & Context-Free Grammar
DFA/NFA di Modul 1 punya keterbatasan besar: mereka tidak bisa "menghitung" atau "mengingat" apa pun
selain sedang di state mana. Coba pikirkan ekspresi ((1 + 2) * 3), untuk tahu apakah
kurungnya seimbang, mesin harus mengingat berapa banyak kurung buka yang belum ditutup. Itu butuh
ingatan, dan FSA tidak punya itu. Pushdown Automata (PDA) menambahkan satu stack (tumpukan,
seperti tumpukan piring: yang terakhir masuk, keluar duluan) di atas FSA biasa, dan itu cukup untuk
mengenali bahasa yang jauh lebih rumit, termasuk ekspresi aritmatika bersarang. Aturan tata bahasanya
sendiri disebut Context-Free Grammar (CFG).
id melambangkan token NUMBER dari hasil tokenizer Modul 1. Tiga nonterminal
(E, T, F) sengaja dipisah berjenjang supaya perkalian/pembagian
otomatis dihitung duluan daripada penjumlahan/pengurangan, tanpa perlu aturan prioritas operator
tambahan di luar grammar-nya sendiri.
Bagian di atas cuma berlaku untuk grammar ekspresi aritmatika yang sudah ditentukan. Di sini, kamu bisa menulis CFG APAPUN dan mengujinya. Triknya: grammar yang kamu tulis otomatis dikonversi dulu ke Chomsky Normal Form (lihat Modul 4), lalu diuji keanggotaannya dengan algoritma CYK. Bila diterima, pohon penurunan dan jejak stack PDA direkonstruksi dari hasil CYK tersebut.