KW506 Desain Kompiler HO-4 Lexer dan Lexer Generator

Opim S Sitompul

Topik

Lexer

Lexer Generator

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Lexer adalah program yang melaksanakan lexical analysis, yakni: Lexer harus membedakan antara beberapa

jenis token yang berbeda, mis. bilangan, variabel dan keywords. Masing-masing dijabarkan dengan RE.

Lexer tidak memeriksa apakah seluruh inputnya disertakan dalam bahasa yang didefinisikan oleh RE. Melainkan, harus memotong input tersebut menjadi bagian-bagian (tokens), masing-masingnya disertakan ke dalam salah satu bahasa.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Apabila terdapat beberapa cara untuk memisahkan input menjadi token yang sah, lexer harus memutuskan yang mana diantaranya yang digunakan.

Program yang menerima satu himpunan definisi token (masing-masing terdiri dari RE dan sebuah nama token) dan menghasilkan sebuah lexer disebut lexer generator.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Pendekatan paling sederhana adalah dengan menghasilkan sebuah DFA untuk setiap definisi token dan menerapkan DFA tersebut satu persatu pada input.

Akan tetapi hal ini sangat lambat, sehingga yang dilakukan adalah dari himpunan definisi token itu dibuatlah sebuah DFA tunggal yang menguji semua token secara simultan.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Jika token-token tersebut didefinisikan oleh RE r1, r2, . . . , rn, maka RE r1 | r2 | . . . | rn menjabarkan gabungan (union) dari bahasa r1, r2, . . . , rn dan DFA yang dibangun dari kombinasi RE ini akan men-scan semua jenis token pada saat yang sama.

Akan tetapi, perlu dibedakan antara jenis-jenis token yang berbeda itu, sehingga harus diketahui yang mana di antara token-token yang banyak itu yang dikenal oleh DFA. KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Hal ini dapat diselesaikan dengan konstruksi kombinasi DFA berikut: 1) Bangun NFA N1,N2, . . . , Nn untuk tiap-tiap r1, r2, . . . , rn. 2) Beri tanda accepting states dari NFA-NFA itu dengan

nama token yang mereka terima. 3) Gabungkan NFA-NFA tersebut menjadi sebuah NFA

tunggal dengan menambahkan sebuah starting state baru yang memiliki epsilon-transition ke setiap starting state dari NFA.

4) Konversi gabungan NFA menjadi sebuah DFA. 5) Setiap accepting state dari DFA terdiri dari satu

himpunan state NFA , paling sedikit satu diantaranya adalah accepting state yang diberi tanda oleh jenis token pada langkah 2. Tanda-tanda ini digunakan untuk menandai accepting states dari DFA, sehingga masing-masingnya akan menunjukkan semua jenis token yang diterimanya.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Apabila accepting state yang sama dalam DFA dapat menerima beberapa jenis token yang berbeda, hal ini dikarenakan adanya overlap.

Keywords biasanya overlap dengan nama variabel

Konstanta floating point dapat terbentuk dari konstanta integer KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Ada dua tindakan yang dapat dilakukan: Lexer generator menghasilkan error dan

meminta user memastikan token-token itu adalah disjoin.

User lexer generator memilih token mana yang diinginkan

Biasanya sangat sulit bagi RE mendefinisikan kumpulan nama yang bukan keyword.

Karenanya Lexer-lah yang memilih berdasarkan sebuah prioriti list.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Biasanya urutan token yang didefinisikan pada input ke lexer generator menunjukkan prioritas. (token yang terlebih dahulu didefinisikan mendahului token yang didefinisikan kemudian). Keywords biasanya didefinisikan

sebelum nama variabel, mis. string if dikenal sebagai keyword dan bukan nama variabel.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Apabila sebuah accepting state dalam satu DFA memuat beberapa accepting states NFA dengan tanda berbeda, tanda yang bersesuaian dengan token prioritas tertinggi (definisi terdahulu) yang digunakan.

Karena itu, penyelesaian paling sederhana dan efektif pada permasalahan itu adalah menghapus semuanya kecuali satu tanda yang berasal tiap accepting state.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Ketika menjabarkan tentang minimisasi DFA, digunakan dua kelompok awal: Satu untuk accepting states dan satu untuk non-accepting states.

Karena ada beberapa jenis accepting states (satu untuk tiap token), kita harus menggunakan satu kelompok untuk tiap token, sehingga akan ada total n + 1 kelompok awal jika terdapat n token yang berbeda.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Untuk mengilustrasikan aturan presedensi, berikut adalah NFA yang menggabungkan beberapa NFA untuk nama variabel, keyword if, integer dan float. Keyword. Keyword seperti if dijabarkan oleh

RE yang sama seperti keyword itu, mis., RE if (yang merupakan penyambungan dua RE i dan f).

Nama variabel. Dalam bahasa pemrograman C, nama variabel terdiri dari huruf, digit dan garis awah dan harus dimulai dengan sebuah huruf atau garis bawah. Dinyatakan dengan RE berikut:

[azAZ_][azAZ_09]*.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Integer. Sebuah konstanta integer adalah satu angka yang didahului tanda (opsional) dan diikuti dengan deretan tidak kososng dari digit: [+-]?[09]+.

oDi sebagian bahasa, tanda adalah simbol terpisah dan bukan bagian dari konstanta itu. Hal ini memungkinkan adanya whitespace diantara tanda dan bilangan, yang tidak mungkin dilakukan dengan definisi di atas. K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Float. Konstanta floating-point secara opsional dapat memiliki tanda. Setelah tanda, bagian mantissa dinyatakan sebagai deretan digit diikuti dengan sebuah titik desimal dan kemudian deretan digit lainnya.

Salah satunya boleh kosong, tetapi tidak boleh kedua-duanya.

Ahkhirnya, terdapat secara opsional bagian eksponen, yang merupakan huruf e (huruf besar atau kecil) diikuti oleh (tandanya opsional) konstanta integer.

Jika terdapat bagian eksponen pada suatu konstanta, bagian mantissa dapat dituliskan sebagai sebuah konstanta integer (yi., tanpa titik desimal).

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Contoh:

3.14 -3. .23 3e+4 11.22e-3

Format tersebut dapat dijabarkan dengan RE berikut:

[+-]?((([09]+. [09]|. [09]+)([eE][+-]?

[09]+)?)|[09]+[eE][+-]?[09]+)

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Deskripsinya menjadi lebih sederhana apabila RE untuk float juga menyertakan integer, dan menggunakan cara lain untuk membedakan integer dari float.

[+-]?(([09]+(. [09])?|. [09]+)([eE][+-]?

[09]+)?)

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Konstanta string constant. Dimulai dengan sebuah tanda kutip diikuti oleh deretan simbol dan akhirnya tanda kutip lain.

"([azAZ09]|\[azAZ])"

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Combined NFA for several tokens

Lexer dan Lexer Generator K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Memisahkan input stream

Lexer harus memotong input menjadi token.

Mis. if17 dapat dipisah dengan beberapa cara:

1) Sebagai sebuah token, berupa nama variabel if17.

2) Sebagai nama variabel if1 diikuti oleh angka 7.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Memisahkan input stream

3) Sebagai keyword if, diikuti oleh angka 17.

4) Sebagai keyword if, diikuti oleh angka 1 dan angka 7.

5) Sebagai nama variabel i diikuti nama variabel f17.

6) Dst KW506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Konvensi yang umum digunakan adalah memilih prefix input terpanjang yang cocok untuk sebuah token, mis. if17.

Prinsip prefix terpanjang yang cocok ditangani dengan membiarkan DFA membaca sejauh mungkin hingga mencapai akhir input atau hingga tidak ada definisi transisi pada simbol input berikutnya.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer dan Lexer Generator

Lexical error

Jika tidak ada prefix input yang membentuk token yang sah, terjadilah lexical error.

Lexer dapat berhenti atau melanjutkan pembacaan hingga diperoleh prefix yang sah dengan melompati karakter-karakter yang ada.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer Generator

Lexer generator biasanya menggunakan notasi RE yang sama. Mis.: * untuk simbol perkalian vs * untuk

simbol perulangan Untuk membedakan digunakan notasi `*`

untuk perulangan.

Input ke lexer generator biasanya akan memuat RE yang masing-masing menyatakan token, disertai oleh satu tindakan yang menjabarkan apa yang diserahkan ke pemakainya (parser).

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer Generator

Biasanya berupa elemen dari jenis data token, yang menjabarkan jenis token itu (mis. NUM, ID, dll).

Atau informasi tambahan misalnya nilai dari token bilangan, nama token identifier, dan mungkin posisi token tersebut dalam file input.

Informasi yang diperlukan untuk membangun nilai tersebut biasanya disediakan oleh lexer generator melalui fungsi pustaka atau variabel.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer Generator

Tindakan yang dapat dilakukan bukan hanya mengembalikan token.

Jika keyword yang dimiliki terlalu besar, tidak digunakan DFA melainkan melalui tabel lookup.

Mengembalikan jenis token yang sesuai

Atau token identifier jika nama itu bukan keyword. K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Lexer Generator

Penggunaan non-trivial lainnya pada lexer adalah untuk mengatasi nested comment yang sangat sulit dijabarkan melalui RE.

Menggunakan sebuah pencacah global untuk mencatat level yang bersarang.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul