Artigo anteriorImplementamos o operador de atribuição
Agora vamos ensinar o tradutor como lidar com o operador de atribuição. E aqui nos deparamos com a tarefa clássica de garantir o cálculo da fórmula algébrica dada na notação que nos é familiar desde os anos escolares. Se quiséssemos fazer um intérprete, precisaríamos calcular o valor da fórmula. No nosso caso, o kernel Lisp irá calcular (em tempo de execução). E só precisamos converter a fórmula da notação usual para Lisp.
A notação com a qual estamos familiarizados é chamada de "notação infix" (o sinal de operação está localizado entre operandos). No Lisp, o sinal de operação é colocado antes dos operandos (essa notação é chamada de “prefixo notação”). Assim, nossa tarefa é converter o formulário do infixo no prefixo.
Você pode resolver esse problema de maneiras diferentes ...
Sugiro converter a fórmula para o chamado “Forma polonesa reversa” (SCF). A notação polonesa reversa (nomeada após o matemático polonês Lukashevich) é uma forma não-bloqueadora de notação, na qual os sinais de operações estão localizados após os operandos ("notação pós-fixada"). A tradução do postfix para o formulário prefixo é bastante simples. Pode-se “resolver o problema em uma ação” - implementar imediatamente a conversão do infixo para o prefixo. Mas essa decisão seria um pouco mais complicada. No entanto, aqueles que desejam podem tentar fazer isso sozinhos.
E estaremos envolvidos na transformação da fórmula no SCR. Na entrada, temos uma fórmula algébrica em notação de infixo, apresentada na forma de uma lista de vários níveis do Lisp. Por exemplo, este:
(12 + x / ( y ^ 2 + z ^ 4))No SCR, essa expressão terá a seguinte forma (à primeira vista - estranha):
(12 xy 2 ^ z 4 ^ + / +)Para calcular o valor da fórmula na forma de SCR, você precisa de uma pilha (estrutura de dados que armazena e entrega dados com o princípio de "chegada e chegada"). O cálculo é muito simples. A lista é lida uma vez. E para cada elemento, são executadas as seguintes ações:
- O número (de valores variáveis) é simplesmente empurrado para a pilha;
- A operação é executada no número correspondente de operandos da parte superior da pilha.
Observe que não há colchetes no SCF e as operações são executadas na ordem em que são gravadas (as prioridades, como na forma de infixo, não estão mais aqui).
A expressão que queremos traduzir para SCR pode conter números, variáveis, funções e sinais de operação. Há um problema - como distinguir uma variável de uma função? Uma maneira natural de resolver esse problema é fazer uma lista de todas as operações e funções e verificar o caractere requerido nessa lista: se o caractere for encontrado na lista, será uma operação, caso contrário, é uma variável.
Além disso, para cada função / operação, você precisa armazenar sua
aridade (número de argumentos). Uma lista básica de operações pode ser assim:
(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)))
Note-se que no processo do tradutor essa lista pode aumentar. O fato é que as funções mini-básicas retornam valores e podem participar de expressões. Os nomes dessas funções e suas áreas devem ser adicionados à lista * oplist *. Isso pode ser feito no procedimento action-proc na ramificação que processa a instrução proc. A variável * oplist * pode ser criada no procedimento inicial (e destruída antes da conclusão). E adicionar uma função no código action-proc pode ser implementado assim:
(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*)))
Agora é necessário que cada operação que ocorre na função defina uma certa prioridade. As prioridades são definidas pela seguinte função:
(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)))
A prioridade mais baixa é dada às operações lógicas “and” e “or”. Depois, há operações de comparação, adição e subtração, etc. As funções têm a maior prioridade.
Agora, descrevemos o algoritmo para traduzir a expressão no SCR. A função inf2ipn aceita um parâmetro necessário (fórmula de entrada) e dois opcionais (pilha de operações e lista de acumuladores). Na lista de baterias, o resultado é acumulado. A função varre a lista de entrada e age da seguinte maneira:
- Se o seu próximo elemento for um número ou uma variável, ele será inserido na bateria.
- Se o próximo elemento for uma lista, a função será aplicada recursivamente a essa lista e seu resultado será adicionado à bateria.
- Se o próximo elemento for uma operação, com uma pilha vazia de operações, o próximo elemento será empurrado para a pilha de operações. Com uma pilha de operações não vazia, a prioridade da operação de entrada é comparada com a parte superior da pilha de operações. Se uma operação de prioridade mais alta chegar, ela será empurrada para a pilha de operações.
- Se uma operação com uma prioridade não superior à parte superior da pilha chegar, a parte superior da pilha de operações será transferida para o acumulador e a operação recém-chegada será inserida na pilha de operações.
- Se a lista de entradas estiver esgotada e a pilha de operações estiver vazia, a função retornará uma bateria invertida (ramificação do terminal). Caso contrário, a função retornará uma bateria invertida com uma lista de operações anexada anteriormente da pilha.
A função que distingue a operação do operando é muito simples - basta verificar se o caractere especificado está na lista global * oplist *:
(defun is-op (o) (member o (mapcar 'car *oplist*)))
E a função de transferência no SCR tem a 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))))))))
Você pode verificar a funcionalidade desta função chamando-a diretamente:
(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 * +)
Obter uma entrada de prefixo de um SCR é bastante simples. A função ipn2inf aceita a expressão no SCR e no parâmetro do inversor. A função funciona assim:
- Se a lista de entrada estiver vazia, o cabeçote da unidade será retornado;
- Se o próximo elemento for um número ou uma variável, esse átomo será anexado à unidade;
- Se o próximo elemento for uma operação da arity n, uma lista que consiste no símbolo desta operação e um segmento invertido da unidade de comprimento n é anexada à unidade sem os primeiros n elementos.
Aqui está o que parece no código:
Verifique a integridade do 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))
Agora, resta apenas gravar o manipulador do operador de atribuição e conectá-lo ao manipulador de procedimentos. O manipulador de atribuição pode ser implementado da seguinte maneira:
(defun action-set (meat) (let ((name-var (car meat)) (r-value (i2p (cddr meat)))) `(setq ,name-var ,r-value)))
O parâmetro meat deve se referir à atribuição da lista:
( = )
O reconhecimento do operador de atribuição é feito na função action-proc, que assume a 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))))
Vamos verificar o desempenho do nosso código. Carregamos o código no ambiente Lisp, chamamos a função start e traduzimos o seguinte procedimento:
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
Vamos ver o que nosso tradutor gerou:
(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)))
Tudo parece estar certo. Agora, vamos chamar nosso procedimento e obter o resultado esperado:
(main) 25 ==> 25
Nosso tradutor também lidará com as funções internas corretamente. Para verificar isso, executaremos, por exemplo, o seguinte 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
E temos:
(main) 0.499999999987039 0.866025403791922 1.0 ==> 1.0
Nosso tradutor ganha vida diante de nossos olhos!
No entanto, ficamos muito empolgados: lutando pelo objetivo final, não pensamos nos erros que o usuário (o programador que usa o mini-básico) pode cometer. De uma maneira boa, tivemos que pensar nos erros imediatamente, mas começamos a trabalhar, não fomos longe demais e não é tarde demais para introduzir manipulação e diagnóstico de erros no código. Além disso, é óbvio que “pequenas melhorias” estão sugerindo (por exemplo, nosso tradutor exige que o operador ocupe exatamente uma linha, o que é inconveniente).
O artigo a seguir será dedicado a todas essas perguntas.
Para ser continuadoO código deste artigo pode ser baixado
aqui.