Datang dengan token untuk lexer

Saya sedang menulis parser untuk bahasa markup yang telah saya buat (menulis dengan python, tapi itu tidak benar-benar relevan dengan pertanyaan ini - bahkan jika ini sepertinya ide yang buruk, saya akan menyukai saran untuk jalur yang lebih baik) .

Saya membaca tentang parser di sini: http://www.ferg.org/parsing/index.html , dan saya sedang mengerjakan penulisan lexer yang seharusnya, jika saya mengerti dengan benar, membagi konten menjadi token. Apa yang saya mengalami kesulitan memahami adalah apa jenis token yang harus saya gunakan atau cara membuatnya. Misalnya, jenis token dalam contoh yang saya tautkan adalah:

• TALI
• IDENTIFIER
• JUMLAH
• WHITESPACE
• KOMENTAR
• EOF
• Banyak simbol seperti {dan (dihitung sebagai jenis token mereka sendiri)

Masalah yang saya alami adalah bahwa jenis token yang lebih umum tampak agak arbitrer bagi saya. Sebagai contoh, mengapa STRING tipe token terpisah vs. IDENTIFIER. Sebuah string dapat direpresentasikan sebagai STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Ini mungkin juga ada hubungannya dengan kesulitan bahasa saya. Misalnya, deklarasi variabel ditulis sebagai {var-name var value}dan digunakan dengan {var-name}. Sepertinya '{'dan '}'harus menjadi token mereka sendiri, tetapi apakah VAR_NAME dan VAR_VALUE jenis token yang memenuhi syarat, atau apakah keduanya termasuk dalam IDENTIFIER? Terlebih lagi, VAR_VALUE dapat benar-benar berisi spasi putih. Spasi putih setelah var-namedigunakan untuk menandakan awal dari nilai dalam deklarasi .. spasi putih lainnya adalah bagian dari nilai. Apakah ruang putih ini menjadi tokennya sendiri? Whitespace hanya memiliki makna itu dalam konteks ini. Selain itu, {mungkin bukan awal dari deklarasi variabel .. itu tergantung pada konteks (ada kata itu lagi!). {:memulai deklarasi nama, dan{ bahkan dapat digunakan sebagai bagian dari nilai tertentu.

Bahasa saya mirip dengan Python dalam blok yang dibuat dengan lekukan. Saya membaca tentang bagaimana Python menggunakan lexer untuk membuat token INDENT dan DEDENT (yang berfungsi kurang lebih seperti apa {dan }akan dilakukan dalam banyak bahasa lain). Python mengklaim bebas konteks yang berarti bagi saya bahwa setidaknya lexer tidak peduli di mana ia berada di aliran saat membuat token. Bagaimana lexer Python mengetahui bahwa ia sedang membangun token INDENT dengan panjang tertentu tanpa mengetahui tentang karakter sebelumnya (misalnya bahwa baris sebelumnya adalah baris baru, jadi mulailah membuat spasi untuk INDENT)? Saya bertanya karena saya perlu tahu ini juga.

Pertanyaan terakhir saya adalah yang paling bodoh: mengapa lexer bahkan perlu? Sepertinya saya bahwa parser bisa pergi karakter demi karakter dan mencari tahu di mana itu dan apa yang diharapkan. Apakah lexer menambah manfaat kesederhanaan?

Pertanyaan Anda (seperti paragraf terakhir Anda mengisyaratkan) sebenarnya bukan tentang lexer, melainkan tentang desain antarmuka yang tepat antara lexer dan parser. Seperti yang Anda bayangkan ada banyak buku tentang desain lexers dan parser. Kebetulan saya suka buku parser karya Dick Grune , tapi itu mungkin bukan buku pengantar yang bagus. Saya kebetulan sangat tidak suka buku berbasis C oleh Appel , karena kode tidak bermanfaat diperluas ke kompiler Anda sendiri (karena masalah manajemen memori yang melekat dalam keputusan untuk berpura-pura C seperti ML). Pengantar saya sendiri adalah buku karya PJ Brown , tapi itu bukan pengantar umum yang bagus (meskipun cukup bagus untuk penerjemah khusus). Tetapi kembali ke pertanyaan Anda.

Jawabannya adalah, lakukan sebanyak yang Anda bisa dalam lexer tanpa perlu menggunakan kendala yang tampak maju atau mundur.

Ini berarti bahwa (tergantung tentu saja pada perincian bahasa) Anda harus mengenali string sebagai karakter "diikuti oleh urutan tidak-" dan kemudian karakter "lainnya. Kembalikan itu ke parser sebagai unit tunggal. Ada beberapa alasan untuk ini, tetapi yang penting adalah

1. Ini mengurangi jumlah status yang harus dipertahankan parser, sehingga membatasi konsumsi memorinya.
2. Hal ini memungkinkan implementasi lexer untuk berkonsentrasi pada mengenali blok bangunan dasar dan membebaskan pengurai untuk menggambarkan bagaimana elemen sintaksis individu digunakan untuk membangun sebuah program.

Seringkali parser dapat mengambil tindakan segera saat menerima token dari lexer. Misalnya, segera setelah IDENTIFIER diterima, parser dapat melakukan pencarian tabel simbol untuk mengetahui apakah simbol sudah diketahui. Jika parser Anda juga mem-parsing konstanta string sebagai QUOTE (IDENTIFIER SPACES) * QUOTE Anda akan melakukan banyak pencarian tabel simbol yang tidak relevan, atau Anda akhirnya akan mengangkat pencarian tabel simbol lebih tinggi ke pohon parser elemen sintaksis, karena Anda hanya dapat melakukan pada titik Anda sekarang yakin Anda tidak melihat string.

Untuk menyatakan kembali apa yang ingin saya katakan, tetapi secara berbeda, lexer harus memperhatikan ejaan benda, dan pengurai dengan struktur benda.

Anda mungkin memperhatikan bahwa uraian saya tentang seperti apa string tampak sangat mirip dengan ekspresi reguler. Ini bukan kebetulan. Analisis leksikal sering diimplementasikan dalam bahasa kecil (dalam arti buku Pemrograman Mutiara Jon Jon yang sangat bagus ) yang menggunakan ekspresi reguler. Saya hanya terbiasa berpikir dalam hal ekspresi reguler ketika mengenali teks.

Mengenai pertanyaan Anda tentang spasi putih, kenali di lexer. Jika bahasa Anda dimaksudkan untuk berformat bebas, jangan kembalikan token WHITESPACE ke parser, karena itu hanya akan membuangnya, sehingga aturan produksi parser Anda akan dibenturkan dengan suara pada dasarnya - hal-hal yang harus dikenali hanya dengan membuang mereka pergi.

Adapun apa artinya itu tentang bagaimana Anda harus menangani spasi ketika itu signifikan secara sintaksis, saya tidak yakin saya bisa membuat penilaian untuk Anda yang benar-benar akan bekerja dengan baik tanpa mengetahui lebih banyak tentang bahasa Anda. Penilaian cepat saya adalah untuk menghindari kasus di mana spasi putih kadang-kadang penting dan kadang tidak, dan menggunakan semacam pembatas (seperti kutipan). Tetapi, jika Anda tidak dapat mendesain bahasa dengan cara apa pun yang Anda inginkan, opsi ini mungkin tidak tersedia untuk Anda.

Ada cara lain untuk melakukan desain sistem parsing bahasa. Tentu saja ada sistem konstruksi kompiler yang memungkinkan Anda untuk menentukan sistem lexer dan parser gabungan (saya pikir versi Java ANTLR melakukan ini) tetapi saya belum pernah menggunakannya.

Terakhir catatan sejarah. Beberapa dekade yang lalu, penting bagi lexer untuk melakukan sebanyak mungkin sebelum menyerahkan ke parser, karena kedua program tidak akan muat dalam memori pada saat yang sama. Melakukan lebih banyak dalam lexer meninggalkan lebih banyak memori yang tersedia untuk membuat parser pintar. Saya dulu menggunakan Whitesmiths C Compiler selama beberapa tahun, dan jika saya mengerti dengan benar, itu akan beroperasi hanya dalam 64KB RAM (itu adalah program MS-DOS model kecil) dan meskipun demikian menerjemahkan varian C yang sangat sangat dekat dengan ANSI C.

Saya akan menjawab pertanyaan terakhir Anda, yang sebenarnya tidak bodoh. Parser dapat dan memang membangun konstruksi kompleks berdasarkan karakter-demi-karakter. Jika saya ingat, tata bahasa di Harbison and Steele ("C - A reference manual") memiliki produksi yang menggunakan karakter tunggal sebagai terminal, dan membangun pengidentifikasi, string, angka, dll sebagai bukan terminal dari karakter tunggal.

Dari sudut pandang bahasa formal, apa pun yang dapat dikenali dan dikategorikan sebagai "string literal", "pengidentifikasi", "angka", "kata kunci", dan sebagainya, bahkan parser LL (1) dapat mengenali. Jadi tidak ada masalah teoritis dengan menggunakan generator parser untuk mengenali semuanya.

Dari sudut pandang algoritmik, pengenal ekspresi reguler dapat berjalan jauh lebih cepat daripada pengurai mana pun. Dari sudut pandang kognitif, mungkin lebih mudah bagi seorang programmer untuk memecah pekerjaan antara regular-expression-lexer dan parser-generator parser tertulis.

Saya akan mengatakan bahwa pertimbangan praktis menyebabkan orang membuat keputusan untuk memiliki lexer dan parser yang terpisah.

Sepertinya Anda mencoba untuk menulis lexer / parser tanpa benar-benar memahami tata bahasa. Biasanya, ketika orang menulis lexer dan parser, mereka menulisnya agar sesuai dengan tata bahasa. Lexer harus mengembalikan token dalam tata bahasa sementara parser menggunakan token tersebut untuk mencocokkan aturan / non-terminal . Jika Anda dapat dengan mudah mem-parse input Anda hanya akan byte demi byte, maka lexer dan parser mungkin berlebihan.

Lexers membuat segalanya lebih sederhana.

Ikhtisar tata bahasa: Tata bahasa adalah seperangkat aturan untuk bagaimana beberapa sintaks atau input seharusnya terlihat. Misalnya, inilah tata bahasa mainan (perintah simple_command is start):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

Tata bahasa ini berarti -
Perintah simple_command terdiri dari
A) WORD diikuti oleh DIGIT diikuti oleh AND_SYMBOL (ini adalah "token" yang saya definisikan)
B) " Selain_ekspresi " (ini adalah aturan atau "non-terminal")

Suatu tambahan_ekspresi terdiri dari:
NUM diikuti oleh '+' diikuti oleh NUM (NUM adalah "token" yang saya definisikan, '+' adalah tanda plus literal).

Oleh karena itu, karena simple_command adalah "simbol awal" (tempat saya mulai), ketika saya menerima token saya memeriksa untuk melihat apakah cocok dengan perintah simple_command. Jika token pertama dalam input adalah WORD dan token berikutnya adalah DIGIT dan token berikutnya adalah AND_SYMBOL, maka saya telah mencocokkan beberapa perintah simple_command dan dapat mengambil tindakan. Kalau tidak, saya akan mencoba mencocokkannya dengan aturan lain dari simple_command yang merupakan penambahan_ekspresi. Jadi, jika token pertama adalah NUM diikuti oleh '+' diikuti oleh NUM, maka saya mencocokkan perintah simple_command dan saya mengambil beberapa tindakan. Jika tidak satu pun dari hal-hal itu, maka saya memiliki kesalahan sintaksis.

Itu intro sangat, sangat mendasar untuk tata bahasa. Untuk pemahaman yang lebih menyeluruh, lihat artikel wiki ini dan cari di seluruh web untuk tutorial tata bahasa bebas konteks.

Menggunakan pengaturan lexer / parser, berikut ini contoh tampilan parser Anda:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Ok, jadi kode itu agak jelek dan saya tidak akan merekomendasikan triple nested if statement. Tapi intinya, bayangkan mencoba melakukan hal di atas karakter demi karakter alih-alih menggunakan fungsi "get_next_token" dan "peek_next_token" Anda yang bagus . Serius, cobalah. Anda tidak akan menyukai hasilnya. Sekarang perlu diingat bahwa tata bahasa di atas sekitar 30x lebih kompleks daripada hampir semua tata bahasa yang berguna. Apakah Anda melihat manfaat menggunakan lexer?

Sejujurnya, lexers dan parser bukan topik paling dasar di dunia. Saya sarankan pertama membaca dan memahami tata bahasa, kemudian membaca sedikit tentang lexers / parser, kemudian menyelam.

Pertanyaan terakhir saya adalah yang paling bodoh: mengapa lexer bahkan perlu? Sepertinya saya bahwa parser bisa pergi karakter demi karakter dan mencari tahu di mana itu dan apa yang diharapkan.

Ini tidak bodoh, itu hanya kebenaran.

Tetapi kepraktisan entah bagaimana tergantung sedikit pada alat dan tujuan Anda. Misalnya, jika Anda menggunakan yacc tanpa lexer, dan Anda ingin mengizinkan huruf unicode di pengidentifikasi, Anda harus menulis aturan besar dan jelek yang menjabarkan semua karakter yang valid untuk menjabarkan semua karakter yang valid. Sementara, dalam lexer, Anda mungkin bisa meminta rutin perpustakaan jika karakter adalah anggota kategori surat.

Menggunakan atau tidak menggunakan lexer adalah masalah memiliki tingkat abstraksi antara bahasa Anda dan tingkat karakter. Perhatikan bahwa level karakter, saat ini, adalah abstraksi lain di atas level byte, yang merupakan abstraksi di atas level bit.

Jadi, akhirnya, Anda bahkan dapat menguraikan pada tingkat bit.

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Tidak, tidak bisa. Bagaimana dengan "("? Menurut Anda, itu bukan string yang valid. Dan lolos?

Secara umum, cara terbaik untuk memperlakukan spasi putih adalah dengan mengabaikannya, di luar batas token. Banyak orang lebih menyukai ruang putih yang sangat berbeda dan menegakkan aturan ruang putih masih kontroversial.