Latihan Pohon Penurunan dan Ambiguitas Tata Bahasa Bebas Konteks

Tata bahasa bebas konteks atau Context Free Grammar (CFG) merupakan salah satu  bahasa formal yang dapat digunakan untuk mendefinisikan sintaks bahasa pemograman. Suatu tata bahasa bebas konteks dapat berbentuk sangat melebar, sangat menyempit, atau terjadi rekursif kiri, yang semuanya sering dinamakan bentuk tidak normal. Suatu tata bahasa bebas konteks dapat dimodifikasi ruas kanan aturan produksinya sedemikian sehingga panjangnya hanya satu atau dua karakter, tentu dapat dengan mudah dibayangkan  bahwa pohon penurunan string yang terbentuk akan menjadi lebih sederhana, yaitu pohon biner yang setiap simpul hanya memiliki cabang satu atau dua. Tata bahasa dengan batasan seperti ini disebut tata bahasa bebas konteks dalam bentuk normal Chomsky (Chomsky Normal Form atau CNF).

Pada tata bahasa bebas konteks atau context free grammar atau biasa dikenal dan disebut sebagai 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 bahsa reguler, sebuah tata bahasa bebas konteks adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. pada saat menurunkan suatu string, symbol-simbol variabel akan mewakili bagian-bagian yang belum terturunkan dari string tersebut. Bila pada tata bahasa reguler, 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 dapat terjadi dimana saja. Ketika penurunan itu telah lengkap, semua bagian yang belum terturunkan telah diganti oleh string-string (yang mungkin saja kosong) dari himpunan simbol terminal. Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser atau proses analisis sintaksis.

Grammar ini diciptakan secara bebas-konteks dan disebut Context Free Grammar (CFG). Hasilnya, dengan pendekatan formal ini, kompiler suatu bahasa pemrograman dapat dibuat lebih mudah dan menghindari ambiguitas ketika parsing bahasa tersebut.

Contoh desain CFG untuk parser, misal :

B → BB | (B) | e

untuk mengenali bahasa dengan hanya tanda kurung {‘(’,’)’} sebagai terminal-nya.

Proses parsing adalah proses pembacaan string dalam bahasa sesuai CFG tertentu, proses ini harus mematuhi aturan produksi dalam CFG tersebut.

Pohon penurunan (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) atau vertex disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. 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.

The quick brown fox jumped over the lazy dog

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

Context Free Grammar (CFG) menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan di definisikan dalam tata bahasa bebas konteks.

Parsing

Parsing adalah suatu cara memecah-mecah suatu rangkaian masukan yang akan menghasilkan suatu pohon uraian (parse tree) yang akan digunakan pada tahap kompilasi berikutnya yaitu analisis sintaksis. Proses Parsing merupakan tahapan analisis sintaksis yang berguna untuk memeriksa urutan kemunculan token. Di dalam mengimplementasikan sebuah metode parsing ke dalam program perlu diperhatikan tiga hal sebagai berikut:

• ·         Rentang Waktu eksekusi

• ·         Penanganan Kesalahan

• ·         Penanganan Kode

Metode Parsing digolongkan menjadi:

1. Top-Down, Metode ini melakukan penelusuran dari root/puncal ke leaf/bawah (dari symbol awal ke symbol terminal/symbol awal S sampai kalimat x).
2. Bottom-Up, Metode ini melakukan penelusuran dari leaf ke root (dari kalimat x sampai symbol awal S)

Penerapan Latihan Soal Pohon Penurunan:

1.      S → AA

A → AAA | a | bA | Ab

Buatlah pohon penurunan dari himpunan produksi diatas untuk

membangkitkan string dengan susunan “bbabaaba”

 

1.      S → AB

A → Aa | bB

B → a | Sb

Buatlah pohon penurunan dari himpunan produksi diatas untuk

membangkitkan string dengan susunan “baabaab”

 

1.      S → Ba | Ab

A → Sa | Aab | a

B → Sb | a | Bba | b

Buatlah pohon penurunan dari himpunan produksi diatas untuk

membangkitkan string dengan susunan “bbaaaabb”

   

Proses penurunan atau parsing bila dilakukan dengan cara sebagai berikut :

•         Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang diperluas terlebih dulu.

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

Ambiguitas

Ambiguitas atau kedwiartian terjadi jika terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai. Misalkan terdapat contoh soal 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”.

Untuk memperoleh untai ‘aabbccdd’ terdapat dua cara penurunan untuk menyelesaikannya. Berikut cara penyelesaiannya:

CARA I

 

CARA II

 

String ambigu merupakan sebuah string yang mempunyai lebih dari satu pohon sintaks atau biasa disebut string ambigu (ambiguous). Sedangkan grammar yang menghasilkan paling sedikit sebuah string ambigu disebut sebagai grammar ambigu.

Daftar Pustaka:

https://www.academia.edu/37758551/Pohon_Penurunan

Penjelasan selengkapnya:
https://youtu.be/h7_rj0rM7FU