TATA BAHASA BEBAS KONTEKS POHON PENURUNAN

Hirarki Chomsky

Pada tahun 1959,seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat,yang disebut dengan hirarki chomsky. Penggolongan tersebut bisa diketahui melalui tabel berikut.

Tata Bahasa Bebas Konteks (Context Free Grammar/CFG)

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebas konteks.

• Bila pada tata bahasa regular terdapat pembatasan pada ruas kanan atau hasil produksinya, maka pada tata bahasa bebas konteks/context free grammar, selanjutnya kita sebut CFG, tidak terdapat pembatasan hasil produksinya. 
  Pada aturan produksi: 
  a–>b
• batasannya hanyalah ruas kiri (a) adalah sebuah simbol variabel. 
• Contoh aturan produksi yang termasuk CFG : 
  B–>CDeFg
  D–>BcDe

PARSING

• Sebuah pohon (tree) adalah : suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) /vertex yang disebut akar (root) dan dari root memiliki lintasan ke setiap simpul.
• Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol non terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Contoh 1

• Misalnya terdapat tata bahasa bebas konteks dengan aturan produksi (simbol awal S, selanjutnya digunakan sebagai simbol awal untuk tata bahasa bebas konteks adalah S).

  S –> AB

  A –> aA | a

  B –> bB | b
• Akan kita gambarkan pohon penurunan untuk memperoleh untai : ‘aabbb’.
• Pada pohon tersebut simbol awal akan menjadi akar (root).
• Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi.
• Simbol-simbol variabel (huruf besar) akan menjadi simpul-simpul yang mempunyai anak.
• Simpul-simpul yang tidak mempunyai anak akan menjadi simbol terminal (huruf kecil).
• Kalau kita baca simbol terminal yang ada pada  gambar dari kiri kekanan akan diperoleh untai ‘aabbb’ :

POHON PENURUNAN UNTUK UNTAI ‘aabbb’

Proses penurunan atau parsing bisa dilakukan dengan cara sebagai berikut :

• Penurunan terkiri (leftmost derivation) : simbol variabel terkiri yang diperluas terlebih dahulu.
• Penurunan terkanan ( rightmost derivation) : simbol variabel terkanan yang diperluas terlebih dahulu.

Contoh 2

• Misal, terdapat tata bahasa bebas konteks :

  S –> aAS | a

  A –> SbA | ba

  Untuk memperoleh untai ‘aabbaa’ dari tata bahasa bebas konteks diatas (‘=>’ bisa dibaca ‘menurunkan’)

  
  

• Dengan penurunan terkiri:

  S => aAS => aSbAS => aabAS => aabbaS => aabbaa,

  
  

• Dengan penurunan terkanan :
  S => aAS=> aAa=>aSbAa=>aSbbaa=>aabbaa.
  
  
  Kita dapat melihat pohon penurunannya pada gambar meskipun proses penurunannya berbeda, namun akan tetap memiliki pohon penurunan yang sama.

POHON PENURUNAN UNTUK UNTAI ‘aabbaa’

Contoh 3

• 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.
• Misalnya sebuah tata bahasa bebas konteks memiliki aturan produksi sebagai berikut.

  S –> aB | bA

  A –> a | aS | bAA

  B –> b | bS | Abb

POHON PENURUNAN UNTUK MEMPEROLEH  ‘aaabbabbba’ BISA DILIHAT PADA GAMBAR

CONTOH IMAGE PARSING UNTUK MENENTUKAN TEKS , WAJAH DAN LATAR

CONTOH IMAGE PARSING

• Fungsinya : proses parsing image untuk memahami suatu gambar menjadi 4 aspek perhitungan ruang.

1. Menghitung 3D scene layout
2. Deteksi obyek 3D . c/: Furniture
3. Deteksi obyek 2D. c/: Jendela, Pintu
4. Segmentasi backround

AMBIGUITAS

• Ambiguitas/ke-dwi artian 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 berikut ini.

  S=>A=>a

  S=>B=>a
• Contoh yang lain, terdapat tata bahasa bebas konteks :

  S–>SbS | ScS | a
• Kita bisa menurunkan untai ‘abaca’ dalam dua cara berikut ini

1. S=>SbS => SbScS => SbSca => Sbaca => abaca
2. S=>ScS => SbScS => abScS => abacS => abaca

POHON PENURUNAN UNTAI ‘abaca’ (1)

• Kita bisa melihat bahwa untuk untai yang sama (‘abaca’) dapat dibuat pohon penurunan yang berbeda, maka bahwa dapat dikatakan tata bahasa bebas konteks tersebut ambigu.
• Jadi, untuk menunjukan 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 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.

Latihan Membuat Pohon Penurunan Parsing/Parse Tree Tata Bahasa Bebas Kontek

Latihan  Parsing/Parse tree 

Latihan 1

S –> AA
A –> AAA | a | bA | Ab

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbabaaba”

Latihan 2 

S –> AB
A –> Aa | bB
B –> a | Sb

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “baabaab”

Latihan 3

S –> Ba | Ab
A –> Sa | Aab | a
B –> Sb | Bba | b

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbaaaabb”

Latihan Membuat Pohon Penurunan Ambiguitas Tata Bahasa Bebas Kontek 

Latihan  Ambiguitas

S –> AB | C
A –> aAb | ab
B –> cBd | cd
C –> aCd | aDd
D –> bDc | bc

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “aabbccdd”

Jawaban dari soal latihan diatas 

 

Berikut adalah video penjelasan dari latihan diatas