Pendahuluan

Dalam ilmu komputer, analisis leksikal adalah proses mengubah urutan karakter ke dalam suatu urutan token. Sebuah program atau fungsi yang melakukan analisis leksikal disebut sebagai analisa leksikal, lexer atau pemindai. lexer A sering ada sebagai fungsi tunggal yang disebut oleh parser atau fungsi lain.

Tata bahasa leksikal

Spesifikasi bahasa pemrograman yang sering akan mencakup seperangkat aturan yang mendefinisikan lexer tersebut. Peraturan-peraturan ini biasa disebut ekspresi reguler dan mereka menentukan urutan karakter set yang digunakan kemungkinan untuk membentuk token atau lexemes. spasi, (yakni karakter yang diabaikan), juga didefinisikan dalam kalimat biasa.

Token

Sebuah token adalah string karakter, dikategorikan menurut aturan sebagai simbol (misalnya identifier, NOMOR, koma, dll). Proses pembentukan token dari input stream karakter disebut (tokenization) dan lexer yang mengkategorikan mereka sesuai dengan jenis simbol. Sebuah token dapat terlihat seperti apa yang berguna untuk memproses input stream teks atau file teks.

Sebuah analisa leksikal biasanya tidak berbuat sesuatu dengan kombinasi bukti, tugas kiri untuk sebuah parser. Sebagai contoh, penganalisis leksikal khas mengakui kurung sebagai bukti, tapi tidak melakukan apapun untuk memastikan bahwa setiap ‘(‘ yang cocok dengan a) ”.

Pertimbangkan ini istilah dalam bahasa pemrograman C: jumlah = 3 2;

Tokenized dalam tabel berikut: lexeme jenis token, jumlah Identifier, = Tugas operator, 3 Jumlah;  Penambahan operator, 2 Jumlah ; Akhir pernyataan.

Token sering ditentukan oleh ekspresi reguler, yang dipahami oleh generator penganalisa leksikal seperti lex. Penganalisa leksikal (baik yang dihasilkan secara otomatis oleh alat seperti lex, atau tangan-crafted) membaca dalam aliran karakter, mengidentifikasi lexemes di sungai, dan mengkategorikan mereka ke dalam token. Hal ini disebut “tokenizing.” Jika lexer menemukan sebuah token yang tidak valid, itu akan melaporkan kesalahan.

tokenizing Berikut ini adalah parsing. Dari sana, data diinterpretasikan boleh diambil ke dalam struktur data untuk penggunaan umum, penafsiran, atau kompilasi.

Scanner

Tahap pertama, pemindai, biasanya didasarkan pada sebuah mesin finite state. Telah dikodekan di dalamnya informasi tentang kemungkinan urutan karakter yang dapat ditampung dalam salah satu token itu menangani (contoh individual dari urutan karakter yang dikenal sebagai lexemes). Sebagai contoh, integer token dapat berisi karakter angka urutan numerik. Dalam banyak kasus, karakter non-spasi pertama dapat digunakan untuk menyimpulkan jenis token yang berikut dan karakter masukan berikutnya kemudian diproses satu per satu sampai mencapai karakter yang tidak di set karakter yang dapat diterima untuk token (ini dikenal sebagai aturan mengunyah maksimal, atau peraturan pertandingan terpanjang). Dalam beberapa bahasa penciptaan lexeme aturan lebih rumit dan bisa melibatkan mundur lebih dari sebelumnya membaca karakter.

Tokenizer

Tokenization adalah proses yang membatasi dan mengelompokkan mungkin bagian dari sebuah string karakter input. Token yang dihasilkan kemudian disampaikan kepada bentuk lain dari pengolahan. Proses ini dapat dianggap sebagai sub-tugas parsing input.

Ambil, misalnya, string berikut. Sesuatu cepat rubah cokelat melompat selama anjing malas. Tidak seperti manusia, komputer tidak dapat secara intuitif ‘melihat’ bahwa ada 9 kata-kata. Untuk komputer ini hanya serangkaian 43 karakter. Suatu proses tokenization dapat digunakan untuk memisahkan kalimat menjadi kata token. Meskipun contoh berikut ini diberikan sebagai XML ada banyak cara untuk mewakili input tokenized:

<sentence>

<word> <The / word>

<word> cepat </> kata

<word> cokelat </> kata

<word> <rubah / word>

<word> melompat </> kata

<word> atas </> Kata

<word> </ word>

<word> malas </> kata

<word> <anjing / word>

</ Kalimat>

Lexeme A, bagaimanapun, adalah hanya sebuah string karakter dikenal dari jenis tertentu (misalnya, sebuah string literal, urutan dari huruf). Dalam rangka membangun sebuah token, penganalisa leksikal kebutuhan tahap kedua, evaluator, yang berjalan selama karakter lexeme untuk menghasilkan nilai. type lexeme, ditambah dengan nilai yang benar merupakan sebuah token yang dapat diberikan kepada sebuah parser. (Beberapa bukti seperti tanda kurung tidak benar-benar memiliki nilai, dan fungsi evaluator untuk ini bisa kembali apa-apa. Para evaluator untuk bilangan bulat, pengidentifikasi, dan string bisa jauh lebih kompleks. Kadang-kadang evaluator dapat menekan lexeme yang sepenuhnya, menutupinya dari parser, yang berguna untuk spasi dan komentar.)

Misalnya, dalam kode sumber dari program komputer string,  net_worth_future = (aset – kewajiban); mungkin akan diubah (dengan spasi dirahasiakan) ke dalam aliran token leksikal: NAMA “net_worth_future” Sama dengan OPEN_PARENTHESIS, NAMA “aset” MINUS,  NAMA “kewajiban” CLOSE_PARENTHESIS, Titik koma

Meskipun adalah mungkin dan kadang-kadang diperlukan untuk menulis lexer dengan tangan, lexers sering dihasilkan oleh alat bantu otomatis. Peralatan ini umumnya menerima ekspresi reguler yang menggambarkan token diperbolehkan dalam input stream. Setiap ekspresi yang teratur berkaitan dengan produksi dalam tata bahasa leksikal dari bahasa pemrograman yang mengevaluasi lexemes yang cocok dengan ekspresi reguler. Alat-alat ini dapat menghasilkan kode sumber yang dapat dikompilasi dan dijalankan atau membangun sebuah tabel negara untuk mesin finite state (yang terhubung ke kode template untuk kompilasi dan eksekusi).

Kalimat biasa kompak merupakan pola bahwa karakter dalam lexemes mungkin mengikuti. Sebagai contoh, untuk bahasa Inggris berbasis, sebuah NAMA token mungkin karakter abjad Inggris atau garis bawah, diikuti oleh jumlah instance dari setiap karakter ASCII alfanumerik atau garis bawah. Hal ini dapat diwakili kompak oleh string [a-zA-Z_] [a-zA-Z_0-9] *. Ini berarti “ada karakter az, AZ atau _, diikuti 0 atau lebih dari az, AZ, _ atau 0-9”.

Kalimat biasa dan mesin finite state mereka hasilkan tidak cukup kuat untuk menangani pola rekursif, seperti “tanda kurung n pembukaan, diikuti dengan pernyataan, diikuti oleh tanda kurung tutup n.” Mereka tidak mampu menjaga menghitung, dan memverifikasi n yang sama di kedua sisi – kecuali jika Anda memiliki seperangkat nilai-nilai terbatas diperbolehkan untuk n. Dibutuhkan parser penuh untuk mengenali pola seperti di umum penuh mereka. parser A dapat mendorong kurung di tumpukan dan kemudian mencoba untuk pop mereka dan melihat apakah stack kosong di akhir. (Lihat contoh di buku SICP)

Alat Lex pemrograman dan compiler yang dirancang untuk menghasilkan kode untuk analisa leksikal cepat berdasarkan deskripsi formal sintaks leksikal. Ini umumnya tidak dianggap cukup untuk aplikasi dengan seperangkat aturan leksikal rumit dan persyaratan kinerja parah, misalnya, GNU Compiler Collection lexers menggunakan tulisan tangan.

Generator Lexer

Analisis leksikal sering dapat dilakukan dalam satu lulus dilakukan jika membaca karakter sekaligus. lexers Single-pass dapat dihasilkan oleh alat seperti flex klasik. Lex ini / keluarga flex generator menggunakan pendekatan tabel-driven yang jauh lebih efisien dibandingkan dengan pendekatan secara langsung kode [meragukan – mendiskusikan]. Dengan pendekatan yang kedua generator menghasilkan mesin yang langsung melompat ke negara tindak lanjut melalui laporan goto. Peralatan seperti re2c dan Quex telah terbukti (misalnya artikel tentang re2c) untuk memproduksi mesin yang antara dua sampai tiga kali lebih cepat daripada mesin dihasilkan flex. [Rujukan?] Hal ini pada umumnya sulit untuk tangan-menulis analisa yang berperforma lebih baik dibandingkan mesin yang dihasilkan oleh alat terakhir ini.

Utilitas sederhana menggunakan generator scanner tidak boleh diabaikan, terutama dalam tahap perkembangan, ketika sebuah spesifikasi bahasa mungkin berubah setiap hari. Kemampuan untuk mengekspresikan leksikal konstruksi sebagai ekspresi reguler memfasilitasi deskripsi penganalisis leksikal. Beberapa alat menawarkan spesifikasi dan pra-kondisi pasca-yang sulit program dengan tangan. Dalam hal ini, dengan menggunakan generator scanner dapat menghemat banyak waktu pembangunan.

Leksikal analyzer generator

ANTLR – ANTLR dihasilkan didasarkan, LL (k) lexers.  Flex – Alternatif varian dari klasik ‘lex’ (C / C). JFlex – penulisan ulang dari JLex.  Ragel – Sebuah mesin scanner negara dan generator leksikal dengan dukungan output untuk C, C Objective-C, D, Jawa dan kode Ruby source. Para penganalisis leksikal berikut dapat menangani Unicode: JLex – A Lexical Analyzer Generator untuk Java. Quex – (atau “Queχ ‘) A Universal Cepat Analyzer Generator leksikal C.

Sumberhttp://en.wikipedia.org