PARSING (BOTTOM UP)
PARSING
(BOTTOM UP)
A.
Definisi
Menurut Wikipedia Bahasa Indonesia,
parsing atau penguraian adalah suatu cara memecha-mecah suatu rangkaian masukan
(misalnya dari berkas atau keyboard)
yang akan menghasilkan suatu pohon uraian (parse tree) yang akan digunakan pada
tahap kompilasi berikutnya, yaitu analisis semantic.
Sumber :
id.wikipedia.org/wiki/parsing
Sedangkan menurut Amrullah Ibrahim Hi.
Hasan dalam blognya mengatakan, parsing adalah proses menganalisis teks,
terbuat dari urutan token untuk menetukan struktur gramtical terhadap hal yang
diberikan tata bahasa formal.
Masih menurut Amrullah, parsing juga
merupakan istilah awal untuk diagram kalimat bahasa alam dan masih digunakan
utnuk diagram bahasa infleksi, seperti bahasa-bahasa Roman atau latin.
Berdasarkan ke-2 pengertian di atas, maka
dapat disimpulkan bahwa parsing dalam istilah komputer adalah suatu metode atau
suatu cara menganalisa suatu masukan
dalam hal ini sintakx atau coding.
B.
Metode
Parsing
Ada dua jenis metode penguraian yang
sering digunakan, yaitu, top down parsing dan bottom up parsing. Namun, bottom
up parsing yang akan dibahas dengan lebih detail (tugas).
1.
Penguraian
dari atas ke bawah (top-down parsing)
Penguraian dari atas ke bawah dapat
dipandang sebagai suatu usaha untuk mencari derivasi paling kiri (leftmost) dari suatu rangkaian masukan.
Dapat dikatakan juga sebagai suatu usaha untuk membentuk pohon urai (parser) untuk masukkan dari akamya dan
membentuk node pohon parser dalam urutan preorder.
Perhatikanlah tata
bahasa ini.
S=>AbA=> bela
2. Penguraian dari bawah
ke atas (bottom-up parsing)
Bottom up adalah teori yang mengajukan
gagasan bahwa proses pengenalan diawali oleh identifikasi terhadap
bagian-bagian spesifik dari suatu pola yang menjadi alasan bagi pengenalan pola
secara keseluruhan.
Contoh :
Jika ada seseorang, kita akan
mengenalinya dari bagian-bagian dirinya, seperti suara, postur, cara berjalan
dan lain-lain, sehingga kita tahu bahwa itu adalah si A.
Bottom up merupakan salah satu metode yang digunakan
untuk melakukan parsing. Operasi yang terdapat pada bottom up parser adalah
shift dan reduce, sehingga seringkali bottom up parser disebut dengan
shift-reduce parser. Pada setiap tahapan reduksi, substring yang berada disisi kanan
dari sebuah production rule (RHS) digantikan dengan symbol dari pada LHS. Untuk
membuat sebuah parsing table maka dibutuhkan DFA dari grammar tersebut. Ada
beberapa jenis parsing table, antara lain LR(0), LR(1), dan SLR.
Penguraian dari
bawah ke atas lebih banyak mempergunakan penguraian bagi suatu masukan dimulai
dari bawah (leaf) dan bergerak keatas
menuju puncak (root). Pada
setiap langkah reduksi suatu substring
yang sesuai dengan sisi kanan suatu produksi diganti dengan simbol yang
berada di kanan produksi itu, langkah ini sering disebut derivasi rightmost.
Perhatikanlah tata bahasa ini.
S => aABe
A=>Abclb B=>d
Kalimat 'abbcde'
dapat direduksi ke S dengan langkah-langkah berikut:
Abbcde -> aAbcde
-> aAde -> aABe -> S
Salah satu contoh
menarik dari parsing bottom-up adalah pada grammar preseden sederhana (GPS). Sebelum
sampai ke parsing tersebut akan dikemukakan beberapa pengertian dasar serta
relasi yang ada pada GPS.
a) Jika a dan x keduanya
diderivasi dari simbol awal grammar tertentu, maka a disebut sentensial
jika a Î (VT½ VN)*, dan x disebut kalimat jika x Î (VT)*
b) Misalkan a = Q1b Q2 adalah sentensial dan A Î VN :
1)
b adalah frase dari sentensial a jika : S → .... → Q1A Q2 dan A→ .... → b
2) b adalah simple frase dari sentensial a jika : S → .... → Q1A Q2 dan A→b
3)
Simple frase
terkiri dinamakan handel
4) frase, simple frase, dan handel adalah string
dengan panjang 0 atau lebih.
CONTOH :
(a) I → I H Hb adalah sentensial dan
b adalah simple frase
→ H H (dibandingkan dengan Q1b Q2 maka Q1= H, b = b, dan Q2 = e)
→ H b Perhatikan : simple
frase (b) adalah yang terakhir diturunkan
(b) I → I H Hb adalah sentensial dan
H adalah simple frase
→ I b (dibandingkan dengan Q1b Q2 maka Q1= e, b = H, dan Q2 = b)
→ H b Perhatikan : simple
frase (H) adalah yang terakhir diturunkan
Sentensial Hb mempunyai dua simple frase (b dan
H), sedangkan handelnya adalah H.
Relasi Preseden dan Grammar Preseden
Sederhana
Relasi
preseden adalah relasi antara 2 simbol grammar (baik VT maupun VN) dimana paling
tidak salah satu simbol tersebut adalah komponen handel.
Misalkan
S dan R adalah 2 simbol. Ada 3 relasi preseden yang : ¬, «, dan ®
Contoh :
Diketahui
grammar dengan G = {Z ® bMb, M ® (L →a, L ® Ma)}. Dari 3
sentensial :
bab, b(Lb,
b(Ma)b, tentukan handel dan relasi yang ada.
Secara
umum : jika A ® aBc adalah sebuah
produksi maka :
- aBc
adalah handel dari sentensial yang mengandung string “aBc”
- relasi
preseden antara a, B, dan c adalah : a « B, B « c
Dengan
memperhatikan ruas kanan produksi yang ada serta berbagai sentensial yang dapat
diderivasi dari Z maka semua relasi preseden tercantum dalam tabel berikut :
|
Z
|
b
|
M
|
L
|
a
|
(
|
)
|
|
|
Z
|
|
|
|
|
|
|
|
|
b
|
|
|
«
|
|
¬
|
¬
|
|
|
M
|
|
«
|
|
|
«
|
|
|
|
L
|
|
®
|
|
|
®
|
|
|
|
a
|
|
®
|
|
|
®
|
¬
|
«
|
|
(
|
|
|
¬
|
«
|
¬
|
¬
|
|
|
)
|
|
®
|
|
|
|
|
|
Grammar
G disebut grammar preseden sederhana, jika :
1.
paling banyak terdapat satu relasi antara setiap dua simbolnya
2. tidak
terdapat dua produksi produksi dengan ruas kanan yang sama
Parsing
Grammar Preseden Sederhana
Prosedur
parsing :
1.
Buat tabel 3 kolom dengan label : sentensial
dan relasi, handel, dan ruas kiri produksi.
2. Tuliskan kalimat (atau sentensial) yang diselidiki pada baris
pertama kolom pertama.
3. Dengan menggunakan tabel relasi preseden cantumkan relasi preseden
antara setiap dua simbol yang bertetangga.
4. Tentukan handel dari sentensial tersebut. Handel adalah string
yang dibatasi “¬“ terakhir dan “® “ pertama jika dilakukan penelusuran dari
kiri atau yang saling mempunyai relasi “«“. Handel tersebut pastilah merupakan ruas kanan produksi, karena itu
tentukan ruas kiri dari handel tersebut.
5. Ganti handel dengan ruas kiri produksinya. GOTO 3.
6. Kalimat yang diselidiki adalah benar dapat diderivasi dari simbol
awal jika kolom “ruas kiri produksi” menghasilkan simbol awal.
Contoh :
Lakukan parsing atas kalimat x = b(aa)b berdasarkan grammar G di
atas.
|
Sentensial dan relasi
|
Handel
|
Ruas kiri produksi
|
|
b ¬ (¬ a ® a «)® b
|
a
|
M
|
|
b ¬ (¬ M « a «)® b
|
Ma)
|
L
|
|
b ¬ (« L® b
|
(L
|
M
|
|
b « M « b
|
bMb
|
Z
|
Prosedur
parsing sampai di simbol awal (Z). Maka kalimat “b(aa)b” memang dapat diderivasi
dari simbol awal Z dengan menggunakan grammar G.
Sumber :
Modul
Praktikum Automata – IT045330
Komentar
Posting Komentar