PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

DIPOSTING OLEH NABILA AURELIA RAHMA DI JUMAT, 10 April 2009

• PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Tata Bahasa Bebas Konteks (Context Free Grammar atau CFG) merupakan salah satu bahasa formal yang dapat digunakan untuk mendefinisikan sintak bahasa pemograman. Tujuan dari Penyederhanaan adalah untuk 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 cara-cara sebagai berikut: 

1. Penghilangan produksi useless ( tidak berguna )
2. Penghilangan produksi unit
3. Penghilangan produksi empty

• Penghilangan Produksi Useless

Di sini produksi useless didefinisikan sebagai :
- Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.
- Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan ( berlebih )

Contoh :
S → aSa | Abd | Bde
A → Ada
B → BBB | a
Maka
1) Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa
dihilangkan
2) Konsekuensi no (1), aturan produksi S → Abd tidak memiliki penurunan

Penyederhanaan menjadi:
S → aSa | Bde
B → BBB | a

Contoh :
S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa

Maka :
1) Aturan produksi A → D, simbol variabel D tidak memiliki penurunan.
2) Aturan produksi C → bb, Penurunan dari simbol S, dengan jalan manapun tidak
akan pernah mencapai C
3) Simbol variabel E tidak memiliki aturan produksi yang menuju terminal
4) Konsekuensi no (3) Aturan produksi B → E, simbol variabel E tidak memiliki
penurunan.
maka produksi yang useless:
A → D
C → bb
E → aEa
B → E
Penyederhanaannya menjadi:
S → Aa | B
A → ab
B → b

• Penghilangan Produksi Unit

Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel,
misalkan: A → B, C → D.
Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.
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
C → ef
C → dd

• Penghilangan Produksi empty(ε)

Produksi ε adalah produksi dalam bentuk
a → ε

atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi e
dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa
menuju produksi e, 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 → e bukan satu-satunya produksi dari A, maka hasil
penyederhanaan:

S → bcAd | bcd
A → bd


Contoh :

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

Prakteknya ketiga penyederhanaan tersebut dilakukan bersama pada suatu tata bahasa bebas konteks.

Berikut video contoh penjelasan :