Artículo anteriorImplementamos el operador de asignación
Ahora enseñemos al traductor cómo manejar el operador de asignación. Y aquí nos enfrentamos con la tarea clásica de garantizar el cálculo de la fórmula algebraica dada en la notación que nos ha sido familiar desde nuestros años escolares. Si tuviéramos que hacer un intérprete, entonces tendríamos que calcular el valor de la fórmula. En nuestro caso, el núcleo Lisp calculará (en tiempo de ejecución). Y solo necesitamos convertir la fórmula de la notación habitual a Lisp.
La notación con la que estamos familiarizados se llama "notación infija" (el signo de la operación se encuentra entre los operandos). En Lisp, el signo de operación se coloca antes de los operandos (dicha notación se denomina "notación de prefijo"). Por lo tanto, nuestra tarea es convertir el formulario infijo al prefijo uno.
Puede resolver este problema de diferentes maneras ...
Sugiero convertir la fórmula a la llamada "Forma polaca inversa" (SCF). La notación polaca inversa (llamada así por el matemático polaco Lukashevich) es una forma de notación no bloqueante en la que los signos de las operaciones se ubican después de los operandos ("notación postfix"). La traducción del postfix al prefijo es bastante simple. Uno podría "resolver el problema en una sola acción": implementar inmediatamente la conversión de infijo a prefijo. Pero esta decisión sería algo más engorrosa. Sin embargo, aquellos que lo deseen pueden intentar hacerlo ellos mismos.
Y participaremos en la transformación de la fórmula en el SCR. En la entrada, tenemos una fórmula algebraica en notación infija, presentada en forma de una lista de niveles múltiples de Lisp. Por ejemplo, este:
(12 + x / ( y ^ 2 + z ^ 4))En el SCR, esta expresión tendrá la siguiente forma (a primera vista, extraña):
(12 xy 2 ^ z 4 ^ + / +)Para calcular el valor de la fórmula en forma de SCR, necesita una pila (estructura de datos que almacena y entrega datos según el principio de "último en llegar, primero en ir"). El cálculo es muy simple. La lista se lee una vez. Y para cada elemento, se realizan las siguientes acciones:
- El número (de valores variables) simplemente se inserta en la pila;
- La operación se realiza en el número correspondiente de operandos desde la parte superior de la pila.
Tenga en cuenta que no hay corchetes en el SCF, y las operaciones se realizan en el orden en que están escritas (las prioridades, como en forma de infijo, ya no están aquí).
La expresión que queremos traducir a SCR puede contener números, variables, funciones y signos de operación. Hay un problema: ¿cómo distinguir una variable de una función? Una forma natural de resolver este problema es hacer una lista de todas las operaciones y funciones y verificar el carácter requerido en esta lista: si el carácter se encuentra en la lista, entonces esta es una operación, de lo contrario es una variable.
Además, para cada función / operación, debe almacenar su
arity (número de argumentos). Una lista básica de operaciones podría verse así:
(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)))
Cabe señalar que en el proceso del traductor esta lista puede aumentar. El hecho es que las funciones mini-básicas devuelven valores y pueden participar en expresiones. Los nombres de estas funciones y su arity deben agregarse a la lista * oplist *. Esto se puede hacer en el procedimiento action-proc en la rama que procesa la instrucción proc. La variable * oplist * puede crearse en el procedimiento de inicio (y destruirse antes de completarse). Y agregar una función en el código action-proc puede implementarse así:
(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*)))
Ahora es necesario que cada operación que ocurre en la función establezca una cierta prioridad. Las prioridades se establecen mediante la siguiente función:
(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)))
La prioridad más baja se da a las operaciones lógicas "y" y "o". Luego están las operaciones de comparación, luego sumas y restas, etc. Las funciones tienen la máxima prioridad.
Ahora describimos el algoritmo para traducir la expresión en el SCR. La función inf2ipn acepta un parámetro requerido (fórmula de entrada) y dos opcionales (pila de operaciones y lista de acumuladores). En la lista de baterías, el resultado se acumula. La función escanea la lista de entrada y actúa de la siguiente manera:
- Si su siguiente elemento es un número o una variable, entonces se ingresa en la batería.
- Si el siguiente elemento es una lista, la función se aplica a esta lista de forma recursiva y su resultado se agrega a la batería.
- Si el siguiente elemento es una operación, entonces con una pila vacía de operaciones, el siguiente elemento se inserta en la pila de operaciones. Con una pila de operaciones no vacía, la prioridad de la operación entrante se compara con la parte superior de la pila de operaciones. Si llega una operación de mayor prioridad, entonces se empuja a la pila de operaciones.
- Si llega una operación con una prioridad no superior a la parte superior de la pila, la parte superior de la pila de operaciones se transfiere al acumulador y la operación recién llegada se ingresa en la pila de operaciones.
- Si la lista de entrada se agota y la pila de operaciones está vacía, la función devuelve una batería invertida (rama de terminal). De lo contrario, la función devuelve una batería invertida con una lista de operaciones previamente adjunta de la pila.
La función que distingue la operación del operando es muy simple: se trata de verificar si el carácter dado está en la lista global * oplist *:
(defun is-op (o) (member o (mapcar 'car *oplist*)))
Y la función de transferencia en el SCR tiene la forma:
(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))))))))
Puede verificar la funcionalidad de esta función llamándola directamente:
(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 * +)
Obtener una entrada de prefijo de un SCR es bastante simple. La función ipn2inf acepta la expresión en el SCR y el parámetro de la unidad. La función funciona así:
- Si la lista de entrada está vacía, se devuelve el cabezal de la unidad;
- Si el siguiente elemento es un número o una variable, entonces este átomo está unido a la unidad;
- Si el siguiente elemento es una operación de aridad n, entonces se agrega una lista que consiste en el símbolo de esta operación y un segmento invertido de la unidad de longitud n a la unidad sin los primeros n elementos.
Así es como se ve en el código:
Verifique el estado del código:
(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))
Ahora solo queda escribir el manejador del operador de asignación y conectarlo al manejador de procedimientos. El controlador de asignación se puede implementar de la siguiente manera:
(defun action-set (meat) (let ((name-var (car meat)) (r-value (i2p (cddr meat)))) `(setq ,name-var ,r-value)))
Se supone que el parámetro de carne se refiere a la asignación de la lista:
( = )
El reconocimiento del operador de asignación se realiza en la función action-proc, que toma la forma:
(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))))
Verifiquemos el rendimiento de nuestro código. Cargamos el código en el entorno Lisp, llamamos a la función de inicio y traducimos el siguiente procedimiento:
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
Veamos qué generó nuestro traductor:
(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)))
Todo parece estar bien. Ahora, llamemos a nuestro procedimiento y obtengamos el resultado esperado:
(main) 25 ==> 25
Nuestro traductor también se encargará de las funciones integradas correctamente. Para verificar esto, ejecutaremos, por ejemplo, el siguiente código:
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
Y obtenemos:
(main) 0.499999999987039 0.866025403791922 1.0 ==> 1.0
¡Nuestro traductor cobra vida ante nuestros ojos!
Sin embargo, nos dejamos llevar: luchando por el objetivo final, no pensamos en absoluto en los errores que puede cometer el usuario (el programador que usa el mini-básico). En el buen sentido, tuvimos que pensar en los errores de inmediato, pero recién comenzamos a trabajar, no fuimos demasiado lejos y no es demasiado tarde para introducir el manejo de errores y el diagnóstico en el código. Además, es obvio que están sugiriendo "mejoras menores" (por ejemplo, nuestro traductor requiere que el operador ocupe exactamente una línea, lo cual es inconveniente).
El siguiente artículo estará dedicado a todas estas preguntas.
Para continuarEl código de este artículo se puede descargar
aquí.