Derivation tree atau pohon penurunan adalah representasi grafis untuk derivasi dari aturan produksi yang diberikan untuk CFG yang diberikan. Ini adalah cara sederhana untuk menunjukkan bagaimana derivasi dapat dilakukan untuk mendapatkan beberapa string dari seperangkat aturan produksi yang diberikan. Pohon derivasi juga disebut pohon parse.
Parse tree mengikuti prioritas operator. Sub-pohon terdalam dilintasi terlebih dahulu. Jadi, operator di simpul orang tua kurang diutamakan daripada operator di sub-pohon.
Pohon parse berisi properti berikut:
- Simpul root selalu merupakan simpul yang menunjukkan simbol awal.
- Derivasi dibaca dari kiri ke kanan.
- Node daun selalu merupakan terminal node
- Node interior selalu merupakan node non-terminal.
Contoh:
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
Dari tata bahasa tersebut, akan kita buatkan 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.
- Simpul-simpul yang tidak mempunyai anak akan menjadi simbol terminal (huruf kecil).
- Kalau kita baca simbol terminal yang ada pada gambar dari kiri kekanan akan diperoleh untai ‘aabbb’ :
Langkah 1:
Langkah 2:
Langkah 3:
Langkah 4:
Langkah 5, maka pohon penurunan untuk untai ‘aabbb’ adalah seperti berikut:
Contoh 1:
Diberikan tata bahasa bebas konteks:
S → AA
A → AAA | a | bA | Ab
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbabaaba”
Langkah 1, buatlah akar root yaitu S dan turunkan terminal-terminalnya:
Langkah 2, turunkan variabel A:
Langkah 3, ruas kiri sudah selesai mendapatkan beberapa string:
Langkah 4:
Langkah 5:
Langkah 6:
Langkah 7:
Maka pohon penurunan untuk untai ‘bbabaaba‘ adalah seperti diatas.
Contoh 2:
Diberikan tata bahasa bebas konteks:
S → AB
A → Aa | bB
B → a | Sb
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “baabaab”.
Langkah 1 :
Langkah 2 :
Langkah 3 :
Langkah 4 :
Langkah 5 :
Langkah 6 :
Langkah 7 :
Langkah 8 :
Langkah 9 :
Maka pohon penurunan untuk untai ‘bbabaaba‘ adalah seperti diatas.
Contoh 3 :
Diberikan tata bahasa bebas konteks:
S → Ba | Ab
A → Sa | Aab | a
B → Sb | Bba | b
Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbaaaabb”.
Langkah 1 :
Langkah 2 :
Langkah 3 :
Langkah 4 :
Langkah 5 :
Langkah 6 :
Maka pohon penurunan untuk untai ‘bbaaaabb‘ adalah seperti diatas.
Ambiguitas
Ambiguitas/ke-dwi artian terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.
Misalkan :
S → A | B
A → a
B → a
Untuk mendapatkan untai ‘a’ bisa terdapat dua cara penurunan berikut ini:
S → A → a
S → B → a
Jadi, untuk menunjukan bahwa suatu tata bahasa 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.
Contoh 1 Ambiguitas:
Diberikan tata bahasa bebas konteks:
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 dengan susunan “aabbccdd”.
Pohon penurunan untai ‘aabbccdd’ (1) :
Pohon penurunan untai ‘aabbccdd’ (2) :
Kita bisa melihat bahwa untuk untai yang sama (‘aabbccdd’) dapat dibuat pohon penurunan yang berbeda, maka bahwa dapat dikatakan tata bahasa bebas konteks tersebut ambigu.
Penjelasan Video Parsing / Parse Tree oleh Fadhlan Sulistiyo
Daftar Pustaka
Modul Dosen Pengampu. Pa. Garno. TEORI BAHASA DAN AUTOMATA: Tata Bahasa Bebas Konteks POHON PENURUNAN
Java Point. Simplification of CFG. https://www.javatpoint.com/automata-simplification-of-cfg (diakses tanggal 9 Maret 2020)
Dlan's Tech 