Hierarky Chomsky
Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (alpha => Beta), Noam Chomsky mengklasifikasikan 4 Type granmar :
* Type 0 (Unresctricted Grammar)
Ciri =
Tidak ada batasan aturan produksi
abc => De
* Type 1 (Context Sensitive Grammar)
Ciri
Jumlah/panjang string ruas kiri <+ ruas kanan
Ab —> DeF
CD–>eF
*Type 2 (Context Free Grammar)
Ciri
Ruas kiri haruslah tepat satu simbol variabel non-terminal
B –>CdeFg
D–>BcDe
* Type 3 (Regular Grammar)
Ciri
Mengingat ketentuan simbol-simbol, ciri ciri RG sering dituliskan
Alpha
NOTASI BNF(Backus Nour Form)
Aturan produksi dapat dinyatakan dengan Notasi BNF
BNF menggunakan abstraksi untuk struktur sintaks :
::= : sama identik dengan simbol
| : sama dengan atau
<> : Pengapit simbol non terminal
{} : elemen yang ada didalamnya merupakan terminal
Contoh :
Aturan produksi sebagai berikut : E —> T | T+E | T-E hasilnya T —> a
Notasi BNF : E ::= <T>|<T>+<E>|<T>-<E> T :==a
Aturan Lefsikal
Berhubungan dengan bahasa sering disebut dengan Scanner bertugas sebelum proses syntax analyzer dan intermediate code dilakukan dimana tugas analisis leksikal ini mendekomposisikan program sumber menjadi bagian-bagian kecil(Token). Tugasnya sebagai berikut :
1. Mengidentifikasi semua pesan yang mengandung Bahasa
2. Mentransformasikan ke token-token (simbol terminal)
3. Menentukan jenis dari token-token
4. Menangani kesalahan, mengabaikan komentar, blank
5. Menangani table simbol
6. Scanner didesain untuk mengenali keyword operator, identifier
7. Mengelompokkan urutan karakter kedalam komponen pokok seperti identifier, delimiter, symbol operator, angka, keyword dll.
Kelompok karakter yang membentuk sebuah token dinamakan Lexeme
Contoh
– Besaran Lexical (tergantung programnya)
– Identifier dapat berupa keyword seperti = IF, THEN, ELSE, BEGIN… END (Pada PASCAL), Integer (PASCAL), Int, Float, (Bahasa C)
– konstanta besaran yang berupa bilangan bulat (integer), bilangan pecahan {float/real}, boolean (true/false), string dan sebagainya.
– Operator : Operator Aritmatika, Operator Logika (And, Or, Not) dan operator Relational (<,>,=,!=)
– Delimiter : berguna sebagai pemisah / pembatas seperti kurung buka, kurung tutup, titik, koma, titik dua, titik koma, white space
– White space : pemisah yang diabakan oleh program seperti enter, dan spasi.
Contoh
Statement : Farenheit := 32+celcius* 1.8
Maka akan diterjemahkan ke dalam token-token sebagai berikut :
Identifier : Fahrenheit Id1
Operator : :=
Integer : 32
Operator penjumlahan : +
Identifier : Celcius Id2
Real/Float : 1.8
SYNTAX ANALYZER
Bertugas memeriksa kebenaran dari urutan token-token yang terbentuk oleh leksikal analisis. Pengelompokkan kedalam class sintaks (bentuk sintaks) seperti procedure, stat n, dan ekpresi. Grammar dipakai oleh syntax analyzer untuk menentukan struktur dari program sumber. Proses pendeteksian (pengenalan token) disebut dengan parsing, maka syntax analyzer disebut dengan parser.
Pohon sintaks yang dihasilkan digunakan untuk semantic analyzer yang bertugas untuk menentukan maksud dari program sumber, misalnya operator penjumlahan maka semantic analyzer akan mengambil aksi apa yang harus dilakukan.
Grammar context-free dan parsing
Bentuk umum produksi CFG adalah
Analisis sintaks adalah penelusuran sebuah kalimat (atau sentensial) sampai pada simbol awal grammar. Analisis sintaks dapat dilakukan melalui derivasi atau parsing. Penelusuran melalui parsing menghasilkan pohon sintaks.
Sebuah kalimat yang mempunyai lebih dari satu pohon sintaks disebut kalimat ambigu (Ambigous). Grammar yang menghasilkan paling sedikit sebuah kalimat ambigu disebut grammar ambigu.
Contoh 1 :
Diketahui grammar
dengan | adalah simbol awal. Berikut kedua cara analisa sintaks untuk kalimat x23b
Derivasi dan Parsing
Metoda Parsing
Ada 2 Metoda Parsing : Top Down dan Bottom Up
1. Top Down Parsing
Kontruksi pohon sintaks dimulai dari akar dilanjutkan turun ke bawah menuju daun
2. Bottom Up Parsing
Kontruksi dimulai dari daun, bergerak keatas menuju akar.
(pembacaan semua leaf dari pohon parsing jika dibaca dari kiri ke kanan)
