LEXICAL ANALYSIS



LEXICAL ANALYSIS

PERANAN LEXICAL ANALYZER (Scanner)

( Membaca source program (input stream), mengenali, mengidentifikasi lexeme (word) kemudian meng-hasilkan rangkaian token sebagai output.

token

source Scanner parser

program

get next

token

Symbol

Table

Scanner biasanya diimplementasikan dalam bentuk subroutine dari program Parser

TUGAS LAIN LEXICAL ANALYZER

1. Membuang comment dan white space (blank, tab , dan newline character).

2. Menghasilkan error messages.

BEBERAPA ISU DALAM LEXICAL ANALYSIS

Alasan mengapa Lexical Analysis dipisahkan dari Syntax Analysis :

1. Desain kompiler menjadi lebih sederhana

2. Efisiensi kompiler meningkat

3. Portabilitas kompiler meningkat

TOKEN, PATTERN DAN LEXEME

Token (simbol atomic) :

Bagian terkecil yang dikenal oleh scanner. Token dapat berupa bilang-an atau konstanta string (x=makan, y=minum),literal(’a’,”lampet”), operator (+,-,*,/,%, sqr, sqrt, exp, sin, cos,tan),exclamation(! ?), functuation (; , . : ), keywords (begin, end, write, read, var, cin, cout, if, while, for, {, }), karakter ganda (:=,,+=,=+,--,++,!=,==,**,), identifier (proc, var, name, const, type)

Lexeme :

Rangkaian karakter (word) yang sama (“matched”) dengan pola (“pattern”) suatu token

Pattern :

Suatu pola/ rules/ aturan yang menggambarkan struktur suatu token

Contoh : const pi = 3.14;

Token Contoh Lexeme Contoh Pattern

const_sym const, define const pi:=3.14,

#define pi 3.14

if_sym if if (expr) then [else]

Loop_sym for, while..do, for var :=init to fnl do

Repeat .. until init :=num

Do… while(expr) while(expr) do stmt

relation = < or or >=

id pi, count, d2 Letter diikuti oleh letters atau digits

num 3.14, 0, 6.0E10 Sembarang konstanta angka

literal “Hallo” Sembarang karakter “diantara“

dan “kecuali “

Pada bahasa-bahasa tertentu Lexical Analysis menjadi lebih sulit, contoh populer : Statement DO pada bahasa pemrograman FORTRAN :

DO 5 I = 1.25 ( Do bagian dari

DO 5 I

DO 5 I = 1,25 ( Do = Keyword

ATRIBUT-ATRIBUT TOKEN

Informasi tentang token (biasanya single atribut)

Dibutuhkan pointer untuk load/ store dalam simbol table entry

Lexeme sebuah identifier dan line number akan tersimpan dalam simbol table entry

dituliskan :

Contoh : E := M * C ** 2

Token-token yang akan dihasilkan :

< id, pointer to symbol table untuk E >

< assign_op, := >

< id, pointer to symbol table untuk M >

< mult_op, * >

< id, pointer to symbol table untuk C >

< exp_op, ** >

< num, integer value 2 >

INPUT BUFFERING

Fungsi : menyimpan hasil scanning untuk menemukan token.

Untuk menemukan 2 token digunakan 2 pointer :

( Pointer forward :

menunjuk akhir token

( Pointer lexeme_beginning :

menunjuk awal token

E = M * C * * 2 eof

Forward chaining

lexeme-ending

lexeme-beginning

backward chaining

Buffer hanya menampung satu baris perintah, dan berhubungan dengan simbol table.

STRATEGI ERROR-RECOVERY

1. Menghapus suatu karakter yang tidak sesuai hingga ditemukan suatu token yang sesuai

2. Menyisipkan sebuah karakter yang hilang.

3. Mengganti suatu karakter yang salah dengan karakter yang benar.

4. Menukarkan dua karakter yang berdampingan.

SYMBOL TABLE

( Symbol table adalah suatu struktur data yang digunakan untuk menyim-pan informasi tentang komponen (token) suatu source program.

( Informasi yang dimaksud :

- Lexeme (word)

- Bentuk identifier

- Type identifier (procedure, variable, label)

- Posisi penyimpanan

( Interaksi dengan simbol table

SYMBOL TABLE INTERFACE

Rutin untuk operasi Save dan Retieve terhadapa Lexeme adalah :

insert (s,t): menghasilkan indeks entry baru untuk string s, token t

lookup (s) : menghasilkan indeks entry baru untuk string s, atau 0 bila s tak ditemukan.

RESERVED KEYWORDS HANDLING

Reserved keywords disimpan dalam symbol-table saat inisialisasi proses kompiler.

contoh rutin yang menangani reserved keywords :

insert (“div”, div_sym)

insert (“mod”, mod_sym)

Sehingga bila dilakukan

lookup(“div”)

( menghasilkan token div_sym

( div tidak bisa digunakan sebagai identifier

IMPLEMENTASI SYMBOL TABLE

Symbol table harus memungkinkan penambahan / pencarian yang efisien

Bisa diimplementasikan dengan : Array, List

SPESIFIKASI TOKEN

STRING DAN LANGUAGES

Alphabet class adalah suatu himpunan terbatas dari simbol-simbol.

String adalah rangkaian simbol-simbol dari alpabetik

Panjang string S ditulis dengan |S| adalah banyaknya simbol dalam string s misalnya : S=abc maka |S| = 3

Empty string ditulis dengan ( dengan panjang string nol (0)

Empty set ditulis dengan Ø atau {(}

Concatenation adalah menggabung 2 buah atau lebih string.

Contoh : x=dog dan y=house maka concatenation x dan y adalah doghouse

Himpunan {0,1} adalah binary alphabet

ISTILAH-ISTILAH PENTING STRING

Contoh : Bila s = abc, maka

prefix s : ε, a, ab, abc

proper prefix s : a, ab

suffix s : abc, bc, c, ε

proper suffix s : bc, c

substring s : prefix s ( suffix s ( b

: ε, a, ab, abc, bc, c, b

proper substring s : substring s – abc - ε

subsequence s : substring s ( ac

EKSPONENSIASI STRING

s0 = ε

s1 = s untuk i > 0, maka

s2 = ss si = si-1s

s3 = sss

sehingga : Ln = Ln-1 L dan L0 = {(}

BEBERAPA OPERASI TERHADAP BAHASA

• Union (()

• Concatenation (.)

• Closure :

- Kleene Closure (*)

Kleene closure dari L adalah L*

L* = ( Li

i=0

- Positive Closure (+)

Positive closure dari L adalah L+

L+ = ( Li

i=1

REGULAR EXPRESSION (RE)

Digunakan untuk mendefenisikan set dan token-token dari suatu bahasa.

Misalnya :

Token identifier ditulis dengan :

letter ⇒letter (letter | digit)*

dimana :

letter ={a,b,..,z, A,B,C,...,Z}

digit ={0,1,2,...,9}

| berarti “atau”

( ) berarti subexpression

* berarti “nol atau lebih”

SIFAT-SIFAT R.E.

□ r|s = s|r

□ r|(s|t) = (r|s)|t

□ (rs)t = r(st)

□ r(s|t) = rs|rt

□ (r = r ( = r

□ r* = (r|()*

□ r** = r *

□ r* = r +|(

□ r+ = r r *

Contoh : alphabet ( = {a, b}

1. RE ab menyatakan himpunan {a,b}

2. RE (a|b)(a|b) menyatakan {aa,ab,ba,bb}

3. RE a* menyatakan {ε,a,aa,aaa,...}

4. RE a+ menyatakan {a,aa,aaa,...}

5. RE (a|b)* menyatakan himpunan

string yang terdiri dari nol atau

beberapa a atau beberapa b.

6. RE a|(a*b) menyatakan himpunan string yang terdiri dari a atau beberapa a, diikuti oleh sebuah b.

REGULAR DEFINITION (RD)

RD adalah suatu sekuensi/ rangkaian definisi dalam bentuk :

d1 ( r1 dimana : di nama unik ri

d2 ( r2 r1 yaitu RE yang terdiri dari

........... simbol-simbol dalam ((

........... {d1,d2,...dI-1}

dn ( rn

Contoh :

1. regular definition untuk identifier :

letter ( A|B|...|Z|a|b|...|z

digit ( 0|1|...|9

id ( letter(leter|digit)*

2. RD untuk unsigned numbers:

digit ( 0|1|…|9

digits ( digit digit*

optional_fraction (.digits|ε

optional_exponent( (E(+|-|ε)digits)|ε

num ( digits optional_fraction

optional_exponent

-----------------------

~

~

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download