Хабрахабр

Пишем простой транслятор на Лиспе — 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

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

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
0001 proc main()
0002 local x,y,z,pi
0003 pi=3.

И получим:

(main)
0.499999999987039
0.866025403791922
1.0
==> 1.0

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

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

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть