TATA BAHASA BEBAS KONTEKS POHON PENURUNAN

Tata Bahasa Bebas Konteks (Context Free Grammar/CFG)

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

Jika pada tata bahasa regular terdapat aturan pembatas pada ruas kanan atau hasil produksinya.
Pada aturan produksi : 
           a → b
  • batasannya hanyalah ruas kiri (a) adalah simbol variabel.
  • Contoh aturan produksi CFG : B → CDeFGH atau D → BgFu

PARSING
Sebuah pohon (tree) adalah suatu graph terhubung tidak silkuler, yang memiliki satu simpul (node)/vertex yang disebut akar (root) 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 digantikan. 
Contoh Soal 1 :
Terdapat tata bahasa bebas konteks dengan aturan produksi :
S → AA
A → AAA | a | bA | Ab
Simbol awalnya adalah S.
  • Membuat pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbabaaba".
  • 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 yang memiliki anak.
  • Simbol-simbol terminal (huruf kecil) akan menjadi simpul yang tidak memiliki anak.
  • Gambar yang diperoleh :

  • Penurunan terkiri (leftmost derivation) yaitu simbol variabel terkiri yang diperluas terlebih dahulu.
  • Penurunan terkanan (rightmost derivation) yaitu simol variabel terkanan yang diperluas terlebih dahulu.
Contoh Soal 2 :
Terdapat tata bahasa bebas konteks dengan aturan produksi :
S → AB
A → Aa | bB
B → a | Sb
 Simbol awalnya adalah S. 


  • Membuat pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "baabaab".
  • 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 yang memiliki anak.
  • Simbol-simbol terminal (huruf kecil) akan menjadi simpul yang tidak memiliki anak.
  • Gambar yang diperoleh :

  • Penurunan terkiri (leftmost derivation) yaitu simbol variabel terkiri yang diperluas terlebih dahulu.
  • Penurunan terkanan (rightmost derivation) yaitu simol variabel terkanan yang diperluas terlebih dahulu.
Contoh Soal 3 :
S → Ba | Ab
A → Sa | Aab | a
B →Sb | Bba | b
 Simbol awalnya adalah S. 
  • Membuat pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbaaaabb".
  • 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 yang memiliki anak.
  • Simbol-simbol terminal (huruf kecil) akan menjadi simpul yang tidak memiliki anak.
  • Gambar yang diperoleh :

  • Penurunan terkiri (leftmost derivation) yaitu simbol variabel terkiri yang diperluas terlebih dahulu.
  • Penurunan terkanan (rightmost derivation) yaitu simol variabel terkanan yang diperluas terlebih dahulu.
AMBIGUITAS
Ambiguitas terjadi apabila 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 didapat dengan dua cara penurunan. S => A => a dan S => B =>a. begitupun pada gambar pohon penurunannya.
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 mauoun pada bahasa pemrograman.
Bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan arti, maka artinya ambigu. 
Untuk lebih memahami dengan jelas lagi dengan contoh soal dibawah ini.

Contoh Soal 4 :
S → AB | C
A → aAb | ab
B → cBd | cdC → aCd | aDdD → bDc | bc

Dari aturan produksi diatas, didapat 2 buah pohon penurunan yaitu :

S => C => SCad => SaaDd => SaabDc => aabbccdd  dan
S => AB => SAB=> SabcBd => Saabbccd => aabbccdd

Gambar Pohon Penurunannya adalah :





Comments

Post a Comment