Latihan 6 : Tata Bahasa Bebas Konteks : "Pohon Penurunan"

Assalammualaikum Warahmatullahi Wabarakaatuh. Saya


NAMA    : RIZKY DARMAWAN
NPM       : 1810631170022
KELAS   : 4B
PRODI    : TEKNIK INFORMATIKA


Dalam blog kali ini saya akan membahas soal Latihan Membuat Pohon Penurunan Parsing/Parse Tree : Tata Bahasa Bebas Kontek dan Latihan Membuat Pohon Penurunan Ambiguitas : Tata Bahasa Bebas Kontek.

Untuk menjawab soal latihan ini yang harus dilakukan adalah simbol awal dari tata bahasa bebas konteks menjadi akar dari pohon penurunannya(root). Setelah itu melakukan percobaan kepada aturan produksi yang ada dalam soal dan memilih aturan produksi yang dapat menuju ke solusi sesuai dengan untai pohon penurunan yang terdapat pada soal.

Parsing

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 simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.

Ambiguitas

Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.

Soal Latihan 1 Parsing/Parse Tree

S → AA

A → AAA | a | bA | Ab 

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbabaaba".

Jawab :        

                                

Soal Latihan 2 Parsing/Parse Tree

S → AB

A → Aa | bB

B → a | Sb

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "baabaab".

Jawab :

Soal Latihan 3 Parsing/Parse Tree

S → Ba | Ab

A → Sa | Aab | a

B → Sb | Bba | b

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbaaaabb".

Jawab :

Latihan Membuat Pohon Penurunan Ambiguitas Tata Bahasa Bebas Konteks

Soal Latihan 1 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".

Jawab :

Untuk menjawab soal latihan 4 ini ada dua cara penyelesaian :

1.  S → AB | C

    A → aAb | ab

    B → cBd | cd

2. S → AB | C

    C → aCd | aDd

    D → bDc | bc

Laman lainnya :

http://eywatsauroty.blogspot.com/2014/09/tata-bahasa-bebas-konteks.html

https://www.youtube.com/watch?v=MS0z1onpsFY&list=WL&index=13&t=0s