Tata Bahasa Bebas Konteks POHON PENURUNAN

Tata Bahasa Bebas Konteks
Pohon Penurunan

CFG / Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :

a → b

batasannya hanyalah ruas kiri (a) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :

B → CDeFg

D → BcDe

Tata bahasa bebas konteks ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.Bila pada tata bahasa regular terdapat pembatasan pada ruas kanan atau hasil produksinya, maka pada tata bahasa bebas konteks/ context free grammar, selanjutnya kita sebut CFG, tidak terdapat pembatasan hasil produksinya. Pada aturan produksi:

a à b

batasannya hanyalah ruas kiri (a) adalah sebuah symbol variabel.
Contoh aturan produksi yang termasuk CFG:

B à CDeFg

D à BcDe

Seperti halnya pada tata bahasa regular, sebuah tata bahasa bebas konteks adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Seperti kita ketahui, pada saat menurunkan  suatu string, symbol-simbol variabel akan mewakili bagian-bagian yang belum yang belum terturunkan dari string tersebut. Bila pada tata bahasa regular, bagian yang belum terturunkan tersebut selalu terjadi pada suatu ujung, pada tata bahasa bebas konteks bisa terdapat lebih banyak bagian yang belum terturunkan itu dan bisa terjadi dimana saja. Ketika penurunan itu sudah lengkap, semua bagian yang belum terturunkan telah diganti oleh string-string (yang mungkin saja kosong) dari himpunan symbol terminal. Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebas konteks.

Parsing

CFG menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan di definisikan dalam tata bahasa bebas konteks. 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.

Contoh, terdapat CFG 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

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. Gambar 1 memberikan contoh sebuah tree yang menguraikan kalimat dalam bahasa Inggris:  The quick brown fox jumped over the lazy dog

Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol- simbol variabel menjadi simbol-simbol terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Misal terdapat tata bahasa bebas konteks dengan aturan produksi (symbol awal S, selanjutnya didalam bab ini digunakan sebagai symbol 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 symbol awal akan menjadi akar (root). Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi. Simbol-simbol variabel akan menjadi simpul-simpul yang mempunyai anak. Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal. Kalau kita baca symbol terminal yang ada pada gambar 2 dari kiri ke kanan akan diperoleh unatai ‘aabbb’.

Proses penurunan atau parsing bisa dilakukan dengan cara:

-          Penurunan terkiri (leftmost derivation): symbol variabel terkiri yang diperluas terlebih dahulu.

-          Penurunan terkanan (rightmost derivation): symbol variabel terkiri yang diperluas terlebih dahulu

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

Meskipun proses penurunannya berbeda akan tetap memiliki pohon penurunan yang sama.

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 pemilihan aturan produksi yang bisa menuju ke solusi. Misalkan  sebuah tata bahasa bebas konteks memiliki aturan produksi:

S à aB | bA

A à a | aS | bAA

B à b | bS | aBB

Pohon penurunan untuk memperoleh :’ aaabbabbba” 

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

Ambiguitas/kedwiartian 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:

S Þ A Þ a

S Þ B Þ a 

Contoh lain, terdapat tata bahasa bebas konteks:

S à SbS | ScS | a

Kita bisa menurunkan untai ‘abaca’ dalam dua cara:

S Þ SbS Þ SbScS Þ SbSca Þ Sbaca Þ abaca

S Þ ScS Þ SbScS Þ abScS Þ abacS Þ abaca

Kita lihat untuk untai yang sama (‘abaca) dapat dibuat pohon penurunan yang berbeda, maka dapat dikatakan tata bahasa bebas konteks tersebut ambigu. Jadi untuk menunjukkan bahwa suatu tata bahasa bebas konteks ambigu, bisa dilakukan dengan menemukan untai yang memungkinkan pembentukan lebih dari satu pohon penurunan.

Latihan 1 Parsing/Parse tree

S à AA

A à AAA | a | bA | Ab

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbabaaba”.

Jawab :

Pohon Penurunan untuk untai “bbabaaba”  :

                                

Latihan 2 Parsing/Parse tree

S à AB

A à Aa | bB

B à a | Sb

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “baabaab”.

Jawab :

Pohon Penurunan untuk untai  “baabaab”  :

                             

Latihan 3 Parsing/Parse tree

S à Ba | Ab

A à Sa | Aab | a

B à Sb | Bba | b

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbaaaabb”.

Jawab :

Pohon Penurunan untuk untai  “bbaaaabb”  :

                                

Latihan 1  Ambiguitas

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”.

Jawab :

Pohon Penurunan untuk untai  “aabbccdd”  :

                                                         

Daftar Pustaka :
http://eywatsauroty.blogspot.com/2014/09/tata-bahasa-bebas-konteks.html