Analisis Sintaksis

 

ANALISIS SINTAKSIS

Analisis Sintaksis (Syntax Analyser) adalah bagian kedua dari compiler yang bertugas memeriksa kebenaran dan urutan dari token-token yang terbentuk oleh lexical analysis. Tugas dari syntax analyser adalah :

1. Pengelompokan token-token kedalam class syntax (bentuk syntax), seperti procedure,statement dan expression.
2. Grammar : sekumpulan aturan-aturan untuk mendefinisikan bahasa sumber.
3. Grammar dipakai oleh syntax analyser untuk menentukan struktur dari program sumber.
4. Proses pendeteksiannya (pengenalan token) disebut dengan parsing.
5. Maka synax analyser sering disebut dengan parser.

Posisi Parser dalam Kompilator 

- Deretan token : dihasilkan oleh penganalisa lesikal (scanner).
- Pohon parse : suatu pohon dimana akarnya (root) adalah simbol awal grammar (starting symbol), setiap node dalam (inner code) adalah simbol nonterminal dan daunnya (leaf) dibaca dari kiri ke kanan adalah deretan token masukan. Pohon parse ini dibentuk berdasarkan aturan grammar yang ditetapkan untuk parser.
- Kesalahan sintaks : terjadi jika pola deretan token tidak memenuhi ketentuan pola yang telah ditentukan grammar untuk parser. Grammar yang dipilih untuk scanner adalah Regular Grammar (RG) sedangkan untuk parser adalah Grammar Context Free (CFG).

Regular Grammar

> Bahasa regular adalah penyusun ekspresi reguler (ER).
> Ekspresi reguler terdiri dari kombinasi simbol-simbol atomik menggunakan 3 operasi yaitu :
    - katenasi,
    - alternasi, dan
    - repitisi/closure

> Pada kasus scanner, simbol-simbol atomik adalah karakter-karakter di dalam program sumber.
> Dua buah ekspresi regular adalah ekuivalen jika keduanya menyatakan bahasa yang sama.

Parsing atau Proses Penurunan

Parsing dapat dilakukan dengan cara : 

1. Penurunan terkiri (lefmost derivation) : simbol variable yang paling kiri diturunkan (tuntas) dahulu.

2. Penurunan terkanan (rightmost derivation) : variable yang paling kanan diturunkan (tuntas) dahulu.

3. Misalkan : ingin dihasilkan string aabbaa dari context free language: S -> a AS | a,
                                                                                                                   A -> SbA | ba

4. Penurunan kiri : S => aAS
                                  => aSbAS
                                  => aabAS
                                  => aabbaaS
                                  => aabbaa

5. Penurunan kanan : S => aAS
                                      => aAa
                                      => aSbAa
                                      => aSbbaa
                                      => aabbaa

Metode Parsing

Proses Parsing merupakan tahapan analisis sintaksis yang berguna untuk memeriksa urutan kemunculan token. Di dalam mengimplementasikan sebuah metode parsing ke dalam program perlu diperhatikan tiga hal sebagai berikut : 

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

Metode Parsing bisa digolongkan sebagai berikut:

1. Top down
    Kalau dilihat dari terminologi pohon penurunan, metode ini melakukan penelusuran (Parsing) dari root.puncak menuju ke leaf/daun (simbol awal sampai simbol terimnal/ simbol awal S sampai kalimat X). Metode top down sendiri meliputi : Backtrack/Backup : Brute Force dan No backtrack : recursive descent panser.

2. Bottom up
    Metode ini melakukan penelusuran dari leaf/daun menuju ke root/puncak (dari kalimat x sampai simbol awal S).

Metode 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.

Metode Recursive-Descent

* 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.

* Ketentuan produksi yang digunakan metode recursive-descent adalah : Jika terdapat dua atau lebih produksi dengan ruas kiri yang sama maka karakter pertama dari semua ruas kanan produksi tersebut tidak boleh sama. Ketentuan ini tidak melarang adanya produksi yang bersifat rekursi kiri.

Parsing Bottom-up

- Salah satunya adalah Grammar Preseden Sederhana (GPS).
- Simple farse terkiri dinamakan handel
- Frase, simple frase, dan handel adalah string dengan panjang => 0.

Parsing dengan Brute Force

- Memilih aturan produksi mulai dari paling kiri.
- Melakukan expand semua non terminal pada aturan produksi sampai yang tertinggal adalah simbol terminal.
- Bila terjadi kesalahan (string tidak sesuai) maka akan dilakukan backtrack.
- Algoritma ini membangun pohon parsing yang top down, yaitu mencoba segala kemungkinan untuk setiap simbol non terminal.