Materi Pembelajaran Teknik Kompilasi "SOAL dan JAWABAN"




Materi Pembelajaran Teknik Kompilasi "SOAL dan JAWABAN" - Soal beserta jawaban berikut ini merupakan rujukan yang akan saya gunakan untuk menghadapi UTS pada akhir bulan Oktober ini. Selain bermanfaat untuk saya. Semoga postingan ini dapat bermanfaat untuk kalian juga ya. Dan jangan lupa do`akan saya untuk kelancaran dalam menghadapi UTSnya. Terima Kasih ^_^




BAB KOMPILATOR SATU JALAN SEDERHANA



1. Untuk menentukan sintaks dari suatu bahasa digunakan ...

Jawab : Untuk menentukan sintaks dari suatu bahasa digunakan tata bahasa bebas konteks (context-free grammar). Untuk memudahkan pengucapan maka disebut Tata Bahasa saja. 

 

2. Secara lengkap suatu tata bahasa bebas konteks dapat mempunyai empat komponen, yaitu

Jawab : Empat komponen tersebut, yaitu : 

1. Himpunan dari token yang dikenal dengan nama simbol token. 
2. Himpunan dari unsur non terminal. 
3. Himpunan dari produksi, dimana masing-masing produksi terdiri dari unsure non-terminal yang disebut bagian kiri dari suatu produksi, tanda panah dan barisan dari token dan/atau bukan terminal, yang disebut bagian kanan dari produksi. 
4. Salah satu dari unsure non-terminal yang telah ditentukan disebut sebagai simbol awal.
 

3. Banyak contoh yang menggunakan ekspresi yang terdiri dari angka-angka dan tanda-tanda plus dan minus seperti 9-5+2, 3-1, dan 7. Karena tanda plus atau minus harus timbul diantara dua angka, maka ekspresi seperti ini dinyatakan sebagai "barisan dari angka-angka yang dipisahkan oleh tanda plus atau minus". Tata bahasa berikut memberikan sintaks dari ekspresi-ekspresi yang dimaksud diatas. Produksi yang ada adalah :

list => list + digit

list => list - digit

list => digit

digit => 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

Sebutkan token dari tata bahasa ini dan kelompokkan menjadi satu produksi dari produksi dengan unsur non terminal list dibagian kiri. ...

Jawab : Token dari tata bahasa yang digunakan adalah simbol + - 0 1 2 3 4 5 6 7 8 9 

Bagian kanan dari produksi dengan unsure non-terminal list bagian kiri dapat dikelompokkan menjadi satu produksi setara yaitu :   list =>  list + digit | list - digit | digit




4. Suatu produksi dikatakan suatu produksi untuk suatu unsure non-terminal bila unsure non-terminal timbul dibagian kiri dari produksi, sedangkan barisan token adalah barisan dari nol atau lebih token. Unsur yang mengandung nol token ditulis ...

Jawab : Unsur yang mengandung nol token ditulis Ɛ, dan disebut dengan nama barisan kosong.




5. Tuliskan ekspresi dan tata bahasa dari pohon urai dibawah ini.

Jawab :
Ekspresi :  9-5+2 
Tata Bahasa:  list => list + digit list => list - digit list => digit digit => 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9




6. Jelaskan mengenai pohon urai ...

Jawab : Suatu pohon urai menggambarkan bagaimana suatu simbol awal dari suatu tata bahasa menyebabkan timbulnya suatu rangkaian dalam suatu bahasa.


7. Jelaskan dan berikan contoh mengenai tata bahasa yang mempunyai arti ganda ...

Jawab : Suatu tata bahasa dapat disebut sebagai tata bahasa yang mempunyai arti ganda apabila, suatu tata bahasa dapat memberikan lebih dari satu pohon urai untuk membentuk suatu rangkaian token dari tata bahasa yang digunakan tersebut.

Contoh : Misalkan tidak dibedakannya antara angka dan list. Maka, tata bahasa yang melibatkan angka dan tanda plus dan minus dapat dituliskan sebagai berikut : 
string -> string + string | string - string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 . 
Sehingga tata bahasa yang seperti itu akan mempunyai lebih dari satu pohon urai, yaitu sebagai berikut :
















Gambar Dua pohon urai dari ekspresi 9-5+2


8. Jelaskan mengenai urutan pengutamaan operator (presedensi dari operator) ...

Jawab : Suatu operator * dikatakan lebih diutamakan (mempunyai presedensi lebih tinggi) dari operator +. Dalam aritmatika biasa, operasi perkalian dan pembagian lebih diutamakan terhadap operasi penjumlahan dan pengurangan.


9. Jelaskan kedua pohon urai pada gambar dibawah ini ...







Jawab : Hal yang berlawanan terjadi pada gambar pohon urai diatas yaitu, pada operator yang bersifat asosiatif kiri seperti operator - (Pohon urai untuk 9-5-2 tumbuh kearah kiri) dan operator yang bersifat asosiatif kanan seperti operator = (Pohon urai untuk a=b=c akan tumbuh ke arah kanan).

Catatan tambahan :

Suatu operator + dikatakan bersifat asosiatif kiri bila suatu bilangan berada diantara dua tanda +, maka bilangan tersebut akan mengunakan operator yang ada disebelah kirinya. Pada kebanyakkan bahasa pemrograman, keempat operator arithmetic, penjumlahan, pengurangan, perkalian dan pembagian bersifat asosiatif kiri.

Beberapa operator yang sering digunakan seperti pemangkatan bersifat asosiatif kanan, sebagai contoh lain operator = pada bahasa C bersifat asosiatif kanan, karena ekspresi a=b=c berarti sama dengan a=(b=c).

Untuk rangkaian karakter a=b=c dimana operatornya bersifat asosiatif kanan digunakan tata bahasa berikut :
right => letter = right | letter
letter => a | b | ... | z

10. Jelaskan mengenai lambang => dan |  ...

Jawab : lambang "=>" merupakan simbol terminal untuk membentuk suatu produksi. Sedangkan lambang "|'' merupakan simbol non terminal yang digunakan untuk memisahkan pilihan yang ada pada bagian kanan (simbol tersebut dapat dibaca "atau").







BAB PENERJEMAH BERDASARKAN SINTAKS


1. Jelaskan mengenai definisi berdasarkan sintaks ...

Jawab : Definisi berdasarkan sintaks menyatakan terjemahan dari suatu bentuk kedalam bentuk dari atribut yang berhubungan dengan komponen sintaktiknya. Definisi berdasarkan sintaks ini menggunakan tata bahasa bebas konteks untuk menyatakan struktur sintaktik dari input yang diberikan.


2. Jelaskan mengenai atribut sintesis ...

Jawab : Suatu atribut disebut atribut sintesis bila nilai pada nodal ditentukan dari nilai atribut anak nodal.

3. Jelaskan mengenai infix dan postfix ...

Jawab : Infix merupakan operand yang diletakkan diantara atau ditengah-tengah kata. Sedangkan, postfix merupakan operand yang diletakkan diakhir kata.


4. Lanjutkanlah gambar 3.4 berikut ini berdasarkan pada gambar 3.3 ...




*maaf ya gambarnya miring hehe KLIK gambar untuk melihat lebih jelas*




Jawab : 







5. Pola terjemahan adalah ...

Jawab : Suatu tata bahasa bebas konteks dimana fragmen program yang disebut dengan aksi semantic disisipkan di bagian kanan suatu produksi.




6. Dalam menggambarkan pohon urai untuk suatu pola terjemahan, maka aksi dinyatakan dengan ...

Jawab : Aksi dinyatakan dengan membentuk suatu anak tambahan untuk aksi tersebut yang disambung dengan garis putus pada nodal dari produksi yang bersangkutan.




7. Penguraian (parsing) adalah ...

Jawab : Suatu proses untuk menentukan apakah suatu rangkaian dari token yang dihasilkan oleh analisis leksikal termasuk dalam suatu tata bahasa yang tertentu.




8. Cara pembentukan puncak-ke-bawah dari suatu pohon urai dilakukan dengan ...

Jawab : Dilakukan dengan dimulai dari akar, yang diberi label suatu unsur bukan terminal, dan secara berulang-ulang melakukan kedua langkah berikut ini : 1. Pada nodal n, yang mempunyai label bukan terminal A, pilih salah satu produksi untuk A dan bentuk anak-anak dari n untuk semua simbol yang ada dibagian kanan produksi;  2. Cari nodal berikutnya dimana pohon bagian akan dibentuk.




9. Simbol lihat-muka adalah ...

Jawab : Simbol lihat-muka merupakan sebutan untuk token yang sedang dibaca dalam input.




10. Jelaskan mengenai penjelajahan dengan mengutamakan kedalaman (depth-first tropersols) ...

Jawab : Dimulai dari akar pohon, kemudian secara rekursif mengunjungi anak dari setiap nodal dengan urutan dari kiri ke kanan. Aturan semantic pada nodal tertentu dihitung setelah semua turunan dari nodal tersebut dikunjungi. Hal ini disebut mengutamakan kedalaman (depth-first) karena disini selalu dikunjungi anak dari suatu nodal yang belum dikunjungi terlebih dahulu, jadi diusahakan untuk mengunjungi nodal-nodal sejauh mungkin dari akar dengan secepat mungkin.




BAB PENERJEMAHAN UNTUK EKSPRESI SEDERHANA




1. Lexeme adalah ...

Jawab : Barisan dari karakter input yang membentuk suatu token.




2. Karakter tambahan yang mungkin terdapat dalam input seperti spasi dan lain-lainnya akan menyebabkan kegagalan dari ...

Jawab : Hal tersebut akan menyebabkan kegagalan dari proses penerjemah.




3. Umumnya penganalisis leksikal mengirimkan token dan atributnya kepada pengurai. Bila token dan atribut tersebut dituliskan sebagai pasangan didalam tanda <>, maka input : 21 + 28 + 69 akan ditransformasikan kedalam barisan pasangan berikut ...

Jawab : <num, 21>, <+,>, <num, 28>,<+,>, <num, 69>


4. Jelaskan mengenai gambar 4.5 berikut ini ...

Jawab : Lexan membaca dan mengembalikan karakter input dengan jalan memanggil rutin getchar dan ungetc;  Fungsi lexan mengembalikan num bila barisan angka terlihat dalam input. Suatu variabel global tokenval diberikan nilai dari barisan angka tersebut.


5. Penganalisis leksikal menggunakan operasi lookup dan operasi insert untuk ...

Jawab : Penganalisis leksikal menggunakan operasi lookup untuk menentukan apakah ada entri untuk suatu lexeme pada tabel simbol. Bila tidak ada, maka akan digunakan operasi insert untuk membuat entri baru dan memasukkan lexeme yang baru pada tabel simbol.


6. Berikan 3 penjelasan berdasarkan gambar 4.6 berikut ini ...

Jawab :

• Setiap rangkaian diakhiri dengan karakter akhir-dari-rangkaian (end-of-string character) yang dituliskan sebagai EOS.
• Setiap entri pada tabel simbol merupakan bagian dari array symtable yang merupakan record yang terdiri dari dua bagian yaitu lexptr, yang menunjuk pada awal dari lexeme, dan token.
• Pada gambar 4.6 tersebut, Entri ke-0 dibiarkan kosong, karena fungsi lookup akan mengembalikan nilai 0 untuk menyatakan bahwa tidak ada entri untuk rangkaian yang diberikan. Entri pertama dan kedua digunakan untuk kata kunci div dan mod, sedang entri ketiga dan keempat digunakan untuk identifier count dan i.


7. Jelaskan perbedaan antara pohon sintaks dengan pohon urai ...

Jawab : Pohon sintaks berbeda dengan pohon urai karena penerjemah yang tidak penting tidak terlihat pada pohon sintaks. Bisa dibilang, pohon urai sangat detail sedangkan pohon sintaks yang penting-penting saja. Untuk lebih jelasnya, lihat gambar berikut ini :







8. Instruksi yang digunakan mesin stak abstrak dikelompokkan kedalam tiga kelompok yang berbeda, yaitu ...

Jawab : Aritmetik bilangan bulat, manipulasi stak dan alir kendali


9. Ada beberapa perintah pada stak untuk mengakses data dari memori, yaitu :

Jawab :
push v memasukkan data kedalam stak.
rvalue l memasukkan isi dari data pada lokasi l pada stak.
lvalue l memasukkan alamat dari lokasi l pada stak.
pop mengeluarkan unsur teratas dari stak.

:= nilai-R pada unsur teratas disimpan pada nilai-L yang berada dibawahnya dan kedua                           unsur tersebut dikeluarkan dari stak.
copy masukan salinan dari unsur teratas dari stak kedalam stak tersebut.


10. Tujuan penganalisis leksikal adalah ...

Jawab : Untuk memungkinkan spasi, tabulasi dan bilangan-bilangan berada dalam ekspresi yang ada. 


BAB ANALISIS LEKSIKAL




1. Tugas utama dan kedua dari penganalisis leksikal adalah ...

Jawab :
• Tugas utamanya adalah membaca karakter input dan memproduksi barisan dari token yang digunakan oleh suatu pengurai untuk melakukan analisis sintaks.
• Tugas kedua dalam hubungannya dengan penulis program adalah membuang dari program sumber komentar ruang kosong seperti karakter spasi, tabulasi, dan baris baru.Hal lain yang juga dilakukan adalah menghubungkan antara pesan-pesan kesalahan yang diperoleh oleh kompilator dengan program sumber.




2. Beberapa hal yang menyebabkan dipisahnya fase analisis leksikal dan penguraian pada suatu proses kompilasi, yaitu ...

Jawab : 

1. Hal yang paling penting adalah perancangan yang akan menjadi lebih sederhana.

2. Efisiensi dari kompilator lebih baik.

3. Peningkatan portabilitas dari kompilator.




3. Jelaskan mengenai token, pola dan lexeme ...

Jawab : 
• Token yaitu barisan dari karakter yang dalam suatu kesatuan mempunyai arti tersendiri.
• Pola adalah aturan yang menerangkan sejumlah lexeme dapat menyatakan suatu token dalam suatu program sumber.
• Lexeme adalah barisan karakter dalam program sumber yang dicocokkan oleh pola untuk menentukan suatu token.




4. Hal-hal berikut biasanya diperlukan oleh suatu token ...

Jawab : Kata kunci, operator, identifier, konstanta, rangkaian huruf, simbol-simbol baca seperti tanda kurung, koma dan titik koma.




5. Kemungkinan lain untuk mengembalikan proses dari suatu kesalahan adalah ...

Jawab : 

1. Menghapus karakter yang berlebihan;

2. Memasukkan karakter yang hilang;

3. Mengganti karakter yang salah;

4. Menukar letak dari dua karakter yang berdekatan.




6. Misalnya L sebagai himpunan {A, B, ..., Z, a, b, ..., z} dan D adalah himpunan {0, 1, ..., 9}.

a. L4

b. D+

Jawab : 

a. L4 adalah himpunan dari rangkaian 4 huruf.

b. D+ adalah himpunan dari semua rangkaian dari satu atau lebih angka.




7. Misalnya ∑ = {a,b}.

a. Ekspresi beraturan (a|b)(a|b) menyatakan himpunan ...

b. Ekspresi beraturan a* menyatakan himpunan dari ...

Jawab : 

a. Ekspresi beraturan (a|b)(a|b) menyatakan himpunan {aa, ab, ba, bb}. Yaitu himpunan dari semua                 rangkaian dari a dan b yang panjangnya dua.

b. Ekspresi beraturan a* menyatakan himpunan dari semua rangkaian yang terdiri dari nol atau lebih a,               yaitu a, aa, aaa, ...





8. Jelaskan mengenai state, edge, state penerima, pointer tanda dapat mundur ... (penjelasan dengan gambar)

Jawab : 

State :

        Edge (sisi) :

        State penerima (accepting state) :

        Pointer tanda dapat mundur :  *


9. Buatlah satu gambar NFA ...

Jawab :




10. Buatlah tabel peralihan untuk NFA yang telah dibuat pada soal nomor 9 ...

Jawab :




11. Buatlah satu gambar DFA ...

Jawab :




12. Buatlah tabel peralihan untuk DFA yang telah anda buat pada soal nomor 11 ...

Jawab :






KISI-KISI ISI-ISI




Soal-soal :




Jawaban : 







 Dikarenakan tidak sempat mengetik, jadi saya scan kisi-kisinya. Mohon maaf atas ketidaknyamanannya.







Selamat Belajar ^_^