TUGAS MATERI 6

Latihan Membuat Pohon Penurunan Parsing/Parse Tree Tata Bahasa Bebas kontek

Latihan 1

S à AA

A à AAA | a | bA | Ab

Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “bbabaaba”.

Jawab:

  A => AAA
     A => bA (agar mendapat string b sebagai lanjutannya sehingga didapat {bb})
     A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bba})
     A => bA (agar mendapat string b sebagai lanjutannya sehingga didapat {bbab})
     A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bbaba})
     A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bbabaa})
Pada simpul kanan (S => A) :
     A => bA (agar mendapat string b sebagai lanjutannya maka kita dapat {bbabaab})
     A => a (agar mendapat string a sebagai lanjutannya maka kita dapat {bbabaaba})

     S => bA (agar mendapat string b sebagai awal sehingga didapat {b})

Pohon penurunan untuk susunan string "aabbaaba"

Latihan 2

S à AB

A à Aa | bB

B à a | Sb

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “baabaab”

Jawab:

Pada simpul kiri (S => A) :
     A => Aa (maka didapatkan string a)
     A => Ab (agar mendapat string b sebagai awal sehingga didapat {b})
     B => a (agar mendapat string a sebagai lanjutan sehingga didapat {baa})
Pada simpul kanan (S => B) :
     B => Sb (maka didapatkan string b sebagai akhir sehingga susunannya menjadi {baa...b})
     S => AB
     A => bB (agar mendapat string b sebagai lanjutannya maka susunannya menjadi {baab...b})
     B => a (agar mendapat string a sebagai lanjutannya maka susunannya menjadi {baaba...b})
     B => a (agar mendapat string a sebagai lanjutannya maka susunannya menjadi {baabaab})
Pohon Penurunan untuk susunan string "baabaab" :

Soal Latihan 3 Parsing/Parse Tree

S → Ba | AbA → Sa | Aab | aB → Sb | Bba | b

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

Jawab:

Akar dari pohon dibuat dari aturan produksi S → Ab (karena ini akan membuat susunan string dari pohon akan berakhiran b.
Setelah itu gunakan produksi A → Aab agar mendapatkan string a dan b sehingga susunannya menjadi {...abb}
Setelah itu gunakan produksi A → Sa agar mendapat string a sehingga susunan stringnya menjadi {...aabb}
Setelah itu gunakan produksi S → Ba agar mendapat string a sehingga susunan stringnya menjadi {...aaabb}
Setelah itu gunakan produksi B → Bba agar mendapat string b dan a sehingga susunan stringnya menjadi {...baaaabb}
Setelah itu gunakan produksi B → b agar mendapat string b sehingga susunan stringnya menjadi {bbaaaabb]

Pohon Penurunan untuk susunan string "bbaaaabb" :

Soal Latihan 1 Ambiguitas
S → AB | CA → aAb | abB → cBd | cdC → aCd | aDdD → bDc | bc
Buatlah pohon penurunan dari himpunan produksi diatas 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/atau lebih dari satu rightmost derivation.

Leftmost Derivation

S => AB => aAbcBd => aabbccdd

Parse Tree

S => AB

S =>aAbcBd

S => aabbccdd 

Rightmost Derivation

S => C => aCd => aaDdd => aabDcdd => aabbccdd

Parse Tree

S => C

S => aCd

S => aaDdd

 S => aabDcdd  

S => aabbccdd

Video penjelasan

Sumber materi: https://www.geeksforgeeks.org/introduction-of-parsing-ambiguity-and-parsers-set-1/

thanks to http://mshang.ca/syntree/ for easier draw the parse tree pattern.