Script Savvy

Compilation Technique - Tugas Personal ke-1 Week 2

Individual Assignment Compilation Technique

---

1. Jelaskan mengenai compiler dan compiler classification!

Jawab :

Compiler adalah program komputer yang mengubah kode sumber dalam bahasa pemrograman ke dalam bentuk yang dapat dieksekusi oleh komputer. Pada umumnya, compiler melakukan proses kompilasi dalam beberapa tahap. Tahap pertama adalah analisis sintaksis (parsing), di mana compiler menganalisis struktur kode sumber dan memastikan bahwa kode tersebut memenuhi aturan sintaksis bahasa pemrograman yang digunakan.

Tahap berikutnya adalah analisis semantik, di mana compiler memeriksa arti dari kode sumber dan memastikan bahwa semua referensi ke variabel dan fungsi valid. Setelah itu, compiler menghasilkan kode antara (intermediate code) yang biasanya dalam bentuk bahasa mesin yang lebih rendah tingkatannya, dan kemudian kode antara tersebut diterjemahkan menjadi kode mesin yang dapat dieksekusi oleh komputer.

Klasifikasi compiler dapat dilakukan berdasarkan beberapa kriteria, seperti arsitektur target, fungsionalitas, dan tingkat optimasi. Berikut adalah beberapa klasifikasi compiler yang umum:

• Native Compiler: Compiler ini menghasilkan kode mesin yang langsung dieksekusi oleh arsitektur komputer target. Contohnya adalah GCC (GNU Compiler Collection), yang digunakan untuk menghasilkan program dalam bahasa C atau C++ yang dapat dieksekusi langsung pada sistem operasi yang mendukung arsitektur tertentu.

• Just-In-Time (JIT) Compiler: Compiler ini menerjemahkan kode sumber ke dalam kode mesin saat program sedang berjalan (runtime). JIT compiler umumnya digunakan dalam lingkungan bahasa pemrograman tingkat tinggi, seperti Java atau C#. Contoh JIT compiler adalah HotSpot JVM (Java Virtual Machine) yang terdapat dalam Java Development Kit (JDK).

• Ahead-of-Time (AOT) Compiler: Compiler ini melakukan proses kompilasi sebelum program dieksekusi. Dalam konteks bahasa pemrograman seperti C atau C++, kompilasi AOT dilakukan sebelum program dijalankan, sehingga hasil kompilasi adalah file biner yang dapat langsung dieksekusi. Contoh AOT compiler adalah Clang dan LLVM (Low Level Virtual Machine).

   

2. Gambarkan finite automata dari regular expression berikut:

Jawab :

• RE = a

          a
  START ------> ACCEPT
  ​

• RE = ab

          a        b
  START ------> q1 ------> ACCEPT
  ​

• RE = (a+b)

         a          b
  START ------> q1 ------> ACCEPT
  ​

• RE = (a+b)*

         a          b
  START ------> q1 ------> ACCEPT
      |          |
      +----------+
  ​

Keterangan:

• START: Keadaan awal (start state).

• ACCEPT: Keadaan akhir (accept state).

• Panah menunjukkan transisi antara keadaan-keadaan dengan simbol input yang sesuai.

 

3. Buatlah konversi dari deterministic finite automata (DFA) ke regular expression dari DFA q2 = q1b + q2b + q3b dengan ilustrasi berikut:

Finite automata:

• a.  RE = a
          a
      (q0) -----> (q1)

• b.  RE = ab
          a       b
      (q0) -----> (q1) -----> (q2)

• c. RE = (a+b)
          a       b
      (q0) -----> (q1) -----> (q2)

• RE = (a+b)*
        a,b
      (q0) -----> (q1)
      |             ^
      |_____________|

   

4. Perhatikan grammar berikut:

S → dEf B → ef | e Input: def

Buatlah Recursive-Descent Parsing (gunakan Backtracking)!

Jawab :

Untuk membangun Recursive-Descent Parsing dengan menggunakan Backtracking untuk grammar yang diberikan, berikut adalah langkah-langkahnya:

Langkah 1: Definisikan fungsi-fungsi yang sesuai untuk setiap produksi dalam grammar.

S() {
    match('d');
    E();
    match('f');
}
​
E() {
    match('e');
    F();
}
​
F() {
    if (peek() == 'f') {
        match('f');
    } else if (peek() == 'e') {
        match('e');
    } else {
        // Backtrack jika tidak ada pilihan yang cocok
        backtrack();
    }
}

Langkah 2: Implementasikan fungsi-fungsi pendukung seperti match() dan peek() untuk memanipulasi input dan melihat simbol berikutnya.

Langkah 3: Panggil fungsi S() untuk memulai parsing.

input = "def";
position = 0;
​
function match(expected) {
    if (input[position] === expected) {
        position++;
    } else {
        throw new Error(`Error: Expected ${expected} but found ${input[position]}`);
    }
}
​
function peek() {
    if (position < input.length) {
        return input[position];
    } else {
        return null;
    }
}
​
function backtrack() {
    throw new Error("Error: Backtracking");
}
​
// Memulai parsing
try {
    S();
    if (position === input.length) {
        console.log("Input diterima");
    } else {
        console.log("Input ditolak");
    }
} catch (error) {
    console.log(error.message);
}

Dalam contoh ini, fungsi match() digunakan untuk membandingkan simbol saat ini dengan simbol yang diharapkan. Fungsi peek() digunakan untuk melihat simbol berikutnya tanpa mengonsumsinya. Jika tidak ada pilihan yang cocok dalam produksi F(), maka dilakukan backtracking dengan memunculkan pesan error.

Dalam kasus ini, input "def" akan diterima oleh parser karena berhasil memenuhi semua produksi dalam grammar.

 

5. Buatlah LR(0) Parsing Table untuk Grammar berikut, serta buktikan bahwa string "bbcb$" diterima!

S → AB A → bA | c B → b

Jawab :

Langkah 1: Tentukan semua item-item untuk setiap produksi dalam grammar.

Item untuk produksi S → AB:

• S → .AB (Start state)

• S → A.B

Item untuk produksi A → bA:

• A → .bA

• A → .c

Item untuk produksi B → b:

• B → .b

Langkah 2: Tentukan semua transisi (shift) yang mungkin dari setiap keadaan.

• State 0:

  • S → .AB, [b, c]

  • A → .bA, [b, c]

  • A → .c, [b, c]

  • B → .b, [$]

• State 1:

  • S → A.B, [b, c]

• State 2:

  • A → b.A, [b, c]

Langkah 3: Tentukan semua reduksi yang mungkin dari setiap keadaan.

• State 0:

  • B → b., [b, c, $]

• State 2:

  • A → c., [b, c]

Langkah 4: Buat Parsing Table dengan mengisi setiap entri berdasarkan transisi dan reduksi yang ditentukan sebelumnya. Parsing Table:

---------------------------------------------------
State  |  b   |  c   |   $   |   A   |   B   |
---------------------------------------------------
  0    | s2   |  r3  |       |   1   |       |
  1    |      |      | accept|       |       |
  2    | s2   |  r3  |       |       |       |
---------------------------------------------------

Keterangan:

• sX menunjukkan perpindahan (shift) ke state X.

• rX menunjukkan reduksi menggunakan produksi X.

Untuk membuktikan bahwa string "bbcb$" diterima oleh grammar ini, kita dapat melakukan langkah-langkah berikut menggunakan Parsing Table:

Stack           | Input          | Action
--------------------------------------------------
0               | bbcb$          | Shift to state 2
0b2             | bcb$           | Shift to state 2
0b2b2           | cb$            | Reduce using B → b
0b2B1           | cb$            | Reduce using A → bA
0A1             | cb$            | Shift to state 2
0A1c2           | b$             | Reduce using B → b
0A1B1           | b$             | Reduce using A → bA
0A1             | b$             | Shift to state 2
0A1b2           | $              | Reduce using B → b
0A1B1           | $              | Reduce using A → bA
0A1             | $              | Reduce using S → AB
0S3             | $              | Accept

Dalam langkah-langkah parsing di atas, string "bbcb$" dapat diproses dengan sukses menggunakan Parsing Table yang telah dibangun, dan akhirnya diterima (accepted).