Versuchen wir, in Lisp zu schreiben ... einem Übersetzer einer einfachen imperativen Sprache. Nein, nein, ich habe mich nicht geirrt - es ist der Übersetzer. Es wird im Lisp-Code ausgestrahlt. Und dann kann dieser Code vom Lisp-System ausgeführt werden.
Ein unschätzbarer Service ist hier die Tatsache, dass es in Lisp keine Barriere zwischen Code und Daten gibt (dies ist eine seltene Eigenschaft einiger Programmiersprachen, die als „Homo-Identität“ bezeichnet werden). Aber auch die visuellen Fähigkeiten von Lisp werden eine wichtige Rolle spielen.
Als Implementierung werde ich HomeLisp verwenden . Interessenten können dieses Projekt an Common Lisp anpassen. Ich werde gleich sagen - in Bezug auf das betrachtete Problem besteht der signifikante Unterschied zwischen Common Lisp und HomeLisp nur in der Verarbeitung von Zeilen und Dateien.
Laden Sie hier eine tragbare Version von HomeLisp herunter. Die Dokumentation befindet sich ebenfalls auf derselben Site. Wer möchte, kann den Code aus dem Artikel kopieren und sofort die Leistung überprüfen.
Das Thema, auf das Sie aufmerksam gemacht wurden, diente als Grundlage für meinen Workshop im berühmten Nowosibirsk LSHUP-2018 . Die Ergebnisse des Workshops finden Sie hier . Und dann habe ich meinen Ansatz dargelegt. Ich nehme an, der Leser ist mit der Lisp-Sprache vertraut.
Runter
Beginnen wir mit der „einfachen imperativen Sprache“, die wir in Lisp ausstrahlen werden.
Die Sprache verarbeitet nur numerische Daten. Code in dieser Sprache besteht aus Funktionen (Prozeduren, die Werte zurückgeben). Unter diesen Funktionen sollte man main nennen. Mit dieser Funktion beginnt die Codeausführung. Obwohl, warum binden Sie sich so? Wir schreiben Funktionen in einer imperativen Sprache, sie werden in Lisp ausgestrahlt und können zusammen mit Lisp-Funktionen verwendet werden. Aber lasst uns nicht weiterkommen ...
Die Menge der Sprachoperatoren ist üblich: Zuweisung, Verzweigung, Rechenzyklus, vorzeitiges Verlassen des Zyklus, Eingabe, Ausgabe und Funktionsaufruf. Syntaktisch wird ein Funktionsaufruf jedoch als Zuordnung ausgeführt (Ergebnis eines Aufrufs). Lassen Sie die Kommentare an der ersten Stelle der Zeile ein Sternchen enthalten. Die Sprache sollte natürlich die Möglichkeit bieten, rekursive Funktionen zu erstellen. Um es klarer zu machen, werde ich Beispiele für Code geben - aufeinanderfolgende ungerade Zahlen drucken und ihre Summe berechnen:
proc main() local s,n,k input n for i=1 to n k=2*i-1 print k s=s+k end_for print s end_proc
In seinem Geist ist es eine grundlegende Sprache. Ich werde es "Mini-Basic" nennen. Unser Übersetzer sollte den angegebenen Code in die folgende Lisp-Funktion konvertieren:
(defun main nil (let ((s 0) (n 0) (k 0)) (setq n (read)) (iter (for i from 1 to n) (setq k (- (* 2 i) 1)) (printline k) (setq s (+ sk))) (printline s)))
Ich mag das iterate- Paket, das als Makro in professionellen Common Lisp-Paketen implementiert ist. In HomeLisp ist die Iter-Funktion (die einen großen Teil der Funktionen der Makro-Iteration implementiert) in der Kernsprache enthalten. Es war meine Sucht nach Iter, die dazu führte, dass die Zyklen unseres „Mini-Basic“ in Iter-Aufrufe übersetzt wurden.
Wo soll mit der Implementierung begonnen werden? Beginnen wir mit der Auswahl der zu sendenden Datei und dem zeilenweisen Lesen und Drucken dieser Datei. Wir müssen den Übersetzer viele Male starten, also lassen Sie dies von Anfang an bequem sein. So könnte diese Funktion aussehen:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (let ((fi (gensym 'fi))) (when fname (filOpen fi fname _INPUT) (loop (getLine fi) (when (or *flagerr* (filEOF fi)) (return t))) (filClose fi) (when *flagerr* (printsline "**** ")))) (unset '*numline*) (unset '*flagerr*))
Die Funktion verfügt über einen optionalen Parameter fname - den Namen der Datei, deren Inhalt gesendet wird. Bei der Eingabe der Funktion werden zwei globale Variablen erstellt: numLine, Zeilennummer der Quelldatei und flagerr , das Fehlerstatus-Flag. Bevor die Funktion beendet wird, werden diese Variablen zerstört (die nicht gesetzte HomeLisp-Funktion zerstört die globalen Variablen).
Wenn der Name der Eingabedatei weggelassen wird, wird der Standarddialog zur Auswahl von Windows-Dateien (sysGetOpenName) aufgerufen. Das aktuelle Verzeichnis (sysHome) wird als Startverzeichnis verwendet. Als nächstes wird ein eindeutiges Zeichen für den Dateimanipulator erstellt und die Datei zum Lesen von Text geöffnet. In einer Endlosschleife wird die Datei dann Zeile für Zeile gelesen (Funktion getLine ). Nach jedem Vorgang wird geprüft, ob ein Fehler aufgetreten ist und ob das Ende der Datei erreicht ist. Wenn ein Fehler auftritt oder das Ende der Datei behoben ist, wird der Zyklus unterbrochen, die Datei wird geschlossen, und wenn Fehler aufgetreten sind, wird eine endgültige Meldung angezeigt.
Das eigentliche Lesen aus der Datei wird von der Funktion getLine ausgeführt :
(defun getLine (fil) (let ((stri "")) (loop (when (filEof fil) (return "")) (setq *numline* (add1 *numline*)) (setq stri (filGetline fil)) (printsline (strCat (format *numline* "0000") " " (strRTrim stri))) (setq stri (strATrim stri)) (unless (or (eq "" stri) (eq "*" (strLeft stri 1))) (return stri)))))
Diese Funktion akzeptiert die Kennung einer geöffneten Datei und führt in einer Endlosschleife die folgenden Aktionen aus:
- Überprüft den Status des Dateiende. In diesem Fall wird die Schleife unterbrochen und die Funktion gibt eine leere Zeichenfolge zurück.
- der Zähler der gelesenen Zeilen erhöht sich um eins;
- Die nächste Zeile der Datei wird gelesen.
- Die gelesene Zeile wird gedruckt, wobei mögliche Leerzeichen rechts entfernt werden.
- Wenn die Lesezeile nicht leer ist und an der ersten Stelle kein Sternchen enthält, ist dies der Fall
kehrt von der Funktion zurück;
Somit fallen alle Zeilen der Datei in ihrer ursprünglichen Form in die Ausgabeliste.
Wir brechen in Verfahren ein
Lassen Sie uns nun unseren Code lehren, den Eingabestream in separate Prozeduren aufzuteilen. Zunächst muss die eingegebene Zeichenfolge in Token (unteilbare lexikalische Eingabeeinheiten) unterteilt werden. Dieser Vorgang wird als Parsing bezeichnet. Wir müssen einen Parser erstellen. Das Schreiben von Parsern ist ein klassisches Thema. Es gibt Bibliotheken mit vorgefertigten Parsern und Spezialwerkzeugen, mit denen Sie den erforderlichen Parser generieren können ... Wir werden unseren eigenen Weg gehen.
Bevor wir den Parser-Algorithmus beschreiben, achten wir darauf, dass alle Zeichen der Eingabezeichenfolge in zwei Klassen unterteilt werden können:
- Gewöhnliche Zeichen;
- Trennzeichen.
Im Zuweisungsoperator "x = 15 + y ^ 2" sind die Zeichen x, 1,5, y und 2 gewöhnliche Zeichen, und die Zeichen "Leerzeichen" , + , ^ sind Begrenzer. Wie unterscheidet sich ein normales Zeichen von einem Trennzeichen? Trennzeichen - trennt immer einen Token von einem anderen. Unser Zuweisungsoperator, der in Token unterteilt ist, sieht folgendermaßen aus: "x", "=", "15", "y", "^", "2" .
Wie Sie sehen können, fallen nicht alle Trennzeichen in das Ergebnis der Analyse (insbesondere Leerzeichen fallen nicht). Wir werden Trennzeichen, die nicht in das Ergebnis fallen, als Trennzeichen des ersten Typs bezeichnen. Andere Trennzeichen werden als Trennzeichen des zweiten Typs bezeichnet.
Die Eingabe des Parsers ist eine Zeichenfolge, die Ausgabe ist eine Liste von Zeichenfolgentoken. Als Laufwerk wird eine lokale Variable verwendet - die Batterie. Die Batterie enthält zunächst eine leere Zeichenfolge.
Der Parsing-Algorithmus kann wie folgt aussehen: Wir lesen die Eingabezeile Zeichen für Zeichen. Wenn Sie einen normalen Charakter treffen, verketten Sie ihn mit der Batterie. Wenn ein Trennzeichen gefunden wird, gilt Folgendes:
- Für das Trennzeichen des ersten Typs setzen wir den Batteriewert (falls er nicht leer ist) auf die Ausgabeliste zurück, löschen die Batterie und lesen das nächste Zeichen.
- Für das Trennzeichen des zweiten Typs geben wir auch den Wert einer nicht leeren Batterie in die Ausgabeliste ein. Danach geben wir das akzeptierte Trennzeichen des zweiten Typs (als unabhängiges Token) in die Ausgabeliste ein, löschen die Batterie und lesen das nächste Zeichen.
Hier ist der Parser-Code:
(defun parser (txt &optional (d1 " ,") (d2 "()+-*/\^=<>%")) (let ((res nil) (lex "") ) (iter (for s in-string (strCat txt (strLeft d1 1))) (cond ((plusp (strInd d1 s)) (when (> (strLen lex) 0) (collecting lex into res)) (setq lex "")) ((plusp (strInd d2 s)) (when (> (strLen lex) 0) (collecting lex into res)) (collecting s into res) (setq lex "")) (t (setq lex (strCat lex s))))) res))
Zusätzlich zu dem erforderlichen Parameter verfügt die Funktion über zwei optionale Parameter: d1 enthält eine Zeichenfolge, von der jedes Zeichen ein Trennzeichen des ersten Typs enthält, und Zeile d2 enthält Trennzeichen des zweiten Typs.
Die Programmlogik der Parserfunktion ist oben beschrieben. Es ist nur zu beachten, dass vor Arbeitsbeginn ein Trennzeichen an das Ende der Eingabezeile angehängt wird. Dies geschieht so, dass der zuletzt verarbeitete Token in der Batterie „hängt“ (die lokale Variable lex spielt die Rolle der Batterie).
Lassen Sie uns unseren Parser "in Aktion" überprüfen:
(parser "x = 15 + y^2") ==> ("x" "=" "15" "+" "y" "^" "2")
Das stimmt, nicht wahr? Das Arbeiten mit Listen von Zeichenfolgen ist jedoch nicht ganz Lisp. Gehen wir von der Liste der Strings zur Liste der Atome. Dazu benötigen wir eine Funktion, die ... alle Token erneut in eine lange Zeile klebt (aber ein Leerzeichen zwischen den Token einfügt), dann die öffnende Klammer an den Anfang dieser Zeile einfügt, die schließende Klammer bis zum Ende schließt ... und dann Lisp zwingt, die Liste zu lesen:
(defun mk-intf (txt) (let ((lex (parser txt " ," "()+-*/\^=<>%")) (intf "")) (iter (for a in lex) (setq intf (strCat intf a " "))) (input (strCat "(" intf ")"))))
Wenn wir nun den Zuweisungsoperator an die Eingabe der Funktion mk-intf senden, erhalten wir:
(mk-intf "x = 15 + y^2") ==> (X = 15 + Y ^ 2)
Was viel schöner ist.
Lassen Sie uns nun die Startfunktion ein wenig ändern: Diese Funktion muss ganze Prozeduren lesen und verarbeiten:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (when fname (let ((fi (gensym 'fi))) (filOpen fi fname _INPUT) (loop (let ((curr-proc (action-proc fi))) (when (or *flagerr* (filEOF fi)) (return t)) (eval curr-proc))) (filClose fi)) (when *flagerr* (printsline "**** "))) (unset '*numline*) (unset '*flagerr*))
Im Hauptteil der Schleife wird die action-proc- Funktion aufgerufen (um die Prozedur zu verarbeiten), die den Hauptteil der bereits auf Lisp akzeptierten Prozedur bildet. Der Hauptteil der Prozedur, der als S-Ausdruck in der Variablen curr-proc gespeichert ist, wird dann an die Eingabe von eval übergeben . Und die akzeptierte Funktion wird in der Lisp-Umgebung „wiedergeboren“!
Was soll action-proc tun? Diese Funktion erhält die Kennung der geöffneten Datei als Parameter. Die Funktion liest die Datei zeilenweise aus der Datei, überspringt leere Zeilen und Kommentare, analysiert den Rest der Zeilen, übersetzt sie in eine Listenform und generiert den Hauptteil der Prozedur.
Wir werden nach und nach die Action-Proc- Generierung „lernen“. Beginnen wir damit, unserer Funktion beizubringen, den Beginn und das Ende eines Vorgangs zu erkennen. In einem Mini-Basic ist der Beginn des Verfahrens:
proc name(p1,p2,p3)
Versuchen Sie, eine Zeile wie folgt zu analysieren:
(mk-intf "proc name(p1,p2,p3)") ==> (PROC NAME (P1 P2 P3))
Wie soll die action-proc- Funktion auf diese Eingabe reagieren? Um sicherzustellen, dass der Kopf der Liste ein PROC- Atom ist, müssen Sie natürlich das zweite Element der Liste als Namen der Funktion und das dritte Element als Liste der Parameter verwenden. Der Name und die Liste der Parameter sollten in lokalen Variablen gespeichert werden. Wenn der Operator end_proc gelesen wird , müssen Sie aus dem Namen der Funktion und der Parameterliste ein defun- Formular mit einem leeren Körper (soweit) bilden und dieses Formular als Ergebnis zurückgeben. So sieht es aus:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm 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)) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm (quote OK))))
Für die endgültige Bildung der Defun- Klausel wird eine Rückwärtssperre verwendet. Beachten Sie, dass die generierte Prozedur als Ergebnis ein OK- Atom zurückgibt.
Jetzt können wir unseren Code in Aktion überprüfen. Fügen Sie den folgenden Code in die Datei 0000.mbs ein:
proc f1(x,y) end_proc proc f2(x) end_proc
Führen Sie die Startprozedur aus , wählen Sie 0000.mbs aus und sehen Sie auf der Konsole:
0001 proc f1(x,y) 0002 end_proc 0003 proc f2(x) 0004 end_proc
Wenn Sie möchten, können Sie sicherstellen, dass die Lisp-Maschine jetzt zwei (bisher unbrauchbare) Funktionen f1 und f2 hat :
(getd 'f1) ==> (EXPR (XY) (QUOTE OK)) (getd 'f2) ==> (EXPR (X) (QUOTE OK))
Außerdem! Sie können bereits gestartet werden:
(f1 1 2) ==> OK (f2 2) ==> OK
Unser Übersetzer holte tief Luft ...
Eingabe-, Ausgabe- und lokale Variablen
Jetzt ist es an der Zeit, unserem neugeborenen Übersetzer den Umgang mit Eingabe- , Druck- und lokalen Bedienern beizubringen.
Der einfachste Weg, um Eingabe und Druck zu handhaben. Beide Operatoren haben dieselbe Syntaxstruktur: Schlüsselwort und Variable. Die Bedienereingabe x sollte sich in eine solche Lisp-Form verwandeln (setq x (read)) . Dementsprechend verwandelt sich der Operator print x in ein Formular (printline x) . Um diese Formulare zu speichern, müssen Sie den lokalen Variablenkörper in der action-proc- Funktion angeben . Diese Variable akkumuliert Formulare, die Berechnungen der zukünftigen Funktion durchführen. Dann ist alles ziemlich einfach:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var 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) ))))) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm ,@body)))
Nun bereiten wir diesen Quellcode auf einer Mini-Basis vor:
proc f1(x,y) print x print y end_proc proc f2(x) input x print x end_proc
und versuchen Sie es zu übersetzen ... Wir werden zwei Lisp-Funktionen f1 und f2 haben . Schauen wir uns ihre definierenden Ausdrücke an und stellen Sie sicher, dass sie korrekt generiert werden:
(getd 'f1) ==> (EXPR (XY) (PRINTLINE X) (PRINTLINE Y)) (getd 'f2) ==> (EXPR (X) (SETQ X (READ)) (PRINTLINE X))
Sie können diese Funktionen aufrufen und sicherstellen, dass sie genau wie vorgesehen funktionieren. Lassen Sie sich nicht stören, dass wir den Wert in die Parametervariable eingeben - wir haben nur noch keine lokalen Variablen ... Fügen wir sie hinzu.
Der lokale Bediener kann sich an einer beliebigen Stelle in der Prozedur befinden und mehrmals auftreten. Wenn der lokale Operator während der Verarbeitung einer Prozedur auftritt, müssen Sie eine Liste von Variablen erstellen und in einer lokalen Variablen speichern. Nachdem die end_proc- Anweisung erfüllt ist, müssen Sie das let- Formular generieren und alle ausführbaren Anweisungen darin "einschließen" ( derzeit nur Eingabe und Druck ). So wird Action-Proc jetzt aussehen:
(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)))) (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))))
Die Liste der lokalen Variablen wird in der Variablen loc-var akkumuliert. Nach Abschluss der Verarbeitung der Prozedur wird aus dieser Liste eine Liste von Paaren des Formulars (Name 0) erstellt . Gleichzeitig ist die Vervielfältigung identischer Namen unerwünscht ... Wie kann dies verhindert werden? Natürlich ist es möglich, bei jeder Verarbeitung des lokalen Operators zu überprüfen, ob doppelte Namen vorhanden sind (ggf. eine Fehlermeldung ausgeben). Aber es scheint mir, dass es besser ist, nur die Wiederholungen zu eliminieren, was der Setof- Aufruf tut . Lassen Sie uns nun dieses Programm übersetzen und ausführen:
proc f1(x,y) local a,b,c print x print y input a print a end_proc
Wir stellen sicher, dass es genau so funktioniert, wie es der Algorithmus vorschlägt. Aber das Interessanteste liegt vor uns!
Von hier aus können Sie die endgültige Version von dem herunterladen, worauf wir gerade sind w codiert ...
Fortsetzung folgt!