Tugas 6 Teori Bahasa dan Automata - Tata Bahasa Bebas Konteks (Pohon Penurunan)
Parsing
Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) / vertex disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. Pohon sintaks / pohon penurunan (syntax tree/derivaton tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal. Setiap simbol variabel diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.
Contoh :
S → AB
A → aA | a
B → bB | b
Untai yang dicari: aabbb . Maka Pohon Penurunannya:
Proses penurunan atau parsing bisa dilakukan dengan cara:
1. Penurunan terkiri (leftmost derivation):
Setiap tahapan penurunan variabel / non terminal terkiri yang diuraikan .
Symbol variabel terkiri yang diperluas terlebih dahulu.
2. Penurunan terkanan (right derivation):
Setiap tahapan penurunan variabel / non terminal paling kanan yang diuraikan.
Symbol variabel terkanan yang diperluas terlebih dahulu.
Misal, terdapat tata bahasa bebas konteks:
S → aAS | a
A → SbA | ba
Untuk memperoleh untai ‘aabbaa’ :
Dengan penurunan terkiri:
S → aAS → aSbAS → aabAS → aabbaS → aabbaa
Dengan penurunan terkanan :
S → aAS → aAa → aSbAa → aSbbaa → aabbaa
Meskipun proses penurunan berbeda, namun akan tetap memiliki pohon penurunan yang sama. Maka Pohon Penurunannya:
Ambiguitas
Terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda utuk memperoleh suatu untai.
Misal terdapat tata bahasa bebas konteks:
S → SbS | ScS | a
Untuk memperoleh untai ‘abaca’.
Cara pertama:
S → SbS → SbScS → SbSca → Sbaca → abaca
Cara kedua:
S → ScS → SbScS → abScS → abacS → abaca
Latihan Soal
Soal 1
Terdapat tata bahasa bebas konteks:
S → AA
A → AAA | a | bA | Ab
Maka untuk memperoleh untai " bbabaaba " adalah sebagai berikut:
- Penurunan Terkiri
S → AA → bAA → bbAA → bbAbA → bbabA →bbabAAA → bbabaaA → bbabaabA → bbabaaba
- Pohon Penurunan
Soal 2
Terdapat tata bahasa bebas konteks:
S → AB
A → Aa | bB
B → a | Sb
Maka untuk memperoleh untai " baabaab " adalah sebagai berikut:
- Penurunan Terkiri
S → AB→ AaB→ bBaB→ baaB → baaSb → baaABb → baabBBb → baabaBb→ baabaab
- Pohon Penurunan
Soal 3
Terdapat tata bahasa bebas konteks:
S → Ba | Ab
A → Sa | Aab | a
B → Sb | Bba | b
Maka untuk memperoleh untai " bbaaaabb " adalah sebagai berikut:
- Penurunan Terkiri :
S → Ab→ Aabb→ Saabb→ Baaabb→ Bbaaaabb → bbaaaabb
- Pohon Penurunan
Soal 4 (Ambiguitas)
Terdapat tata bahasa bebas konteks (Ambiguitas):
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
Maka terdapat 2 untai " aabbccdd " adalah sebagai berikut:
Karena soal diatas adalah ambiguitas maka terdapat dua penurunan yaitu :
- S → AB
- S → C
Penurunan Terkiri dari S → AB adalah :
S → AB→ aAbB→ aabbB→ aabbcBd→ aabbccdd
Pohon Penurunanya adalah :
Penurunan Terkiri dari S → C adalah :
S → C→ aCd→ aaDdd→ aabDcdd→ aabbccdd
Pohon Penurunannya adalah :
Untuk lebih jelasnya saya menjelaskan lewat media berupa video dan bisa ditonton dibawah ini.
- https://www.academia.edu/8702157/20120515_Teori_Bahasadan_Otomata_TBO_-Pohon_Penurunan
- http://apranolo.tif.uad.ac.id/wp-content/uploads/2014/12/TBA_TID_Kelompok-7_TATA-BAHASA-BEBAS-KONTEKS.pdf
- Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan) [pdf]. Dosen Pengampu: Garno, M.Kom. Fakultas Ilmu Komputer, Universitas Singaperbangsa Karawang.
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment