Article précédentNous implémentons l'opérateur d'affectation
Maintenant, apprenons au traducteur comment gérer l’opérateur d’affectation. Et nous voilà confrontés à la tâche classique d'assurer le calcul de la formule algébrique donnée dans la notation qui nous est familière depuis nos années scolaires. Si nous devions faire un interprète, alors nous aurions besoin de calculer la valeur de la formule. Dans notre cas, le noyau Lisp calculera (au moment de l'exécution). Et nous avons juste besoin de convertir la formule de la notation habituelle en Lisp.
La notation que nous connaissons est appelée «notation infixe» (le signe d'opération est situé entre les opérandes). En Lisp, le signe d'opération est placé avant les opérandes (une telle notation est appelée «notation de préfixe»). Ainsi, notre tâche est de convertir le formulaire infixe en préfixe.
Vous pouvez résoudre ce problème de différentes manières ...
Je suggère de convertir la formule en soi-disant «Forme polonaise inversée» (SCF). La notation polonaise inversée (nommée d'après le mathématicien polonais Lukashevich) est une forme de notation non bloquante dans laquelle les signes des opérations sont situés après les opérandes («notation postfixe»). La traduction de postfix en préfixe est assez simple. On pourrait «résoudre le problème en une seule action» - implémenter immédiatement la conversion d'infixe en préfixe. Mais cette décision serait un peu plus lourde. Cependant, ceux qui le souhaitent peuvent essayer de le faire eux-mêmes.
Et nous participerons à la transformation de la formule dans le SCR. En entrée, nous avons une formule algébrique en notation infixe, présentée sous la forme d'une liste multi-niveaux Lisp. Par exemple, celui-ci:
(12 + x / ( y ^ 2 + z ^ 4))Dans le SCR, cette expression aura la forme (à première vue - étrange) suivante:
(12 xy 2 ^ z 4 ^ + / +)Pour calculer la valeur de la formule sous forme de SCR, vous avez besoin d'une pile (une structure de données qui stocke et fournit des données sur le principe du "dernier arrivé, premier arrivé"). Le calcul est très simple. La liste est lue une fois. Et pour chaque élément, les actions suivantes sont effectuées:
- Le nombre (de valeurs variables) est simplement poussé sur la pile;
- L'opération est effectuée sur le nombre correspondant d'opérandes à partir du haut de la pile.
Veuillez noter qu'il n'y a pas de parenthèses dans le SCF, et les opérations sont effectuées dans l'ordre où elles sont écrites (les priorités, comme dans le format infixe, ne sont plus ici).
L'expression que nous voulons traduire en SCR peut contenir des nombres, des variables, des fonctions et des signes d'opération. Il y a un problème - comment distinguer une variable d'une fonction? Un moyen naturel de résoudre ce problème est de faire une liste de toutes les opérations et fonctions et de vérifier le caractère requis sur cette liste: si le caractère est trouvé dans la liste, alors c'est une opération, sinon c'est une variable.
De plus, pour chaque fonction / opération, vous devez stocker son
arité (nombre d'arguments). Une liste de base des opérations pourrait ressembler à ceci:
(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)))
Il convient de noter que dans le processus du traducteur, cette liste peut augmenter. Le fait est que les fonctions mini-basiques renvoient des valeurs et peuvent participer aux expressions. Les noms de ces fonctions et leur arité doivent être ajoutés à la liste * oplist *. Cela peut être fait dans la procédure action-proc de la branche qui traite l'instruction proc. La variable * oplist * peut être créée dans la procédure de démarrage (et détruite avant la fin). Et l'ajout d'une fonction dans le code action-proc peut être implémenté comme ceci:
(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*)))
Maintenant, il est nécessaire pour chaque opération qui se produit dans la fonction de définir une certaine priorité. Les priorités sont fixées par la fonction suivante:
(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 priorité la plus basse est donnée aux opérations logiques «et» et «ou». Il y a ensuite les opérations de comparaison, puis l'addition et la soustraction, etc. Les fonctions ont la priorité la plus élevée.
Nous décrivons maintenant l'algorithme de traduction de l'expression en SCR. La fonction inf2ipn accepte un paramètre obligatoire (formule d'entrée) et deux facultatifs (pile d'opérations et liste d'accumulateurs). Dans la liste des batteries, le résultat est cumulé. La fonction analyse la liste des entrées et agit comme suit:
- Si son élément suivant est un nombre ou une variable, il est alors entré dans la batterie.
- Si l'élément suivant est une liste, la fonction est appliquée à cette liste de manière récursive et son résultat est ajouté à la batterie.
- Si l'élément suivant est une opération, alors avec une pile d'opérations vide, l'élément suivant est poussé sur la pile d'opérations. Avec une pile d'opérations non vide, la priorité de l'opération entrante est comparée avec le haut de la pile d'opérations. Si une opération de priorité plus élevée arrive, elle est poussée sur la pile des opérations.
- Si une opération avec une priorité non supérieure au sommet de la pile arrive, alors le sommet de la pile d'opérations est transféré vers l'accumulateur, et l'opération nouvellement arrivée est entrée dans la pile d'opérations.
- Si la liste d'entrée est épuisée et que la pile d'opérations est vide, la fonction renvoie une batterie inversée (branche terminale). Sinon, la fonction renvoie une batterie inversée avec une liste d'opérations précédemment attachée de la pile.
La fonction qui distingue l'opération de l'opérande est très simple - il s'agit de vérifier si le caractère donné est dans la liste globale * oplist *:
(defun is-op (o) (member o (mapcar 'car *oplist*)))
Et la fonction de transfert dans le SCR a la forme:
(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))))))))
Vous pouvez vérifier la fonctionnalité de cette fonction en l'appelant directement:
(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 * +)
L'obtention d'une entrée de préfixe à partir d'un SCR est assez simple. La fonction ipn2inf accepte l'expression dans le SCR et le paramètre d'entraînement. La fonction fonctionne comme ceci:
- Si la liste d'entrée est vide, la tête d'entraînement est renvoyée;
- Si l'élément suivant est un nombre ou une variable, alors cet atome est attaché au lecteur;
- Si l'élément suivant est une opération d'arité n, alors une liste constituée du symbole de cette opération et d'un segment inversé du lecteur de longueur n est ajoutée au lecteur sans les n premiers éléments.
Voici à quoi cela ressemble dans le code:
Vérifiez la santé du code:
(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))
Il ne reste plus qu'à écrire le gestionnaire de l'opérateur d'affectation et à le connecter au gestionnaire de procédure. Le gestionnaire d'affectation peut être implémenté comme suit:
(defun action-set (meat) (let ((name-var (car meat)) (r-value (i2p (cddr meat)))) `(setq ,name-var ,r-value)))
Le paramètre de viande est censé faire référence à l'affectation de liste:
( = )
La reconnaissance de l'opérateur d'affectation se fait dans la fonction action-proc, qui prend la forme:
(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))))
Vérifions les performances de notre code. Nous chargeons le code dans l'environnement Lisp, appelons la fonction start et traduisons la procédure suivante:
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
Voyons ce que notre traducteur a généré:
(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)))
Tout semble aller bien. Maintenant, appelons notre procédure et obtenons le résultat attendu:
(main) 25 ==> 25
Notre traducteur gérera également correctement les fonctions intégrées. Pour vérifier cela, nous allons exécuter, par exemple, le code suivant:
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
Et nous obtenons:
(main) 0.499999999987039 0.866025403791922 1.0 ==> 1.0
Notre traducteur prend vie sous nos yeux!
Cependant, nous étions très emportés: en visant l'objectif final, nous ne pensions pas du tout aux erreurs que l'utilisateur (le programmeur utilisant le mini-basique) pouvait faire. Dans le bon sens, nous avons dû penser aux erreurs tout de suite, mais nous avons juste commencé à travailler, nous ne sommes pas allés trop loin et il n'est pas trop tard pour introduire la gestion des erreurs et les diagnostics dans le code. De plus, il est évident que des «améliorations mineures» suggèrent (par exemple, notre traducteur exige que l'opérateur occupe exactement une ligne, ce qui n'est pas pratique).
L'article suivant sera consacré à toutes ces questions.
À suivreLe code de cet article peut être téléchargé
ici.