Mari kita coba menulis dalam Lisp ... penerjemah bahasa imperatif sederhana. Tidak, tidak, saya tidak salah - itu adalah penerjemah. Ini akan disiarkan dalam kode Lisp. Dan kemudian kode ini dapat dieksekusi oleh sistem Lisp.
Di sini, layanan yang tak ternilai harganya akan disediakan oleh fakta bahwa di Lisp tidak ada penghalang antara kode dan data (ini adalah properti langka dari beberapa bahasa pemrograman yang disebut "homo-identity"). Tetapi kemampuan visual Lisp juga akan memainkan peran penting.
Sebagai implementasi, saya akan menggunakan HomeLisp . Mereka yang tertarik dapat menyesuaikan proyek ini dengan Common Lisp. Saya akan mengatakan segera - dalam kaitannya dengan masalah yang sedang dipertimbangkan, perbedaan yang signifikan antara Common Lisp dan HomeLisp hanya dalam pemrosesan baris dan file.
Unduh versi portabel HomeLisp di sini . Dokumentasi juga terletak di situs yang sama . Mereka yang ingin dapat menyalin kode dari artikel dan segera memeriksa kinerjanya.
Topik yang menjadi perhatian Anda menjadi dasar bagi lokakarya saya di Novosibirsk LSHUP-2018 yang terkenal . Hasil lokakarya dapat ditemukan di sini . Dan kemudian saya memulai pendekatan saya. Saya kira pembaca sudah terbiasa dengan bahasa Lisp.
Turun
Mari kita mulai dengan "bahasa imperatif sederhana" yang akan kami siarankan di Lisp.
Bahasa hanya akan memproses data numerik. Kode dalam bahasa ini terdiri dari fungsi (prosedur yang mengembalikan nilai). Di antara fungsi-fungsi ini, seseorang harus disebut main. Dengan fungsi inilah eksekusi kode dimulai. Meski begitu mengapa mengikat dirimu sendiri? Kami menulis fungsi dalam bahasa imperatif, mereka disiarkan dalam Lisp dan dapat digunakan bersama dengan fungsi Lisp. Tapi jangan maju dulu ...
Seperangkat operator bahasa biasa: penugasan, percabangan, siklus aritmatika, keluar awal dari siklus, input, output dan panggilan fungsi. Namun, secara fungsi pemanggilan fungsi dieksekusi sebagai tugas (hasil dari panggilan). Biarkan komentar berisi tanda bintang di posisi pertama baris. Bahasa, tentu saja, harus menyediakan kemampuan untuk menciptakan fungsi rekursif. Untuk membuatnya lebih jelas, saya akan memberikan contoh kode - mencetak nomor ganjil berturut-turut dan menghitung jumlah mereka:
proc main() local s,n,k input n for i=1 to n k=2*i-1 print k s=s+k end_for print s end_proc
Dalam semangatnya, itu adalah bahasa dasar seperti. Saya akan menyebutnya "mini-basic." Penerjemah kami harus mengonversi kode yang diberikan ke fungsi Lisp berikut:
(defun main nil (let ((s 0) (n 0) (k 0)) (setq n (read)) (iter (for i from 1 to n) (setq k (- (* 2 i) 1)) (printline k) (setq s (+ sk))) (printline s)))
Saya sangat suka paket iterate , yang diimplementasikan sebagai makro dalam paket Common Lisp profesional. Dalam HomeLisp, fungsi iter (yang mengimplementasikan sebagian besar kemampuan iterate makro) termasuk dalam bahasa inti. Kecanduan saya pada iter yang menyebabkan siklus "mini-basic" kami diterjemahkan ke dalam panggilan iter.
Di mana memulai implementasi? Mari kita mulai dengan memilih file yang akan disiarkan dan membaca dan mencetak file itu baris demi baris. Kami harus memulai penerjemah berkali-kali, jadi biarkan ini mulai dari awal menjadi mudah. Seperti inilah fungsi ini:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (let ((fi (gensym 'fi))) (when fname (filOpen fi fname _INPUT) (loop (getLine fi) (when (or *flagerr* (filEOF fi)) (return t))) (filClose fi) (when *flagerr* (printsline "**** ")))) (unset '*numline*) (unset '*flagerr*))
Fungsi ini memiliki parameter opsional fname - nama file yang isinya akan disiarkan. Saat memasukkan fungsi, dua variabel global dibuat: numLine, nomor baris file sumber, dan flagerr , bendera status kesalahan. Sebelum fungsi berakhir, variabel-variabel ini dihancurkan (fungsi HomeLisp tidak disetel menghancurkan variabel global).
Jika nama file input dihilangkan, maka dialog windows standar untuk memilih file (sysGetOpenName) dipanggil. Direktori saat ini (sysHome) digunakan sebagai direktori awal. Selanjutnya, karakter unik dibuat untuk manipulator file dan file dibuka untuk membaca teks. Kemudian, dalam loop tanpa akhir, file tersebut dibaca baris demi baris (fungsi getLine ). Setelah setiap operasi, diperiksa apakah kesalahan telah terjadi dan jika akhir file tercapai. Jika kesalahan terjadi atau akhir file diperbaiki, siklus terputus, file ditutup, dan jika ada kesalahan, pesan terakhir ditampilkan.
Sebenarnya membaca dari file dilakukan oleh fungsi getLine :
(defun getLine (fil) (let ((stri "")) (loop (when (filEof fil) (return "")) (setq *numline* (add1 *numline*)) (setq stri (filGetline fil)) (printsline (strCat (format *numline* "0000") " " (strRTrim stri))) (setq stri (strATrim stri)) (unless (or (eq "" stri) (eq "*" (strLeft stri 1))) (return stri)))))
Fungsi ini menerima pengidentifikasi file yang terbuka dan, dalam loop tak terbatas, melakukan tindakan berikut:
- memeriksa akhir status file. Dalam hal ini, loop terputus dan fungsi mengembalikan string kosong;
- penghitung garis baca bertambah satu;
- baris file selanjutnya dibaca;
- baris baca dicetak dengan menghilangkan ruang yang mungkin ada di sebelah kanan;
- jika baris baca tidak kosong dan tidak mengandung tanda bintang di posisi pertama, maka itu
kembali dari fungsi;
Dengan demikian, semua baris file dalam bentuk aslinya termasuk dalam daftar output.
Kami membobol prosedur
Sekarang mari kita ajarkan kode kita untuk memecah aliran input ke dalam prosedur terpisah. Pertama, string yang dimasukkan harus dibagi menjadi token (input unit leksikal yang tidak dapat dibagi). Proses ini disebut parsing; kita harus membuat parser. Menulis parser adalah tema klasik, ada pustaka parser siap pakai dan alat khusus yang memungkinkan Anda untuk menghasilkan parser yang diperlukan ... Kami akan pergi dengan cara kami sendiri.
Sebelum menjelaskan algoritma parser, kami memperhatikan fakta bahwa semua karakter dari string input dapat dibagi menjadi dua kelas:
- Karakter biasa;
- Karakter pemisah.
Jadi, di operator penugasan "x = 15 + y ^ 2", karakter x, 1,5, y dan 2 adalah karakter biasa, dan karakter "spasi" , + , ^ adalah pembatas. Bagaimana karakter normal berbeda dari pemisah? Pemisah - selalu memisahkan satu token dari yang lain. Operator penugasan kami, yang dibagi menjadi token, terlihat seperti ini: "x", "=", "15", "y", "^", "2" .
Seperti yang Anda lihat, tidak semua pembatas jatuh ke dalam hasil parsing (spasi, khususnya, tidak jatuh). Kami akan memanggil pemisah yang tidak termasuk dalam hasil sebagai pemisah dari tipe pertama. Pemisah lain akan disebut pemisah dari tipe kedua.
Input parser akan berupa string, outputnya adalah daftar token string. Sebagai drive, variabel lokal akan digunakan - baterai. Baterai awalnya berisi string kosong.
Algoritma parsing dapat sebagai berikut: kita membaca karakter baris input oleh karakter. Jika Anda bertemu karakter biasa, gabungkan dengan baterai. Jika pembatas ditemukan, maka:
- Untuk pemisah dari tipe pertama, kami mereset nilai baterai (jika tidak kosong) ke daftar output, kosongkan baterai dan lanjutkan membaca karakter berikutnya;
- Untuk pemisah jenis kedua, kami juga membuang nilai baterai yang tidak kosong ke dalam daftar keluaran, dan setelah itu kami memasukkan pemisah yang diterima untuk jenis kedua (sebagai token independen) ke dalam daftar keluaran, kosongkan baterai dan lanjutkan membaca karakter berikutnya.
Berikut adalah kode parser:
(defun parser (txt &optional (d1 " ,") (d2 "()+-*/\^=<>%")) (let ((res nil) (lex "") ) (iter (for s in-string (strCat txt (strLeft d1 1))) (cond ((plusp (strInd d1 s)) (when (> (strLen lex) 0) (collecting lex into res)) (setq lex "")) ((plusp (strInd d2 s)) (when (> (strLen lex) 0) (collecting lex into res)) (collecting s into res) (setq lex "")) (t (setq lex (strCat lex s))))) res))
Selain parameter yang diperlukan, fungsi memiliki dua parameter opsional: d1 berisi string, masing-masing karakter memiliki pemisah dari tipe pertama, dan garis d2 berisi pemisah dari tipe kedua.
Logika program dari fungsi parser dijelaskan di atas. Hanya perlu dicatat bahwa sebelum memulai pekerjaan, pemisah ditambahkan ke akhir jalur input. Hal ini dilakukan agar token yang diproses terakhir "hang" di baterai (variabel lokal lex memainkan peran baterai).
Mari kita periksa parser kami "beraksi":
(parser "x = 15 + y^2") ==> ("x" "=" "15" "+" "y" "^" "2")
Itu benar, bukan? Tetapi bekerja dengan daftar string tidak cukup Lisp. Mari kita beralih dari daftar string ke daftar atom. Untuk melakukan ini, kita memerlukan fungsi yang ... menempelkan semua token lagi menjadi garis panjang (tapi menyisipkan spasi di antara token), lalu menempelkan braket pembuka ke awal baris ini, menutup braket penutup sampai akhir ... dan kemudian memaksa Lisp untuk membaca daftar:
(defun mk-intf (txt) (let ((lex (parser txt " ," "()+-*/\^=<>%")) (intf "")) (iter (for a in lex) (setq intf (strCat intf a " "))) (input (strCat "(" intf ")"))))
Sekarang, jika kita mengirimkan operator penugasan ke input dari fungsi mk-intf, kita mendapatkan:
(mk-intf "x = 15 + y^2") ==> (X = 15 + Y ^ 2)
Yang, Anda lihat, jauh lebih baik.
Sekarang mari kita ubah sedikit fungsi mulai: fungsi ini harus membaca dan memproses seluruh prosedur:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (when fname (let ((fi (gensym 'fi))) (filOpen fi fname _INPUT) (loop (let ((curr-proc (action-proc fi))) (when (or *flagerr* (filEOF fi)) (return t)) (eval curr-proc))) (filClose fi)) (when *flagerr* (printsline "**** "))) (unset '*numline*) (unset '*flagerr*))
Dalam tubuh loop, fungsi action-proc dipanggil (untuk memproses prosedur), yang akan membentuk tubuh prosedur yang diterima yang sudah ada di Lisp. Tubuh prosedur, disimpan sebagai ekspresi S dalam variabel arus -proc , kemudian diteruskan ke input eval . Dan fungsi yang diterima adalah "bereinkarnasi" di lingkungan Lisp!
Apa yang harus dilakukan tindakan-proc ? Fungsi ini menerima pengidentifikasi file yang terbuka sebagai parameter. Fungsi membaca baris file demi baris dari file, melompati baris kosong dan komentar, mem-parsing sisa baris, menerjemahkannya ke dalam bentuk daftar, dan menghasilkan isi prosedur.
Kami secara bertahap akan "belajar" menghasilkan tindakan-proc . Dan mari kita mulai dengan mengajarkan fungsi kita untuk mengenali awal dan akhir suatu prosedur. Dalam mini-basic, awal prosedur adalah:
proc name(p1,p2,p3)
coba parsing baris seperti ini:
(mk-intf "proc name(p1,p2,p3)") ==> (PROC NAME (P1 P2 P3))
Bagaimana seharusnya fungsi tindakan-proc menanggapi input ini? Tentu saja, memastikan bahwa kepala daftar adalah atom PROC , Anda perlu mengambil elemen kedua dari daftar sebagai nama fungsi, dan elemen ketiga sebagai daftar parameter. Nama dan daftar parameter harus disimpan dalam variabel lokal. Ketika operator end_proc dibaca , maka Anda perlu membentuk bentuk defun dengan tubuh kosong (sejauh ini) dari nama fungsi dan daftar parameter, dan mengembalikan formulir ini sebagai hasilnya. Begini tampilannya:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm (quote OK))))
Untuk pembentukan akhir klausa defun , kunci terbalik digunakan. Perhatikan bahwa prosedur yang dihasilkan akan mengembalikan atom OK sebagai hasilnya.
Sekarang kita dapat memeriksa kode kita dalam aksi. Masukkan kode berikut ke dalam file 0000.mbs:
proc f1(x,y) end_proc proc f2(x) end_proc
Jalankan prosedur mulai , pilih 0000.mbs dan lihat di konsol:
0001 proc f1(x,y) 0002 end_proc 0003 proc f2(x) 0004 end_proc
Jika mau, Anda dapat memastikan bahwa mesin Lisp sekarang memiliki dua fungsi (sejauh ini tidak berguna) f1 dan f2 :
(getd 'f1) ==> (EXPR (XY) (QUOTE OK)) (getd 'f2) ==> (EXPR (X) (QUOTE OK))
Apalagi! Itu sudah bisa dimulai:
(f1 1 2) ==> OK (f2 2) ==> OK
Penerjemah kami menarik napas pertama ...
Input, output, dan variabel lokal
Sekarang adalah waktunya untuk mengajar penerjemah kami yang baru lahir bagaimana menangani input , cetak, dan operator lokal .
Cara termudah untuk menangani input dan pencetakan. Kedua operator memiliki struktur sintaksis yang sama: kata kunci dan variabel. Input operator x harus berubah menjadi bentuk Lisp (setq x (baca)) . Dengan demikian, operator cetak x berubah menjadi formulir (printline x) . Untuk menyimpan formulir ini, Anda harus menyediakan variabel lokal di fungsi action-proc . Variabel ini akan mengakumulasi formulir yang melakukan perhitungan fungsi di masa mendatang. Maka semuanya sangat sederhana:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var nil) (body nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) ((eq (car stmt) 'print) (setq body (append body (list (cons 'printline (cdr stmt)))))) ((eq (car stmt) 'input) (setq body (append body (list (list 'setq (cadr stmt) (list 'read) ))))) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm ,@body)))
Sekarang mari kita siapkan kode sumber ini pada mini-basic:
proc f1(x,y) print x print y end_proc proc f2(x) input x print x end_proc
dan coba terjemahkan ... Kami akan memiliki dua fungsi Lisp f1 dan f2 . Mari kita lihat ekspresi mereka dan pastikan mereka dihasilkan dengan benar:
(getd 'f1) ==> (EXPR (XY) (PRINTLINE X) (PRINTLINE Y)) (getd 'f2) ==> (EXPR (X) (SETQ X (READ)) (PRINTLINE X))
Anda dapat memanggil fungsi-fungsi ini, dan memastikan fungsinya persis seperti yang dimaksudkan. Biarkan itu tidak mengganggu Anda bahwa kami memasukkan nilai dalam variabel parameter - kami hanya belum memiliki variabel lokal ... Mari kita tambahkan mereka.
Operator lokal dapat berada di mana saja dalam prosedur dan terjadi lebih dari satu kali. Jika operator lokal ditemui selama pemrosesan prosedur, maka Anda perlu mengambil daftar variabel dan menyimpannya dalam variabel lokal. Setelah pernyataan end_proc terpenuhi, Anda perlu membuat form let dan “melampirkan” semua pernyataan yang dapat dieksekusi di dalamnya (untuk saat ini, hanya masukan dan cetak ). Inilah yang akan terlihat seperti tindakan-proc :
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var nil) (lv nil) (body nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) ((eq (car stmt) 'print) (setq body (append body (list (cons 'printline (cdr stmt)))))) ((eq (car stmt) 'input) (setq body (append body (list (list 'setq (cadr stmt) (list 'read) ))))) ((eq (car stmt) 'local) (setq loc-var (append loc-var (cdr stmt)))) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) (iter (for a in (setof loc-var)) (collecting (list a 0) into lv)) `(defun ,proc-name ,proc-parm (let ,lv ,@body))))
Daftar variabel lokal diakumulasikan dalam variabel loc-var . Setelah pemrosesan prosedur selesai, daftar pasangan bentuk (nama 0) dibuat dari daftar ini. Pada saat yang sama, duplikasi nama yang identik tidak diinginkan ... Bagaimana mencegahnya? Tentu saja, dimungkinkan untuk memeriksa setiap pemrosesan operator lokal apakah ada nama duplikat (jika ada, berikan pesan kesalahan). Tapi, menurut saya, lebih baik menghilangkan pengulangan, yang dilakukan oleh setof call. Sekarang mari kita terjemahkan dan jalankan program ini:
proc f1(x,y) local a,b,c print x print y input a print a end_proc
Kami memastikan bahwa itu berfungsi persis seperti yang disarankan algoritma. Tapi yang paling menarik ada di depan!
Dari sini, Anda dapat mengunduh versi final dari apa yang kami aktifkan w berkode ...
Untuk dilanjutkan!