Pushdown Automata & Parsing

Parsing digunakan untuk mendapatkan string menggunakan aturan produksi tata bahasa. Ini digunakan untuk memeriksa penerimaan string. Compiler digunakan untuk memeriksa apakah suatu string benar secara sintaksis atau tidak. Seorang parser mengambil input dan membangun pohon parse.

Pengurai dapat terdiri dari dua jenis -

Top-Down Parser - Penguraian dari atas ke bawah dimulai dari atas dengan simbol awal dan mendapatkan string menggunakan pohon parse.
Bottom-Up Parser - Penguraian bottom-up dimulai dari bawah dengan string dan sampai ke simbol awal menggunakan pohon parse.

Desain Parser Top-Down

Untuk penguraian top-down, PDA memiliki empat jenis transisi berikut -

Pop non-terminal di sisi kiri produksi di bagian atas tumpukan dan dorong string sisi kanannya.
Jika simbol atas tumpukan cocok dengan simbol input yang sedang dibaca, lepaskan.
Dorong simbol awal 'S' ke dalam tumpukan.
Jika string input dibaca sepenuhnya dan tumpukan kosong, lanjutkan ke status terakhir 'F'.

Contoh

Rancang parser top-down untuk ekspresi "x + y * z" untuk tata bahasa G dengan aturan produksi berikut -

P: S → S + X | X, X → X * Y | Y, Y → (S) | Indo

Solution

Jika PDA-nya adalah (Q, ∑, S, δ, q ₀ , I, F), maka penguraian top-downnya adalah -

(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)

⊢ (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)

⊢ (y * z, X * YI) ⊢ (y * z, y * YI) ⊢ (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)

Desain Pengurai Bottom-Up

Untuk parsing bottom-up, PDA memiliki empat jenis transisi berikut -

Dorong simbol masukan saat ini ke dalam tumpukan.
Ganti sisi kanan produksi di bagian atas tumpukan dengan sisi kiri.
Jika bagian atas elemen tumpukan cocok dengan simbol input saat ini, lepaskan.
Jika string input dibaca sepenuhnya dan hanya jika simbol awal 'S' tetap ada di tumpukan, lepaskan dan lanjutkan ke status terakhir 'F'.