LATIHAN 2.1 Gambarkan aturan lexical analisis di dalam desain kompilasi.Source Program Lexical Analyzer TokenPermintaan untuk token

Parser

Tabel Sim bol

2.2 Apakah mungkin untuk mendesain suatu compiler tanpa fase lexical analisis yang berbeda? Tidak, Karena tugas utama yang terpenuhi yang oleh tahap ini akan mengidentifikasi satu rangkaian dari suatu bahasa yang terjadi pada masukan. Bab ini merinci perkakas dan konsep [yang] dilibatkan sedang dalam proses analisa berhubungan dengan kamus. Bagaimanapun, perancangan manapun perkakas untuk mengidentifikasi kata-kata dari suatu bahasa.;Sejak] kita kebanyakan terkait dengan bahasa program, kita dapat mengamati yang mungkin satuan kata-kata dalam yang sedemikian suatu bahasa adalah finite_they menghadirkan yang manapun kata kunci dari bahasa, suatu lambang [seperti;suka] nama varible, label, subprogram, dan lain lain number-integers, real,etc. beberapa perhitungan dan operator logis dan seterusnya. Untuk mendisain suatu recognizer untuk words,the ini satuan kata-kata mungkin diwakili oleh suatu notasi mengenal sebagai Regular Expression. 2.3 Apakah itu regular expression? Beri definisinya secara rinci. Pola yang sesuai untuk sebuah token biasanya ditentukan menggunakan notasi ringkas yang dikenal sebagai regular expression. Regular expression dari sebuah bahasa diciptakan dengan mengkombinasikan alfabetnya. Sebagai contoh, untuk sebuah bahasa L dengan kumpulan alfabet , aturan berikut menjelaskan tentang ekspresi reguler:1.

merupakan ekspresi regular yang merupakan bahasa { }, dimana kumpulan tersebut hanya terdiri dari string kosong.

2. Jika a menjadi simbol dalam , maka a juga merupakan sebuah ekspresi regular yang sesuai dengan bahasa { a} , dimana kumpulan tersebut hanya terdiri dari string a. 3. Jika r1 dan r2 menjadi dua ekspresi reguler yang sesuai dengan bahasa L1 dan L2 berturut-turut, maka(a) r1|r2 adalah ekspresi reguler yang sesuai dengan bahasa L1 U L2,

kumpulan tersebut mencakup semua string pada L1 dan L2. (b) r1r2 adalah regular expression yang sesuai dengan bahasa yang dibentuk dengan perangkaian string L2 sampai string L1. (c) r1* adalah reguler expression yang sesuai dengan bahasa L1*, dimana kumpulan tersebut terdiri dari nol atau lebih bentukan string milik L1. Sebagai catatan,L1* juga mencakup string kosong, walaupun L1 tidak mencakup string kosong tersebut. (d) (r1) adalah regular expression yang sesuai dengan bahasa L1 itu sendiri.

2.4 Bedakan antara NFA dan DFA. Bandingkan kekuatannya sebagai pengenal token! Non-deterministic Finite Automata (NFA) mempunyai ciri-ciri utama adalah dapat memiliki transisi lebih dari satu kemungkinan dari suatu keadaaan (state) dengan simbol masukan yang sama. Sebagai contoh, dari state si ada kemungkinan transisi ke dua keadaan berbeda yaitu sj dan sk yang ditandai dengan simbol masukan yang sama am. Transisi yang terjadi sebenarnya dipilih secara tidak menentu oleh mesin. Ketidaktentuan lainnya ada pada transisi yang ditandai dengan e, dikenal dengan e-transisi. masukan apa pun. Sedangkan pada Deterministic Finite Automata (DFA), transisi bersifat pasti (tentu) pada suatu DFA. Maka, tidak bisa ada lebih dari satu Jika terdapat suatu e-transisi dari kedaan si ke keadaan sj, maka mesin dapat melakukan transisi tanpa menggunakan

transisi yang berasal dari keadaan sama yang ditandai dengan simbol masukan yang sama. Kedua, tidak boleh ada e-transisi. Adanya ketidakpastian yang dibuat oleh NFA menjadikannya tidak lebih kuat dibanding DFA. Bagaia manapun, hal itu juga menyangkut ukuran (banyaknya keadaan) dari mesin ini. Seperti yang perlu diketahui, kehadiran suatu ketidakpastian memerlukan suatu perbaikan yang baik dengan digantikan DFA dalam kaitan beberapa keadaan. Setiap suatu alur ketidakpastian dari suatu NFA mendapat pengubahan ke dalam alur jelas dari keadaan awal sampai keadaan akhir di dalam hubungan DFA. Sering kali hal ini menimbulkan ledakan jumlah keadaan (state) pada DFA. 2.5 Tuliskan regular expression dari a. pengidentifikasi bahasa C. b. string biner seperti 0 yang selalu diikuti oleh 1 0(0|1)*0 c. untuk memeriksa alamat IP untuk syntax yang benar, untuk 4 grup dari digit 1-3set str 66.70.7.154 regexp "(\[0-9]{1,3})\.(\[0-9]{1,3})\.(\[0-9]{1,3})\.(\[0-9]{1,3})" $str all first second third fourth puts "$all \n $first \n $second \n $third \n $fourth \n"

d. untuk memeriksa syntax yang benar untuk alamat email.{^[A-Za-z0-9._-]+@[[A-Za-z0-9.-]+$} ;# RS

e. kalimat (yang berawalan dengan huruf kapital dan berakhir penuh)[A-Z].*?[.!?] ( (?=\s[A-Z]) | $ )

f. bilangan desimal kelipatan 5r"[+-]?((\d+(\.\d*)?)|\.\d+)([eE][+-]?[0-9]+)?"

g. string yang panjangnya kelipatan 5var string3="1,2, 3, 4, 5" parsestring3=string3.split(/\s*,\s*/) //Returns the array ["1","2","3","4","5"]

2.6 Apakah maksud regular expression berikut : a. a(ab)*a = berarti string masukan terdiri dari 3 karakter b. [0-7][0-7]* = string masukan meliputi bilangan 0-7 c. (0|1)*0(0|1)(0|1)(0|1) = berarti string biner terdiri dari 3 karakter, dimana empat karakter terakhir pasti bernilai 0 d. (a|b)*abb = berarti string masukan terdiri dari 4 karakter dengan dua karakter terakhir pasti b e. (a|b)*a(a|b)(a|b)(a|b) = berarti string terdiri dari 3 karakter, dimana empat karakter terakhir pasti bernilai a 2.7 Bentuklah NFA untuk regular expression untuk soal 2.6. a. a(ab)*a a,b

0

a

1

b

2

b. [0-7][0-7]*[0-7]

0

1

[0-7]

2

c. (0|1)*0(0|1)(0|1)(0|1)00,1

1

0

2

0,1

3

0,1

4 4

0,1

5

d. (a|b)*abb0a,b

1

a

2

b

3

b

4

e. (a|b)*a(a|b)(a|b)(a|b)0a,b

1

a

2

a,b

3

a,b

4 4

a,b

5

2.8 Ubahlah NFA yang dibentuk soal 2.6 ke DFAb a a

0a. c.

1

b

2

1

0

0,1

1

0

2

0,1

3

0,1

4 4

0,1

5

d.

b

a a

a b

0

a,b

1

2

3

b

4

e.

b a,b a a,b a,b

0

1

2

3

4 4

a,b

5

2.9

C++ mempunyai bervariasi konstanta integer. Dinamakan untuk nilai integer. Sebuah

sekuensial sederhana dari digit desimasl selalu merupakan konstanta integer. Sebuah digit hexadesimal sekuensial yang dinyatakan dengan 0x merupakan sebuah konstanta integer. Sebuah digit oktal sekuensial yang dinyatakan dengan 0 merupakan konstanta integer. Sebuah konstanta integer bisa diikuti oleh L atau l untuk mengindikasikan bahwa variabel tersebut adalah long int. Tulis sebuah regular expression untuk konstanta integer C++ sebagaimana di deskripsikan disini. Susun NFA dan DFA terkait.

2.10 Tulis file spesifikasi LEX untuk mengenali token bahasa C. declarations %% rules %% auxiliary routines

2.11 Tulis sebuah program Lex yang menerima kata-kata dalam bahasa Inggris (tanpa menggganggu maknanya) dan mengganti masing-masing string abc ke ABC.enum {ARTICLE, VERB, NOUN, ADJECTIVE, ADVERB, PUNCTUATION, PREPOSITION, END}; %% return END; " " "\t" | ;

the an? go(es)? runs? likes? eats? dogs? cats? fish fox(es)? moose quick slow lazy clever smart stupid brown black blue red orange white big small quickly easily openly slowly "." , "?" ; : ! @ # "$" "%" "^" & "*" "(" ")" over under around through between %%

| return ARTICLE; | | | return VERB; | | | | return NOUN; | | | | | | | | | | | return ADJECTIVE; | | | return ADVERB; | | | | | | | | | | | | | | return PUNCTUATION; | | | | return PREPOSITION;

| |

int main(void) { int result; int running = 1; while (running) { result = yylex(); switch (result) { case ARTICLE: printf("Article "); break; case VERB: printf("Verb "); break; case NOUN: printf("Noun "); break; case ADJECTIVE: printf("Adjective "); break; case ADVERB: printf("Adverb "); break; case PUNCTUATION: printf("Punctuation "); break; case PREPOSITION: printf("Preposition "); break; case END: running=0; break; default: printf ("Huh?"); } } return 0; }

2.12 Jelaskan mengapa tidak mungkin mendesain sebuah lexical analysis tool yang bisa mendeteksi string yang memiliki jumlah karakter yang sama, misalkan a dan b.