Teori Bahasa Dan Automata - Tata Bahasa Bebas Konteks (Pohon Penurunan)

Dibuat Oleh pada
Assalamualaikum Wr. Wb.

Pada postingan ini saya akan membagikan sebuah materi penyederhanaan tata bahasa bebas konteks. Tujuan saya membuat postingan ini adalah untuk memenuhi Tugas Materi 6 pada Mata Perkuliahan TEORI BAHASA DAN AUTOMATA.

POHON PENURUNAN

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

PARSING

Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node)/vertex yang disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. Gambar dibawah ini memberikan contoh sebuah tree yang menguraikan kalimat dalam bahasa inggris.

Context Free Grammar ( CFG ) menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan di definisikan dalam tata bahasa bebas konteks

Pohon penurunan  (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol–simbol terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Proses Parsing merupakan tahapan analisis sintaksis yang berguna untuk memeriksa urutan kemunculan token. Di dalam mengimplementasikan sebuah metode parsing ke dalam program perlu diperhatikan tiga hal sebagai berikut:
  • Rentang Waktu eksekusi
  • Penanganan Kesalahan
  • Penanganan Kode

Misalnya terdapat tata bahasa bebas konteks dengan aturan produksi (simbol awal S, selanjutnya di dalam bab ini digunakan sebagai simbol awal untuk tata bahasa konteks adalah S):
        S à AB
        A à aA | a
        B à bB | b

Akan kita gambarkan pohon penurunan untuk memeperoleh untai: ‘aabbb’. Pada pohon tersebut simbol awal akan menjad akar (root). Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi. Simbol – simbol variabel akan menjadi simpul  - simpul yang mempunyai anak. Simpul-simpul yang tidak mempunyai anak akan menjadi simbol terminal. Kalau kita baca simbol terminal yang ada (pada gambar) dari kiri ke kanan akan diperoleh untai ‘aabbb’.
Gambar 1

        Proses penurunan atau parsing bila dilakukan dengan cara sebagai berikut:
  1. Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang diperluas terlebih dulu.
  2. Penurunan terkanan (rightmost derivation): simbol variabel terkanan yang diperluas terlebih dahulu.

Contoh
Terdapat tata bahasa bebas konteks:
        S à aAS | a
        A à SbA | ba

Untuk memperoleh untai ‘aabbaa’ dari tata bahasa bebas kontkeks diatas (tanda ‘=>’ bisa dibaca ‘menurunkan’):
  • Dengan penuruna terkiri : S => aAS => aSbAS =>aabAS => aabbaS => aabbaa
  • Dengan penurunan terkanan : S => aAS => aAa => aSbAa => aSbaa => aabbaa
Kita dapat melihat pohon penurunannya (pada gambar) meskipun proses penurunannya berbeda, namun akan tetap memiliki pohon penurunan yang sama.
Gambar 2

 Contoh
Biasanya persolaan yang diberikan berkaitan dengan pohon penurunan adalah untuk mencari penurunan yang hasilnya menuju kepada suatu untai yang ditentukan. Daalm hal ini, perlu untuk melakukan percobaan pemilihan aturan produksi yang bisa menuju ke solusi. Misalkan sebuah tata bahasa bebas konteks memiliki aturan produksi sebagai berikut :
        S à B | bA
        A à a | aS | bAA
        B à b | bS | aBB

Pohon penurunan untuk memperoleh ‘aaabbabbba’ bisa dilihat pada gambar 3
Gambar 3

AMBIGUITAS

Ambiguitas/kedwiartian 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 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 penurunannya bisa dilihat pada gambar:

Gambar 4 (a-b-a-c-a)

Gambar 5 (a-b-a-c-a)

Tambahan
Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu string. Misalkan terdapat tata bahasa sebagai berikut :
        S à A | B A à a B à a

Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan sebagai berikut :
         S => A => a S => B => a

Contoh ambiguitas lain:
Diketahui grammar G = {S à SOS|A , O à *|+, A à 0|1|2|…|9} String : 2 * 3 + 7 mempunyai dua pohon sintaks berikut:

Gambar 6

Gambar 7

String ambigu Sebuah string yang mempunyai lebih dari satu pohon sintaks disebut string ambigu (ambiguous). Grammar yang menghasilkan paling sedikit sebuah string ambigu disebutgrammar ambigu.

Kita bisa mlihat bahwa untuk untai yang sama (‘abaca’) dapat dibuat pohon penurunan yang berbeda, maka dapat dikatakan tata bahasa bebas konteks tersebut ambigu. Jadi, untuk menunjukkan bahwa suatu tata bahasa bebas konteks ambigu, bisa dilakukan dengan menemukan untai yang memungkinan pembentukan lebih dari satu pohon penurunan. Ambiguitas dapat menimbulkan masalah pada bahasa – bahasa tertentu, baik bahasa alami maupun pada bahasa pemograman. Bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan art, maka artinya menjadi ambigu

KESIMPULAN

Tata bahasa bebas konteks adalah suatu cara yang menunjukkan bagaimana menghasilkan untai–untai dalam sebuah bahasa, dan tidak terdapat pembatasan pada hasil produksinya.

Pohon sintaks/pohon penurunan (syntax tree/derivaton tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal. Setiap simbol variabel diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan. Proses penurunan atau parsing bisa dilakukan dengan cara:
  1. Penurunan terkiri (leftmost derivation) yaitu simbol variabel terkiri yang diperluas terlebih dahulu.
  2. Penurunan terkanan (rightmost derivation) yaitu simbol variabel terkanan yang diperluas terlebih dahulu.

Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu string. Sebuah string yang mempunyai lebih dari satu pohon sintaks disebut string ambigu (ambiguous). Grammar yang menghasilkan paling sedikit sebuah string ambigu disebut grammar ambigu.


Sekian materi yang saya posting di blog ini. Mohon maaf apabila ada kekurangan dan kesalahan dalam penulisan. Semoga dapat bermanfaat bagi kita semua

Terima Kasih

Wassalamualaikum Wr. Wb.
-----------------------------------------------------------------------------------------------------------------------------------------------
DAFTAR PUSTAKA
  • Materi Persentasi "Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan)" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang
  • Materi Persentasi "Materi 6 Tata Bahasa Bebas Konteks Latihan Parsing" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang
  • Media online: https://www.academia.edu/37758551/Pohon_Penurunan
  • Media online: http://mshang.ca/syntree/  (digunakan untuk membuat pohon penurunan)

Komentar

Posting Komentar