Materi Tata Bahasa Bebas Konteks Pohon Penurunan

Tata bahasa bebas konteks

Adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untaidalam sebuah bahasa. Tidak terdapat pembatas hasil produksinya.Pada aturan produksi :a →bBatasannya hanyalah ruas kiri adalah sebuah simbol variabel.Seperti kita ketahui pada saat menurunkan suatu string simbol-simbol variabelakan me!akili bagian yang belum terturunkan. Saat penurunannya telah lengkapsemua bagian yang belum terturunkan telah diganti oleh srting-string dari himpunansimbol terminal

POHON PENURUNAN

Pohon penurunan ( derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.

PARSING

Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node/vertex) disebut akar (root)dan dari suatu titik memiliki lintasan kesetiap simpul.

Contoh, dengan aturan produksi sebagai berikut dengan simbol awal S :

S → AB

A → aA | a

B → bB | b

Maka jika kita ingin mencari gambar pohon penurunan dengan untai : ‘aabbb’ hasilnya adalah seperti di bawah :

Proses penurunan / parsing bisa dilakukan dengan cara sebagai berikut :

- Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang di perluas terlebih dahulu.

- Penurunan terkanan ( rightmost derivation ) : simbol variabel terkanan yang diperluas terlebih dahulu.

Misal : Tata bahasa sbb :

S → aAS | a

A → SbA | ba

Untuk memperoleh untai ‘aabbaa’ dari tata bahasa diatas dilakukan dengan cara :

· Penurunan terkiri: S => aAS => aSbAS => aabAS => aabbaS => aabbaa

· Penurunan terkanan : S => aAS => aAa => aSbAa => aAbbaa => aabbaa

AMBIGUITAS

Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.

Misalkan terdapat tata bahasa sebagai berikut :

S → A | B

A → a

B → a

Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan sebagai berikut :

· S => A => a

· S => B => a

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS ( CFG )

Penyederhanaan tata bahasa bebas konteks dapat di lakukan dengan 3 cara :

1. Penghilangan produksi useless

2. Penghilangan produksi unit

3. Penghilangan produksi Є

1. Penghilangan Produksi Useless

Definisinya sbb:

· Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.

· Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundan.

Contoh :

S → aSa | Abd | Bde

A → Ada

B → BBB |a

· Langkah penyederhanaannya :

· Hilangkan aturan yang tidak menuju terminal.

· Hapus anggota S yang mengandung simbol himpunan ke terminal yang tidak berguna

· Hilangkan Redundan ( Anggota yang tidak ada di S dan Sebaliknya )

 Maka, hasil penyederhanaanya adalah sbb :

S → aSa | Bde

B → BBB | a

Contoh lain :

S → Aa | B

A → ab | D

B → b | E

C → bb

E → aEa

Produksi yang useless adalah :

A → D

C → bb

E → aEa

B → E 

Hasil akhir dari penyederhanaanya adalah :

S → Aa | B

A → ab

B → b

2. Penghilangan Produksi Unit

Definisi sbb :

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan : A → B, C → D. Keberadaanya membuat tata bahasa memiliki kerumitan yang tak perlu, maka bisa dihilangkan.

Langkah penyederhanaanya :

· Jabarkan masing-masing himpunan

· Sederhanakan ruas kiri dan kanan yang hanya berupa variabel simbol sama

· Hapus simbol variabel yang tidak berguna / tidak mempunyai turunan

Contoh suatu CFG sbb :

S → Sb

S → C

C → D

C → ef

D → dd

- Jabarkan penurunan masing – masing himpunan :

C → D => C → dd

S → C => S → dd | ef

- Maka hasilnya adalah sbb :

S → Sb

S → dd | ef

C → dd

C → ef

D → dd

3. Penghilangan Produksi Empty ( Є )

Langkah Penyederhanaannya :

· Hilangkan simbol yang terdapat empty ( Є ) dalam himpunan produksi

· Simbol variabel tidak di hapus jika terdapat cabang terminal / variabel yang saling berhubungan

· Buat himpunan dengan simbol yang dihilangkan dan yang tidak

Contoh :

S → bcAd

A → e

Maka variabel A bisa di hilangkan, sehingga menjadi :

S → bcd

· Kasus lain :

S → bcAd

A → bd | Є

· Maka hasilnya akan menjadi :

S → bcAd | bcd

A → bd

Karena A → Є bukan satu-satunya produksi dari A

· Kasus lainya :

S → Ab | Cd

A → d

C → Є

· Hasil penyederhanaan sebagai berikut :

S → Ab | d

A → d

Daftar pustaka:

https://bhrv.files.wordpress.com/2012/02/pohon-penurunan1.docxhttps://id.scribd.com/doc/314979281/Pohon-penurunan