Tata Bahasa Bebas Konteks
Bila pada tata bahasa regular terdapat pembatasan pada ruas kanan atau hasl produksinya, maka pada tata bahasa bebas konteks/ context free grammar, selanjutnya kita sebut CFG, tidak terdapat pembatasan hasil produksinya. Pada aturan produksi.
ɑ ->β
batasannya hanyalah ruas kiri (ɑ) 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
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 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)
Contoh Pertama :
misal terdapat tata bahasa bebas konteks
S -> AA
A -> AAA | a | bA | Ab
membangkitkan string bbabaaba
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 diatas dari kiri ke kanan akan diperoleh untai bbabaaba
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
Contoh Kedua :
misal terdapat tata bahasa bebas konteks
S -> AB
A -> Aa | bB
B -> a | Sb
membangkitkan string baabaab, dengan menggunakan penurunan terkiri maka kita dapat lihat hasilnya pada gambar dibawah
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.
Contoh 3 :
Misal terdapat Tata Bahasa Bebas Konteks
S -> Ba | Ab
A -> Sa | Aab | a
B -> Sb | Bba | b
membangkitkan string bbaaaabb
AMBIGUITAS
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 => dibaca menurunkan
Contoh lain :
S -> AB | C
A -> aAb | ab
B -> cBd | cD
D -> bDc | bc
membangkitkan string aabbccdd
- Cara pertama
- Cara kedua
Kita lihat untuk untai yang sama aabbccdd 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. Ambiguitas dapat menimbulkan masalah pada bahasa-bahasa tertentu, baik pada 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.
Referensi :
Tidak ada komentar:
Posting Komentar