Selasa, 09 September 2014
Tata Bahasa Bebas Konteks
CFG / Bahasa Bebas Konteks adalah sebuah
tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh
Pada aturan produksi :
a → b
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.
S
→ AB
A
→ aA | a
B
→ bB | b
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
Demikianlah sedikit membahas tentang Tata Bahas Bebas Konteks. semoga bermanfaat.. dan Terima kasih atas kunjungan nya..
Tata Bahasa Bebas Konteks
BalasHapus