Assalamualaikum Wr. Wb.
Pada kesempatan kali ini saya ingin membahas materi tentang pohon penurunan tata bahasa bebas konteks.
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
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:
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’:
- 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’:
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
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
- S => SbS => SbScS => SbSca => Sbaca => abaca
- S => ScS => SbScS => abScS => abacS => abaca
Pohon penurunan untai 'abaca' (2) :
Kita bisa melihat bahwa untuk untai yang sama (‘abaca’) dapat dibuat pohon penurunan yang berbeda, maka dapat dikatakan bahwa 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.
Wassalamualaikum Wr. Wb.
Daftar Pustaka:
Materi 6 Tata Bahasa Bebas Konteks (Pohon Penurunan) [pdf]. Dosen Pengampu: Garno, M.Kom. Fakultas Ilmu Komputer, Universitas Singaperbangsa Karawang.
EmoticonEmoticon