New Post!
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
Pohon Deviratif Tata Bahasa Bebas Konteks
PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS
Penyederhanaan tata bahasa bebas konteks adalah melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.
Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan :
- Penghilangan produksi useless (tidak berguna)
- Penghilangn produksi unit
- Penghilangan produksi ε
Produksi useless didefinisikan sebagai :
Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya, produksi ini tidak berguna karena bila diturunkan tidak akan pernah selesai.
Produksi yang tidak akan pernah di capai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih)
Contoh menghilangkan produksi useless :
S → aB | C
B → e |Ab
C → bCb | adF | ab
F → cFB
Analisis :
B → | Ab ( A tidak punya penurunan , sehingga harus dihilangkan)
F → cFB ( F tidak ada turunan keterminal , sehingga harus dihilangkan)
C → adF ( Karena F sudah di hilangkan , maka C → adF harus dihilangkan karena useless)
B.Penghilangan produksi unit
Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksinya hanya berupa satu simbol variabel misalnya :
A → B, C → D
Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu. Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit. Kita lakukan penggantian (Penghilangan Produksi Unit) berurutan mulai dari aturan produksi paling dekat menuju terminal- terminal.
Contoh penghilangan produksi unit :
S → Aa | B
B → A | bb
A → a | bc | B
Analisis :
Kalau dilihat dari dari teori yang marker merah maka A → B bisa diganti menjadi A → bb.
Sehingga :
A → a | bc | bb
Lalu B → A | bb bisa diubah menjadi
B → a | bc | bb
Lalu S → Aa | B pun bisa diubah menjadi
S → Aa | a | bc | bb
Sehingga hasilnya menjadi :
S → Aa | a | bc | bb
B → a | bc | bb
A → a | bc | bb
C. PenghilangProduksi ε
Produksi ε adalah produksi dalam bentuk :
a → ε
atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε, atau biasa disebut nullable.
Prinsip penggantiannya bisa dilihat kasus berikut:
S → bcAd
A → ε
A nullable serta A → ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi:
S → bcd
Tetapi bila kasusnya:
S → bcAd
A → bd | ε
A nullable, tapi A → ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan:
S → bcAd | bcd
A → bd
Contoh penghilang produksi ε :
S → AB
A → abB | aCa | ε
B → bA | BB | ε
C → ε
Langkah pertama hilangkan C, setelah dihilangkan maka akan menjadi :
S → AB
A → abB | aa | ε
B → bA | BB | ε
Langkah kedua hilangkan B yang mengandung ε, sehingga menjadi :
S → AB | A
A → abB | aa | ε | ab
B → bA | BB
Langkah ketiga hilangkan A yang mengandung ε, setelah dihilangkan menjadi,
S → AB | A | B
A → abB | aa | ab
B → bA | BB | b
Ketika sudah tidak ada ε maka sudah selesai.
Kesimpulan
Dari semua teknik , untuk menyelesaikan suatu penyederhanaan yang kompleks, terdapat alur yang harus dijalani.
Alur penyederhanaan Tata Bahasa :
Contoh Soal Kompleks :
S → BACa
B → AC
A → dC | ε
C → D | ε
D → d
Langkah pertama adalah hilangkan
semua ε, langkah 1 hilangkan C → ε,
makan akan menjadi :
S → BACa | BAa
B → AC | A
A → dC | ε | d
C → D
D → d
selanjutnya hilangkan A → ε,
makan akan menjadi :
S → BACa | BAa | BCa | Ba
B → AC | A | C | ε
A → dC | d
C → D
D → d
selanjutnya hilangkan B → ε,maka akan menjadi :
S → BACa | BAa | BCa | Ba | ACa |
Aa | Ca | a
B → AC | A | C
A → dC | d
C → D
D → d
Langkah kedua menghilangkan
produksi unit
C → D (diubah menjadi C → d )
B → C (diubah menjadi B → d )
B → A (diubah menjadi B → dC | d
)
Sehingga menjadi,
S → BACa | BAa | BCa | Ba | ACa |
Aa | Ca | a
B → AC | dC | d
A → dC | d
C → d
D → d
Langkah ketiga adalah
penghilangan produksi useless, dalam kasus ini , D → d adalah useless (Redundant)
sehingga harus dihapus.
Jadi hasil akhirnya adalah :
S → BACa | BAa | BCa | Ba | ACa |
Aa | Ca | aB → AC | dC | d
A → dC | d
C → d
Sumber : https://ztudent101.blogspot.com/2020/04/test.html
Penyerdehanaan Tata Bahasa Bebas Konteks (Teori Bahasa dan Automata)
Contoh
Penjumlahan Bilangan Desimal Positif dengan Bilangan Desimal Negatif
1. 169(10)
+ (-69)(10) = 100(10)
2. -69(10)
+ 99(10) = 60(10)
Hasil akhir
No. 1 adalah 100 ubah kedalam biner yang menjadi 01100100
Hasil akhir
No. 2 adalah 60 ubah kedalam biner yang menjadi 00111100
Dan
Penjumlahan dalam Biner adalah :
0 1
1 0 0
1 0 0
(100)
0 0 1 1 1 1 0 0 (60)
------------------------ +
1 0 1 0 0 0 0 0
Contoh Penjumlahan Bilangan Desimal Positif dengan Bilangan Desimal Negatif dan Penjumlahan Biner
Apa Itu Bilangan Desimal, Biner, Oktal, Hexadimal ?
Bilangan Desimal adalah bilangan yang terdiri dari 10 angka, yaitu
0,1,2,3,4,5,6,7,8,9. Apabila sudah sampai ke angka 9, maka sistem bilangan akan
kembali lagi ke angka 0 dan nilai angka di depannya bertambah 1.
Bilangan Biner (binery, binery digit, atau bit) adalah bilangan yang
terdiri dari 2 angka yaitu, 0 dan 1. Sama halnya dengan bilangan desimal, jika
sistem bilangan telah mencapai angka terakhirnya, maka akan kembali lagi ke
angka awalnya, dan nilai angka didepannya akan bertambah 1.
Bilangan Oktal adalah bilangan yang terdiri dari 8 angka yaitu,
0,1,2,3,4,5,6,7. Bilangan oktal juga sama seperti bilangan desimal dan biner,
apabila telah mencapai angka terakhir maka akan kembali lagi ke angka awalnya
dan nilai angka didepannya bertambah 1.
Bilangan Hexadesimal adalah bilangan yang terdiri dari 10 angka dan 6
huruf yaitu, 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. Nilai dari huruf A,B,C,D,E,F
adalah lanjutan dari angka pada bilangan hexadesimal.
Bagaimana Cara Konversi Antara Bilangan Desimal,
Biner, Oktal & Hexadesimal ?
1. Bilangan Desimal
Bilangan desimal (decimal) merupakan bilangan dengan
basis 10. Angka untuk bilangan desimal adalah 0, 1, 2, … , 8, 9. Bilangan ini
sering kita gunakan dalam kehidupan sehari-hari.
Rumus Konversi Desimal ke Basis Bilangan Lainnya
Untuk melakukan konversi dari bilangan desimal ke
basis bilangan lainnya, misal basis n, adalah dengan membagi bilangan tersebut
dengan n secara berulang sampai bilangan bulat hasil bagi nya sama dengan nol.
Lalu sisa hasil bagi dari setiap iterasi ditulis dari terakhir (bawah) hingga
ke awal (atas). Untuk lebih jelasnya lihat contoh konversi desimal ke basis
lainnya pada penjelasan berikutnya.
Konversi Desimal ke Biner
Dengan menggunakan rumus perhitungan konversi bilangan
desimal ke basis lainnya kita bisa lakukan sebagai berikut.
Contoh :
6710 = …….2 ?
Misalkan kita akan melakukan konversi 67 basis sepuluh
(desimal) ke dalam basis 2 (biner).
1. Pertama-tama kita bagi 67 dengan 2, didapat
bilangan bulat hasil bagi adalah 33 dengan sisa hasil bagi adalah 1, atau
dengan kata lain 67 = 2*33 + 1
2. Selanjutnya bilangan bulat hasil bagi tersebut (33)
kita bagi dengan 2 lagi, 33/2 = 16, sisa hasil bagi 1.
3. Kemudian kita ulangi lagi, 16/2 = 8, sisa hasil
bagi 0.
4. Ulangi lagi langkah tersebut sampai bilangan bulat
hasil bagi sama dengan 0. Setelah itu tulis sisa hasil bagi mulai dari bawah ke
atas.
5. Dengan demikian kita akan mendapatkan
bahwa 6710 = 10000112.
Konversi Desimal ke Oktal
Dengan rumus yang sama seperti biner kita bisa lakukan juga untuk bilangan berbasis 8 (oktal).
Dengan rumus yang sama seperti biner kita bisa lakukan juga untuk bilangan berbasis 8 (oktal).
Contoh:
6710 = …….8 ?
1. Pertama-tama 67/8 = 8, sisa 3
2. Lalu 8/8 = 1, sisa 0,
3. Terakhir 1/8=0, sisa 1.
4. Dengan demikian dari hasil perhitungan
didaptkan 6710 = 1038
Konversi Desimal ke Hexadesimal
Seperti
halnya biner dan oktal, kita pun akan menggunakan teknik perhitungan yang sama.
Contoh:
6710 =
…….16 ?
1. Pertama-tama 67/16 = 4, sisa 3
2. Lalu 4/16 = 0, sisa 4
3. Dengan
demikian dari hasil perhitungan didapatkan 6710 = 4316
2. Bilangan Biner
Bilangan biner (binary)
merupakan bilangan berbasis dua. Angka dari bilangan biner hanya berupa angka 0
dan 1.
Konversi Biner ke Desimal
Untuk melakukan konversi dari bilangan biner atau
bilangan berbasis selain 10 ke bilangan berbasis 10 (desimal) maka anda tinggal
mengalikan setiap digit dari bilangan tersebut dengan pangkat 0, 1, 2, …, dst,
dari basis mulai dari yang paling kanan.
Contoh:
101102 = …….10 ?
101102 = + 1x24 +
0x23 + 1x22 + 1x21 + 0x20 =
16 + 0 + 4 + 2 + 0 = 2210
Konversi
Biner ke Oktal
Untuk melakukan konversi biner ke oktal lakukan bagi
setiap 3 digit menjadi sebuah angka oktal dimulai dari paling kanan.
Contoh:
101102 = …….8 ?
1. Pertama-tama bagi menjadi kelompok yang terdiri dari
3 digit biner: 10 dan 110.
2. Kemudian konversi setiap kelompok dengan menggunakan
perhitungan konversi biner ke desimal.
3. Sehingga didapat 101102 = 268
Konversi
Biner ke Hexadesimal
Konversi biner ke hexa desimal mirip dengan konversi biner ke oktal.
Hanya saja pembagian kelompok terdiri dari 4 digit biner. Selain itu untuk
nilai 10, 11, 12, .., 15 diganti dengan huruf A, B, C, …, F.
Contoh:
1110102 = …….16 ?
1. Pertama-tama bagi menjadi kelompok yang terdiri dari
4 digit biner: 11 dan 1010.
2. Kemudian konversi setiap kelompok dengan menggunakan
perhitungan konversi biner ke desimal.
3. Sehingga didapat 1110102= 3A16
3. Bilangan
Oktal
Bilangan
oktal (octal) adalah bilangan berbasis 8. Sehingga angka digit yang digunakan
adalah 0, 1, 2, …, 7, 8.
Konversi Bilangan Oktal ke Desimal
Untuk
konversi oktal ke binner anda perlu mengalikan digit dengan pangkat dari
bilangan 8.
Contoh:
3658 =
…….10 ?
Untuk
melakukan konversi bilangan oktal ke bilangan berbasis 10 (desimal) lakukan
dengan mengalikan setiap digit dari bilangan tersebut dengan pangkat 0, 1, 2,
…, dst, dari basis mulai dari yang paling kanan.
3658 = (3 x 82)10 + (6 x 81)10 + (5 x 80)10 = 192 + 48 + 5 = 245
3658 = (3 x 82)10 + (6 x 81)10 + (5 x 80)10 = 192 + 48 + 5 = 245
Konversi Bilangan Oktal ke Biner
Cara
ini merupakan kebalikan cara konversi biner ke oktal. Setiap digit oktal akan
langsung dikonversi ke biner lalu hasilnya digabungkan.
Contoh:
548 = …….2 ?
548 = …….2 ?
1. Pertama-tama
hitung 58 = 1012 (Lihat cara konversi dari
desimal ke biner).
2. Lalu hitung 48 =
1002
3. Sehingga didapat
548 = 1011002
Konversi Bilangan Oktal ke Hexadesimal
Untuk perhitungan secara manual, konversi bilangan
oktal ke desimal dilakukan dengan mengkonversi bilangan oktal ke bilangan basis
antara terlebih dahulu. Ada dua cara yang sering digunakan untuk konversi oktal
ke hexadecimal. Cara pertama konversi dahulu bilangan oktal ke desimal, lalu
dari bilangan desimal tersebut dikonversi lagi ke heksadesimal. Cara kedua
adalah dengan menkonversi bilangan oktal ke bilangan biner, lalu dari biner di
konversi lagi menjadi bilangan heksadesimal. Cara kedua merupakan cara yang
paling sering digunakan.
Contoh :
3658 = …….16
3658 = …….16
1. Konversi bilangan oktal menjadi bilangan biner, angka 3, 6, dan 5 dikonversi terlebih dahulu menjadi
biner 3658 =
11 110 1012
2. Kemudian bilangan biner tersebut dikelompokkan
setiap 4 digit dimulai dari yang paling kanan.
3.Selanjutnya 4 digit biner transformasikan
menjadi heksadesimal 11 110
1012 = F516
4.
Bilangan Hexadesimal
Bilangan heksadesimal (hexadecimal)merupakan bilangan
berbasis 16. Sehingga angka digit yang digunakan adalah 0, 1, 2, …, 8, 9, A, B,
…, E, F dimana A s/d F merupakan nilai untuk 10 s/d 15 desimal.
Konversi
Bilangan Hexadesimal
Untuk konversi heksadesimal ke desimal lakukan
dengan mengalikan digit bilangan heksa dengan pangkat bilangan 16 dari kanan ke
kiri mulai dengan pangkat 0, 1, 2, …, dst.
Contoh:
F516 = …….8 ?
F516 = (15 x 161)10 +
(5 x 16-0)10 = 240 + 5 = 245
Konversi
Bilangan Hexadesimal ke Biner
Cara ini merupakan kebalikan cara konversi biner ke
heksadesimal. Setiap digit heksadesimal langsung dikonversi ke biner lalu
hasilnya dipadukan.
Contoh:
F516 = …….2 ?
F516 = …….2 ?
1. Pertama-tama hitung F16 = 11112 (F16 =
1510 = 11112, Lihat cara konversi dari desimal ke
biner).
2. Lalu hitung 516 = 01012 (harus
selalu dalam 4 digit biner, bila nilai hasil konversi tidak mencapai 4 digit
biner maka tambahkan angka 0 di depan hingga menjadi 4 digit biner).
3. Kemudian didapat F516 = 111101012
Konversi
Bilangan Hexadesimal ke Oktal
Untuk konversi heksa desimal ke oktal mirip dengan
cara konversi oktal ke desimal. Lakukan konversi heksadesimal ke biner terlebih
dahulu lalu dari binner di konversi lagi ke oktal.
Contoh:
F516 = …….8
F516 = …….8
1. Konversi bilangan heksadesimal menjadi bilangan
biner angka F dan 5 dikonversi terlebih dahulu menjadi
biner. F516 =
1111 01012
2. Kemudian bilangan biner tersebut
dikelompokkan setiap 3 digit dimulai dari yang paling kanan
3. Selanjutnya 3 digit biner transformasikan
menjadi oktal 11 110 101 2 =
3658
Operasi Perhitungan Pada Sistem Bilangan
Penjumlahan
1.
Penjumlahan sistem bilangan biner
Aturan dasar dari penjumlahan biner adalah sebagai berikut:
0
+ 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
Dengan aturan tersebut, kita dapat menjumlahkan bilangan biner seperti
penjumlahan bilangan desimal (dilakukan dari kanan ke kiri).
2. Penjumlahan istem bilangan oktal
Aturan dasar dari penjumlahan biner adalah sebagai
berikut:
0 + 0 = 0 0 + 5 = 5 1 + 3 = 4 3 + 5 = 10
0 + 1 = 1 0 + 6 = 6 1 + 5 = 6 4 + 5 = 11
0 + 2 = 2 0 + 7 = 7 1 + 7 = 10 4 + 6 = 12
0 + 3 = 3 1 + 1 = 2 2 + 6 = 10 Dst…
0 + 4 = 4 1 + 2 = 3 2 + 7 = 11
Dengan dasar ini, penjumlahan oktal sama halnya
dengan penjumlahan bilangan desimal.
3. Penjumlahan sistem bilangan heksadesimal
Operasi penjumlahan
heksadesimal sama halnya seperti penjumlahan pada desimal.
Pengurangan
1. Pengurangan sistem bilangan biner
Pengurangan pada sistem bilangan biner diterapkan
dengan cara pengurangan komplemen 1 dan pengurangan komplemen 2 dimana cara
inilah yang digunakan oleh komputer digital.
a. Pengurangan biner menggunakan komplemen 1
Bilangan biner yang akan dikurangi dibuat tetap dan bilangan biner
sebagai pengurangnya diubah ke bentuk komplemen 1, kemudian dijumlahkan. Jika
dari penjumlahan tersebut ada bawaan putaran ujung (end-around carry), maka
bawaan tersebut ditambahkan untuk mendapatkan hasil akhir.
b. Pengurangan
biner menggunakan komplemen 2
Bilangan biner yang dikurangi tetap kemudian bilangan biner sebagai
pengurangnya di komplemen 2, lalu dijumlahkan. Jika hasilnya ada bawaan
(carry), maka hasil akhir adalah hasil penjumlahan tersebut tanpa carry
(diabaikan). Lebih jelasnya dapat dilihat beberapa contoh di bawah ini.
2. Pengurangan sistem bilangan oktal dan heksadesimal
Untuk pengurangan bilangan oktal dan heksadesimal,
polanya sama dengan pengurangan bilangan desimal.
Perkalian
1. Perkalian sistem bilangan biner
Perkalian biner dapat juga dilakukan seperti
perkalian desimal, bahkan jauh lebih mudah karena pada perkalian biner hanya
berlaku empat hal, yaitu :
0 × 0 = 0
0 × 1 = 0
1 × 0 = 0
1 × 1 = 1
2. Perkalian sistem bilangan oktal dan heksadesimal.
Pembagian
1. Pembagian sistem bilangan biner
Untuk pembagian bilangan biner tak ubahnya seperti
pada pola pembagian bilangan desimal.
2. Pembagian sistem bilangan oktal dan heksadesimal
Daftar Pustaka :
https://www.cara.aimyaya.com/2013/02/cara-konversi-bilangan-desimal-biner.htmlhttps://bespus-community.blogspot.com/2012/11/operasi-perhitungan-pada-sistem-bilangan.html
