Saturday, April 18, 2020
Pohon Deviratif Tata Bahasa Bebas
Konteks
Bahasa
Bebas Konteks atau Context
Free Grammar (CFG) adalah sebuah tata bahasa yang dimana tidak terdapat pembatasan pada
hasil produksinya, Contoh Pada aturan produksi :
α → β
Batasannya
hanyalah ruas kiri (α) yang dimana adalah
sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG
adalah seperti di bawah :
- B → CDeFg
- D → BcDe
Latar
Belakang Context Free Grammar (CFG)
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.
PARSING
Proses
parsing yakni adalah
suatu proses
pembacaan string dalam bahasa sesuai CFG tertentu, proses ini harus mematuhi
aturan produksi dalam CFG tersebut. 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 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 ingin
dicari gambar pohon penurunan dengan string : ‘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 Grammar sebagai berikut :
- S → aAS | a
- A → SbA | ba
Untuk
memperoleh string ‘aabbaa’ dari grammar
diatas dilakukan dengan cara :
- Penurunan terkiri: S => aAS => aSbAS => aabAS => aabbaS => aabbaa.
- Penurunan terkanan : S => aAS => aAa => aSbAa => aAbbaa => aabbaa.
Video :
.
Source : https://ztudent101.blogspot.com/2020/04/pohon-deviratif-tata-bahasa-bebas.html
