Tata Bahasa Bebas Konteks ( Parsing Tree )

Tata Bahasa Bebas Konteks

 

   Bila pada tata bahasa regular terdapat pembatasan pada ruas kanan atau hasl produksinya, maka pada tata bahasa bebas konteks/ context free grammar, selanjutnya kita sebut CFG, tidak terdapat pembatasan hasil produksinya. Pada aturan produksi.

                                                               ɑ ->β

batasannya hanyalah ruas kiri (ɑ) adalah sebuah symbol variabel. Contoh aturan produksi yang termasuk CFG:

                                                            B -> CDeFg

                                                            D -> BcDe

   Seperti halnya pada tata bahasa regular, sebuah tata bahasa bebas konteks adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Seperti kita ketahui, pada saat menurunkan suatu string, symbol-simbol variabel akan mewakili bagian-bagian yang belum yang belum terturunkan dari string tersebut. Bila pada tata bahasa regular, bagian yang belum terturunkan tersebut selalu terjadi pada suatu ujung, pada tata bahasa bebas konteks bisa terdapat lebih banyak bagian yang belum terturunkan itu dan bisa terjadi dimana saja. Ketika penurunan itu sudah lengkap, semua bagian yang belum terturunkan telah diganti oleh string-string (yang mungkin saja kosong) dari himpunan symbol terminal. Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebas konteks.

Parsing

  Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node)/vertex disebut akar (root) 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. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Misal terdapat tata bahasa bebas konteks dengan aturan produksi (symbol awal S, selanjutnya didalam bab ini digunakan sebagai symbol awal untuk tata bahasa bebas konteks adalah S)

Contoh Pertama :

misal terdapat tata bahasa bebas konteks

S -> AA

A -> AAA | a | bA | Ab

membangkitkan string bbabaaba

Pada pohon tersebut symbol awal akan menjadi akar (root). Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi. Simbol-simbol variabel akan menjadi simpul-simpul yang mempunyai anak. Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal.Kalau kita baca symbol terminal yang ada pada gambar diatas dari kiri ke kanan akan diperoleh untai bbabaaba 

Proses penurunan atau parsing bisa dilakukan dengan cara:

•    Penurunan terkiri (leftmost derivation): symbol variabel terkiri yang diperluas terlebih dahulu.

•    Penurunan terkanan (rightmost derivation): symbol variabel terkiri yang diperluas terlebih dahulu

Contoh Kedua :

misal terdapat tata bahasa bebas konteks

S -> AB

A -> Aa | bB

B -> a | Sb 

membangkitkan string baabaab, dengan menggunakan penurunan terkiri maka kita dapat lihat hasilnya pada gambar dibawah

 

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.

Contoh 3 :

Misal terdapat Tata Bahasa Bebas Konteks

S -> Ba | Ab

A -> Sa | Aab | a

B -> Sb | Bba | b

membangkitkan string bbaaaabb 

AMBIGUITAS 

Ambiguitas/kedwiartian terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai. 

Misalkan terdapat tata bahasa bebas konteks: 

S -> A | B 

A -> a 

B -> a

Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan:

S => A => a

S => B => a                                             => dibaca menurunkan 

Contoh lain :

S -> AB | C

A -> aAb | ab

B -> cBd | cD

D -> bDc | bc

membangkitkan string aabbccdd 

• Cara pertama

 

• Cara kedua

 

 

Kita lihat untuk  untai  yang  sama aabbccdd dapat dibuat pohon penurunan  yang berbeda,  maka  dapat  dikatakan  tata  bahasa  bebas  konteks  tersebut  ambigu.  Jadi untuk  menunjukkan  bahwa  suatu  tata  bahasa  bebas  konteks  ambigu,  bisa  dilakukan dengan  menemukan  untai  yang  memungkinkan  pembentukan  lebih  dari  satu  pohon penurunan.  Ambiguitas  dapat  menimbulkan  masalah  pada  bahasa-bahasa  tertentu, baik  pada  bahasa  alami  maupun  pada  bahasa  pemrograman.  Bila  suatu  struktur bahasa  memiliki  lebih  dari  suatu  dekomposisi  (penurunan),  dan  susunannya  akan menentukan arti, maka artinya menjadi ambigu. 

 

Referensi :

https://dinus.ac.id/repository/docs/ajar/bab%2010_file_2013-05-31_080824_dr.r._heru_tjahjana_s.si_m.si__.pdf 

Penyederhanaan Tata Bahasa Bebas Konteks

Sebuah bahasa formal adalah abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinasikan kedalam entitas yang disebut kalimat. Bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alphabet atau rangkaian simbol-simbol yang mempunyai makna. Bahasa Kosong adalah bahasa yang tidak terdiri dari string-string, dinotasikan dengan ->. Bahasa kosong berbeda dengan bahasa yang terdiri dari string kosong {ε}. Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.

Contoh Penyederhanaan tata bahasa dalam Teori bahasa dan Otomata,berikut adalah

Cara Penyederhanaan:

1. Penghilangan produksi useless ( tidak berguna )

2. Penghilangan produksi unit

3. Penghilangan produksi ε

Pembahasan

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

Contoh 1:

S -> AB | a

A -> a

• 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:

1. Penghilangan produksi useless ( tidak berguna )

2. Penghilangan produksi unit

3. Penghilangan produksi ε

1 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 -> aB | C

B -> e | Ab

C -> bCb | adF | ab

F  -> cFB

Maka :

1) Simbol variabel F tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan

2) Konsekuensi no (3), aturan produksi C -> adF tidak memiliki penurunan

3) Aturan produksi B -> Ab dimana A tidak memiliki penurunan, sehingga bisa dihilangkan  

maka produksi yang useless:

B -> Ab

C -> adF

F -> cFB 

Penyederhanaan menjadi:

S -> aB | C

B -> e

C -> bCb | ab

Contoh selanjutnya

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 atau disebut redundan

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

2. 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 -> Aa | B

B -> A | bb

A -> a | bc | B

Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):

A -> B => A -> bb

B -> A => B -> a | bc

S -> B => S -> a | bc | bb 

Sehingga aturan produksi setelah penyederhanaan:

S -> Aa | a | bc | bb

B -> a | bc | bb

A -> a | bc | bb 

Contoh lain:

S -> A | Aa

A -> B

B -> C | b

C -> D | ab

D -> b

Penggantian yang dilakukan :

C -> D => C -> b

B -> C => B -> b | ab

A -> B => A -> b | ab | b

S -> A => S -> b | ab | b 

Sehingga aturan produksi setelah penyederhanaan:

S -> b | ab | b | Aa

A -> b | ab | b

B -> b | ab | b

C -> b | ab

D -> b

3. Penghilangan Produksi ε

Produksi ε adalah produksi dalam bentuk

α -> ε

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 -> AB

A -> aBCD | aCa | ε

B -> bA | BB | ε 

C -> ε

Maka:

A -> ε, B -> ε, C->ε dapat dihilangkan maka A -> aBCD menjadi A -> aBD dan A -> aCa menjadi A -> aa didapat hasil penyederhanaan:

S-> AB

A ->aBD | aa 

B -> bA | BB

Contoh lagi, terdapat tata bahasa bebas konteks:

S -> aBCD | bb | A | ε

A -> CDa | ef

B -> b | aF | ε

C -> BbC | ea

D -> ε

Variabel yang nullable adalah variabel D, B -> ε, S -> ε. Karena penurunan D -> ε merupakan penurunan satu-satunya dari D, maka kita ganti A -> CDa menjadi A -> Ca dan S -> aBCD menjadi S -> aBC. Kemudian produksi D -> ε, B -> ε, S -> ε kita hapus.

Setelah penyederhanaan menjadi:

S -> aBC | bb | A

A -> Ca | ef

B -> b | aF 

C -> BbC | ea

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.

Urutan penghapusan aturan produksi :

1) Hilangkan produksi ε

2) Hilangkan produksi unit

3) Hilangkan produksi useless

Contoh :

S -> BACa

B -> AC

A -> dC | ε

C -> D | ε

D -> d  

Hilangkan produksi ε, sehingga menjadi:

C -> ε, maka

A -> dC => A => d

B -> AC => B -> A

S -> BACa => S -> BAa, kemudian C -> ε dihapus

A -> ε, maka

B -> AC => B -> A | C

S -> BACa => S -> BAa | Ba, kemudian A -> ε dihapus

Sehingga hasil penyederhanaan: 

S -> BACa | BAa | Ba

B -> AC | A | C

A -> dC | d

C -> D

D -> d

 
Referensi
http://herilovemetallica.blogspot.com/2009/10/penyederhanaan-tata-bahasa-dalam-teori.html