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.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKkTxPEZNNIZ9HKYslgq7Y3AbO80f6HxNCgukCV-LD8GuY0DwuIkJsPtz-ztdNjH4MxvPuKKzKWk6oDIF-vZA3N575LikJXkKkHWi_1AoesutgwpepDGLnGadDyg7dOTvgxgFojoMoXLN-/s640/chomsy.png)
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–>CDeFgD–>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 –> ABA –> aA | aB –> 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 | aA –> SbA | baUntuk 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 | bAA –> a | aS | bAAB –> b | bS | Abb
CONTOH IMAGE PARSING
- Fungsinya : proses parsing image untuk memahami suatu gambar menjadi 4 aspek perhitungan ruang.
- Menghitung 3D scene layout
- Deteksi obyek 3D . c/: Furniture
- Deteksi obyek 2D. c/: Jendela, Pintu
- 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|BA–>aB–>aUntuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan berikut ini.S=>A=>aS=>B=>a
- Contoh yang lain, terdapat tata bahasa bebas konteks :S–>SbS | ScS | a
- Kita bisa menurunkan untai ‘abaca’ dalam dua cara berikut ini
- S=>SbS => SbScS => SbSca => Sbaca => abaca
- 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”
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”
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”
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
0 Comments