Module-02.pdf

ANALISIS LEKSIKAL

Teknik Kompilasi

2.1

Dr. Nidjo Sandjojo, M.Sc

BAB 2. ANALISIS LEKSIKAL PERAN PENGANALISIS LEKSIKAL INPUT BUFFERING SPESIFIKASI TOKEN PENGENALAN TOKEN SATU BAHASA UNTUK PENENTUAN (SPECIFYING) PENGANALISIS LEKSIKAL FINITE AUTOMATA DARI EKSPRESI REGULAR KE NFA RANCANGAN PEMBENTUK PENGANALISIS LEKSIKAL PENGOPTIMASIAN POLA BERDASARKAN-DFA Teknik Kompilasi

2.2

Dr. Nidjo Sandjojo, M.Sc

1

PERAN PENGANALISIS LEKSIKAL

source program

token

L i l Lexical Analyzer

get next token

Parser

p parse tree

Symbol Table

Teknik Kompilasi

2.3

SOURCE TEXT

PARSER

LEXER

Tokens

Characters

Teknik Kompilasi

Dr. Nidjo Sandjojo, M.Sc

2.4

Dr. Nidjo Sandjojo, M.Sc

2

PERAN PENGANALISIS LEKSIKAL PERAN PENGANALISIS LEKSIKAL ADALAH: Membaca karakter input & menghasilkan token Menghilangkan komentar dan ruang kosong Menghubungkan antara pesan kesalahan yang diperoleh kompilator dengan program sumber Mengenali identifier dan keyword Identifier = variables, arrays, function, etc etc.,, token Keyword = fixed characters: begin, end, if, etc.

Teknik Kompilasi

2.5

Dr. Nidjo Sandjojo, M.Sc

ALASAN PEMISAHAN PHASE ANALISIS Phase Analysis dipisah menjadi dua, yaitu: Lexical Analyzer dan Syntax Analyzer dengan alasan: Penyederhanaan rancangan Efisiensi kompilator lebih baik Portabilitas kompilator meningkat

Teknik Kompilasi

2.6

Dr. Nidjo Sandjojo, M.Sc

3

TOKEN, LEXEME dan PATTERN Lexeme

Pattern

Token

Suatu rangkaian k kt pada karakter d program sumber yang cocok atau sesuai dengan pola (pattern) untuk membentuk satu token.

Peraturan yang menjelaskan j l k sett lexeme yang dapat merepresentasikan satu token tertentu dalam program sumber.

Merupakan rangkaian k kt yang dalam karakter d l satu t kesatuan memiliki arti tersendiri, dapat berupa: kata kunci (key word), operator, identifier constant, rangkaian huruf (literal string); simbol baca (function symbol) misalnya: tanda kurung, koma, titik koma, dan sebagainya.

Satu set string input yang dijelaskan oleh satu peraturan. Harus cocok (match) dengan setiap string yang ada dalam set tersebut.

Teknik Kompilasi

2.7

Dr. Nidjo Sandjojo, M.Sc

TOKEN, LEXEME dan PATTERN TOKEN

SAMPLE LEXEMES

INFORMAL DESCRIPTION OF PATTERN

const

const

const

if

if

if

<, <=, =, <>, >, >=

< or <= or = or <> or > or =

id

pi, count, D2

letter followed by letters and digits

num

3 1416 0 3.1416, 0, 6 6.02E23 02E23

any numeric constant

literal

"core dumped"

any character between " and " except "

relation

Teknik Kompilasi

2.8

Dr. Nidjo Sandjojo, M.Sc

4

ATTRIBUTE UNTUK TOKEN Bila terdapat lebih dari satu pattern yang sesuai dengan satu lexeme, lexical analyzer harus melengkapi informasi tambahan tentang lexeme mana yang dimaksud atau yang sesuai dengan phase berikutnya dari kompiltor. Token biasanya hanya mempunyai satu atribut yaitu POINTER yang disimpan dalam tabel simbol.

Teknik Kompilasi

2.9

Dr. Nidjo Sandjojo, M.Sc

ATTRIBUTE UTK TOKEN CONTOH: Pattern num cocok untuk string 0 dan 1, sedangkan code generator harus tahu string mana yang dimaksud, misalnya E = M *C**2 akan ditulis berpasangan sbb: <exp_op,> Teknik Kompilasi

2.10

Dr. Nidjo Sandjojo, M.Sc

5

KESALAHAN LEKSIKAL Hanya sedikit kesalahan leksikal (lexical errors) yang dapat dilihat di phase lexical analyzer karena phase ini mempunyai pandangan yang sempit pada program sumber Misal; fi(a = = f(x)) dalam bahasa C, maka lexical analyzer tidak dapat menjelaskan apa fi tersebut betul sebagai identifier atau salah eja yang seharusnya adalah if

Teknik Kompilasi

2.11

Dr. Nidjo Sandjojo, M.Sc

KESALAHAN LEKSIKAL (Cont’d) KEMUNGKINAN PEMULIHAN KESALAHAN Menghapus karakter yang berlebihan Memasukkan karakter yang diduga hilang Menganti karakter yang diduga salah dengan yang benar Menukar letak dari dua karakter yang berdekatan

Teknik Kompilasi

2.12

Dr. Nidjo Sandjojo, M.Sc

6

INPUT BUFFERING Tiga pendekatan umum untuk mengimplementasikan suatu Penganalysis Leksikal (Lexical Analyzer). 1 Gunakan pembentuk lexical 1. lexical-analyzer analyzer seperti kompilator Lex untuk menghasilkan penganalisis leksikal dari satu spesifikasi berdasarkan ekspresi reguler. 2. Menulis lexical analyzer dengan satu sistem bahasa pemrograman konvensional, menggunakan fasilitas I/O untuk membaca input. y dengan g bahasa assembly y dan secara 3. Menulis lexical analyzer ekplisit mengatur pembacaan input.

Teknik Kompilasi

2.13

Dr. Nidjo Sandjojo, M.Sc

INPUT BUFFERING (Cont’d) BUFFER PAIRS

Satu buffer dibagi menjadi dua bagian Jumlah karakter tiap bagian = 1024 (210) atau 4096 (4 X 210) yang merupakan N N karakter tersebut dibaca sekaligus untuk ditempatkan di tiap setengah buffer-nya Teknik Kompilasi

2.14

Dr. Nidjo Sandjojo, M.Sc

7

INPUT BUFFERING (Cont’d) SENTINEL The sentinel is a special character that cannot be part of the source program, and a natural choice is eof.

Teknik Kompilasi

2.15

Dr. Nidjo Sandjojo, M.Sc

SPESIFIKASI TOKEN STRINGS & LANGUAGE: String adalah satu rangkaian simbol dari alphabet (finite sequence of symbols). Kalimat dan kata sering disebut string Panjang string: S

|S|;

Contoh: banana: |S|=6, String kosong = ∈, sehingga |S|=0,

Language adalah setiap set dari string pada suatu alphabet yang tetap (set of strings)

Teknik Kompilasi

2.16

Dr. Nidjo Sandjojo, M.Sc

8

OPERASI PADA BAHASA Terdapat beberapa operasi penting yang dapat diterapkan pada bahasa (languages). Khusus untuk lexical analysis: union, concatenation (rangkaian), closure (pengakhiran/penutupan), exponentiation operator. Misal; L sebagai himpunan {A,B, …Z,a,b,…z} dan D sebagai himpunan {0,1,2,…9} 1. 2. 3. 4. 5.

L∪D = himpunan huruf dan angka. LD = himpunan string terdiri dari satu huruf diikuti oleh satu angka. L4 = himpunan string 4 huruf. L* = himpunan string huruf-huruf termasuk string ∈. L(L∪D)* = himpunan semua string huruf dan angka yang dimulai dengan huruf. 6. D+ = himpunan semua string angka (satu atau lebih). Teknik Kompilasi

2.17

Dr. Nidjo Sandjojo, M.Sc

OPERASI PADA BAHASA (Cont’d) OPERASI Union (gabungan) L dan M

DEFINISI L ∪ M = {{s | s di L atau t M}

ditulis L ∪ M Sambungan L dan M ditulis LM Penutup Kleene L

LM = {st | s di L dan t di M} ∞

L* = ∪ Li L* = penyambungan nol atau lebih L i=0

ditulis L L* Penutup Positif L ditulis L+

Teknik Kompilasi

∞

L+ = ∪ Li L+ = penyambungan satu atau lebih L i=1

2.18

Dr. Nidjo Sandjojo, M.Sc

9

EKSPRESI BERATURAN Identifier = satu set string dari huruf-huruf dan angka-angka yang dimulai dengan huruf atau satu huruf diikuti 0 atau huruf-huruf atau g ((digit). g ) angka Suatu ekspresi beraturan (regular expression = RE) dibentuk berdasarkan ekspresi beraturan lain yang lebih sederhana. Contoh notasi RE: letter(letter|digit)*. Garis tegak berarti atau, tanda kurung digunakan untuk mengelompokkan ekspresi bagian, dan tanda * artinya adalah nol atau lebih kali dari ekspresi yang diberi kurung kurung. Satu bahasa yang ditunjukkan oleh satu ekspresi beraturan disebut REGULAR SET.

Teknik Kompilasi

2.19

Dr. Nidjo Sandjojo, M.Sc

EKSPRESI BERATURAN (Cont’d) Regular definitions adalah satu urutan dari bentuk : d1 d2 ... dn

r1 r2 rn

d = nama r = regular expression

Teknik Kompilasi

2.20

Dr. Nidjo Sandjojo, M.Sc

10

EKSPRESI BERATURAN (Cont’d) Non-Regular Sets (himpunan tidak beraturan). Ada bahasa yang tidak dapat dijelaskan dengan regular expression. Ekspresi beraturan tidak dapat digunakan untuk menyatakan bentuk yang seimbang atau terulang. Misalnya himpunan dari semua rangkaian tanda kurung yang seimbang tidak dapat dinyatakan oleh suatu ekspresi beraturan, tetapi dapat dinyatakan dalam suatu tata bahasa bebas konteks (Context Free Grammar (CFG)). Rangkaian g yang y g berulangg tidak dapat p dinyatakan y oleh ekspresi p beraturan. Contoh: {wcw|w adalah rangkaian dari a dan b} tidak dapat dinyatakan sebagai suatu ekspresi beraturan, dan juga tidak dapat dinyatakan dengan tata bahasa bebas konteks. Teknik Kompilasi

2.21

Dr. Nidjo Sandjojo, M.Sc

EKSPRESI BERATURAN (Cont’d) CONTOH: Misal: ∑ = {a,b} RE: a|b; yaitu himpunan {a,b} RE: (a|b) (a|b); yaitu himpunan {aa,ab,ba,bb} atau untuk RE: aa|ab|ba|bb RE: a*; yaitu himpunan string ε atau beberapa a, yaitu himpunan {ε, a, aa, aaa, …} RE: (a|b)*; yaitu himpunan semua string yang terdiri dari ε atau a atau b. Sama dengan RE: (a*b*)* RE: a|a*b; yaitu himpunan a atau {ε, a, aa, aaa, …} diikuti oleh b. a*

Teknik Kompilasi

2.22

Dr. Nidjo Sandjojo, M.Sc

11

PENGENALAN TOKEN Misal: penggalan tata bahasa sebagai berikut: stmt | | exp | term |

Teknik Kompilasi

if exp then stmt if exp then stmt else stmt ∈ term relop term term id num

2.23

Dr. Nidjo Sandjojo, M.Sc

PENGENALAN TOKEN (Cont’d) Terminal-terminal tersebut diatas yaitu: if, then, else, relop, id dan num membentuk himpunan rangkaian (string) yang diberikan oleh definisi beraturan sebagai g berikut: if then else relop id num

if then else < | <= | = | <> | > | >= letter(letter|digit)* digit+(.digit ( digit+)?(E(+|-)?digit+)?

Lexical analyzer akan mengenali keywords if, then, else serta lexeme yang dinyatakan oleh relop, id dan num. Keywords adalah kata-kata reserved yang tidak dapat digunakan sebagai identifier (id). Teknik Kompilasi

2.24

Dr. Nidjo Sandjojo, M.Sc

12

MENGHILANGKAN WHITE SPACE Lexical analyzer akan menghilangkan white space (i.e., blanks, tabs, new lines) dengan menggunakan regular definition sebagai berikut: delim ws

blank|newline|tab delim

Sehingga apabila menemukan pola yang cocok dengan ws, maka lexical analyzer tidak akan memberikan token kepada parser tetapi akan melanjutkan mencari character lain setelah white space tersebut.

Teknik Kompilasi

2.25

Dr. Nidjo Sandjojo, M.Sc

TRANSITION DIAGRAM (TD) Sebagai langkah antara di dalam membentuk lexical analyzer, dibuatlah satu transition diagram. TD atau diagram peralihan adalah stylized flowchart (bagan alir) yang dibentuk sebagai langkah antara dalam pembentukan token pada lexical analyzer. TD tersebut menggambarkan aksi yang dilakukan bila Lexical Analyzer dipanggil oleh pengurai utk memperoleh token berikutnya y (g (get next token). )

Teknik Kompilasi

2.26

Dr. Nidjo Sandjojo, M.Sc

13

TRANSITION DIAGRAM (Cont’d)

Catatan:

:

state : edge (sisi) : accepting state : pointer tanda dapat mundur Teknik Kompilasi

* 2.27

Dr. Nidjo Sandjojo, M.Sc

TRANSITION DIAGRAM (TD) Contoh: TD utk pattern > atau >= Pembacaan dimulai dari state 0, membaca karakter berikutnya yaitu > utk menuju ke state 6. 6 Bila yg dibaca benar > maka lanjut, bila bukan maka akan gagal mengenali pattern > atau >=. Dari state 6 karakter yg akan dibaca adalah = utk menuju ke state 7. Bila yg dibaca benar = maka berhasil mengenali pola >= bila bukan = maka akan menuju ke state 8.

Teknik Kompilasi

2.28

Dr. Nidjo Sandjojo, M.Sc

14

A LANGUAGE for SPECIFYING LEXICAL ANALYZERS (1)

Ada piranti (tool) khusus yang lazim digunakan utk menentukan lexical analyzers yaitu Lex Compiler dengan inputnya Lex Language. Penggunaannya sebagai berikut: Lihat Fig. 3.17 a.out adalah object program yg merupakan lexical analyzer yang dapat merobah rangkaian input menjadi token

Lex specifications. p f Program g lex terdiri dari 3 bagian g : 1. Deklarasi (Declarations) 2. Aturan Translasi (Translation Rules) 3. Prosedur Tambahan (Auxiliary Procedures)

Teknik Kompilasi

2.29

Dr. Nidjo Sandjojo, M.Sc

A LANGUAGE for SPECIFYING LEXICAL ANALYZERS (2)

Teknik Kompilasi

2.30

Dr. Nidjo Sandjojo, M.Sc

15

A LANGUAGE for SPECIFYING LEXICAL ANALYZERS (3) %{ /* definitions of manifest constants LT, LE, EQ, NE, GT, GE, IF, THEN, ELSE, ID, NUMBER, RELOP */ %}

/* regular definitions */ delim

[ \t\n]

ws

{delim}+

letter [A [A-Za-z] Za z] digit

[0-9]

id

{letter}({letter}|{digit})*

number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)? %%

Teknik Kompilasi

2.31

Dr. Nidjo Sandjojo, M.Sc

A LANGUAGE for SPECIFYING LEXICAL ANALYZERS (4) {ws}

{/* no action and no return */}

if

{return(IF);}

then

{return(THEN);}

else

{return(ELSE);}

{id}

{yylval = install_id(); return(ID);}

{number} {yylval = instalI_num(); return(NUMBER);} "<"

{yylval = LT; return(RELOP);}

"<="

{yylval = LE; return(RELOP);}

"="

{yylval = EQ; return(RELOP);}

"<>" <>

{yylval = NE; return(RELOP);}

">"

{yylval = GT; return(RELOP);}

">="

{yylval = GE; return(RELOP);}

%%

Teknik Kompilasi

2.32

Dr. Nidjo Sandjojo, M.Sc

16

A LANGUAGE for SPECIFYING LEXICAL ANALYZERS (5) install_id() { /* procedure to install the lexeme, whose first character is p pointed to by y yy yytext and whose length is yyleng, into the symbol table and return a pointer thereto */ } install_num() { /* similar procedure to install a lexeme that is a number */ }

Fig. 3.18. Lex program for the tokens of Fig. 3.10.

Teknik Kompilasi

2.33

Dr. Nidjo Sandjojo, M.Sc

A LANGUAGE for SPECIFYING LEXICAL ANALYZERS (6)

Teknik Kompilasi

2.34

Dr. Nidjo Sandjojo, M.Sc

17

FINITE AUTOMATA (1) Recognizer suatu bahasa; program yang mengambil string x sebagai input dan menjawab “yes” bila x adalah kalimat dari bahasa tersebut, tersebut dan menjawab “no” no bila sebaliknya sebaliknya. Regular expression di compile menjadi recognizer dengan membentuk diagram peralihan disebut finite automata (otomata berhingga). Finite Automata; dua macam : 1. DETERMINISTIC Finite Automata (DFA) 2. Non-DETERMINISTIC Finite Automata (NFA)

Teknik Kompilasi

2.35

Dr. Nidjo Sandjojo, M.Sc

FINITE AUTOMATA (2) Persamaan DFA & NFA Dapat mengenali pola ekspresi beraturan dengan tepat.

Perbedaan DFA NFA Menghasilkan pengenal lebih Menghasilkan pengenal lebih cepat. lambat. Ukuran DFA lebih besar untuk hal yg sama.

Teknik Kompilasi

Ukuran NFA lebih kecil untuk hal yang sama.

2.36

Dr. Nidjo Sandjojo, M.Sc

18

NON-DETERMINISTIC FINITE AUTOMATA (NFA) NFA= model matematika yg terdiri dari: 1. Satu set state S. 2 Satu 2. S t sett symbol b l input i t Σ (alphabet ( l h b t simbol i b l input). i t) 3. Fungsi transisi move yang memetakan pasangan state-simbol ke dalam himpunan state. 4. Satu state S0 yg dinyatakan sebagai state awal (start/initial state). 5. Satu set state F yg dinyatakan sebagai state penerima/ akhir ( (accepting/final ti /fi l state). t t )

NFA dapat direpresentasikan dalam bentuk bagan sebagai suatu grafik yang berlabel disebut Transition Graph, dengan node sebagai state dan sisi berlabel menyatakan fungsi transisi. Teknik Kompilasi

2.37

Dr. Nidjo Sandjojo, M.Sc

NON-DETERMINISTIC FINITE AUTOMATA (Cont’d) Transition graph untuk mengenali bahasa (a|b)*abb

Catatan: set state = {0,1,2,3} set simbol input = {a,b} Teknik Kompilasi

state awal = state 0 state penerima = state 3 2.38

Dr. Nidjo Sandjojo, M.Sc

19

NON-DETERMINISTIC FINITE AUTOMATA (Cont’d) NFA Memungkinkan terjadi lebih dari satu transisi (simbol) yang keluar dari satu state untuk input yang sama Dapat dijelaskan dengan Graph Representation yang implementasinya dengan menggunakan Tabel Peralihan (Transition table). Row = State Column = input symbol (boleh ∈)

Contoh: Fig 3.19 Fig 3.20

Teknik Kompilasi

2.39

Dr. Nidjo Sandjojo, M.Sc

NON-DETERMINISTIC FINITE AUTOMATA (Cont’d)

Teknik Kompilasi

2.40

Dr. Nidjo Sandjojo, M.Sc

20

NON-DETERMINISTIC FINITE AUTOMATA (Cont’d)

Teknik Kompilasi

2.41

Dr. Nidjo Sandjojo, M.Sc

NON-DETERMINISTIC FINITE AUTOMATA (Cont’d)

Transition table for the finite automaton aa*|bb* NFA: aa*|bb*

State

Teknik Kompilasi

Input Symbols ∈

a

b

0

{1,3}

-

-

1

-

{2}

-

2

-

{2}

-

3

-

-

{4}

4

-

-

{4}

2.42

Dr. Nidjo Sandjojo, M.Sc

21

DETERMINISTIC FINITE AUTOMATA (DFA) DFA adalah kasus khusus NFA yang : 1. Tidak ada state dengan transisi ε; yaitu transisi input ε & 2. Untuk setiap state s dan simbol input a hanya ada paling banyak satu sisi berlabel a yang meninggalkan state s.

Bila menggunakan transition table untuk merepresentasikan fungsi transisi DFA, setiap entry pada transition table adalah “single input”. DFA untuk mengenali bahasa (a|b)*abb, yang inputnya (string) dibaca ababb mengikuti urutan state 0,1,2,1,2,3 sbb: Fig 3.23

Teknik Kompilasi

2.43

Dr. Nidjo Sandjojo, M.Sc

DETERMINISTIC FINITE AUTOMATA (Cont’d)

Teknik Kompilasi

2.44

Dr. Nidjo Sandjojo, M.Sc

22