Пишем простой транслятор на Лиспе — II

Предыдущая статья

Реализуем оператор присвоения

А теперь научим транслятор обрабатывать оператор присвоения. И здесь перед нами встает классическая задача – обеспечить вычисление алгебраической формулы, заданной в привычной для нас со школьных лет записи. Если бы мы делали интерпретатор, то нам бы понадобилось вычислять значение формулы. В нашем же случае вычислять (во время выполнения) будет ядро Лиспа. А нам нужно всего лишь преобразовать формулу из привычной нам записи в лисповскую.
Привычная нам запись называется “инфиксной нотацией” (знак операции располагается между операндами). В Лиспе знак операции располагается перед операндами (такая запись называется “префиксной нотацией”). Таким образом, наша задача состоит в преобразовании инфиксной формы в префиксную.

Решать эту задачу можно разными путями…

Я предлагаю преобразовать формулу в т.н. “обратную польскую форму” (ОПЗ). Обратная польская запись (названная так в честь польского математика Лукашевича) – это бесскобочная форма записи, в которой знаки операций расположены после операндов (“постфиксная нотация”). Перевод из постфиксной формы в префиксную выполняется достаточно просто. Можно было бы “решить задачу в одно действие” – сразу реализовать преобразование из инфиксной формы в префиксную. Но это решение оказалось бы несколько более громоздким. Впрочем, желающие могут попробовать сделать это сами.

А мы займемся преобразованием формулы в ОПЗ. На входе у нас алгебраическая формула в инфиксной нотации, представленная в виде лисповского многоуровневого списка. Например, вот такого:

(12 + x / ( y ^ 2 + z ^ 4))

В ОПЗ это выражение будет иметь следующий (на первый взгляд – странный) вид:

(12 x y 2 ^ z 4 ^ + / +)

Чтобы вычислить значение формулы в форме ОПЗ, нужен стек (структура данных, хранящая и поставляющая данные по принципу “последний пришёл – первый ушёл”). Вычисление выполняется очень просто. Список читается один раз. И для каждого элемента выполняются следующие действия:

• Число (значений переменной) просто кладётся в стек;
• Операция выполняется над соответствующим количеством операндов с вершины стека.

Обратите внимание – в ОПЗ нет скобок, а операции выполняются в той последовательности, как они записаны (приоритетов, как в инфиксной форме здесь уже нет).

Выражение, которое мы хотим перевести в ОПЗ, может содержать числа, переменные, функции и знаки операций. Возникает проблема – как отличить переменную от функции? Естественный способ решения этой проблемы – завести список всех операций и функций и проверять требуемый символ по этому списку: если символ найден в списке – значит это операция, иначе – переменная.
Кроме того, для каждой функции/операции нужно хранить её арность (количество аргументов). Базовый список операций может выглядеть так:

(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)))

Следует отметить, что в процессе работы транслятора этот список может увеличиваться. Дело в том, что функции мини-бэйсика возвращают значения и могут участвовать в выражениях. Имена этих функций и их арность необходимо добавлять к списку *oplist*. Это можно сделать в процедуре action-proc в той ветви, которая обрабатывает оператор proc. Переменную *oplist* можно создать в процедуре start (и уничтожить перед завершением). А добавление функции в коде action-proc можно реализовать так:

(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*)))  

Теперь необходимо каждой операции, которая встречается в функции, задать определенный приоритет. Приоритеты задает следующая функция:

(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))) 

Самый низший приоритет – у логических операций “и” и “или”. Потом идут операции сравнения, затем сложение и вычитание и т.п. Самый высокий приоритет у функций.

Теперь опишем алгоритм перевода выражения в ОПЗ. Функция inf2ipn принимает один обязательный параметр (входная формула) и два необязательных (стек операций и список-аккумулятор). В списке аккумуляторе накапливается результат. Функция просматривает входной список и действует следующим образом:

• Если очередной его элемент есть число или переменная, то он заносится в аккумулятор.
• Если очередной элемент есть список, то функция применяется к этому списку рекурсивно, а ее результат добавляется в аккумулятор.
• Если очередной элемент есть операция, то при пустом стеке операций, очередной элемент заносится в стек операций. При непустом стеке операций выполняется сравнение приоритета пришедшей операции и вершины стека операций. Если пришла операция большего приоритета, то она заносится в стек операций.
• Если пришла операция с приоритетом, не большим, чем вершина стека, то вершина стека операций переносится в аккумулятор, а вновь пришедшая операция заносится в стек операций.
• Если входной список исчерпан и стек операций пуст, то функция возвращает реверсированный аккумулятор (терминальная ветвь). В противном случае функция возвращает реверсированный аккумулятор с предварительно присоединенным списком операций из стека.

Функция, отличающая операцию от операнда, очень проста — она сводится к проверке попадает ли заданный символ в глобальный список *oplist*:

(defun is-op (o) 
  (member o (mapcar 'car *oplist*)))

А функция перевода в ОПЗ имеет вид:

(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 a r))))))))

В работоспособности этой функции можно убедиться, вызвав ее непосредственно:

(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 * +)

Получить из ОПЗ префиксную запись совсем просто. Функция ipn2inf принимает выражение в ОПЗ и параметр-накопитель. Функция работает так:

• Если входной список пуст, возвращается голова накопителя;
• Если очередной элемент — число или переменная, то этот атом присоединяется к накопителю;
• Если очередной элемент – операция арности n, то к накопителю без n первых элементов присоединяется список, состоящий из символа этой операции и реверсированного отрезка накопителя длины n.

Вот как это выглядит в коде:

;; Получение арности операции

(defun arity (o)
  (iter (for a in *oplist*) (when (eq o (car a)) (return (cadr a)))))   

;; Перевод из ОПЗ в префиксную

(defun ipn2pref (f &optional (s nil))
  (cond ((null f) (car s))
        ((numberp (car f)) (ipn2pref (cdr f) (cons (car f) s)))
        ((is-op (car f))
         (let ((ar (arity (car f)))) 
           (ipn2pref (cdr f) (cons (cons (car f)
                  (reverse (subseq s 0 ar))) (subseq s ar)))))
        (t (ipn2pref (cdr f) (cons (car f) s)))))

;; Функция-обертка, переводящая инфиксную запись в префиксную
 
(defun i2p (f)
  (ipn2pref (inf2ipn f)))        

Проверим работоспособность кода:

(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))

Теперь осталось только написать обработчик оператора присвоения и подключить его к обработчику процедуры. Обработчик присвоения может быть реализован так:

(defun action-set (meat)
  (let ((name-var (car meat))
        (r-value (i2p (cddr meat))))
    `(setq ,name-var ,r-value)))

Предполагается, что параметр meat ссылается на присвоение в виде списка:

(имя = выражение)

Распознавание оператора присвоения делаем в функции action-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))))
               ((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))))

Давайте проверим работоспособность нашего кода. Загрузим код в среду Лиспа, вызовем функцию start и протранслируем вот такую процедуру:

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


Посмотрим, что сгенерировал наш транслятор:

(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)))

Кажется, все верно. А теперь вызовем нашу процедуру и получим вполне ожидаемый результат:

(main)
25
==> 25

Наш транслятор будет правильно обрабатывать и встроенные функции. Чтобы убедиться в этом, исполним, к примеру, следующий код:

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


И получим:

(main)
0.499999999987039
0.866025403791922
1.0
==> 1.0

Наш транслятор оживает на глазах!

Однако, мы сильно увлеклись: стремясь к конечной цели, совсем не подумали об ошибках, которые может совершить пользователь (т.е. программист, использующий мини-бэйсик). По-хорошему, об ошибках нужно было думать сразу, но мы только начали работу, ушли не слишком далеко, и внести в код средства обработки ошибок и диагностику еще не поздно. Кроме того, совершенно очевидно, что напрашиваются “мелкие улучшательства” (к примеру, наш транслятор требует, чтобы оператор занимал ровно одну строку, а это неудобно).

Всем этим вопросам будет посвящена следующая статья. Продолжение следует!

Код к этой статье можно скачать здесь

Автор: catstail1954

Источник