A.
Tata
Bahasa Bebas Konteks
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 sebagai CFG, tidak terdapat pembatasan
hasil produksinya. Pada aturan produksi :
A
→ b
batasannya hanyalah ruas kiri (A) dalah sebuah simbol variabel. Contoh aturan produksi yang
termasuk CFG :
B
→ CdeFg
D
→ BcDe
Seperti halnya
pada tata bahasa reguler, 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, simbol – 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 bisa 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/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator
kebanyakan didefinisikan dalam tata bahasa bebas konteks.
Terinspirasi dari bahasa natural manusia,
ilmuwan-ilmuwan ilmu komputer yang mengembangkan bahasa pemrograman turut serta
memberikan grammar (pemrograman) secara formal. 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.
B.
Pohon
Penurunan
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 sintaks / 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.
C.
Parsing
Sebuah pohon (tree) adalah suatu graph terhubung tidak
sirkuler, yang memiliki satu simpul (node)/vertex yang disebut akar (root) dan
dari situ memiliki lintasan ke setiap simpul. Gambar dibawah ini memberikan
contoh sebuah tree yang menguraikan kalimat dalam bahasa inggris.
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.
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.
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). metode ini meliputi:
-
Backtrack/backup : Brute Force
-
No Backtrack : Recursive Descent Parser
2. Bottom
– Up
Metode ini melakukan
penelusuran dari leaf ke root (dari kalimat x sampai symbol
awal S)
Proses
penurunan atau parsing bisa dilakukan dengan cara sebagai berikut :
1. Penurunan
terkiri (leftmost derivation) :
simbol variabel terkiri yang diperluas terlebih dulu.
2. Penurunan
terkanan (rightmost derivation):
simbol variabel terkanan yang diperluas terlebih dahulu.
Misalnya
terdapat tata bahasa bebas konteks dengan aturan produksi (simbol awal S,
selanjutnya di dalam bab ini digunakan sebagai simbol awal untuk tata bahasa
konteks adalah S):
S à AB
A à aA | a
B à bB | b
Akan
kita gambarkan pohon penurunan untuk memeperoleh untai : ‘aabbb’. Pada pohon
tersebut simbol awal akan menjad 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 simbol terminal. Kalau
kita baca simbol terminal yang ada (pada gambar) dari kiri ke kanan akan
diperoleh untai ‘aabbb’.
Soal
Latihan :
1)
S
→ AA
A → AAA | a | bA| Ab
Buatlah pohon penurunan dari himpunan produksi di atas untuk
membangkitkan string dengan susunan “bbabaaba”
Jawab :
2)
S
→ AB
A → Aa | bB
B → a | Sb
Buatlah pohon penurunan dari himpunan produksi diatas untuk
membangkitkan string dengan susunan “baabaab”
Jawab :
3)
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 :
D.
Ambiguitas
Ambiguitas / kedwiartian terjadi bila terdapat lebih
dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.
Soal Latihan :
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
:
Soal diatas memilki 2 pohon penurunan yang berbeda tetapi untai string yang dibangkitkan sama.
Untuk lebih jelasnya lagi, kalian dapat menonton video pembahasan lengkap mengenai pohon penurunan/ parsing tree di video di bawah ini. Let's play!!
DAFTAR PUSTAKA
http://eywatsauroty.blogspot.com/2014/09/tata-bahasa-bebas-konteks.html?m=1
https://www.coursehero.com/file/41091318/5-6-Pohon-Penurunan-dan-Penyederhanaanpdf/
https://s.docworkspace.com/d/AGf0fEqe6dYnwtb93vWmFA
Tidak ada komentar:
Posting Komentar