Analisis Sintaksis

Pohon (tree) adalah suatu graph terhubung yang tidak sirkuler, memiliki satu buah simpul (vertex/node) yaitu akar (root) dan dari akar ini memiliki lintasan (edge) ke setiap simpul yang lain. 

Pohon penurunan (derivation tree / syntax tree / parse tree) berguna untuk menggambarkan bagaimana cara memperoleh suatu untai (string) dengan cara menurunkan atau mengganti simbol-simbol variabel menjadi terminal. Setiap simbol variabel akan diturunkan atau diganti menjadi terminal. 

Simbol variabel     => dinotasikan dengan huruf besar (kapital).

Simbol terminal    => dinotasikan dengan huruf kecil, menempati posisi daun (leaf).

Simbol awal          => variabel S, menempati posisi puncak pohon (root).

Proses penurunan (parsing) bisa dilakukan antara lain dengan cara: 

1. penurunan melalui arah kiri (leftmost derivation): simbol variabel terkiri yang diperluas lebih dulu.
2. penurunan melalui arah kanan (rightmost derivation): simbol variabel terkananyang diperluas lebih dulu.

Contoh :

Tata bahasa bebas konteks memiliki aturan produksi: 

S -> AB               {S menurunkan variabel A B}

A-> aA | a           {A menurunkan terminal a variabel A atau terminal a}

B-> bB | b           {B menurunkan terminal b variabel B atau terminal b}

Berikut ini adalah gambar pohon penurunan untuk memperoleh untai ‘aabbb’

Catatan, melalui aturan produksi yang samadapat dihasilkan beberapa buah untai. 

Contoh: ‘aabbb’, ‘ab’, ‘aaaabbbb’, dan lain-lain.

Metode parsing 

Analisis sintaksis (proses parsing) berguna untuk memeriksa urutan kemunculan token. Pada proses ini, hal yang perlu diperhatikan adalah: 

1. Kebutuhan waktu eksekusi.
2. Penanganan kesalahan.
3. Penanganan kode

Metode parsing dapat dilakukan secara top down atau bottom up, dimana untai masukan akan dibaca (scan) dari arah kiri ke kanan. 

Metode parsing top down

Membangun pohon parse dari puncak pohon (root) menuju ke daun (leaf). Penelusuran dilakukan dari simbol awal sampai dengan simbol terminal. 

Metode parsing top down  dapat dilakukan menggunakan proses: 

1. backtrack (dikerjakan secara brute force).
2. no backtrack (dikerjakan secara recursive descent parser).

Proses backtrack: proses ini dilakukan seandainya pada saat mengerjakan suatu langkah x menyebabkan kesalahan, maka akan melakukan proses backtrack yaitu proses kembali ke kondisi terakhir sebelum langkah x dikerjakan. 

Proses brute force: mencoba semua kemungkinan secara terstruktur. Kelemahan proses brute force adalah relatif membutuhkan waktu yang lamakarena mencoba semua aturan produksi yang ada, dan membutuhkan alokasi memori yang besar untuk mencatat lokasi proses, sehingga dimungkinkan untuk melakukan proses backtrack. 

Metode parsing bottom up

Pohon parse dibangun dari daun (leaf) menuju ke puncak pohon (root). Penelusuran dilakukan dari simbol terminal menuju ke simbol awal. Kebalikan dari metode parsing top down. 

Metode parsing bottom up  dapat dilakukan menggunakan proses: 

1. shift reduce parsing
2. operator precedence parsing
3. simple precedence grammars parsingd.LR grammars parsing

Jawaban Analisis Semantik

 Pertemuan 8

1. Apa yang dimaksud dengan analisis semantik?

Jawab :

Analisis Semantik adalah proses setelah melewati proses scanning dan parsing. Pada tahap ini dilakukan pengecekan pada struktur akhir yang telah diperoleh dan diperiksa kesesuaiannya dengan komponen program yang ada.

2. Sebutkan fungsi semantic analyzer !

Jawab :

semantic analyzer berfungsi untuk menentukan makna dari serangkaian instruksi yang terdapat dalam program sumber. 

3. Apa saja poin yang di cek oleh analisis semantik?

Jawab :

a) Memeriksa keberlakuan nama-nama meliputi pemeriksaan berikut. 

• Duplikasi : pada tahap ini dilakukan pengecekan apakah sebuah nama terjadi pendefinisian lebih dari dua kali. Pengecekan dilakukan pada bagian pengelola blok.

• Terdefinisi : Melakukan pengecekan apakah sebuah nama yang dipakai pada tubuh program sudah terdefinisi atau belum. Pengecekan dilakukan pada semua tempat kecuali blok.

b) Memeriksa tipe. Melakukan pemeriksaan terhadap kesesuaian tipe dalam statement-statement yang ada. Misalkan bila terdapat suatu operasi, diperiksa tipe operand. Contohnya bila ekspresi yang mengikuti instruksi IF berarti tipenya boolean, akan diperiksa tipe identifier dan tipe ekspresi. Bila ada operasi antara dua operand, maka tipe operand pertama harus bisa dioperasikan dengan operand kedua.

Pertanyaan dan Jawaban tentang Grammer Chomsky

1. Mengapa grammer universal?

Grammer universal akan menyarankan bahwa semua bahasa memiliki kumpulan kategori dan hubungan yang sama dan bahwa untuk berkomunikasi melalui bahasa, penutur menggunakan sarana terbatas yang tak terbatas, sebuah gagasan yang disarankan Wilhelm von Humboldt pada tahun 1830-an.

2. Apa teori grammer universal Noam Chomsky?

Grammer universal (UG) (kata benda): sebuah teori dalam linguistik yang biasanya dikreditkan ke Noam Chomsky yang menyarankan bahwa kemampuan untuk mempelajari tata bahasa dibangun ke dalam otak manusia sejak lahir terlepas dari bahasanya. Pada 1960-an, ahli bahasa menjadi tertarik pada teori baru tentang tata bahasa, atau hukum bahasa.

3. Apa yang diyakini Noam Chomsky tentang perkembangan bahasa?

Chomsky percaya bahwa bahasa adalah bawaan lahir atau dengan kata lain, kita dilahirkan dengan kemampuan bahasa. Aturan bahasa dipengaruhi oleh pengalaman dan pembelajaran, tetapi kapasitas bahasa itu sendiri ada dengan atau tanpa pengaruh lingkungan.

4.  Apa sebutan teori Chomsky?

Kapasitas bawaan untuk bahasa. Pada tahun 1957, ahli bahasa Noam Chomsky menerbitkan buku inovatif berjudul "Struktur Sintaksis". Ini mengusulkan ide baru: Semua manusia mungkin dilahirkan dengan pemahaman bawaan tentang bagaimana bahasa bekerja. Ide Chomsky sejak itu diterima secara luas.

5. Bahasa mana yang memiliki tata bahasa terbaik?

Bahasa Swedia juga diberkati dengan tata bahasa sederhana dan sejumlah kata yang akrab bagi penutur bahasa Inggris, berkat kedua bahasa tersebut adalah bahasa Jermanik. Urutan kata juga cukup selaras, menjadikannya salah satu bahasa terbaik untuk dipelajari bagi mereka yang memulai dari dasar penuturan bahasa Inggris saja.

Analisis Sintaksis / Parser

Analisis Sintaksis (Parsing)

Parsing merupakan tahapan yang berguna untuk memeriksa urutan kemunculan token. Parsing adalah konsturksi atau pembentukan Pohon Sintaks untuk suatu kalimat (ekspresi).

Metode Parsing :

1. TOP DOWN Parsing : melakukan penelusuran dari root/puncak menuju leaf/daun.

2. BOTTOM UP Parsing : melakukan penelusuran dari leaf menuju root/puncak.

Grammer

Sebuah string diterima oleh grammar, jika simbol awal  dapat diturunkan dengan menggunakan 0 atau lebih rule sehingga menghasilkan string tersebut, dimana string ⊆ (Vt )*.

Pohon Sintaks

Merupakan suatu graf terhubung tidak sirkuler, yang memiliki satu simpul (node / akar) dan memiliki lintasan ke setiap simpul akhir (daun). Pohon Sintaks menggambarkan bagaimana memperoleh suatu string/untai (menurunkan simbol variabel menjadi simbol terminal).

Simbol awal        => menjadi akar

Simbol terminal  => menjadi daun

Ambigous Grammer

Kondisi ketika suatu string dieksekusi dengan grammar yang sama, menghasilkan pohon sintaks yang berbeda. Hasil eksekusi nya juga akan berbeda.

Grammer ke diagram sintaks

RUAS KIRI       => menjadi JUDUL diagram

RUAS KANAN => menjadi diagram

Konversi NFA ke DFA

Dari suatu mesin Non Deterministic Finite Automata (NFA) dapat dikonversi atau dibuat menjadi suatu mesin Deterministic Finite Automata (DFA) yang memiliki kemampuan menerima Bahasa yang sama (ekuivalen).

Berikut contoh konversi dari Non Deterministic Finite Automata menjadi Deterministic Finite Automata: 

Berikut table transisi dan diagram transisi untuk NFA :

Lalu dikonversi menjadi DFA, dengan cara membuat state baru berupa gabungan dari S0 dan S1.

Lalu untuk state {S0,S1} jika diberi inputan a maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan a yaitu {S0,S1}

Lalu untuk state {S0,S1} jika diberi inputan b maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan b yaitu {S0,S1}

Berikuta table transisi dan diagram transisi untuk DFA nya :

Perbedaan DFA dan NFA

Finite automata merupakan mesin automata dari bahasa reguler. Seperti yang kita ketahui, finite automata terbagi menjadi 2:

1. Deterministic Finite Automata (DFA) menerima masukan (input) yang hanya memiliki 1 busur keluar.

DFA sendiri merupakan finite automata dengan memiliki 5 tuple yang direpresentasikan sebagai berikut:

Q, himpunan state, contohnya {q0, q1, q2}

Σ, input alphabet, contohnya {a, b}

δ, fungsi transisi

q0, state awal

F, state akhir

2. Non-Deterministic Finite Automata (NFA) menerima masukan (input) dengan memiliki lebih dari 1 busur keluar atau bahkan tidak memiliki busur keluar.

NFA sendiri merupakan finite automata dengan memiliki 5 tuple yang direpresentasikan sebagai berikut:

Q, himpunan state, contohnya {q0, q1, q2}

Σ, input alphabet, contohnya {a, b}

δ, fungsi transisi

q0, state awal

F, state akhir

Perbedaan DFA dan NFA

DFA

• DFA tidak dapat menggunakan transisi string kosong (empty string)
• Dipahami sebagai sebuah mesin
• DFA untuk state selanjutnya bisa ditetapkan dengan jelas
• DFA lebih sulit dibuat
• Waktu yang dibutuhkan untuk mengeksekusi string input lebih sedikit
• Semua DFA merupakan NFA
• DFA membutuhkan lebih banyak ruang (space)

NFA

• NFA dapat menggunakan transisi string kosong (empty string)
• NFA dipahami sebagai beberapa mesin kecil yang melakukan komputasi di waktu bersamaan
• NFA untuk state selanjutnya mempunyai banyak kemungkinan
• NFA lebih mudah dibuat
• Waktu yang dibutuhkan untuk mengeksekusi string input lebih banyak
• Tidak semua NFA adalah DFA
• NFA membutuhkan lebih sedikit ruang (space)

Rangkuman Analisis Leksikal

 Analisis Leksikal

Analisis leksikal merupakan antarmuka antara kode program sumber dan analisis sintatik (parser). Scanner melakukan pemeriksaan karakter per karakter pada teks masukan, memecah sumber program menjadi bagian-bagian disebut token. Analisis leksikal mengerjakan pengelompokkan urutan-urutan karakter ke dalam komponen pokok yaitu identifier, delimeter, simbol-simbol operator, angka, keyword, noise word, blank, komentar, dan seterusnya menghasilkan suatu token leksikal yang akan digunakan pada analisis semantik.

Model dasar untuk membentuk suatu analisis leksikal adalah Finite-State Automata, 2 aspek penting pembuatan analisis leksikal adalah :

• Menentukan token-token bahasa.
• Mengenali token-token bahasa dari program sumber.

Tahap-tahap pelaksanaan analisis leksikal

1. Pada single one pass

Terjadi interaksi antara scanner dan parser, scanner dipanggil saat parser memerlukan token berikutnya. Pendekatan ini lebih baik karena bentuk internal program sumber yang lengkap tidak perlu dibangun dan disimpan di memori sebelum parsing dimulai.

2. Pada separate pass

Scanner memproses secara terpisah, dilakukan sebelum parsing.Hasil scanner disimpan dalam file. Dari file tersebut, parsing melakukan kegiatannya. Scanner mengirim niulai-nilai integer yang mempresentasikan bentuk internal token, bukan nilai-nilai string. Keunggulan cara ini adalah ukurannya kecil dan tetap.

Input Buffering

Perancangan analisis leksikal seharusnya dapat membuat buffering masukkan yang membantu mempercepat proses pembacaan dari file serta mempunyai fleksibelitas yang tinggi agar analisis leksikal tidak bergantung platform sehingga mempunyai portabilitas yang tinggi.

Ekspresi Reguler

Bahasa reguler dapat dinyatakan sebagai ekspresi reguler dengan menggunakan 3 operator : concate, alternate, dan slosure.

TRANSLATOR PADA TEKNIK KOMPILASI

 Pengertian Translator

Translator yaitu mengubah source code / program sumber ke dalam target code / object code. Source code ditulis dalam sumber sedangkan object code bisa dalam bahasa pemrograman lain atau bahasa mesin pada suatu komputer. Proses penerjemahan dilakukan oleh kompilator disebut compiling atau kompilasi. Kompilator (compilator) bertugas untuk melaporkan jika kemungkinan terjadinya kesalahan atau error.

Macam-macam Translator

1. Assembler

Source code : bahasa assembly

Object code : bahasa mesin

Contoh : Turbo Assembler dan Macro Assembler

2. Kompilator (Compiler)

Sebuah program yang membaca suatu program yang dituliskan ke dalam suatu bahasa sumber dan menerjemahkannya ke dalam suatu bahasa. Source code dan data diproses pada waktu yang berbeda.

Source code : Bahasa tingkat tinggi

Object code : bahasa mesin / bahasa assembly

Contoh : Turbo Pascal.

3. Interpreter

Sebuah program yang digunakan untuk menterjemahkan, mengeksekusi dan memberikan hasil dari eksekusi instruksi masukannya. Interpreter tidak membangkitkan object code, hasil translasinya dalam bentuk internal. Source code dan data diproses pada saat yang sama.

Contoh : BASICA/GW-BASIC, LIPS, SMALLTALK.

Proses kompilasi dikelompokkan ke dalam dua kelompok besar :

1. Analisa : Program sumber dipecah-pecah dan dibentuk menjadi bentuk antara (inter-mediate representation)

2. Sintesa : Membanggun program sasaran yang diinginkan dari bentuk.

Contoh Program JFrame Netbeans Tiket Masuk

Nama : Rita Amelia
NIM   : 181021400139
Kelas : 01TPLP002

1. Deskripsi
Program ini dibuat untuk mempermudah dalam memproses data jumlah pengunjung yang datang dan mempermudah dalam menghitung pendapatan perharinya.

Input:
- Hari
- Tanggal
- Bulan
- Tahun
- Jumlah pengunjung dewasa
- Jumlah pengunjung anak-anak

Variabel awal:
- Tarif dewasa = 50.000/orang
- Tarif anak-anak = 30.000/anak

Output: Total yang harus dibayarkan

Input dewasa = Integer.parseInt(TextDewasa.getText());
Input anak = Integer.parseInt(TextAnak.getText());
Output total yang harus dibayarkan = Tarif dewasa+Tarif anak-anak

2. Screenshoot Form
Screenshoot design:

Screenshoot run:

3. Source Coding

import javax.swing.JOptionPane;

public class FrameWisataAir extends javax.swing.JFrame {

public FrameWisataAir() {

        initComponents();

    }

@SuppressWarnings("unchecked")

    private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) {                                        

        // TODO add your handling code here:

        int dewasa=Integer.parseInt(TextDewasa.getText());

        int tarifdewasa=dewasa*50000;

                TextTarifD.setText(""+tarifdewasa);

               

        int anak=Integer.parseInt(TextAnak.getText());

        int tarifanak=anak*30000;

                TextTarifA.setText(""+tarifanak);

               

        int total=tarifdewasa+tarifanak;

        TextTotal.setText(""+total);

    }                                        

    private void ButtonDewasaActionPerformed(java.awt.event.ActionEvent evt) {                                            

        // TODO add your handling code here:

        int dewasa=Integer.parseInt(TextDewasa.getText());

        int tarifdewasa=dewasa*50000;

                TextTarifD.setText(""+tarifdewasa);

    }                                           

    private void ButtonAnakActionPerformed(java.awt.event.ActionEvent evt) {                                           

        // TODO add your handling code here:

        int anak=Integer.parseInt(TextAnak.getText());

        int tarifanak=anak*30000;

                TextTarifA.setText(""+tarifanak);

    }                                         

    private void jButton2ActionPerformed(java.awt.event.ActionEvent evt) {                                        

        // TODO add your handling code here:

        TextDewasa.setText("");

        TextAnak.setText("");

        TextTarifD.setText("");

        TextTarifA.setText("");

        TextTotal.setText("");

    }

    private void jButton3ActionPerformed(java.awt.event.ActionEvent evt) {                                        

        // TODO add your handling code here:

        JOptionPane.showMessageDialog(this, "Apakah anda akan keluar program?");

    }                                       

    private void formWindowActivated(java.awt.event.WindowEvent evt) {                                    

        // TODO add your handling code here:

         for(int Tgl=1;Tgl<=31;Tgl++){

            ComboTanggal.addItem(""+Tgl);

        }                 

          for(int Thn=2019;Thn<=2030;Thn++){

            ComboTahun.addItem(""+Thn);

    }                        

    }

UTS Algoritma dan Pemrograman

Nama : Rita Amelia
NIM   : 181021400139
Kelas  : 01TPLP002

Tiket Masuk Wisata Air
1. Deskripsi
Algoritma Pemrograman Tiket Masuk Wisata Air dibuat untuk mempermudah memproses data sebagai berikut:
Tiket Masuk Anak-anak = 30.000/orang
Tiket Masuk Dewasa      = 50.000/orang
 Langkah penyelesaian
Tarif yang harus dibayar dikali harga masing-masing jenis tiket
Jika Anak-anak, Tarif yang harus dibayar = Anak*30.000
Jika Dewasa, Tarif yang harus dibayar      = Dewasa*50.000
Keterangan : Tiket masuk yang harus dibayar = Jenis tiket dikali masing-masing harga jenis tiket.

2. Flowchart

3. Screenshoot Run

4. Coding

package wisataair;

import java.util.Scanner;

public class WisataAir {

    public static void main(String[] args) {

        // TODO code application logic here

        Scanner tarif=new Scanner (System.in);

       

        System.out.println("1. Tiket Masuk Anak-anak = 30000/orang");

        System.out.println("2. Tiket Masuk Dewasa = 50000/orang");

       

        System.out.print ("Jenis Tiket =");

        int TiketMasuk=tarif.nextInt();

       

        if(TiketMasuk<=1){

        System.out.print ("Jumlah Tiket yang akan dibeli =");

        int Anak=tarif.nextInt();

        int Tarif=Anak*30000;

        System.out.println("Tarif Masuk yang Harus dibayar = "+Tarif);

        }

       

        else if (TiketMasuk<=2){

        System.out.print ("Jumlah Tiket yang akan dibeli =");

        int Dewasa=tarif.nextInt();

        int Tarif=Dewasa*50000;

        System.out.println("Tarif Masuk yang Harus dibayar = "+Tarif);

        }             

    }      

    }