Tata Bahasa Bebas Konteks POHON PENURUNAN
Tata Bahasa Bebas Konteks
Pohon Penurunan
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:
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 :
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.
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”
:
http://eywatsauroty.blogspot.com/2014/09/tata-bahasa-bebas-konteks.html
Komentar
Posting Komentar