SINTAKS Bahasa mesin adalah bentuk terendah komputer. Kita dapat berhubungan langsung dengan bagian-bagian yang ada di dalam komputer seperti bits, register. Bahasa mesin terdiri dari bit-bit 0 dan 1. Bagaimana dengan orang yang tidak mengerti bahasa mesin? . Bahasa mesin tergantung jenis komputer yang digunakan. Bagaimana jika jenis computer mengalami perubahan?. Oleh karena itu manusia berusaha menciptakan suatu bahasa yang dapat dimengerti baik oleh manusia maupun computer, yang disebut dengan nama bahasa tingkat tinggi. Pada bahasa tingkat tinggi ke dalam bahasa mesin dibutuhkan sesuatu untuk menterjemahkan agar mesin computer mengerti apa yang diinginkan oleh manusia, yaitu : 1. Interpreter 2. Compiler Untuk membuat penterjemah seperti compiler perlu dibuat standar atau tata bahasa (aturan) seperti manusia berkomunikasi mempunyai tata bahasa agar lawan bicaranya dapat mengerti yang dibicarakan. Demikian juga untuk menterjemahkan ke dalam mesin, harus dibuat suatu aturan agar computer mengerti apa yang diinginkan oleh manusia melalui program yang dibuatnya. SINTAKS Sintaks merupakan kumpulan aturan yang mendefenisikan suatu bentuk bahasa. Sintaks mendefenisikan bagaimana suatu kata dikembangkan menjadi suatu statement yang benar sehingga dapat disusun menjadi suatu program yang dapat berjalan dengan benar. Sintaks dari bahasa pemrograman di defenisikan dengan 2 kumpulan aturan, yaitu: 1. Aturan Lexical (Lexical Analysis)/ Scanner 2. Aturan Syntactic (Syntactic Analyzer)/ Parser KONSEP DAN NOTASI BAHASA • Alfabet : Kumpulan dari objek-objek yang disebut dengan symbol. Contoh : ∑ 1 = { a,b,c,….,z} ∑ 2 = {c,f} Algoritma Pemrograman 1C
1
• Bahasa : Kumpulan symbol-simbol yang ditulis secara berurutan. • Tata bahasa (Grammar) : Sekumpulan dari himpunan variabel-variabel, simbol-simbol terminal, simbol non-terminal, symbol awal yang dibatasi oleh aturan-aturan produksi. • Tahun 1956 -1959 Noam Chomsky melakukan penggolongan tingkatan dalam bahasa, yaitu menjadi 4 class yang disebut dengan hirarki Chomsky. • Tahun 1959 Backus memperkenalkan notasi formal baru untuk sintaks bahasa yang lebih spesifik. • Peter Nour (1960) merevisi metode dari sintaks yang sekarang dikenal dengan BNF (Backus Nour Form) Contoh tata bahasa sederhana : • • • • • •
<program> B | b|i| <stat> ; <stat> END
| A | B |…..| Z +|-|= ^|*|/ |
Contoh : Begin A:1 B: A+1 End ATURAN PRODUKSI • Aturan produksi dinyatakan dalam bentuk : α β (α menghasilkan(menurunkan) β) • α simbol-simbol untuk ruas kiri, β simbol-simbol untuk ruas kanan • Simbol-simbol bisa berupa terminal atau non-terminal • Contoh aturan produksi: T a artinya T menghasilkan a E T|T+E artinya E menghasilkan T atau menghasilkan T + E
Algoritma Pemrograman 1C
2
HIRARKI CHOMSKY Tipe 0 Tipe 1 Tipe 2
Tipe 0 = Unresticted Tipe 1 = Context Sensitive
Tipe 3
Tipe 2 = Context Free Tipe 3 = Regular
Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar : • Tipe 0 ( Unrestricted Grammar) Ciri : α, β ∈ (V T V N )*, α> 0 Tidak ada batasan aturan produksi Abc De • Tipe 1 (Context Sensitive Grammar) Ciri : α, β ∈ (V T V N )*, 0 < α ≤ β Panjang string ruas kiri harus <= ruas kanan Ab DeF CD eF • Tipe 2 (Context Free Grammar) Ciri : α ∈ V N , β ∈ (V T V N )* Ruas kiri haruslah tepat satu simbol variabel non-terminal B CdeFg D BcDe • Tipe 3 (Regular Grammar) Ciri : α ∈ V N , β ∈ {V T , V T V N } atau α ∈ V N , β ∈ {V T , V N V T } Mengingat ketentuan simbol-simbol, ciri-ciri RG sering dituliskan sebagai : α ∈ V N , β ∈ {a, bC} atau α ∈ V N , β ∈ {a, Bc}
Algoritma Pemrograman 1C
3
Ruas kanan hanya memiliki maksimum 1 simbol non-terminal yang diletakkan paling kanan sendiri A eFG A efgH C D 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 Notasi BNF
T|T+E|T–E a
: E ::= | + <E> | - <E> T ::= a ::= | ::= a|b|c|…|y|z
• Aturan Leksikal 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. Tugas-tugasnya secara detil adalah : 1. Mengidentifikasi semua pesan yang mengandung bahasa 2. Mentransformasikan ke token-token (simbol terminal) 3. Menentukan jenis dari token-token 4. Menangani kesalahan 5. Menangani table simbol 6. Scanner di desain untuk mengenali keyword, operator, identifier
Algoritma Pemrograman 1C
4
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 dsb • Operator : Operator aritmatika, operator logika (and, or,not), operator relational (<,>,=,!=) • Delimiter : berguna sebagai pemisah / pembatas seperti kurung buka, kurung tutup, titik, koma, titik dua, titik koma, white space • White space : pemisah yang diabaikan oleh program seperti enter, spasi
Contoh: Statement : Fahrenheit := 32 + celcius * 1.8 Maka akan diterjemahkan ke dalam token-token sebagai berikut: Identifier : Fahrenheit id1
S
Operator : := Integer : 32
id1
:=
ekspresi
32
+
Operator penjumlahan : + Identifier : celcius id2
Farenheit
id2
*
1.8
Operator perkalian : * Real / Float : 1.8
cecius
SINTAKS ANALYZER (PARSER) Bertugas memeriksa kebenaran dari urutan token-token yang terbentuk oleh leksikal analisis. Pengelompokkan ke dalam class sintaks (bentuk sintaks) seperti procedure, stat n dan ekspresi. Grammar dipakai oleh sintaks analyzer untuk menetukan struktur dari program sumber. Proses pendeteksian Algoritma Pemrograman 1C
5
(pengenalan token) disebut dengan parsing, maka syntax analyzer sering 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 : α → β, α ∈ V N , β ∈ (V N V T )* 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. Contoh 1 : Diketahui grammar G 1 = {I → HI HIA, H → abc...z, A → 012...9} dengan I adalah simbol awal. Berikut ini kedua cara analisa sintaks untuk kalimat x23b. cara 1 (derivasi)
cara 2 (parsing)
I ⇒ IH
I
⇒ IAH ⇒ IAAH
I
H
⇒ HAAH ⇒ xAAH
I
A
b
⇒ x2AH ⇒ x23H
I
A
3
⇒ x23b H
Algoritma Pemrograman 1C
x
2
6
Metoda Parsing Ada 2 metoda parsing : top-down dan bottom-up. 1. TOP-DOWN PARSING Konstruksi pohon sintaks dimulai dari akar dilanjutkan turun ke bawah menuju daun 2. BOTTOM-UP PARSING Konstruksi dimulai dari daun, bergerak keatas menuju akar
Pembacaan semua leaf dari pohon parsing jika dibaca dari kiri ke kanan
Algoritma Pemrograman 1C
7
