Makalah Teknik Kompilasi [PDF]

Citation preview

KATA PENGANTAR Puji syukur alhamdulillah kami panjatkan kehadirat Allah SWT yang telah melimpahkan rahmat-Nya serta hidayah-Nya sehingga kami bisa menyelesaikan Makalah dengan judul “Top-down Parsing Full Bactracking dan Parsing Tanpa Backtracking ”. Sholawat serta salam semoga selalu tercurahkan kepada Nabi Muhammad SAW beserta keluarga dan para sahabatnya hingga pada umatnya sampai akhir zaman. Makalah ini disusun untuk memenuhi tugas matakuliah teknik kompilasi dan dalam proses penyusunan makalah ini, kami mendapatkan banyak sekali bantuan, bimbingan serta dukungan dari berbagai pihak, sehingga dalam kesempatan ini kami juga bermaksud menyampaikan rasa terima kasih Penulis berharap makalah yang telah disusun ini bisa memberikan sumbangsih untuk menambah pengetahuan para pembaca, dan akhir kata, dalam rangka perbaikan selanjutnya, kami akan terbuka terhadap saran dan masukan dari semua pihak karena kami menyadari makalah yang telah disusun ini memiliki banyak sekali kekurangan.



Makassar, 1 November 2019



1



BAB I PENDAHULUAN A. Latar Belakang Teknik kompilasi merupakan teknik untuk melakukan pembacaan suatu source program yang ditulis salam bahasa sumber, misal Pascal kemudian diterjemah ke dalam suatu bahasa lain yang disebut bahasa sasaran atau bentuk yang dapat dieksekusi secara langsung dari sistem operasi yang tersedia dalam suatu computer. Struktur Compiler terdiri dari lexical analysis (scanner), syntax analysis (parser), intermediate code, code optimization, code generation dan object code. Tugas lexical ini mendekomposisi program sumber menjadi bagian-bagian kecil. Code generation dan code optimization berfungsi pembangkitan/ pembuatan dan optimasi program (object program). Scanner mengelompokkan pogram asal/ sumber menjadi token. Parser bertugas mengurai/ memeriksa kebenaran dari tokentoken yang terbentuk oleh scanner. Proses pendeteksian (pengenalan token) disebut dengan parsing atau penurunan. Penurunan hbhb gfvtfv yh



B. Rumusan Masalah 1. Apa itu parsing? 2. Sebutkan metode – metode parsing! 3. Apa itu metode top down? 4. Jelaskan metode top down backtracking dan tanpa backtracking!



C. Tujuan



2



1. Mendeskripsikan pengertian parsing 2. Mendeskripsikan metode parsing 3. Mendeskripsikan metode top down backtracking dan tanpa backtracking



3



BAB II PEMBAHASAN A. Teknik Kompilasi Teknik Kompilasi merupakan Teknik dalam melakukan pembacaan suatu program yang ditulis dalam bahasa sumber, kemudian diterjemahkan ke dalam suatu bahasa lain yang disebut bahasa sasaran. Dalam melakukan proses penerjemahan tersebut, sudah barang tentu kompilator akan melaporkan adanya keanehan-keanehan atau kesalahan yang mungkin ditemukannya. Proses penerjemahan



yang



dilakukan



oleh



kompilator



ini



disebut



proseskompilasi (compiling). Bila dipandang sepintas



lalu, maka akan



timbul



beranekaragam



kompilator yang dapat dibuat antara lain sebagai berikut : 1. Bahasa Sumber seperti bahasa FORTRAN, PASCAL, C dan juga bahasabahasa lainnya yang sifat dan pemakaiannya agak spesifik atau khusus, seperti bahasa untuk program DBASE, SPSS dan lain sebagainya. 2. Bahasa Sasaran dapat berupa bahasa sumber lain seperti C, FORTRAN dan lain sebagainya atau Bahasa Mesin (Machine Language) yang digunakan oleh



suatu



prosessor



mikro



atau



sumber



komputer



besar



maupunkomputer super Secara umum proses dalam tahap analis terdiri dari 3 bagian utama, yaitu : 1. Proses analisis leksikal 2. Proses analisis sintaktik 3. Proses analisis semantik Tahap sintesis yang berikutnya program sasaran dibentuk berdasarkan representasi antara yang dihasilkan pada tahap analisis.



4



Untuk tahap sintetis terdiri dari 2 bagian utama, yaitu : 1. Proses yang menghasilkan kode (code generator) 2. Proses optimasi kode (code optimizer) Proses Analisis Leksikal membaca program sumber, karakter demi karakter. Sederetan (satu atau lebih) karakter dikelompokkan menjadi satu kesatuan mengacu kepada pola kesatuan kelompok karakter (token) yang ditentukan dalam bahasa sumber. Kelompok karakter yang membentuk sebuah token dinamakan lexeme untuk token tersebut. Setiap token yang dihasilkan disimpan di dalam tabel simbol. Sederetan karakter yang tidak mengikuti pola token akan dilaporkan sebagai token tak dikenal (unidentified token) Proses Analisis sintaks memeriksa kesesuaian pola deretan token dengan aturan sintaks yang ditentukan dalam bahasa sumber. Sederetan token yang tidak mengikuti aturan sintaks akan dilaporkan sebagai kesalahan sintaks (sintax error). Secara logika deretan token yang bersesuaian dengan sintaks tertentu akan dinyatakan sebagai pohon parsing (parse tree). Proses Analisis semantic memeriksa token dan ekspresi dari batasanbatasan yang ditetapkan. Batasan-batasan tersebut misalnya : a. panjang maksimum token identifier adalah 8 karakter, b. panjang maksimum ekspresi tunggal adalah 80 karakter, c. nilai bilangan bulat adalah -32768 s/d 32767, d. operasi aritmatika harus melibatkan operan-operan yang bertipe sama.



B. Metode Parsing Metode parsing atau proses penurunan adalah Analisis parsing atau sintaksis adalah proses menganalisis serangkaian simbol, baik dalam bahasa alami atau dalam bahasa komputer, sesuai dengan aturan tata bahasa formal.



5



Parsing dapat dilakukan dengan cara : 1. Penurunan terkiri (leftmost derivation) : simbol variable yang paling kiri diturunkan (tuntas) dahulu. 2. Penurunan terkanan (rightmost derivation) : simbol variable yang paling kanan diturunkan (tuntas) dahulu.



6



Parsing digolongkan menjadi 2, yaitu : 1. Top down : penelusuran dari root ke leaf atau dari simbol awal ke simbol terminal. Metode ini meliputi :  Backtracking / backup : Brute Force  No Backtracking : Recursive Descent Parser 2. Bottom Up : penelusuran dari leaf ke root.



C. Brute Force Kelas metode dengan backup, termasuk metode Brute-Force, adalah kelas metode parsing yang menggunakan produksi alternatif jika ada, ketika hasil penggunaan sebuah produksi tidak sesuai dengan simbol input. Penggunaan produksi sesuai dengan nomor urut produksi. 



Memilih aturan produksi mulai dari kiri







Meng-expand simbol non terminal sampai pada simbol terminal







Bila terjadi kesalahan (string tidak sesuai) maka dilakukan backtrack







Algoritma ini membuat pohon parsing secara top-down, yaitu dengan cara mencoba segala kemungkinan untuk setiap simbol non-terminal.



Contoh suatu Bahasa dengan aturan produksi sebagai berikut : S



aAd | aB



A



b|c



B



ccd | ddc



7



Kelemahan metode bruce force : 



Mencoba semua aturan produksi yang ada sehingga menjadi lambat (waktu eksekusi)







Mengalami kesulitan untuk melakukan pembetulan kesalahan







Banyak memakan memori, karena membuat backup lokasi backtrack







Grammar yang memiliki rekursif kiri tidak bias diperiksa, sehingga harus diubah dulu sehingga tidak rekursif kiri, karena rekursif kiri akan mengalami loop yang terus-menerus.



8



D. Recursive descent parser Kelas metode tanpa backup, termasuk metode recursive descent, adalah kelas metode parsing yang tidak menggunakan produksi alternatif ketika hasil akibat penggunaan sebuah produksi tidak sesuai dengan simbol input. Jika produksi A mempunyai dua buah ruas kanan atau lebih maka produksi yang dipilih untuk digunakan adalah produksi dengan simbol pertama ruas kanannya sama dengan input yang sedang dibaca. Jika tidak ada produksi yang demikian maka dikatakan bahwa parsing tidak dapat dilakukan. 



Salah satu cara untuk mengaplikasikan Bahasa context free







Symbol terminal maupun symbol variabelnya sudah bukan sebuah karakter







Besaran leksikal sebagai symbol terminalnya, besaran syntax sebagai symbol variabelnya / non terminalnya.







Dengan cara penurunan secara rekursif untuk semua variable dari awal sampai ketemu terminal







Tidak pernah mengambil token secara mundur (backtracking)







Beda dengan turing yang selalu maju dan mundur dalam melakukan parsing.



9



BAB II PENUTUP A. Kesimpulan Teknik Kompilasi Merupakan Teknik dalam melakukan pembacaan suatu program yang ditulis dalam bahasa sumber, kemudian diterjemahkan ke dalam suatu bahasa lain yang disebut bahasa sasaran. Metode parsing atau proses penurunan adalah proses menganalisis serangkaian simbol, baik dalam bahasa alami atau dalam bahasa komputer, sesuai dengan aturan tata bahasa formal. Parsing digolongkan menjadi 2, yaitu Top down (Backtracking dan No Backtracking) dan Bottom Up.



B. Saran Demikian makalah yang dapat kami buat, semoga dapat bermanfaat bagi pembaca. Apabila ada saran dan kritik yang ingin disampaikan, silahkan sampaikan kepada kami. Apabila terdapat kesalahan mohon dapat dimaafkan dan dimaklumi, karena kami hanyalah manusia biasa yang tidak luput dari kesalahan.



10



DAFTAR PUSTAKA http://jupankjl.blogspot.com/2016 /11/metode-parsing-teknik-kompilasi_9.html (diakses tanggal 1 November 2019) Rahayu,Saiful.2012.MAKALAHTEHNIKKOMPILASI.http://semutuyet.blogspot.com/2012/1 1/makalah-tehnik-kompilasi.html (diakses tanggal 1 November 2019) Ernastuti,Sulistyo.Phttps://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=we b&cd=6&cad=rja&uact=8&ved=2ahUKEwiQInGzeHlAhWXaCsKHS5PDjIQFjAFegQIAhAC&url=http%3A%2F%2Fymukhlis.st aff.gunadarma.ac.id%2FDownloads%2Ffiles%2F12304%2FTEKNIK%2BKOMPIL ASI%2BII.pdf&usg=AOvVaw2AuO_JaQDlm5uwcYr_V_qq



(diakses



tanggal



1



November 2019) Pratama, Rizky.2019.Cara Membuat Makalah dengan Struktur yang Baik dan Benar.https://bocahkampus.com/cara-membuat-makalah (diakses tanggal 1 November 2019) Pratama, Rizky.2019.Cara Menulis Daftar Pustaka dari Buku, Jurnal, dan Internet.https://bocahkampus.com/cara-menulis-daftar-pustaka(diakses



tanggal



1



November 2019)



11