POHON PENURUNAN PARSING/PARSE TREE
PARSING
Sebuah
pohon (tree) adalah suatu graph
terhubung tidak sirkuler, yang memiliki satu simpul (node) /vertex yang disebut
akar(root)dan dari root memiliki lintasan kesetiapsimpul.
Pohon
penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana
memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol non
terminal. Setiap simbol variabel akan diturunkan menjadi terminal,
sampaitidakadayangbelumtergantikan.
Contoh
1. Misalnya
terdapat tata bahasa bebas konteks dengan aturan produksi (simbol awal S,
selanjutnya digunakan sebagai simbol awal untuk tata Bahasa bebas konteks adalah
S).
S
→ AB
A
→ aA | a
B
→ bB | b
Akan
kita gambarkan pohon penurunan untuk memperoleh untai : ‘aabbb’.
Pada
pohon tersebut simbol awal akan menjadi akar (root).
Setiap
kali penurunan dipilih aturan produksi yang menuju ke solusi.
Simbol-simbol
variabel (huruf besar) akan menjadi
simpul-simpul yang mempunyai anak.
Kalau
kita baca simbol terminal yang ada pada gambar dari kiri kekanan akan diperoleh
untai ‘aabbb’ :
Proses penurunan atau
parsing bisa dilakukan dengan cara sebagai berikut
Penurunan terkiri
(leftmost derivation) : simbol variabel terkiri yang diperluas terlebih dahulu
Penurunan terkanan (
rightmost derivation) : simbol variabel terkanan yang diperluas terlebihdahul
2. Misal, terdapat tata bahasa bebas konteks :
S → aAS | a
A → SbA | ba
Untuk memperoleh untai ‘aabbaa’ dari tata bahasa bebas
konteks diatas (‘=>’ bisa dibaca ‘menurunkan’):
Dengan penurunan terkiri:
S => aAS => aSbAS => aabAS => aabbaS =>
aabbaa,
Dengan penurunan terkanan :
S => aAS => aAa =>aSbAa =>aSbbaa =>aabbaa.
Kita dapat melihat pohon penurunannya pada gambar
meskipun proses penurunannya berbeda, namun akan tetap memiliki pohon penurunan
yang sama.
3. Biasanya persoalan yang diberikan berkaitan dengan
pohon penurunan adalah untuk mencari penurunan yang hasilnya menuju kepada
suatu untai yang ditentukan.
Dalam hal ini, perlu untuk melakukan percobaan
pemilihanaturanproduksiyangbisamenujuke solusi.
Misalnya sebuah tata bahasa bebas konteks memiliki
aturanproduksisebagaiberikut.
S → aB | bA
A → a | aS | bAA
B → b | bS | Abb
AMBIGUITAS
Ambiguitas/ke-dwi artian terjadi bila terdapat lebih
dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.
Misalkan terdapat tata bahasa bebas konteks :
S → A|B A → a B → a
Untuk memperoleh untai ‘a’ bisa terdapat dua cara
penurunan berikut ini.
S=>B=>a
Contoh yang lain, terdapat tata bahasa bebas konteks:
S–>SbS | ScS | a
Kita bisa menurunkan untai ‘abaca’ dalam dua
caraberikutini
S=>SbS => SbScS => SbSca => Sbaca =>
abaca
S=>ScS => SbScS => abScS => abacS =>
abaca
- Kita bisa melihat bahwa untuk untai yang sama (‘abaca’) dapat dibuat pohon penurunan yang berbeda, maka bahwa dapat dikatakan tata bahasa bebas konteks tersebut ambigu. Jadi,untukmenunjukanbahwasuatutatabahasa bebas konteks ambigu, bisa dilakukan dengan menemukan untai yang memungkinkan pembentukan lebih dari satu pohon penurunan.
- Ambiguitas dapat menimbulkan masalah pada bahasa-bahasa tertentu, baik bahasa alami maupun pada Bahasa pemrograman.
- Bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan arti, maka artinya menjadi ambigu
Soal dan Pembahasan
Parsing/Parse tree
Latihan 1
S → AA
A → AAA | a | bA| Ab
Buatlah pohon penurunan dari himpunan produksi diatas untuk
membangkitkan string dengans usunan “bbabaaba”
Jawaban :
Latihan 2
S → AB
A → Aa| bB
B → a | Sb
Buatlah pohon penurunan dari himpunan produksi diatas untuk
membangkitkan string dengans usunan “baabaab”
Jawaban :
Latihan 3
S → Ba | Ab
A → Sa | Aab| a
B → Sb| Bba| b
Buatlah pohon penurunan dari himpunan produksi diatas untuk
membangkitkan string dengans usunan “bbaaaabb”
Jawaban :
Ambiguitas
Latihan1
S → AB | C
A → aAb| ab
B → cBd| cd
C → aCd| aDd
D → bDc| bc
Buatlah pohon penurunan dari himpunan produksi diatas
untuk membangkitkan string dengans usunan “aabbccdd”
Jawaban :
Daftar Pustaka :
https://fairuzelsaid.wordpress.com/2011/06/16/tbo-context-free-grammar-cfg/
Nama : Fitriana Nur Dhewayani
NPM : 1810631170115
4F
Nama : Fitriana Nur Dhewayani
NPM : 1810631170115
4F
Comments
Post a Comment