TEORI BAHASA DAN AUTOMATA
Tata Bahasa Bebas Konteks (POHON PENURUNAN)
- Hirarky Chomsky
Tata Bahasa Bebas Konteks (Context Free Grammar/CFG)
Adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis, bagian sintaksis dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebaas konteks.
Terbagi menjadi 2 yaitu PARSING dan AMBIGUITAS
1. PARSING
Pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) yang disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurukan simbol-simbol variabel menjadi simbol-simbol terminal.
Latihan 1
S → AB
A → AAA | a | bA | Ab
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan "bbabaaba".
Jawab :
Baca variabel terminal dari kiri ke kanan, maka susunan string akan sesuai dengan susunan "bbabaaba".
Latihan 2
S → AB
A → Aa | bB
B → a | Sb
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan "baabaab".
Jawab :
Dengan demikian susunan simpul sudah sesuai dengan susunan string "baabaab".
Latihan 3
S → Ba | Ab
A → Sa | Aab | a
B → Sb | Bba | b
Jawab :
Pada soal ini kita bisa menyelesaikan dengan dua metode yaitu leftmost derivation dan rightmost derivation. Namun, karena produksi S → Ba (leftmost derivation) akan menyebabkan susunan string berakhiran "...a" sementara string "bbaaaabb" berakhiran b maka produksi S → Ba tidak valid dijadikan sebagai akar (root). Dengan demikian akar dari parse tree memakai produksi S → Ab.
Dengan demikian susunan simpul sudah sesuai dengan susunan string "bbaaaabb".
2. AMBIGUITAS
Terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.
Latihan 1
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan "aabbccdd".
Jawab :
CFG dikatakan ambigu apabila terdapat penurunan yang dapat dikerjakan dengan dua cara sekaligus, lebih dari satu leftmost derivation dan lebih dari satu rightmost derivation.
Leftmost Derivation
S => AB => aAbcBd => aabbccdd
Pohon 1 :
Adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis, bagian sintaksis dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebaas konteks.
Terbagi menjadi 2 yaitu PARSING dan AMBIGUITAS
1. PARSING
Pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) yang disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurukan simbol-simbol variabel menjadi simbol-simbol terminal.
Latihan 1
S → AB
A → AAA | a | bA | Ab
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan "bbabaaba".
Jawab :
Latihan 2
S → AB
A → Aa | bB
B → a | Sb
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan "baabaab".
Jawab :
Latihan 3
S → Ba | Ab
A → Sa | Aab | a
B → Sb | Bba | b
Jawab :
Pada soal ini kita bisa menyelesaikan dengan dua metode yaitu leftmost derivation dan rightmost derivation. Namun, karena produksi S → Ba (leftmost derivation) akan menyebabkan susunan string berakhiran "...a" sementara string "bbaaaabb" berakhiran b maka produksi S → Ba tidak valid dijadikan sebagai akar (root). Dengan demikian akar dari parse tree memakai produksi S → Ab.
2. AMBIGUITAS
Terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.
Latihan 1
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan "aabbccdd".
Jawab :
CFG dikatakan ambigu apabila terdapat penurunan yang dapat dikerjakan dengan dua cara sekaligus, lebih dari satu leftmost derivation dan lebih dari satu rightmost derivation.
Leftmost Derivation
S => AB => aAbcBd => aabbccdd
Pohon 1 :
Rightmost Derivation
S => C => aCd => aaDdd => aabDcdd => aabbccdd
Pohon 2 :
Dibawah ini merupakan video penjelasan dari penyederhanaan tata bahasa bebas konteks (Pohon Penurunan) :
Daftar Pustaka :
- Materi 6 Perkuliahan "Tata Bahasa Bebas Konteks (Pohon Penurunan)" Dosen pengampu Teori Bahasa dan Automata : Garno, M,Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang
Terimakasih, semoga dapat bermanfaat. Mohon maaf apabila ada kesalahan kata dalam penulisan, jika ada kesalahan silahkan tulis di kolom komentar.
Komentar
Posting Komentar