Perdanayudha's Blog

Just another WordPress.com weblog

ANALISA SINTAKS

pada Januari 18, 2011

Definisi SintaksPendefisian Sintaks suatu bahasa dilakukan dengan menggunakan suatu notasi tata bahasa bebas konteks (context-free grammar) atau untuk memudahkan disebut tata bahasa saja.Suatu tata bahasa secara alamiah menerangkan struktur hirarki dari banyak bentuk bahasa pemrograman. Misalkan perintah if-else dari bahasa C mempunyai bentuk:if (ekspresi) perintah else perintahKet :Dalam hal ini suatu perintahadalah gabungan dari :- kata kunci if- kurung buka- ekspresi- kurung tutup- perintah- kata kunci else- perintah lainnya(Dalam bahasa C tidak ada kata kunci then).Bila digunakan nama variabel expr untuk menyatakan suatu ekspresi dan variabel stmt untuk menyatakan suatu perintah, maka struktur aturan ini dapat dinyatakan sebagai berikut :stmt → if (expr) stmt else stmtKet:→ (tanda panah dibaca sebagai) “Dapat berbentuk suatu”.Aturan diatas disebut juga suatu produksi (production). Dalam suatu produksi seperti ini unsur leksikal seperti kata kunci if dan tanda kurung “(“,”)” disebut suatu token

 

 

Variabel seperti expr dan stmt disebut dengan non-terminal.Secara lengkap suatu tata bahasa bebas konteks dapat mempunyai 4 komponen berikut:1. Himpunan dari tokenyang dikenal dengan simbol token.2. Himpunan dari unsur non-terminal3. Himpunan dari produksi, di mana masing-masing produksi terdiri dari unsur non-terminal (bagian kiri tanda panah dari suatu produksi). Bagian kanan produksi berupa → (tanda panah) dan barisan dari token dan/atau non-terminal (sebelah kanan tanda panah).4. Salah satu unsur non-terminal yang telah ditentukan sebagai awal tata bahasa disebut sebagai simbol awal.Aturan umum yang digunakan dalam menentukan suatu tata bahasa adalah dengan menuliskan produksi yang ada dengan dimulai dariproduksi yang mengandung simbol awal.Terminaldapat berupa angka-angka, tanda-tanda seperti <=, dan rangkaian karakter yang ditulis huruf tebal seperti while dan lain-lainnya juga nama lain yang tidak dicetak miring.Non-teminaldapat berupa nama yang dicetak miring.Untuk memudahkan penulisan, maka produksi yang mempunyai simbol non-teminal disebelah kiri yang sama bagian kanannyadapat dikelompokkan dengan menggunakan tanda “|” yang memisahkan pilihan bagian kanan yang ada. pengelompokkan seperti ini dapat dibaca sebagai “atau”Contoh 1:9-5+2, 3-1, 7 merupakan barisan dari angka-angka yang dipisahkan oleh tanda ‘+’ atau ‘-‘.Tata bahasa berikut memberkan sintaks dari ekspresi-ekspresi di atas. Produksi yang ada adalah:

 

list list + digitlist list digitlist digitdigit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Bagian kanan dari produksi untuk unsur non-terminal listlist list + digitlist list digitlist digitdi bagian kiri dapat dikelompokkan menjadi 1 produksi yang setara, yaitu:list list + digit | list digit | digit– Penulisan menjadi:list list + digit | list digit | digitdigit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9- Token yang menjadi digunakan adalah simbol +,-,0,1,2,3,4,5,6,7,8,9- Sedangkan unsur adalah nama-nama yang digaris miring seperti dan – adalah produksi non-terminal Suatu unsur non-terminal dapat merupakan suatu produksi bila unsur non-terminal tersebut timbul dibagian kiri dari produksiBarisan token adalah barisan dari nol atau lebih token. Unsur yang mengandung nol token ditulis sebagai ε, dan disebut dengan nama barisan kosong.Suatu bahasa diperoleh dari :- barisan-barisan yang dimulai dari – bagian kanan yang masih berupa non-terminal (bukan token/terminal) dari produksi dapat diganti dengan mencari acuan pada bagian kiri dari produksi yang ada dengan non-terminal yang sama.- mengganti unsur non-terminal pada bagian kiri produksi dengan bagian kanan dari produksi non-terminal tersebut. – Barisan token pada bagian kanan produksi yang menjadi pengganti unsur non terminal acuan pada bagian kiri produksi merupakan akhir dalam pembentukan bahasa.Produksiterminalnon-terminallistdigitSimbol Awallistsimbol awal

 

Contoh 2:Bahasa yang didefinisikan oleh tata bahasa pada contoh 1 terdiri dari barisan angka-angka yang dipisahkan oleh tanda ‘-‘ atau ‘+’.Kesepuluh produksi dari unsur nonterminal digit (digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) dapat digunakan sebagai penganti token-token yang berhubungan dengan angka yaitu 0,1,2,3,4,5,6,7,8,9 dari produksi list digit, maka dapat dikatakan bahwa 1 angka yang berdiri sendiri adalah suatu list juga, yaitu :Pada produksi list digit0 merupakan bahasa yang dibentuk list1 merupakan bahasa yang dibentuk list2 merupakan bahasa yang dibentuk list3 merupakan bahasa yang dibentuk list4 merupakan bahasa yang dibentuk list5 merupakan bahasa yang dibentuk list6 merupakan bahasa yang dibentuk list7 merupakan bahasa yang dibentuk list8 merupakan bahasa yang dibentuk list9 merupakan bahasa yang dibentuk list

Pada produksi lainnyalist list + digitlist list digitmenyatakan bahwa list yang diikuti oleh tanda ‘+’ atau ‘-‘ dan diikuti oleh list akan membentuk suatu list baru.Ternyata semua produksi yang digunakan pada contoh 1 adalah produksi-produksi yang diperlukan untuk dapat mendefinisikan bahasa yang diinginkan untuk ekspresi 9-5+2, 3-1, 79-5+2 merupakan salah satu anggota dari bahasa yang dibentuk list, dimana list adalah simbol awal. Hal ini dapat ditunjukkan sebagai berikut:a. 9 merupakan list dari produksi “list digit” dimana digit membentuk 9 pada “digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9″ atau secara terpisah menjadi:

 

 

d git → 0digit → 1digit → 2digit → 3digit → 4digit → 5digit → 6digit → 7digit → 8digit.

b. 9-5 merupakan list dari produksi “list list digit” dimana 9 sudah berupa list dan digit membentuk 5 pada “digit → 5″.c. 9-5+2 merupakan list dari produksi “list list + digit” = (9-5) + 2. Dimana 9-5 sudah berupa list dan digit membentuk 2 pada “digit → 2″.Hal ini dapat dilihat pada gambar 1 berikut iniGambar 1 Pohon urai dari ekspresi 9-5+2 menurut tata bahasa contoh 1Pada gambar ini setiap nodal (titik pertemuan antar garis) pada pohon urai diberi label salah satu simbol tata bahasa.Nodal dalam (internal node / nodal di atas nodal yang lain) dan anak-anaknya (nodal yang terletak di bawah nodal dalam) berhubungan dengan suatu produksi.Nodal dalam berhubungan dengan bagian kiri dari produksi, sedangkan anak-anaknya berhubungan dengan bagian kanan dari produksi yang sama.

 

 

. Jadi suatu blok dapat hanya terdiri dari 2 token yaitu begin dan endPada produksi stmt_list sangat mirip dengan produksi list pada contoh 1, dimana tanda “|” menggantikan operator “+” dan “-” (list list + digit | list digit | digit). Unsur non-terminal stmt menggantikan unsur non-terminal digit.Contoh 3 Pada bahasa Pascal dapat dijumpai dalam cakupan blok begin-end. Salah satu perbedaan yang sangat mencolok yang terdapat pada contoh adalah adanya list dari perintah-perintah yang mungkin kosong diantara token-token begin dan end. Untuk itu dikembangkan suatu tata bahasa yang mengandung produksi berikut:block → begin opt_stmts endopt_stmts stmt_list | εstmt_list stmt_list εstmt | stmtPada produksi opt_stmts, kemungkinan ke-2 bagian kanan pada “opt_stmts stmt_list | ε” adalah perintah yang boleh memilih “ε”, yang mengartikan rangkaian kosong dari simbol-simbol

 

 

Definisi Pascal C C++

Sama dengan = == ==

Tidak sama dengan <> != !=

Kurang dari < < <

Kurang dari sama dengan <= <= <=

Lebih dari > > >

Lebih dari sama dengan >= >= >=

– Jangan sampai tertukar antara operator assignment ‘=’ dengan operator pembanding ‘==’.

Hal ini sering terjadi pada orang yang terbiasa dengan Pascal dan beralih ke C.

Kondisional

If..then dan if..then..else

if (a > b) then

begin

a := b;

end;

if (a > b)

{

a = b;

}

if (a > b)

{

a = b;

}

if ((y mod x) = 0)

then

begin

write(‘Divisible’);

end

else

begin

write(‘Not

divisible’);

end;

if ((y % x) == 0)

{

printf(“Divisible”);

}

else

{

 

 

printf(“Not

divisible”);

}

if ((y % x) == 0)

{

std::cout<<“Divisible”;

}

else

{

std::cout<<“Not

divisible”;

}

– Syntax if..then..else dalam C & C++ sama persis.

– Bedanya dengan Pascal adalah tidak adanya keyword then jadi instruksi setelah if() akan

dilaksanakan jika true.

Case..of

case bulan of

1 : begin … end;

2 : begin .. end;

end;

switch (bulan)

{

case 1: …

break;

case 2: …

break;

}

switch (bulan)

{

case 1: …

break;

case 2: …

break;

}

case bulan of

1, 3, 5, 7, 8, 10, 12:

begin

 

 

days := 31;

end;

4, 6, 9, 11:

begin

days := 30;

end;

2:

begin

end;

switch (bulan)

{

case 1:

case 3:

case 12:

days = 31;

break;

case 4:

case 11:

days = 30;

break;

switch (bulan)

{

case 1:

case 3:

case 12:

days = 31;

break;

case 4:

case 11:

days = 30;

break;

end; case 2:

}

case 2:

}

 

 

– Syntax case..of pada C & C++ sama persis.

– Pada C & C++, harus menggunakan keyword switch dan case.

– Pada C & C++ harus digunakan perintah break karena jika tidak ada break, switch akan

membaca sisa perintah yang ada di bawahnya.

Operator ? Ternary

Ada cara lain untuk menuliskan if..then..else yaitu dengan operator ternary ‘?’.

Formatnya: <kondisi> ? <if-true> : <if-false>

Contoh: x = (a < b) ? a : b;

jika a = 5 dan b = 7 maka baris ini akan menjadi x = a;

tapi jika a = 10 dan b = 5 maka baris ini akan menjadi x = b;

Baris di atas setara dengan if (a < b) {x = a;} else {x = b;};

Keunggulan dari ternary adalah singkat, tetapi kelemahannya adalah tidak bisa untuk kondisi

yang agak kompleks.

Pengulangan

Loop For

var i: integer;

for i := 1 to 10 do

begin

end;

int i;

for (i = 1; i <= 10; i++)

{

}

int i;

for (i = 1; i <= 10;

i++)

{

}

– Syntax for dalam C & C++ sama persis.

 

 

– Format: for (<initial value>; <stop condition>; <incremental>) {}

Loop While

var found: boolean;

while (not found) do

begin

end;

unsigned char found;

while (!found)

{

}

bool found;

while (!found)

{

}

– Syntax while dalam C & C++ sama persis.

– Format: while (<kondisi-lanjut>) {}

– Tidak ada keyword do pada while, deretan perintah setelah while() itulah yang akan dieksekusi.

 

 

Tugas analisa sintaks

Posisi Penganalisa Sintaks (Parser) dalam proses kompilasi adalah sebagai berikut :

– Deretan token : dihasilkan oleh Penganalisa Leksikal (Scanner)

– Pohon parse : suatu pohon dimana akarnya (root) adalah simbol awal grammar

(starting symbol), setiap node dalam (inner node) adalah simbol nonterminal, dan

daunnya (leaf) dibaca dari kiri ke kanan adalah deretan token masukan. Pohon parse ini

dibentuk berdasarkan aturan grammar yang ditetapkan untuk parser.

– Kesalahan sintaks : terjadi jika pola deretan token tidak memenuhi ketentuan pola yang

telah ditentukan grammar untuk parser.

Grammar yang dipilih untuk scanner adalah Regular Grammar (RG) sedangkan

untuk parser adalah Grammar Context Free (CFG). Penting diketahui perbedaan cara

pandang RG dengan CFG terhadap sebuah token yang mengalir antara scanner dan

parser. Bagi RG (scanner) sebuah token (kecuali reserve word) adalah sebuah kalimat

dimana setiap karakter pembentuk token tersebut adalah simbol terminal. Sebaliknya bagi

CFG (parser) sebuah token adalah sebuah simbol terminal dimana sederetan tertentu token

akan membentuk sebuah kalimat.

 

 

Review Hal-hal Penting dari CFG

a. Pola umum CFG : A ® a, A Î V N , a Î (V N ½ V T )*

b. Sifat ambigu (ambiguity) :

Sebuah kalimat adalah ambigu jika terdapat lebih dari satu pohon sintaks yang dapat

dibentuk oleh kalimat tersebut. Secara gramatikal kalimat ambigu dihasilkan oleh

grammar ambigu yaitu grammar yang mengandung beberapa produksi dengan ruas

kiri yang sama sedangkan dua atau lebih ruas kanan-nya mempunyai string terkiri

(prefix) yang sama. Contoh :

S ® if E then S½if E then S else S,

dengan S : statement dan E : expression, mempunya dua produksi dengan ruas kiri

sama (S) sedangkan kedua ruas kanannya dimulai dengan string sama (if E then S).

Grammar ambigu dapat diperbaiki dengan metoda faktorisasi kiri (left

factorization). Prefix dari produksi di atas adalah sentensial if E then S sehingga

faktorisasi akan menghasilkan :

S ® if E then S T, T ® e½else S {e : simbol hampa}

c. Sifat rekursi kiri (left recursion) :

Sebuah grammar dikatakan bersifat rekursi kiri jika untuk sebuah simbol nonterminal

A terdapat derivasi non hampa A Þ¼Þ Aa. Produksi berbentuk A ® Aa disebut

produksi yang bersifat immediate left recursion.

Rekursi kiri dapat dieliminir dengan transformasi berikut :

A® Aa½b transformasi menjadi : A ® bR, R® aR½e

Transformasi ini dapat diperluas sehingga :

A® Aa1 ½Aa 2 ½… ½Aan ½b 1 ½b 2 ½…½b n

bertransformasi menjadi :

A ® b 1 R½b 2 R½…½b n R, R® a1 R½a 2 R½..½a n R½e

Contoh 1 : Diketahui : E ® E + T½ T, T ® T * F ½ F, F ® (E)½ I

yang jelas mengandung immediate left recursion untuk simbol E dan T.

Transformasi menghasilkan :

E ® TR E , R E® +TRE ½e , T® FR T , R T®*FR T ½e , F ® (E)½ I

Prosedur transformasi di atas dituangkan dalam algoritma berikut :

 

 

Algoritma Rekursi_Kiri

1. Rename semua nonterminal menjadi A 1 , A 2 , …, A n

2. for i = 1 to n do begin

2.a. for j = 1 to i-1 do begin

ganti setiap produksi berbentuk A i® A j g

dengan produksi-produksi : A i® d 1 g½d 2 g½… ½d k g

dimana : A j® d 1 ½d 2 ½… ½d k produksi-A j saat iterasi ini

end

2.b. eliminasi semua immediate left recursion produksi-A i

end

Contoh 2 : Diketahui : S ® Aa½b, A® Ac½S d½e

Algoritma Rekursi_Kiri akan digunakan terhadap himpunan produksi ini.

Langkah 1 : A 1 := S, A 2 := A sehingga produksi menjadi

A1® A 2 a½b, A 2® A 2 c½A1 d½e

Saat i = 1 inner loop tidak dipenuhi karena (j =1) > (i-1= 0), maka program masuk ke (2.b)

untuk A1 . Tetapi A1 tidak bersifat immediate left recursion. Jadi saat i = 1 program tidak

melakukan apapun.

Saat i = 2,

(2.a) j = 1 : ganti A 2® A 1 d dengan A 2® A 2 ad½bd

(2.b) A2® A 2 c½A2 ad½bd½e adalah immediate left recursion, sehingga diperoleh

transformasinya :

A 2® bdR A ½RA , R A® c R A ½adR A ½e

Hasilnya : A 1® A 2 a½b, A 2® bdR A ½RA , R A® c R A ½adR A ½e , atau :

S ® Aa½b, A® bdR A ½RA , R A® cR A ½adR A ½e

 

 

Predictive Parser

Predictive Parser akan digunakan untuk mengimplementasikan Penganalisa Sintaks

(Parser). Berikut ini adalah model dari Predictive Parser.

Gambar 4.2 : Skema Predictive Parser

Input : rangkaian token dan diakhiri dengan tanda $.

Stack : berisi simbol grammar (VN atau VT ). Pada keadaan

awal stack hanya berisi $ dan S (simbol awal).

Parsing Table M : array 2 dimensi M(A,a), dimana A adalah simbol

nonterminal dan a adalah simbol terminal (token)

atau sibol $. Nilai M(A,a) adalah : sebuah produksi A

® a atau tanda-tanda kesalahan (keduanya akan

dibahas kemudian)

Predictive Parsing Program (P3) : sebuah program yang mengendalikan parser

berdasar-kan nilai A dan a.

Sifat dan tanggapan P3 terhadap simbol A (pada stack) dan a (pada input) :

1. Jika A = a = $ : parser berhenti dan memberitahukan bahwa kerja parser telah selesai

tanpa ditemukan kesalahan sintaks.

2. Jika A = a ¹ $ : parser akan mengeluarkan A dari stack, dan selanjutnya membaca

token berikutnya.

3. Jika A Î VT , A ¹ a : terjadi kesalahan sintaks, dan selanjutnya akan dipanggil routine

penanganan kesalahan (error handler).

4. Jika A Î VN : program akan membaca tabel M(A,a). Jika M(A,a) berisi produksi A®

UVW maka parser akan mengganti A dengan WVU (yaitu dengan U berada di puncak

stack). Jika M(A,a) berisi tanda-tanda kesalahan maka parser akan memang- gil

Error_Handler routine.

 


2 responses to “ANALISA SINTAKS

  1. tuaffi mengatakan:

    Waahh.. sangat membantu.
    Salam kenal.🙂

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: