Lexers hanyalah parser sederhana yang digunakan sebagai optimasi kinerja untuk parser utama. Jika kita memiliki lexer, lexer dan parser bekerja bersama untuk menggambarkan bahasa yang lengkap. Parser yang tidak memiliki tahap lexing terpisah kadang-kadang disebut "tanpa pemindai".
Tanpa lexers, parser harus beroperasi berdasarkan karakter-demi-karakter. Karena parser harus menyimpan metadata tentang setiap item input, dan mungkin harus melakukan pra-perhitungan tabel untuk setiap status item input, ini akan menghasilkan konsumsi memori yang tidak dapat diterima untuk ukuran input yang besar. Secara khusus, kita tidak perlu node terpisah per karakter di pohon sintaksis abstrak.
Karena teks berdasarkan karakter per karakter cukup ambigu, ini juga akan menghasilkan lebih banyak ambiguitas yang mengganggu untuk ditangani. Bayangkan sebuah aturan R → identifier | "for " identifier
. di mana pengidentifikasi terdiri dari surat-surat ASCII. Jika saya ingin menghindari ambiguitas, sekarang saya perlu lookahead 4 karakter untuk menentukan alternatif mana yang harus dipilih. Dengan lexer, parser hanya perlu memeriksa apakah ia memiliki IDENTIFIER atau FOR token - lookahead 1-token.
Tata bahasa dua tingkat.
Lexers bekerja dengan menerjemahkan alfabet input ke alfabet yang lebih nyaman.
Pengurai tanpa pemindai menggambarkan tata bahasa (N, Σ, P, S) di mana non-terminal N adalah sisi kiri aturan dalam tata bahasa, alfabet Σ misalnya karakter ASCII, produksi P adalah aturan dalam tata bahasa , dan simbol awal S adalah aturan tingkat atas parser.
Lexer sekarang mendefinisikan alfabet token a, b, c, .... Ini memungkinkan pengurai utama untuk menggunakan token ini sebagai alfabet: Σ = {a, b, c, ...}. Untuk lexer, token ini adalah non-terminal, dan aturan awal S L adalah S L → ε | a S | b S | c S | ..., yaitu: urutan token apa pun. Aturan dalam tata bahasa lexer adalah semua aturan yang diperlukan untuk menghasilkan token ini.
Keuntungan kinerja berasal dari mengekspresikan aturan lexer sebagai bahasa biasa . Ini dapat diurai jauh lebih efisien daripada bahasa bebas konteks. Secara khusus, bahasa reguler dapat dikenali dalam O (n) ruang dan O (n) waktu. Dalam praktiknya, pembuat kode dapat mengubah lexer menjadi tabel lompatan yang sangat efisien.
Mengekstrak token dari tata bahasa Anda.
Untuk menyentuh contoh Anda: digit
dan string
aturan diekspresikan pada tingkat karakter-demi-karakter. Kita bisa menggunakan itu sebagai token. Tata bahasanya tetap utuh. Berikut tata bahasa lexer, ditulis sebagai tata bahasa linier-kanan untuk memperjelas bahwa itu biasa:
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
string = '"' , string-rest ;
string-rest = '"' | STRING-CHAR, string-rest ;
STRING-CHAR = ? all visible characters ? - '"' ;
Tetapi karena ini biasa, kami biasanya menggunakan ekspresi reguler untuk mengekspresikan sintaks token. Berikut adalah definisi token di atas sebagai regex, ditulis menggunakan sintaks pengecualian kelas karakter NET dan. Charclass POSIX:
digit ~ [0-9]
string ~ "[[:print:]-["]]*"
Tata bahasa untuk parser utama kemudian berisi aturan yang tersisa yang tidak ditangani oleh lexer. Dalam kasus Anda, itu hanya:
input = digit | string ;
Ketika lexers tidak dapat digunakan dengan mudah.
Saat mendesain bahasa, kami biasanya berhati-hati bahwa tata bahasa dapat dipisahkan dengan bersih menjadi tingkat lexer dan tingkat parser, dan bahwa tingkat lexer menggambarkan bahasa biasa. Ini tidak selalu memungkinkan.
Saat menyematkan bahasa. Beberapa bahasa memungkinkan Anda untuk interpolasi kode ke string: "name={expression}"
. Sintaks ekspresi adalah bagian dari tata bahasa bebas konteks dan oleh karena itu tidak dapat dikenali oleh ekspresi reguler. Untuk mengatasi ini, kami menggabungkan kembali parser dengan lexer, atau kami memperkenalkan token tambahan seperti STRING-CONTENT, INTERPOLATE-START, INTERPOLATE-END
. Aturan tata bahasa untuk string maka akan terlihat seperti: String → STRING-START STRING-CONTENTS { INTERPOLATE-START Expression INTERPOLATE-END STRING-CONTENTS } STRING-END
. Tentu saja Ekspresi dapat berisi string lain, yang membawa kita ke masalah selanjutnya.
Kapan token bisa berisi satu sama lain. Dalam bahasa mirip-C, kata kunci tidak dapat dibedakan dari pengidentifikasi. Ini diselesaikan dalam lexer dengan memprioritaskan kata kunci di atas pengidentifikasi. Strategi seperti itu tidak selalu memungkinkan. Bayangkan file config di mana Line → IDENTIFIER " = " REST
, di mana sisanya adalah karakter apa pun hingga akhir baris, bahkan jika sisanya terlihat seperti pengenal. Baris contoh akan menjadi a = b c
. Lexer benar-benar bodoh dan tidak tahu di mana urutan token dapat terjadi. Jadi jika kita memprioritaskan IDENTIFIER daripada REST, lexer akan memberi kita IDENT(a), " = ", IDENT(b), REST( c)
. Jika kami memprioritaskan ISTIRAHAT daripada IDENTIFIER, lexer hanya akan memberi kami REST(a = b c)
.
Untuk mengatasi ini, kita harus menggabungkan kembali lexer dengan parser. Pemisahan dapat dipertahankan agak dengan membuat lexer malas: setiap kali parser membutuhkan token berikutnya, ia meminta dari lexer dan memberi tahu lexer set token yang dapat diterima. Secara efektif, kami membuat aturan tingkat atas baru untuk tata bahasa lexer untuk setiap posisi. Di sini, ini akan menghasilkan panggilan nextToken(IDENT), nextToken(" = "), nextToken(REST)
, dan semuanya berfungsi dengan baik. Ini membutuhkan parser yang mengetahui set token lengkap yang dapat diterima di setiap lokasi, yang menyiratkan parser bottom-up seperti LR.
Ketika lexer harus mempertahankan status. Misalnya bahasa Python membatasi blok kode bukan oleh kurung kurawal, tetapi oleh lekukan. Ada beberapa cara untuk menangani tata letak yang peka terhadap sintaksis dalam tata bahasa, tetapi teknik-teknik itu berlebihan untuk Python. Sebagai gantinya, lexer memeriksa lekukan setiap baris, dan memancarkan token INDENT jika blok indentasi baru ditemukan, dan token DEDENT jika blok telah berakhir. Ini menyederhanakan tata bahasa utama karena sekarang dapat berpura-pura token itu seperti kurung kurawal. Namun lexer sekarang perlu mempertahankan status: lekukan saat ini. Ini berarti lexer secara teknis tidak lagi menggambarkan bahasa biasa, tetapi sebenarnya bahasa yang peka konteks. Untungnya perbedaan ini tidak relevan dalam praktiknya, dan lexer Python masih dapat bekerja dalam waktu O (n).
input = digit | string
.