Materi Tata Bahasa Bebas Konteks Pohon Penurunan

Materi Tata Bahasa Bebas Konteks Pohon Penurunan

Haaai...

Saya Aditya Wijaya (1810631170083) dari kelas 4G,

Dalam artikel kali ini saya akan menjelaskan tentang pohon penurunan tata bahasa bebas konteks. Bagaimana penjelasannya???? Mari kita bahas dibawah ini

Hirarki Chomsky

Tata Bahasa Bebas Konteks
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

Pembahasan:

·         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 bias 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 untai ‘aaabbabbba’:

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
      A → a
Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan berikut ini.
      S => A => a
      S => B => a

Contoh 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) :

Pohon penurunan untai 'abaca' (2) :

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

Demikian artikel saya kali ini semoga bermanfaat bagi pembaca dan dapat memahami tentang materi tentang pohon penurunan tata bahasa bebas konteks. 

Daftar Pustaka:

Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan) dari Dosen Pengampu: Garno, M.Kom. Fakultas Ilmu Komputer, Universitas Singaperbangsa Karawang.

https://www.scribd.com/doc/314979281/Pohon-penurunan

http://lerykapressy.blogspot.com/2018/04/hirarki-chomsky.html

https://fairuzelsaid.wordpress.com/2011/06/16/tbo-context-free-grammar-cfg/