Penyederhanaan Tata Bahasa Bebas Konteks Parsing dan Ambiguitas

Tata Bahasa Bebas Konteks Parsing dan Ambiguitas

A.    Parsing

Untuk mengimplementasikan Parser diperlukan TBBK (Context Free Grammar). TBBK adalah sekumpulan simbol-simbol variabel (non-terminal) yang menunjukkan bagaimana menghasilkan untai-untai, yang masing-masing merepresentasikan bahasa. Bahasa yang direpresentasikan dengan simbol-simbol nonterminal tersebut diproses secara rekursif dengan suatu aturan-aturan yang disebut aturan produksi.

Tata bahasa bebas konteks (tipe 2) memiliki elemen:
1. Terminal : simbol dasar yang tidak dapat diturunkan lagi. Terminal disebut juga token.
2. Non terminal : variabel sintaktik yang masih dapat diturunkan lagi.

Pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) yang disebut akar dan dari situ memiliki lintasan ke setiap simpul. Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal.

Proses penurunan atau parsing bisa dilakukan dengan cara:

·         Penurunan terkiri (leftmost derivation). Simbol variabel terkiri yang diperluas terlebih dahulu.

·         Penurunan terkanan (right derivation). Simbol variabel terkanan yang diperluas terlebuh dahulu.

Misal, terdapat tata bahasa bebas konteks:
S → aAS | a
A → SbA | ba
Untuk memperoleh untai ‘aabbaa’ :
Simbol ( => ) dibaca menurunkan
• Dengan penurunan terkiri: S => aAS => aSbAS => aabAS => aabbaS => aabbaa
• Dengan penurunan terkanan: S => aAS => aAa => aSbAa => aSbbaa => aabbaa
Meskipun proses penurunan berbeda, namun akan tetap memiliki pohon penurunan yang sama.

Biasanya persoalan yang diberikan berkaitan dengan pohon penurunan, adalah untuk mencari penurunan yang hasilnya menuju kepada suatu untai yang ditentukan. Dalam hal ini, perlu untuk melakukan percobaan pemilihan aturan produksi yang bisa menuju ke solusi.

B.     Ambiguitas

Terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda utuk memperoleh
suatu untai. Misal terdapat tata bahasa bebas konteks:
S → SbS | ScS | a
Untuk memperoleh untai ‘abaca’

Cara pertama:
S >> SbS >> SbScS >> SbSca >> Sbaca >> abaca

Cara kedua:
S => ScS => SbScS => abScS => abacS => abaca

Contoh Soal :

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 di atas 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 di atas untuk membangkitkan string dengan susunan “bbaaaabb”

Jawab :

4. S -> AB | C
A -> aAb| ab
B -> cBd| cd
C -> aCd| aDd
D -> bDc| bc
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “aabbccdd”.

Jawab :

Video penjelasan :

Penyederhanaan Tata Bahasa dan konteks bebas

Assalamualaikum wr. wb.

Saya Dwiarti Rahma Utami dengan NPM 1810631170174 dari kelas 4C Teknik Informatika FASILKOM UNSIKA.

PENYEDERHANAAN TATA BAHASA DAN KONTEKS BEBAS

Tujuan Penyederhanaan

Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.

contoh :

S -> AB | a

A -> a

Kelemahannya : aturan produksi AB menjadi tidak berarti karena B tidak memiliki penurunan.

Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan cara berikut ini :

1.Penghilangan produksi useless

2.Penghilangan produksi unit

3.Penghilangan produksi E

Penghilangan Produksi Useless

Produksi useless adalah :

• Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan

menghasilkan terminal-terminal seluruhnya (masih ada simbol variabel yang tersisa)

• 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

C -> h

Dapat disimpulkan :

1. Simbol variabel A tidak memiliki penurunan yang menuju terminal jadi bisa dihilangkan.

2. Konsekuensi dari no (1), aturan S -> Abd tidak memiliki penurunan

3. C -> h adalah Redundan

 Maka tata bahasa bebas konteks setelah disederhanakan menjadi :

S -> aSa | Bde

B -> BBB | a

Contoh Penghilangan Useless

S -> aB I C

A -> bcD I dAC

B -> e I Ab

C -> bCb I adF I ab

F -> cFB

Useless :

1. A -> bcD (D tidak punya penurunan)

2. A -> dAC (A tidak punya penurunan ke terminal)

3. B -> Ab ( A tidak punya penurunan)

4. F -> cFB (F tidak punya penurunan ke terminal)

5. C -> adF (F tidak punya penuruanan)

Penghilangan Produksi Unit

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan A -> B, C -> D

Contoh :

S -> Sb

S -> C

C -> D

C -> ef

D -> dd

Penghilangan Produksi E

 Produksi E adalah produksi dalam bentuk αα -> εε atau bisa dianggap sebagai produksi kosong.

Penghilangan produksi εε dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi εε atau biasa disebut nullable.

Contoh :

S -> bcAd

A -> εε

Pada kasus diatas A nullable, maka variabel A bisa ditiadakan.

Hasil penyederhanaan :

S -> bcd

Berikut contoh soal dan jawaban mengenai materi ini :

1.       Penyederhanaan dengan penghilangan produksi Useless

S -> aB | C

B -> e |Ab

C -> bCb | adF | ab

F -> cFB

Jawab :

S  -> aB |C

B  -> e

C  -> bCd | aB

2. Penyederhanaan dengan penghilangan produksi Useless

S -> Aa | B

A -> ab | D

B -> b | E

C -> bb

E -> aEa

Jawab :

S  -> Aa | B

A  -> ab

B  -> b

3.       Penyederhanaan dengan penghilangan produksi Unit

S -> Aa | B

B -> A | bb

A -> a | bc | B

Jawab :

S  -> B menjadi a|bb|bC

B  -> A menjadi a|bc

A  -> B menjadi bb

Hasil,

S  -> Aa|a|bb|bc

B  -> a |bc|bb

A  -> a|bc|bb

4.       Penyederhanaan dengan penghilangan produksi Unit

S -> A | Aa

A -> B

B -> C | b

C -> D | ab

D -> b

Jawab :

S  ->  A menjadi b

A  -> B menjadi b|ab

B  -> C menjadi ab|b

C  -> D menjadi b

Hasil,

S  -> B |Aa

A  -> B |AB

B  -> ab |b|b

C  -> b |ab

D  -> b|b

5.       Penyederhanaan dengan penghilangan produksi Empty (ε)

S -> AB

A -> abB | aCa | ε

B -> bA | BB | ε

C -> ε

Jawab :

S  -> AB | A|B

A   -> abB|ab|aa

B  -> bA|b|BB|B

6.       Penyederhanaan dengan penghilangan produksi Empty (ε)

S -> aBCD | bb | A | ε

A -> CDa | ef

B -> b | Af | ε

C -> BbC | ea

D -> ε

Jawab :

A  -> CDA |eA

B  -> b |Af

C  -> Bbc|bC|ea

7.       Lakukan penyederhanaan pada himpunan produksi berikut dengan penghilangan empty+unit+useless sekaligus.

S -> BACa

B -> AC

A ->dC | ε

C -> D | ε

D -> d

Jawab :

Hasil penyederhanaan unit

S  -> BACA |Baa|BCa|Ba

A  -> AC|dC|d

B  -> dC|d

C  -> d

D  -> d

Hasil penyederhanaan useless

S  -> BACa|BAa|BCa|Bc

B  -> Ac|dc|d

A  -> dc|d

C ->d

Penjelasan soal dan jawaban dalam bentuk video :

Terima kasih.
wassalamualaikum wr. wb.


source materi :
Materi PPT dosen Teori Bahasa dan Automata, Pak Garno (Dosen Unsika).