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. • Kalimat adalah deretan symbol-simbol terminal • Tata bahasa (Grammar) : Sekumpulan dari himpunan variabel-variabel, simbol-simbol terminal, simbol non-terminal, symbol awal yang dibatasi oleh aturan-aturan produksi. • Simbol Terminal: o Huruf kecil alphabet : a,b,c,….,z o Digit 0,1,2,…,9 o Simbol tanda baca seperti tanda kurung, koma dsb o Simbol operator +,- dsb o Rangkaian tercetak tebal spt: if, then, else • Simbol Non Terminal : o Huruf Besar Alfabet : A,B,C,…,Z o Huruf S sebagai symbol awal o String yang tercetak miring, spt expr • Tata Bahasa G didefenisikan sebagai pasangan 4 tuple yaitu VT,VN, S,Q yang dituliskan G=( VT,VN, S Q) dimana: VT = himpunan symbol terminal VN = himpunan symbol non terminal S = Simbol awal Q = Himpunan/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)
Algoritma Pemrograman 1C
2
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
3
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 < α ≤ β Jumlah/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
4
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 (Token). 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, mengabaikan komentar,blank 5. Menangani table simbol 6. Scanner di desain untuk mengenali keyword, operator, identifier 7. Mengelompokan urutan karakter kedalam komponen pokok spt identifier, delimiter,symbol operator,angka, keyword dll. Kelompok karakter yang membentuk sebuah token dinamakan lexeme Contoh : Besaran lexical (tergantung programnya) Algoritma Pemrograman 1C
5
• 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
Token
Lexeme
Const
Const
If
If
Relation
<,<=,=,>=,>, < >,
Identifier
Pi, Count,D2
Num
3,14,
Algoritma Pemrograman 1C
0,602E23
6
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 (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. Sebuah kalimat yang mempunyai lebih dari satu pohon sintaks disebut kalimat ambigu (ambiguous). Grammar yang menghasilkan paling sedikit sebuah kalimat ambigu disebut grammar ambigu. S S
O
A
*
2
S S
S
S
O
S
S
O
S
A
+
A
A
*
A
7
2
3
Algoritma Pemrograman 1C
O
S
+
7
3
7
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
2
x
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
8
