Tujuan
v Melakukan
pembatasan sehingga tidak menghasilkan pohon
penurunan
yang memiliki kerumitan
yang
tidak perlu atau aturan produksi
yang
tidak berarti.
Contoh 1:
v S à AB |
a
v Aàa
v Aturan
produksi S à AB tidak
berarti
karena
B tidak
memiliki penurunan
contoh
2
SàA
AàB
BàC
CàD
D à a| A
Memiliki kelemahan terlalu panjang jalannya padahal berujung
pada
S à a,
Produksi D à A juga menyebabkan
kerumitan
Cara Penyederhanaan
v Penghilangan produksi useless ( tidak berguna )
v Penghilangan produksi unit
v Penghilangan produksi ε
Penghilangan Produksi Useless
Di sini produksi useless
didefinisikan sebagai :
v Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang
akan menghasilkan terminal-terminal seluruhnya.
v Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari
simbol awal, sehingga produksi itu redundan ( berlebih )
Contoh
v S à aSa | Abd | Bde
v A à Ada
v B à BBB | a
Maka :
1.
Simbol variabel A tidak memiliki penurunan yang
menuju terminal, sehingga bias
Dihilangkan
2.
Konsekuensi no (1), aturan produksi S à Abd tidak
memiliki penurunan
Penyederhanaan
menjadi:
S à aSa | Bde
B à BBB | a
S à Aa | B
A à ab | D
B à b | E
C à bb
E à aEa
Contoh
Maka :
a)
Aturan produksi A à D, simbol variabel D tidak memiliki penurunan.
b)
Aturan produksi C à bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah
mencapai
c)
Simbol variabel E tidak memiliki aturan produksi yang menuju terminal
d)
Konsekuensi no (3) Aturan produksi B à E, simbol variabel E tidak memiliki penurunan.
maka produksi yang
useless:
v A à D
v C à bb
v E à aEa
v B à E
Penyederhanaannya
menjadi:
v S à Aa | B
v A à ab
v B à b
Contoh
S à aAb | cEB
A à dBE | eeC
B à ff
C à ae
D à h
Analisa :
v Aturan produksi S à cEB, A à dBE dapat dihilangkan ( E tidak memiliki
penurunan)
v Aturan produksi D à h, redundan
Sisa aturan produksi
S à aAb
A à eeC
B à ff
C à ae
Analisis lagi
B à ff juga redundan,
Hasil penyederhanaan
menjadi:
S à aAb
A à eeC
C à ae
vContoh lain lagi :
S à aB
A à bcD | dAC
B à e | Ab
C à bCb | adF | ab
F à cFB
Analisis
v Aturan produksi A à bcD, variabel D
tidak memiliki penurunan
v Konsekuensi no (1), simbol variabeA tidak memiliki penurunan yang menuju
terminal (tinggal A à dAC)
v Konsekuensi no (2), B à Ab tidak memiliki penurunan
v Simbol variabel F tidak memiliki penurunan yang menuju terminal
v Konsekuensi no (4), C à adF tidak
memiliki penurunan
Setelah disederhanakan
menjadi
S à aB
B à e
C à bCb | ab
Contoh lain lagi :
S à aBD
B à cD | Ab
D à ef
A à Ed
F à dc
Analisa
v Aturan produksi A à Ed, E tidak
memiliki penurunan
v Aturan produksi F à dc, redundan
Sisa aturan produksi:
S à aBD
B à cD | Ab
D à ef
v Analisa lagi
B à Ab, A tidak memiliki penurunan.
v Hasil penyederhanaan:
S à aBD
B à cD
D à ef
Contoh
lagi
S à Abc | ab
A à AAA | ε
Aturan produksi setelah
disederhanakan:
S à Abc | ab
A à AAA | ε
Ingat A à ε juga harus diperhitungkan
PRINSIP : Setiap kali
melakukan penyederhanaan
diperiksa lagi aturan
produksi yang tersisa, apakah semua produksi yang useless sudah hilang.
Menghilangkan
produk unit
v Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu
simbol variabel, misalkan: A à B, C à D.
v Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.
v Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi
unit.
Contoh
S à Sb
S à C
C à D
C à ef
D à dd
Dilakukan penggantian
berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan
terminal-terminal (‘=>’ dibaca ‘menjadi’):
C à D => C à dd
S à C => S à dd | ef
Sehingga aturan
produksi setelah penyederhanaan:
S à Sb
S à dd | ef
C à dd | ef
Contoh
lainnya
S à A
S à Aa
A à B
B à C
B à b
C à D
C à ab
D à b
Penggantian yang
dilakukan :
C à D => C à b
B à C => B à b | ab, karena B à b sudah
ada, maka cukup
dituliskan B à ab
A à B => A à ab | b
S à A => ab | b
Sehingga aturan
produksi setelah penyederhanaan:
S à ab | b
S à Aa
A à ab | b
B à ab
B à b
C à b
C à ab
D à b
Contoh
lagi
S à Cba | D
A à bbC
B à Sc | ddd
C à eAn | f | C
D à E | SABC
E à gh
Penggantian yang
dilakukan:
D à E menjadi D à gh
C à C , kita hapus
S à D menjadi S à gh | SABC
Sehingga aturan
produksi setelah penyederhanaan:
S à Cba | gh | SABC
A à bbC
B à Sc | ddd
C à eA | f
D à gh | SABC
E à gh
Penghilangan Produksi ε
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 lagi, terdapat
tata bahasa bebas konteks:
S à Ab | Cd
A à d
C à ε
Variabel yang nullable
adalah variabel C. Karena penurunan C à ε merupakan
penurunan satu-satunya dari C, maka kita ganti S à Cd menjadi S à d. Kemudian
produksi C à ε kita hapus
Setelah penyederhanaan
menjadi:
S à Ab | d
A à d
Contoh lain lagi:
S à dA | Bd
A à bc
A à ε
B à c
Variabel yang nullable
adalah variabel A. A à ε bukan penurunan satu-satunya dari A (
terdapat A à bc ), maka kita
ganti S à dA menjadi S à dA | d.A à ε kita hapus.
Setelah penyederhanaan
:
S à dA | d | Bd
A à bc
B à c
Contoh tata bahasa
bebas konteks:
S à AaCD
A à CD | AB
B à b | ε
C à d | ε
D à ε
Variabel yang nullable
adalah variabel B, C, D. Kemudian dari
A à CD, maka variabel A juga nullable ( A
à ε ). Karena D hanya memilki penurunan D à ε,
maka kita sederhanakan
dulu:
S à AaCD => S à AaC
A à CD => A à C
D à ε kita hapus
Selanjutnya kita lihat
variabel B dan C memiliki penurunan e, meskipun bukan satu-satunya penurunan,
maka dilakukan penggantian:
A à AB => A à AB | A | B
S à AaC => S à AaC | aC | Aa | a
B à ε dan C à ε kita hapus
Setelah penyederhanaan:
S à AaC | aC | Aa | a
A à C | AB | A | B
B à b
C à ε
Variabel yang nullable
adalah A, B, C. Dari S à AB, maka S juga
nullable.
Kita lakukan
penggantian:
A à aCa => A à aa
B à bA => B à bA | b
B à BB => B à BB | B
A à abB => A à abB | ab
S à AB => S à AB | A | B | ε
C à ε, B à ε, A à ε dihapus
*Perhatikan untuk
penggantian S àAB kita tetap
mempertahankan S à e, karena S
merupakan simbol awal. Ini merupakan satu-satunya perkecualian produksi e yang
tidak dihapus, yaitu produksi ε yang
dihasilkan oleh simbol awal.
Hasil akhir dari
penyederhanaan:
S à AB | A | B | ε
A à abB | ab | aa
B à bA | b | BB | B
Contoh tata bahasa
bebas konteks:
S à aAb
A à aAb | ε
Hasil penyederhanaan:
S à aAb | ab
A à aAb | ab
Contoh tata bahasa
bebas konteks:
S à ABaC
A à BC
B à b | ε
C à D | ε
D à d
Hasil penyederhanaan:
S à ABaC | BaC | AaC | ABa | aC | Aa |Ba | a
A à B | C | BC
B à b
C à D
D à d
v Prakteknya ketiga penyederhanaan tersebut
dilakukan bersama pada suatu tata bahasa bebas konteks, yang nantinya
menyiapkan tata bahasa bebas konteks tersebut untuk diubah kedalam suatu bentuk
normal Chomsky.
v Urutan penghapusan aturan produksi
a) Hilangkan produksi ε
b) Hilangkan produksi unit
c) Hilangkan produksi useless
contoh
S à AA | C | bd
A à Bb | ε
B à AB | d
C à de
Hilangkan produksi ε, sehingga menjadi:
S à A | AA | C | bd
A à Bb
B à B | AB | d
C à de
Selanjutnya
penghilangan produksi unit menjadi:
S à Bb | AA | de | bd
A à Bb
B à AB | d
C à de
v Penghilangan produksi unit bisa menghasilkan produksi useless.
v Terakhir dilakukan penghilangan produksi useless:
S à Bb | AA | de | bd
A à Bb
B à AB | d
v Hasil akhir aturan produksi tidak lagi memiliki produksi e, produksi
unit, maupun produksi useless.
Tatabahasa Bebas Konteks dan
Bahasa Pemrograman
Tatabahasa bebas konteks digunakan
untuk mendefinisikan sintaks bahasa pemrograman
Menggunakan notasi BNF (BackusNaur
Form)
variabel / non terminal : <...>
terminal : tanpa tanda
à
diganti
dengan ::=
Contoh statemen if then else
< if_statement> ::= if
<expression>
<then_clause>
<else_clause>
Posting Komentar