Artikel sebelumnyaKami menerapkan operator penugasan
Sekarang mari kita ajarkan penerjemah bagaimana menangani operator penugasan. Dan di sini kita dihadapkan dengan tugas klasik untuk memastikan perhitungan formula aljabar yang diberikan dalam notasi yang telah kita kenal sejak kita sekolah dulu. Jika kita membuat juru bahasa, maka kita perlu menghitung nilai formula. Dalam kasus kami, kernel Lisp akan menghitung (pada saat run time). Dan kita hanya perlu mengubah formula dari notasi biasa menjadi Lisp.
Notasi yang kita kenal disebut "notasi infiks" (tanda operasi terletak di antara operan). Dalam Lisp, tanda operasi ditempatkan sebelum operan (notasi seperti itu disebut "notasi awalan"). Dengan demikian, tugas kami adalah mengubah bentuk infiks ke bentuk awalan.
Anda dapat menyelesaikan masalah ini dengan berbagai cara ...
Saya sarankan untuk mengubah formula menjadi apa yang disebut "Membalikkan bentuk Polandia" (SCF). Notasi Polandia terbalik (dinamai setelah ahli matematika Polandia Lukashevich) adalah bentuk notasi non-blocking di mana tanda-tanda operasi terletak setelah operan ("notasi postfix"). Terjemahan dari bentuk postfix ke bentuk prefix cukup sederhana. Orang dapat "memecahkan masalah dalam satu tindakan" - segera menerapkan konversi dari infiks ke awalan. Tetapi keputusan ini akan sedikit lebih rumit. Namun, mereka yang berharap dapat mencoba melakukannya sendiri.
Dan kami akan terlibat dalam transformasi formula di SCR. Pada input, kami memiliki rumus aljabar dalam notasi infiks, disajikan dalam bentuk daftar multi-level Lisp. Misalnya, ini:
(12 + x / ( y ^ 2 + z ^ 4))Dalam SCR, ungkapan ini akan memiliki bentuk (sekilas - aneh) berikut:
(12 xy 2 ^ z 4 ^ + / +)Untuk menghitung nilai rumus dalam bentuk SCR, Anda memerlukan tumpukan (struktur data yang menyimpan dan mengirimkan data pada prinsip "last come - first go"). Perhitungannya sangat sederhana. Daftar dibaca sekali. Dan untuk setiap elemen, tindakan berikut dilakukan:
- Jumlah (nilai variabel) hanya didorong ke tumpukan;
- Operasi dilakukan pada jumlah operan yang sesuai dari atas tumpukan.
Harap dicatat bahwa tidak ada tanda kurung di SCF, dan operasi dilakukan sesuai urutan tertulis (prioritas, seperti dalam bentuk infix, tidak ada lagi di sini).
Ekspresi yang ingin kami terjemahkan ke dalam SCR dapat berisi angka, variabel, fungsi, dan tanda operasi. Ada masalah - bagaimana membedakan suatu variabel dari suatu fungsi? Cara alami untuk menyelesaikan masalah ini adalah dengan membuat daftar semua operasi dan fungsi dan memeriksa karakter yang diperlukan dalam daftar ini: jika karakter ditemukan dalam daftar, maka ini adalah operasi, jika tidak itu adalah variabel.
Selain itu, untuk setiap fungsi / operasi, Anda perlu menyimpan
aritynya (jumlah argumen). Daftar operasi dasar mungkin terlihat seperti ini:
(setq *oplist* '((+ 2) (- 2) (* 2) (/ 2) (^ 2) (\ 2) (% 2) (= 2) (== 2) (/= 2) (> 2) (>= 2) (< 2) (<= 2) (and 2) (or 2) (not 1) (sin 1) (cos 1) (abs 1) (exp 1) (log 1) (sqrt 1)))
Perlu dicatat bahwa dalam proses penerjemah daftar ini dapat meningkat. Faktanya adalah bahwa fungsi mini-basic mengembalikan nilai dan dapat berpartisipasi dalam ekspresi. Nama-nama fungsi ini dan aritynya harus ditambahkan ke daftar * oplist *. Ini dapat dilakukan dalam prosedur tindakan-proc di cabang yang memproses pernyataan proc. Variabel * oplist * dapat dibuat di prosedur awal (dan dihancurkan sebelum selesai). Dan menambahkan fungsi dalam kode tindakan-proc dapat diimplementasikan seperti ini:
(cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt)) (setq *oplist* (cons (list proc-name (length proc-parm)) *oplist*)))
Sekarang perlu untuk setiap operasi yang terjadi dalam fungsi untuk menetapkan prioritas tertentu. Prioritas ditetapkan oleh fungsi berikut:
(defun prty (OP) (cond ((EQ OP 'and) 1) ((EQ OP 'or) 1) ((EQ OP '>) 2) ((EQ OP '>=) 2) ((EQ OP '<) 2) ((EQ OP '<=) 2) ((EQ OP '=) 2) ((EQ OP '==) 2) ((EQ OP '/=) 2) ((EQ OP '+) 3) ((EQ OP '-) 3) ((EQ OP '*) 4) ((EQ OP '/) 4) ((EQ OP '\) 4) ((EQ OP '%) 4) ((EQ OP '^) 5) ((member op (mapcar 'car *oplist*)) 6)))
Prioritas terendah diberikan untuk operasi logis "dan" dan "atau". Lalu ada operasi perbandingan, lalu penjumlahan dan pengurangan, dll. Fungsi memiliki prioritas tertinggi.
Sekarang kami menggambarkan algoritma untuk menerjemahkan ekspresi dalam SCR. Fungsi inf2ipn menerima satu parameter yang diperlukan (formula input) dan dua opsional (tumpukan operasi dan daftar akumulator). Dalam daftar baterai, hasilnya diakumulasikan. Fungsi memindai daftar input dan bertindak sebagai berikut:
- Jika elemen selanjutnya adalah angka atau variabel, maka dimasukkan ke dalam baterai.
- Jika elemen berikutnya adalah daftar, maka fungsinya diterapkan ke daftar ini secara rekursif, dan hasilnya ditambahkan ke baterai.
- Jika elemen berikutnya adalah operasi, maka dengan tumpukan operasi kosong, elemen berikutnya didorong ke tumpukan operasi. Dengan tumpukan operasi yang tidak kosong, prioritas operasi yang masuk dibandingkan dengan bagian atas tumpukan operasi. Jika operasi dengan prioritas lebih tinggi tiba, maka ia didorong ke tumpukan operasi.
- Jika operasi dengan prioritas tidak lebih besar dari bagian atas tumpukan tiba, maka bagian atas tumpukan operasi dipindahkan ke akumulator, dan operasi yang baru tiba dimasukkan ke dalam tumpukan operasi.
- Jika daftar input habis dan tumpukan operasi kosong, maka fungsi mengembalikan baterai terbalik (cabang terminal). Jika tidak, fungsi mengembalikan baterai terbalik dengan daftar operasi yang sebelumnya terpasang dari tumpukan.
Fungsi yang membedakan operasi dari operan sangat sederhana - ia turun untuk memeriksa apakah karakter yang diberikan ada dalam daftar * oplist * global:
(defun is-op (o) (member o (mapcar 'car *oplist*)))
Dan fungsi transfer dalam SCR memiliki bentuk:
(defun inf2ipn (f &optional (s nil) (r nil)) (cond ((null f) (if (null s) (reverse r) (inf2ipn nil (cdr s) (cons (car s) r)))) ((listp (car f)) (inf2ipn (cdr f) s (append (reverse (inf2ipn (car f))) r))) ((numberp (car f)) (inf2ipn (cdr f) s (cons (car f) r))) ((not (is-op (car f))) (inf2ipn (cdr f) s (cons (car f) r))) (t (cond ((null s) (inf2ipn (cdr f) (cons (car f) s) r)) ((> (prty (car f)) (prty (car s))) (inf2ipn (cdr f) (cons (car f) s) r)) (t (let ((a (car s))) (inf2ipn (cdr f) (cons (car f) (cdr s)) (cons ar))))))))
Anda dapat memverifikasi fungsionalitas fungsi ini dengan memanggilnya langsung:
(inf2ipn '(2 + 3 * 6)) ==> (2 3 6 * +) (inf2ipn '((2 + 3) * 6)) ==> (2 3 + 6 *) (inf2ipn '(3 + a * sin ( 5 + x))) ==> (3 A 5 X + SIN * +)
Mendapatkan entri awalan dari SCR cukup sederhana. Fungsi ipn2inf menerima ekspresi di SCR dan parameter drive. Fungsi kerjanya seperti ini:
- Jika daftar input kosong, kepala drive dikembalikan;
- Jika elemen berikutnya adalah angka atau variabel, maka atom ini dilampirkan ke drive;
- Jika elemen berikutnya adalah operasi arity n, maka daftar yang terdiri dari simbol operasi ini dan segmen yang dibalik dari drive dengan panjang n ditambahkan ke drive tanpa elemen n pertama.
Begini tampilannya dalam kode:
Periksa kesehatan kode:
(i2p '(3 + a * sin ( 5 + x))) ==> (+ 3 (* A (SIN (+ 5 X)))) (i2p '((3 + a) * sin ( 5 ) + x)) ==> (* (+ 3 A) (+ (SIN 5) X)) (i2p '((3 + a) * sin ( 5 ^ 2 - x ) + x)) ==> (* (+ 3 A) (+ (SIN (- (^ 5 2) X)) X))
Sekarang tinggal menulis handler dari operator penugasan dan menghubungkannya ke handler prosedur. Penangan penugasan dapat diimplementasikan sebagai berikut:
(defun action-set (meat) (let ((name-var (car meat)) (r-value (i2p (cddr meat)))) `(setq ,name-var ,r-value)))
Parameter daging seharusnya merujuk pada tugas daftar:
( = )
Pengakuan operator penugasan dilakukan dalam fungsi action-proc, yang mengambil bentuk:
(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)))) ((eq (cadr stmt) '=) (setq body (append body (list (action-set 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))))
Mari kita periksa kinerja kode kita. Kami memuat kode ke lingkungan Lisp, memanggil fungsi mulai dan menerjemahkan prosedur berikut:
0001 proc main()
0002 local x,y,z
0003 x=3
0004 y=4
0005 z=x^2+y^2
0006 print z
0007 end_proc
Mari kita lihat apa yang dihasilkan oleh penerjemah kami:
(getd 'main) ==> (EXPR NIL (LET ((X 0) (Y 0) (Z 0)) (SETQ X 3) (SETQ Y 4) (SETQ Z (+ (^ X 2) (^ Y 2))) (PRINTLINE Z)))
Segalanya tampak benar. Sekarang, mari panggil prosedur kami dan dapatkan hasil yang diharapkan:
(main) 25 ==> 25
Penerjemah kami juga akan menangani fungsi-fungsi bawaan dengan benar. Untuk memverifikasi ini, kami akan menjalankan, misalnya, kode berikut:
0001 proc main()
0002 local x,y,z,pi
0003 pi=3.1415926535
0004 x=sin(pi/6)
0005 y=cos(pi/6)
0006 z=x^2+y^2
0007 print x
0018 print y
0019 print z
0010 end_proc
Dan kita mendapatkan:
(main) 0.499999999987039 0.866025403791922 1.0 ==> 1.0
Penerjemah kami menjadi hidup di depan mata kami!
Namun, kami sangat terhanyut: berjuang untuk tujuan akhir, kami tidak memikirkan sama sekali tentang kesalahan yang dapat dilakukan oleh pengguna (pemrogram menggunakan mini-basic). Dengan cara yang baik, kami harus segera memikirkan kesalahan, tetapi kami baru saja mulai bekerja, kami tidak melangkah terlalu jauh, dan belum terlambat untuk memperkenalkan penanganan kesalahan dan diagnostik ke dalam kode. Selain itu, jelas bahwa "perbaikan kecil" menunjukkan (misalnya, penerjemah kami mengharuskan operator untuk menempati tepat satu baris, yang tidak nyaman).
Artikel berikut akan dikhususkan untuk semua pertanyaan ini.
Untuk dilanjutkanKode untuk artikel ini dapat diunduh di
sini.