Vorheriger ArtikelWir implementieren den Zuweisungsoperator
Lassen Sie uns nun dem Übersetzer den Umgang mit dem Zuweisungsoperator beibringen. Und hier stehen wir vor der klassischen Aufgabe, die Berechnung der algebraischen Formel in der uns seit unseren Schuljahren bekannten Notation sicherzustellen. Wenn wir einen Interpreter erstellen würden, müssten wir den Wert der Formel berechnen. In unserem Fall berechnet der Lisp-Kernel (zur Laufzeit). Und wir müssen nur die Formel von der üblichen Notation in Lisp konvertieren.
Die uns bekannte Notation heißt „Infix-Notation“ (das Operationszeichen befindet sich zwischen Operanden). In Lisp wird das Operationszeichen vor den Operanden platziert (eine solche Notation wird als "Präfixnotation" bezeichnet). Unsere Aufgabe ist es daher, das Infix-Formular in das Präfix-Formular zu konvertieren.
Sie können dieses Problem auf verschiedene Arten lösen ...
Ich schlage vor, die Formel in die sogenannte umzuwandeln "Reverse Polish Form" (SCF). Die umgekehrte polnische Notation (benannt nach dem polnischen Mathematiker Lukaschewitsch) ist eine nicht blockierende Form der Notation, bei der sich die Zeichen der Operationen hinter den Operanden befinden („Postfix-Notation“). Die Übersetzung vom Postfix in das Präfixformular ist recht einfach. Man könnte "das Problem in einer Aktion lösen" - sofort die Konvertierung von Infix zu Präfix implementieren. Diese Entscheidung wäre jedoch etwas umständlicher. Wer es wünscht, kann es jedoch selbst versuchen.
Und wir werden uns mit der Transformation der Formel im SCR befassen. Am Eingang haben wir eine algebraische Formel in Infixnotation, die in Form einer mehrstufigen Lisp-Liste dargestellt wird. Zum Beispiel dieses:
(12 + x / ( y ^ 2 + z ^ 4))In der SCR hat dieser Ausdruck die folgende (auf den ersten Blick seltsame) Form:
(12 xy 2 ^ z 4 ^ + / +)Um den Wert der Formel in Form von SCR zu berechnen, benötigen Sie einen Stapel (eine Datenstruktur, die Daten nach dem Prinzip "last come - first go" speichert und liefert). Die Berechnung ist sehr einfach. Die Liste wird einmal gelesen. Für jedes Element werden die folgenden Aktionen ausgeführt:
- Die Anzahl (der variablen Werte) wird einfach auf den Stapel geschoben.
- Die Operation wird an der entsprechenden Anzahl von Operanden von der Oberseite des Stapels ausgeführt.
Bitte beachten Sie, dass der SCF keine Klammern enthält und die Operationen in der Reihenfolge ausgeführt werden, in der sie geschrieben wurden (Prioritäten wie in Infixform sind hier nicht mehr vorhanden).
Der Ausdruck, den wir in SCR übersetzen möchten, kann Zahlen, Variablen, Funktionen und Operationszeichen enthalten. Es gibt ein Problem - wie kann man eine Variable von einer Funktion unterscheiden? Eine natürliche Möglichkeit, dieses Problem zu lösen, besteht darin, eine Liste aller Operationen und Funktionen zu erstellen und das erforderliche Zeichen in dieser Liste zu überprüfen: Wenn das Zeichen in der Liste gefunden wird, handelt es sich um eine Operation, andernfalls handelt es sich um eine Variable.
Außerdem müssen Sie für jede Funktion / Operation ihre
Arität (Anzahl der Argumente) speichern. Eine grundlegende Liste von Operationen könnte folgendermaßen aussehen:
(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)))
Es ist zu beachten, dass sich diese Liste im Verlauf des Übersetzers erhöhen kann. Tatsache ist, dass die Mini-Grundfunktionen Werte zurückgeben und an Ausdrücken teilnehmen können. Die Namen dieser Funktionen und ihre Arität müssen zur Liste * oplist * hinzugefügt werden. Dies kann in der action-proc-Prozedur in dem Zweig erfolgen, der die proc-Anweisung verarbeitet. Die Variable * oplist * kann in der Startprozedur erstellt (und vor Abschluss zerstört) werden. Das Hinzufügen einer Funktion zum Action-Proc-Code kann folgendermaßen implementiert werden:
(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*)))
Jetzt muss für jede Operation, die in der Funktion ausgeführt wird, eine bestimmte Priorität festgelegt werden. Prioritäten werden durch die folgende Funktion festgelegt:
(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)))
Die logische Operation "und" und "oder" hat die niedrigste Priorität. Dann gibt es Vergleichsoperationen, dann Addition und Subtraktion usw. Funktionen haben die höchste Priorität.
Nun beschreiben wir den Algorithmus zum Übersetzen des Ausdrucks in den SCR. Die Funktion inf2ipn akzeptiert einen erforderlichen Parameter (Eingabeformel) und zwei optionale Parameter (Operationsstapel und Akkumulatorliste). In der Batterieliste wird das Ergebnis akkumuliert. Die Funktion durchsucht die Eingabeliste und verhält sich wie folgt:
- Wenn das nächste Element eine Zahl oder eine Variable ist, wird es in die Batterie eingegeben.
- Wenn das nächste Element eine Liste ist, wird die Funktion rekursiv auf diese Liste angewendet und das Ergebnis zur Batterie hinzugefügt.
- Wenn das nächste Element eine Operation ist, wird bei einem leeren Stapel von Operationen das nächste Element auf den Operationsstapel verschoben. Bei einem nicht leeren Operationsstapel wird die Priorität der eingehenden Operation mit der Oberseite des Operationsstapels verglichen. Wenn eine Operation mit höherer Priorität eintrifft, wird sie auf den Operationsstapel verschoben.
- Wenn eine Operation mit einer Priorität ankommt, die nicht größer als die Oberseite des Stapels ist, wird die Oberseite des Stapel von Operationen an den Akkumulator übertragen, und die neu angekommene Operation wird in den Stapel von Operationen eingegeben.
- Wenn die Eingabeliste erschöpft ist und der Operationsstapel leer ist, gibt die Funktion eine umgekehrte Batterie zurück (Anschlusszweig). Andernfalls gibt die Funktion eine umgekehrte Batterie mit einer zuvor angehängten Liste von Vorgängen vom Stapel zurück.
Die Funktion, die die Operation vom Operanden unterscheidet, ist sehr einfach - es kommt darauf an, zu überprüfen, ob das angegebene Zeichen in der globalen * oplist * -Liste enthalten ist:
(defun is-op (o) (member o (mapcar 'car *oplist*)))
Und die Übertragungsfunktion im SCR hat die Form:
(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))))))))
Sie können die Funktionalität dieser Funktion überprüfen, indem Sie sie direkt aufrufen:
(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 * +)
Das Abrufen eines Präfixeintrags von einem SCR ist recht einfach. Die Funktion ipn2inf akzeptiert den Ausdruck im SCR und den Antriebsparameter. Die Funktion funktioniert folgendermaßen:
- Wenn die Eingabeliste leer ist, wird der Laufwerkskopf zurückgegeben.
- Wenn das nächste Element eine Zahl oder eine Variable ist, wird dieses Atom an das Laufwerk angehängt.
- Wenn das nächste Element eine Operation der Arität n ist, wird eine Liste, die aus dem Symbol dieser Operation und einem umgekehrten Segment des Laufwerks der Länge n besteht, ohne die ersten n Elemente an das Laufwerk angehängt.
So sieht es im Code aus:
Überprüfen Sie den Zustand des Codes:
(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))
Jetzt muss nur noch der Handler des Zuweisungsoperators geschrieben und mit dem Prozedurhandler verbunden werden. Der Zuweisungshandler kann wie folgt implementiert werden:
(defun action-set (meat) (let ((name-var (car meat)) (r-value (i2p (cddr meat)))) `(setq ,name-var ,r-value)))
Der Fleischparameter soll sich auf die Listenzuordnung beziehen:
( = )
Die Erkennung des Zuweisungsoperators erfolgt in der Funktion action-proc, die folgende Form hat:
(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))))
Lassen Sie uns die Leistung unseres Codes überprüfen. Wir laden den Code in die Lisp-Umgebung, rufen die Startfunktion auf und übersetzen das folgende Verfahren:
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
Mal sehen, was unser Übersetzer generiert hat:
(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)))
Alles scheint richtig zu sein. Rufen wir nun unsere Prozedur auf und erhalten das erwartete Ergebnis:
(main) 25 ==> 25
Unser Übersetzer wird auch die eingebauten Funktionen korrekt handhaben. Um dies zu überprüfen, führen wir beispielsweise den folgenden Code aus:
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
Und wir bekommen:
(main) 0.499999999987039 0.866025403791922 1.0 ==> 1.0
Unser Übersetzer wird vor unseren Augen lebendig!
Wir waren jedoch sehr begeistert: Beim Streben nach dem Endziel haben wir überhaupt nicht über die Fehler nachgedacht, die der Benutzer (der Programmierer, der das Mini-Basic verwendet) machen kann. Auf eine gute Weise mussten wir sofort über Fehler nachdenken, aber wir haben gerade angefangen zu arbeiten, sind nicht zu weit gegangen und es ist nicht zu spät, Fehlerbehandlung und -diagnose in den Code einzuführen. Darüber hinaus ist es offensichtlich, dass „geringfügige Verbesserungen“ vorgeschlagen werden (unser Übersetzer verlangt beispielsweise, dass der Bediener genau eine Zeile belegt, was unpraktisch ist).
Der folgende Artikel widmet sich all diesen Fragen.
Fortsetzung folgtDer Code für diesen Artikel kann hier heruntergeladen
werden.