3.1. Definisi Syntax Syntax suatu bahasa pemrograman adalah satu himpunan

BAB 3. ANALISIS SINTAK PERAN PENGURAI CONTEXT-FREE GRAMMAR PENULISAN GRAMMAR PENGURAIAN TOP-DOWN PENGURAIAN BOTTOM-UP PENGURAIAN OPERATOR-PRECEDENCE PENGURAIAN LR PENGGUNAAN AMBIGUOUS GRAMMAR PEMBENTUK PENGURAI

Teknik Kompilasi

3.1

Dr. Nidjo Sandjojo, M.Sc

Syntax & Semantics Definisi Syntax à Syntax suatu bahasa pemrograman adalah satu himpunan peraturan yang menjelaskan bagaimana simbol-simbol simbol simbol bahasa dapat dirangkai bersama untuk membentuk pernyataan (statement) yang berarti. à Aturan formal yang mengatur bagaimana seseorang menulis instruksi yang valid dalam pada suatu bahasa. Definisi Semantics à Himpunan aturan yang memberikan artian dari suatu instruksiinstruksi instruksi yang ditulis pada suatu bahasa pemrograman.

Teknik Kompilasi

3.2


1

Pendahuluan Setiap bahasa pemrograman mempunyai aturan-aturan yang menjelaskan struktur sintak dari program-program yang dibuatnya. Misalnya i l pada d bahasa b h Pascal: l à Program terbentuk dari beberapa blok. à Blok terbentuk dari beberapa statements. à Statements terbentuk dari beberapa ekspresi. à Ekspresi terbentuk dari beberapa token. à Token terbentuk dari beberapa characters.

Teknik Kompilasi

3.3


Pendahuluan (cont’d) Sintak dari bentuk bahasa pemrograman dapat dijelaskan oleh notasi Context-Free Grammars atau Backus-Naur Form (BNF) yang memberikan beberapa keuntungan baik kepada perancang maupun penulis compilers. Keuntungan-keuntungan tersebut adalah: à Spesifikasi sintak jelas dan mudah dimengerti à Efisiensi & dapat menemukan ambiguity à Mendeteksi kesalahan untuk membuat program yang benar à Menampilkan ilk construct (bentuk) (b k) baru b dan d kemampuan k tambahan.

Teknik Kompilasi

3.4


2

PERAN PENGURAI

token source program

Lexical Analyzer

get next token

Parser

parse tree

Rest of intermediate Front End representation

Symbol Table

Position of parser in compiler model

Teknik Kompilasi

3.5


PERAN PENGURAI (cont’d) Penguraian (parsing) adalah proses penentuan apakah satu rangkaian/untaian (string) tokens dapat dibentuk (generated) oleh satu tata bahasa. Dalam pembahasan masalah ini akan sangat membantu dengan berfikir bahwa satu pohon urai sedang dibentuk walaupun sebenarnya compiler tidak membentuk pohon urai semacam itu. Namun demikian suatu pengurai (parser) harus dapat membentuk pohon urai atau bila tidak maka penerjemahan tidak dijamin berjalan benar. benar

Teknik Kompilasi

3.6


3

PERAN PENGURAI (cont’d) Adapun peran utama pengurai (parser) adalah: Parser menerima token dari Lexical Analyzer Menguji bahwa token tersebut dapat dibentuk oleh tata bahasanya Parser melaporkan kesalahan sintak Parser harus dapat kembali bekerja walau telah menemukan kesalahan sampai proses akhir.

3.7

Teknik Kompilasi


Perbedaan Pohon Sintak & Pohon Urai POHON SINTAK Disebut Abstract Syntax Tree atau Syntax Tree

POHON URAI Disebut Concrete Syntax Tree

Setiap node merepresentasikan operator dan anak-anak node merepresentasikan operand

Akar (root)-nya merupakan simbol mulai (start symbol) dan daun-nya merupakan produksi sebelah kanan suatu grammar, atau lebih menekankan grammar) Contoh: Pohon urai untuk 9-5+2 berdasarkan grammar: List Æ list + digit List Æ list - digit List Æ digit Digit Æ 0|1|2|3|4|5|6|7|8|9

Contoh: Pohon syntax untuk 9-5+2

Teknik Kompilasi

3.8


4

Perbedaan Pohon Sintak & Pohon Urai (cont’d) Gambar Pohon Sintak

Teknik Kompilasi

Gambar Pohon Urai

3.9


Tipe Pengurai 1.Universal à Dapat digunakan untuk menguraikan semua jenis tata bahasa. Sangat tidak efisien digunakan untuk keperluan kompilasi. kompilasi 2.Top-Down à Membentuk pohon urai dari atas atau root (akar) ke bawah atau daun (leaf). 3.Bottom-Up pohon urai dari bawah ke atas. à Memebentuk p Tersebut nomor dua dan tiga adalah yang lazim dan lebih efisien digunakan dalam pembuatan atau proses kompilasi.

Teknik Kompilasi

3.10


5

Syntax Error Handling Bila satu Compiler hanya memproses program yang benar, rancangan & implementasi-nya akan lebih sederhana. Tetapii programer sering i menulis li program yang tidak id k benar b dan d compiler yang baik harus dapat membantu programmer didalam mengidentifikasi dan melokalisasi kesalahan.

Teknik Kompilasi

3.11


Kesalahan Kesalahan dapat terjadi pada beberapa tingkat yang berupa: 1. Leksikal, misal salah mengejah identifier, keyword (kata kunci), dan operator. 2. Sintak, misal ekpresi arithmetic dengan tanda kurung yang tidak seimbang. 3. Semantik, misal suatu operator dipakai pada operand yang tidak cocok. 4 Logika 4. Logika, misal recursive call (pemanggilan berulang) yang tidak terhingga (endless loop).

Teknik Kompilasi

3.12


6

Pendeteksian Kesalahan Pendekteksian Kesalahan dan penanggulangannya dipusatkaan pada phase ANALISIS. Alasannya : à Kesalahan terjadi pada sifat sintaknya, sintaknya atau kumpulan token yang datang dari lexical analyzer tidak sesuai dengan tata bahasanya. à Ketepatan dari metode parser modern yang dapat mendeteksi kesalahan sintak dengan efisien.

Teknik Kompilasi

3.13


Tujuan Mengatasi Kesalahan 1.Melaporkan adanya kesalahan dengan jelas dan akurat. 2.Harus dapat cepat kembali mendeteksi kesalahan selanjutnya l j jika jik telah l h mendeteksi d k i kesalahan k l h sebelumnya. b l 3.Tidak harus memperlambat proses jika dilakukan terhadap program yang benar.

Teknik Kompilasi

3.14


7

Cara Pelaporan Bagaimana pengendali kesalahan (error handler) melaporkan adanya kesalahan? à Salah satu cara: mencetak baris dimana kesalahan mungkin terjadi; pesan juga ditampilkan. Setelah mendeteksi adanya kesalahan, pengurai (parser) kembali berfungsi walaupun kadang-kadang kesalahan pertama akan mempengaruhi proses selanjutnya, namum proses tidak berhenti. Pada umumnya pengurai kembali pada suatu phase dengan melanjutkan l j tk pemrosesan input i t dengan d harapan h input i t tersebut t b t dapat d t diurai dengan benar.

3.15

Teknik Kompilasi


Error--Recovery Strategies Error Panic Mode (Mode Panik) Paling sederhana bila menemukan kesalahan, parser membuang simbol i b l input i sampaii salah l h satu token k penyelaras l ( (synchronizing h i i ttoken) k ) ditemukan, misalnya; dan end. Metode ini tidak menimbulkan endless loop. Phrase Level (Kombinasi Kata-kata) Pada saat menemukan kesalahan, parser melakukan pembetulan loka pada sisa input dengan menggati awalan (prefix) dari sisa input dengan string yang dapat meneruskan proses. Pembetulan sederhana misalnya menghapus titik koma yang berlebihan, menggati koma dengan titik koma, tapi kadang menimbulkan loop tak terhingga (endless loop)

Teknik Kompilasi

3.16


8

Error--Recovery Strategies (cont’d) Error Error Production (Produksi Kesalahan) Bila menemukan kesalahan yang umum/biasa, kemudian memperluas tentang bahasanya dengan memproduksi bentuk bentuk-bentuk bentuk yang salah. Produksi yang diperluas tersebut digunakan untuk proses penguraian untuk dapat mendiagnosa bentuk input yang salah. Global Correction (Pembetulan Menyeluruh) Kompilator yang ideal hanya akan membuat perubahan sedikit mungkin dalam hal proses input yang tidak benar. Ada beberapa global dengan cara tertentu sehingga perubahan pada token dilakukan sekecil mungkin. Metoda ini sangat mahal dari segi waktu/tepat.

3.17

Teknik Kompilasi


CONTEXT--FREE GRAMMAR CONTEXT Banyak bentuk bahasa pemrograman memiliki struktur rekursif (recursive: berulang) yang dapat didefinisikan oleh context-free grammar (CFG). Misalnya kita memiliki statement bersyarat yang didefinisikan oleh satu peraturan seperti: à Bila S1 dan S2 adalah statement dan E adalah expression, maka; If E then S1 else S2 adalah sebuah statement.

à Dalam bentuk produksi: stmt Æ if expr then stmt else stmt

Bentuk statement bersyarat ini tidak dapat ditentukan dengan menggunakan notasi regular expression. Regular expression dapat menentukan struktur leksikal dari suatu token.

Teknik Kompilasi

3.18


9

CONTEXT--FREE GRAMMAR (cont’d) CONTEXT Dengan menentukan variabel stmt untuk menyatakan kelas dari statement dan expr menyatakan kelas dari expression, kita dapat mengekpresikan statement diatas dengan menggunakan produksi tata bahasa. à Dalam bentuk produksi: stmt Æ if expr then stmt else stmt

CFG terdiri dari Terminal, Non-Terminal, Start symbol, dan Produksi. .

3.19

Teknik Kompilasi


CONTEXT--FREE GRAMMAR (cont’d) CONTEXT KOMPONEN Satu set token Satu set non-terminal Satu set produksi Satu non-terminal sebagai tanda start Contoh Grammar :

stmt Æ Start symbol

Teknik Kompilasi

produksi

if (expr) stmt else stmt

token

Variables Æ urutan token = non-terminal

3.20


10

CONTEXT--FREE GRAMMAR (cont’d) CONTEXT CONTOH List

Æ List + Digit

List

Æ List - Digit

List

Æ Digit

Digit Æ 0|1|2|3|4|5|6|7|8|9 Dapat ditulis menjadi: List

Æ |List+Digit|List-Digit|Digit

Catatan: à Simbol2 terminal: + - | à Simbol2 non-terminal: list digit 0 …9

Teknik Kompilasi

3.21


CONTEXT--FREE GRAMMAR (cont’d) CONTEXT KEGUNAAN CONTEXT-FREE GRAMMAR ADALAH: Menentukan syntax suatu bahasa. Menjelaskan dengan tepat syntax suatu bahasa. Menjelaskan struktur hierarkhi bentuk-bentuk bahasa. Membantu mengarahkan penerjemahan.

Teknik Kompilasi

3.22


11

CONTEXT--FREE GRAMMAR (cont’d) CONTEXT TERDIRI DARI : 1. Terminal Simbol dasar dari suatu rangkaian yang terbentuk token Æ terminal, kata kunci if then dan else Æ terminal

2. Non-Terminal Æ stmt dan expr Adalah variabel sintatik yang menyatakan kumpulan dari rangkaian, mendefinisikan kumpulan dari rangkaian yang membantu bahasa yang ddibentuk be tu oleh o e tata bahasa. ba asa. Memberikan e be a struktur st u tu hirarki a yang ya g bermanfaat be a aat dalam proses analisis sintak translasi

3.23

Teknik Kompilasi


CONTEXT--FREE GRAMMAR (cont’d) CONTEXT 3. Awal Simbol Satu non-terminal berfungsi sebagai awal simbol, kumpulan rangkaian yang dinyatakannya merupakan bahasa yang didefinisikan tata bahasa tersebut.

4. Produksi Menentukan perilaku dimana terminal dan non-terminal dapat digabungkan untuk membentuk rangkaian. Setiap produksi terdiri dari non-terminal diikuti oleh tanda panah (kadangkadang simbol ::=), diikuti oleh rangkaian dari suatu non-terminal dan terminal. i l à Bila S1 dan S2 adalah statement dan E adalah expression, maka; If E then S1 else S2 adalah sebuah statement. à Dalam bentuk produksi: stmt Æ if expr then stmt else stmt

Teknik Kompilasi

3.24


12

Ketentuan--Ketentuan Notasi Ketentuan 1. Simbol-simbol Terminal à Huruf kecil awal alfabet, misal a, b, c à Simbol operator operator, misal +, + -, - dsb à Simbol tanda baca, misal tanda kurung, koma dsb à Digit 0, 1, 2, ….9 à Rangkaian tercetak tebal, misal id atau if 2. Simbol-simbol Non-Terminal à Huruf besar alfabet, misal A, B, C à Huruf S jika muncul biasanya dianggap sebagai simbol awal à Nama dengan huruf kecil seperti expr atau stmt 3. Terminal/Non-Terminal à Huruf besar akhir alfabet spt X,Y,Z merepresentasikan simbol tata bahasa (mungkin terminal atau non-terminal) Teknik Kompilasi

3.25


Ketentuan--Ketentuan Notasi (cont’d) Ketentuan 4. Terminal à Huruf kecil akhir alfabet seperti x, y, z merupan rangkaian (strings) dari suatu terminal. 5. Huruf kecil yunani seperti α β dan γ merupakan rangkaian (strings) dari simbol tata bahasa. Produksi, A Æα menyatakan ada satu non-terminal A disebelah kiri tanda panah & rangkaian simbol tata bahasa α disebelah kanan. 6. Jika A Æ α1, A Æ α2 … A Æ αk (atau A-produksi) dapat ditulis sebagai AÆα1|α2 …|αk where α1, α2 … αk, sebagai alternatif untuk A. 7. Jika tidak disebutkan, sisi kiri dari produksi yang pertama adalah simbol awal.

Teknik Kompilasi

3.26


13

Ketentuan--Ketentuan Notasi (cont’d) Ketentuan Grammar Notation The following notation used in the text is fairly standard in the literature: à Terminals include lower-case letters earlyy in the alphabet p like a, b, c, operator symbols like +, -, punctuation symbols like comma and parentheses; digits 0, 1, …, 9; boldface strings like id or const. à Non-terminals include upper-case early in the alphabet like A, B, C; the letter S (usually the start symbol); lower-case italized names like expr or stmt. à Upper-case letters late in the alphabet like X, Y or Z stand for grammar symbols; i.e. either terminals or non-terminals. à Lower Lower-case case letters late in the alphabet like u, u v, v …zz stand for strings of terminal symbols. à Lower-case Greek letters like α, β, γ stand for strings of grammar symbols. Hence a typical context-free grammar can be written as A Æ α.

Teknik Kompilasi

3.27


DERIVASI E Æ -E Æ -(E) Æ -(id) Urutan penggantian E berturut-turut sampai dengan –(id) disebut DERIVASI untuk k –(id) (id) dari d i E. Simbol Æ artinya derive dalam 1 langkah atau derive dalam nol atau lebih, or *Æ +Æ derive dalam 1 langkah atau lebih. Pohon urai & derivasi See fig …derivasi

Teknik Kompilasi

3.28


14

DERIVASI (cont’d) Gambar Derivasi

3.29

Teknik Kompilasi


AMBIGUITY Grammar yang dapat memiliki lebih dari satu pohon urai yang dihasilkan dari satu rangkaian token yang diketahui. Contoh : Grammar: List Æ|list+digit|list-digit|digit. Misalnya kita tidak dapat membedakan antara list dan digit, sehingga keduanya dianggap sebagai string; maka grammar-nya: stringÆ|string+string|string-string|string. Sehingga pohon urainya dapat : string string

string 9

string string

g string

string

string +

5

string -

9

2

+

5

string -

2

Kedua pohon urai tersebut untuk: 9 + 5 - 2 Teknik Kompilasi

3.30


15

PENULISAN SUATU TATA BHS Tata bahasa mempunyai kemampuan untuk menjelaskan sehingga besar, tetapi tidak semua, syntax dari bahasa pemrograman Sebagian b i kecil k il dari d i analisis li i syntax dikerjakan dik j k oleh l h penganalisis li i leksikal l k ik l sebagaimanan ia menghasilkan rangkaian token dari karakter inputnya. Setiap metode pengurian hanya dapat menangani satu bentuk tertentu, tata bahasa awal mungkin harus ditulis kembali untuk dapat memungkinkanya menguraikan dengan metode yang dipilih.

3.31

Teknik Kompilasi


PENULISAN SUATU TATA BHS (cont’d) Regular Expressions vs Context-Free Grammar Setiap bentuk yang dapat di jelaskan oleh satu regular expression, d t juga dapat j dijelaskan dij l k oleh l h satu t tata t t bahasa. b h Misal: regular expression (a|b)*abb dan tata bahasa: A0 Æ aA0|bA0|aA1 A1 Æ bA2 A2 Æ bA3 A3 Æ ∈ menjelaskan bahasa yang sama, set string “a” dan “b” yang diakhiri dengan abb.

Teknik Kompilasi

3.32


16

PENULISAN SUATU TATA BHS (cont’d) Karena setiap set regular adalah satu bahasa bebas konteks, maka timbul pertanyaan : à Mengapa menggunakan ekspresi regular untuk mendefinisikan lexical syntax dari suatu bahasa? Alasan-alasanya sebagai berikut: 1. Peraturan-peraturan leksikal dari satu bahasa pada umumnya cukup sederhana, dan untuk menjelaskannya tidak memerlukan notasi sebagus/sekuat grammar. 2. Expresi regular pada umumnya menyediakan notasi yang singkat dan lebih mudah dimengerti oleh token dari pada tata bahasa. 3 Lexical analyzer yang lebih efisien dapat dibentuk secara otomatis dari ekspresi 3. regular dari pada grammar. 4. Pemisahan struktur sintak dari suatu bhs ke dalam bagian-bagian leksikal dan nonleksikal menyediakan kemudahan dalam hal modulasi front end menjadi dua komponen yang mudah diatur. Teknik Kompilasi

3.33


PENULISAN SUATU TATA BHS (cont’d) There are no firm guidelines as to what to put into the lexical rules, as opposed to the syntactic rules. Regular expressions are most useful for describing the structure of lexical constructs such as identifiers, constants, keywords, and so forth. Grammars, on the other hand, are most useful in describing nested structures such as balanced parentheses, matching begin-end's, corresponding ifif-then-else's, then else s, and so on. As we have noted, these nested structures cannot be described by regular expressions.

Teknik Kompilasi

3.34


17

PENULISAN SUATU TATA BHS (cont’d) Secara mekanik kita dapat merubah satu NFA menjadi grammar yang menghasilakan bahasa yang sama yang dikenali oleh NFA tersebut. Tata bahasa tersebut diatas dibentuk dari NFA sebagai berikut: a

b

a

start 0

b 2

1

3

b Teknik Kompilasi

3.35


PENULISAN SUATU TATA BHS (cont’d) Menggunakan susunan sebagai berikut : Untuk setiap state i dari NFA, membentuk satu simbol nonterminal Ai. Bila state i mempunyai satu transisi ke state j simbol a, mengenalkan produk Ai Æ aAj Bila state i ke state j dgn input ε, mengenalkan produksi Ai ÆAj Bila i adalah state penerima, mengenalkan Ai Æ ε Bila i adalah state awal, membuat Ai sbg simbol start dari grammar.

Teknik Kompilasi

3.36


18

PENGURAIAN TOPTOP-DOWN Penguaraian (turun berulang) Penguraian top-down Æ usaha untuk: à Mencari M i derivasi d i i paling li kiri ki i (left-most) (l ft t) suatu t rangkaian k i input i t à Membentuk pohon urai Contoh à Tata Bhs: S Æ cAd, A Æ ab|a à Input: w Æ cad S

S c

A

d

c

A a

Teknik Kompilasi

S d b

c

A

d

a

3.37


PENGURAIAN PRAKIRA stmt Æ if expr then stmt else stmt | while expr do stmt | begin b i stmt_list t t li t end d Kata kunci if, while dan begin akan menentukan produksi

Teknik Kompilasi

3.38


19

PENGURAIAN BOTTOMBOTTOM-UP Penguraian shift-reduce Penguraian dasar-atas Æ memperoleh derivasi rightmost Contoh : à Tata bahasa: S Æ aABe A Æ Abc|b BÆd Kalimat : abbcdc dapat direduksi ke S, sbb : abbcde AÆb Jadi abbcde dapat direduksi menjadi S. S aAbcde A Æ Abc Derivasi Right-Most: aA de BÆd S ÆaABc ÆaAde Æ aAbcde Æ abbcde aA B e S Æ aABe S Teknik Kompilasi

3.39


20

3.1. Definisi Syntax Syntax suatu bahasa pemrograman adalah satu himpunan

Recommend Documents