Tata Bahasa Bebas Konteks POHON PENURUNAN

Hirarki Chomsky

Tata bahasa ( grammar ) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Pada tahun 1959, seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut dengan hirarki Chomsky. Penggolongan tersebut bisa dilihat pada 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.

Context Free Grammar (CFG)/ Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :

α → β

batasannya hanyalah ruas kiri (α) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :

B → CDeFg

 D → BcDe

Context Free Grammar ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

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.
• Poh on 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

S -> AA

A-> AAA | a | bA | Ab

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

Akan kita gambarkan pohon penurunan untuk memperoleh untai : “bbabaaba”

Gambar 1. Pohon Penurunan untuk untai “bbabaaba”

-          - Pada pohon tersebut simbol awal akan menjadi akar (root).

-          - Setiap kali penurunan dipilih aturan produksi  yang menuju solusi.

-          - Simbol-simbol variabel (huruf besar) akan menjadi simpul-simpul yang mempunyai anak.

-          - Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal (huruf kecil)

-          - Kalau kita baca simbol terminal yang ada pada gambar 1 dari kiri ke kanan akan diperoleh untai          “bbabaaba”.

Contoh 2

S -> AB

A -> Aa | bB

B -> a | Sb

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

Akan kita gambarkan pohon penurunan untuk memperoleh untai : “baabaab”

Gambar 2. Pohon Penurunan untuk untai : “baabaab”

-          - Pada pohon tersebut simbol awal akan menjadi akar (root).

-          - Setiap kali penurunan dipilih aturan produksi  yang menuju solusi.

-          -  Simbol-simbol variable (huruf besar) akan menjadi simpul-simpul yang m empunyai anak.

-          - Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal (huruf kecil).

-          - Kalau kita baca simbol terminal yang ada pada gambar 1 dari kiri ke kanan akan diperoleh

        untai“baabaab”.

Contoh 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”

Akan kita gambarkan pohon penurunan untuk memperoleh untai : “bbaaaabb”

Gambar 3. Pohon Penurunan untuk untai : “bbaaaabb”

-       -   Biasanya persoalan yang diberikan berkaitan dengan pohon penurunan adalah untuk mencari              penurunan yang hasilnya menuju pada suatu untai yang ditentukan.

     -  Dalam hal ini, perlu untuk melakukan percobaan pemilihan aturan produksi yang bisa menuju ke solusi.

Ambiguitas

Ambiguitas/ke-dwi adalah terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu string/untai.

Contoh 1

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”

Pohon penurunan untaian : “aabbccdd” (1)

Pohon penurunan untaian : “aabbccdd” (2)

-    Kita bisa melihat bahwa untuk untai yang sama (“aabbccdd”) dapat dibuat pohon penurunan yang berbeda, maka bahwa dapat dikatakan tata bahasa bebas konteks tersebut ambiguitas.

-   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 ambigutas.

Berikut ini video penjelasan dari Latihan soal diatas :