AGUS DIAN RISTANTO

Parsing
Parsing adalah konsturksi atau pembentukan Pohon Sintaks untuk suatu kalimat (ekspresi).

Bila terdapat lebih dari satu pohon sintaks untuk sebuah grammar maka dikatakan grammar tersebut Ambiguous.

Dua cara melakukan validitas sintaks dengan parsing :
TOP DOWN Parsing : melakukan derivasi string dari NT
BOTTOM UP Parsing : melakukan reduksi simbol ke NT.


Parsing Top Down
Jika  adalah input string, maka derivasi dari Top Down Parse dapat ditunjukkan sebagai berikut :
S …  …  …  
Parse Tree untuk Top Down Parsing selalu dimulai dari sebelah kiri

Parsing Top Down (cont.)
Contoh : Parsing Top Down untuk identifier x2
Derivasinya :
   x  x2
Parsing Top Down (cont.)
Contoh : ekspresi a + b * c
grammar : E ::= T + E | T
T ::= V * E | V
V ::=
Parsing Bottom Up
Parsing Bottom Up membangun pohon sintaks melalui urutan simbol yang direduksi, atau dimulai dengan sebuah string hingga mencapai simbol start Grammar

Contoh : diketahui identifier x2, dengan parsing bottom up menjadi :
Relasi Preseden dan Pemakaiannya
Teknik parsing pada metode Bottom-Up dilakukan dengan mencari berulang-ulang, handle (leftmost simple phrase) u dari bentuk sentensial saat itu dan mereduksinya menjadi suatu nonterminal U dnegan memakai reduksi U  u

Jadi tujuan utamanya adalah mencari Handle dari sebuah bentuk sentensial yaitu simple phrase terkiri (leftmost) dari bentuk sentensial tersebut.

Masalah tersebut diselesaikan dengan Grammar Preseden


Relasi Preseden dan Pemakaiannya (cont.)
Misal, R dan S berada dalam suatu grammar G. Beberapa bentuk sentensial dapat dibentuk dari simbol R dan G tersebut (…RG…..). Ada tiga kemungkinan yang timbul dalam handle yang dibuat dari R dan S.
R adalah bagian dari suatu handle tapi S tidak (R  S)
dikatakan R > S (R memiliki Preseden atas S).
R harus merupakan ekor dari beberapa produksi U  …R.
Karena handle berada di kiri S,maka S harus merupakan terminal

Relasi Preseden dan Pemakaiannya (cont.)
R dan S keduanya adalah bagian dalam suatu handle (R  S)
dikatakan R dan S memiliki Preseden yang sama, dan harus direduksi secara bersamaan waktu
Harus ada suatu produksi U  …RS...
Relasi Preseden dan Pemakaiannya (cont.)
Contoh : Diketahui, Grammar dengan simbol Start Z dan produksi :
Z  bMb
M  (L | a
L  Ma)
Berikut ini akan ditunjukkan bentuk sentensial, phon sintaks,handel dari relasi yang dapat diturunkan dari produksi.

Bentuk sentensial : bab
Pohon Sintaks :
Relasi Preseden dan Pemakaiannya (cont.)
Bentuk sentensial : b(Lb
Pohon Sintaks :