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 :
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
: S 1 = { a,b,c,….,z}
S 2 = {c,f}
Algoritma Pemrograman 1C
· 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 :
·
B | b|i|
•
|
•
A | B |…..| Z
·
+|-|=
·
^|*|/
•
Contoh :
Begin
A:1
B: A+1
End
ATURAN PRODUKSI
· Aturan produksi dinyatakan dalam bentuk : a ß
(a menghasilkan(menurunkan) ß)
· a simbol-simbol untuk ruas kiri, ß simbol-simbol untuk ruas kanan
· Simbol-simbol bisa berupa terminal atau non-terminal
· Contoh aturan produksi:
a artinya T menghasilkan a
T | T + E artinya E menghasilkan T atau menghasilkan T + E
T
E
Algoritma Pemrograman 1C
HIRARKI CHOMSKY
Tipe 0
Tipe 3
Tipe 2
Tipe 1
Tipe 0 = Unresticted
Tipe 1 = Context Sensitive
Tipe 2 = Context Free
Tipe 3 = Regular
Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (a®b),
Noam Chomsky mengklasifikasikan 4 tipe grammar :
· Tipe 0 ( Unrestricted Grammar)
Ciri : a, bÎ (V T ½V N )*, .a.>0
Tidak ada batasan aturan produksi
Abc
De
•
Tipe 1 (Context Sensitive Grammar)
Ciri : a, bÎ (V T ½V N )*, 0 < .a.
£ .b.
Panjang string ruas kiri harus <= ruas kanan
Ab
DeF
CD
eF
•
Tipe 2 (Context Free Grammar)
Ciri : aÎ V N , bÎ (V T ½V N )*
Ruas kiri haruslah tepat satu simbol variabel non-terminal
CdeFg
BcDe
•
Tipe 3 (Regular Grammar)
Ciri : aÎ V N , bÎ {V T ,V T V N } atau aÎ V N , bÎ {V T ,V N V T }
Mengingat ketentuan simbol-simbol, ciri-ciri RG sering dituliskan sebagai : a
Î V N , bÎ {a, bC} atau aÎ V N , bÎ {a, Bc}
B
D
Algoritma Pemrograman 1C
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|T+E|T–E
T
a
NotasiBNF :E::=
T ::= a
•
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
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
Operator penjumlahan : +
Identifier : celcius id2
Farenheit 32 + 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
(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 : a®b, aÎ V N , bÎ (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 ® H½IH½IA, H ® a½b½c½...½z, A ® 0½1½2½...½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 IH
.
HAAH
.
xAAH I A b
.
x2AH
.
x23H I A 3
.
x23b
H 2
x
Algoritma Pemrograman 1C
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
Tidak ada komentar:
Posting Komentar