ALGORITMA PEMROGRAMAN 1C SINTAKS

ALGORITMA PEMROGRAMAN 1C

SINTAKS Indah Wahyuni

Konsep Bhs. Pemrograman, 2012

PENDAHULUAN 



1.

Interpreter

2.

Compiler

Sintaks, Indah Wahyuni



Bahasa mesin adalah bentuk terendah komputer. Kita dapat berhubungan langsung dengan bagianbagian yang ada didalam komputer seperti bits, register. Bahasa mesin terdiri dari bit-bit 0 dan 1. Bahasa tingkat tinggi adalah suatu bahasa yang dapat dimengerti baik oleh manusia maupun komputer. Pada bahasa tingkat tinggi kedalam bahasa mesin dibutuhkan sesuatu untuk menterjemahkan agar mesin komputer mengerti apa yang diinginkan oleh manusia, yaitu: 2


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 pemrograma didefenisikan dengan 2 kumpulan aturan, yaitu: 


Aturan Lexical (Lexical Analysis)/ Scanner 2. Aturan Syntactic (Syntactic Analyzer)/ Parser 1.

3


KONSEP & NOTASI BAHASA  Alfabet:

Kumpulan dari objek-objek yang disebut dengan symbol. 

Kumpulan symbol-simbol yang ditulis secara berurutan.  Tata bahasa (Grammar): Sekumpulan dari himpunan variabel-variabel, simbolsimbol terminal, simbol non-terminal, symbol awal yang dibatasi oleh aturanaturan produksi.


Contoh: ∑ 1 = { a,b,c,….,z} ∑ 2 = {c,f}

 Bahasa:

4


GRAMMAR  Sebuah

grammar didefinisikan dengan 4

tipe: ( Vn, Vt, S, Q)




Dimana:  

 

Vn: simbol non terminal (ditulis dgn huruf besar) Vt: simbol terminal (ditulis dgn huruf kecil) S: suatu elemen tertentu dari Vn yang disebut simbo start Q: sebuah elemen (α,β) dari Q yang ditulis sebagai α β yang disebut produksi

5


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 nonterminal  Contoh aturan produksi: 


T a, artinya T menghasilkan a  E T | T + E, artinya E menghasilkan T atau menghasilkan T + E 

6


HIRARKI CHOMSKY


7


HIRARKI CHOMSKY  Tipe  

Ciri : α, β ∈ (VT |VN)*, |α| > 0 Tidak ada batasan aturan produksi Abc De

 Tipe




0 ( Unrestricted Grammar)

1 (Context Sensitive Grammar)

Ciri : α, β ∈ (VT |VN)*, 0 < |α| ≤ |β|  Panjang string ruas kiri harus <= ruas kanan  Ab DeF  CD eF 

8


HIRARKI CHOMSKY 




Tipe 2 (Context Free Grammar)  Ciri : α ∈ VN , β ∈ (VT | VN)*, |α| > 0  Ruas kiri haruslah tepat satu simbol variabel nonterminal  B CdeFg  D BcDe Tipe 3 (Regular Grammar)  Ciri: α ∈ VN, β ∈ {VT , VTVN},atau α ∈ VN, β ∈ {a, bC}  Ruas kanan hanya memiliki maksimum 1 simbol non-terminal yang diletakkan paling kanan sendiri  A efG  A efgH  C D

9



S C C 

aCa aCa b


Contoh  L(G3) = { an b an | n >= 1 }  Dimana: G3 = ( {S,C}, {a,b}, S, Q )  Dengan Q adalah produksi:


CONTEXT FREE GRAMMAR

Contoh turunan/derifasi untuk a3ba3 : S

aCa a aCa a aa aCa aa aaabaaa

10

::=  |  <>  {} terminal 



: : : :

sama identik dengan simbol sama dengan atau pengapit simbol non terminal elemen yang ada didalamnya merupakan


Aturan produksi dapat dinyatakan dengan notasi BNF  BNF menggunakan abstraksi untuk struktur sintaks: 


BACKUS NAUR FORM (BNF)

Contoh: Aturan produksi sebagai berikut : E T|T+E|T–E

T

a

11



Notasi BNF : E ::= | + <E> | - <E> T ::= a


::= | ::= a|b|c|…|y|z


BACKUS NAUR FORM (BNF)

12



1. 2.

3. 4. 5. 6.

Mengidentifikasi semua pesan yang mengandung bahasa Mentransformasikan ke token-token (simbol terminal) Menentukan jenis dari token-token Menangani kesalahan Menangani table simbol Scanner di desain untuk mengenali keyword, operator, identifier




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 :


ATURAN LEKSIKAL / LEXICAL ANALYSIS (SCANNER)

13



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 : pemisah yang diabaikan oleh program seperti enter, spasi



14



Bilangan penyajian internal 1 2 3 4 5 6 7 8 9 10 11 12


Identifier (variabel) :  Identifier (konstanta) :  Identifier (label) :  Identifier (keyword) :  Operator (penjumlahan) :  Operator (penugasan) :  Operator (pengurangan) :  Operator (perkalian) :  Operator (pembagian) :  Tanda baca (koma) :  Tanda baca (titik dua) :  Tanda baca (titik koma) : 



15



Contoh. Statement : Fahrenheit := 32 + celcius * 1.8 Bil. Penyajian

Besaran Leksikal

Lokasi

Fahrenheit

1

Identifier

1

:=

6

Operator (penugasan)

0

32

2

Konstanta (integer)

2

+

5

Operator (penjumlahan)

0

Celcius

1

Identifier

3

*

8

Operator (perkalian)

0

1.8

2

Konstanta (real)

4


Token



16


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


ATURAN SYNTACTIC / SYNTAX ANALYZER (PARSER)

17

1. 2.

Penurunan terkiri (leftmost derivation): simbol variabel yang paling kiri diturunkan dahulu Penurunan terkanan (rightmost derivation): simbol variabel yang paling kanan diturunkan dahulu


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.  Parsing atau proses penurunan dapat dilakukan dengan: 



18






Ada 2 metoda parsing: 1. TOP-DOWN PARSING: Konstruksi pohon sintaks dimulai dari akar dilanjutkan turun kebawah menuju daun Meliputi, Backtrack: Brute Force  Memilih aturan produksi mulaik dari kiri  Meng-expand simbol nonterminal sampai simbol terminal  Bila terjadi kesalahan (string tidak sesuai) maka dilakukan back track  Algoritma ini membuat pohon parsing secara top-down, yaitu dengan cara mencoba segala kemungkinan untuk setiap nonterminal BOTTOM-UP PARSING: Konstruksi dimulai dari daun, bergerak keatas menuju akar



19



Contoh: Buatlah derifasi kiri & kanan dari string aabbaa dari context free grammar



aAS | a SbA | ba Penurunan kiri S aAS a SbA S aabA S aabba S aabba a

• Penurunan kanan S aAS a Aa a SbA a a Sbba a a a bbaa


S A



20

Konsep Bhs. Pemrograman, 2012 Sintaks, Indah Wahyuni

21

ALGORITMA PEMROGRAMAN 1C SINTAKS

Recommend Documents