Essayons d'écrire en Lisp ... un traducteur d'un langage impératif simple. Non, non, je ne me suis pas trompé - c'est le traducteur. Il sera diffusé en code Lisp. Et puis ce code peut être exécuté par le système Lisp.
Ici, le service inestimable sera fourni par le fait qu'en Lisp, il n'y a pas de barrière entre le code et les données (c'est une propriété rare de certains langages de programmation appelés «homo-identité»). Mais les capacités visuelles de Lisp joueront également un rôle important.
En tant qu'implémentation, j'utiliserai HomeLisp . Les personnes intéressées peuvent adapter ce projet au Common Lisp. Je dirai tout de suite - par rapport au problème considéré, la différence significative entre Common Lisp et HomeLisp ne concerne que le traitement des lignes et des fichiers.
Téléchargez une version portable de HomeLisp ici . La documentation se trouve également sur le même site. Ceux qui le souhaitent peuvent copier le code de l'article et vérifier immédiatement les performances.
Le sujet porté à votre attention a servi de base à mon atelier au célèbre Novosibirsk LSHUP-2018 . Les résultats de l'atelier sont disponibles ici . Et puis j'ai exposé mon approche. Je suppose que le lecteur connaît le langage Lisp.
Descendre
Commençons par le «langage impératif simple» que nous diffuserons en Lisp.
La langue ne traitera que les données numériques. Le code dans ce langage se compose de fonctions (procédures qui renvoient des valeurs). Parmi ces fonctions, une devrait être appelée principale. C'est avec cette fonction que commence l'exécution du code. Mais pourquoi vous lier ainsi? Nous écrivons des fonctions dans un langage impératif, elles sont diffusées en Lisp et peuvent être utilisées avec des fonctions Lisp. Mais ne prenons pas de l'avance sur nous-mêmes ...
L'ensemble des opérateurs de langage est habituel: affectation, branchement, cycle arithmétique, sortie anticipée du cycle, entrée, sortie et appel de fonction. Cependant, syntaxiquement, un appel de fonction est exécuté comme une affectation (résultat d'un appel). Laissez les commentaires contenir un astérisque à la première position de la ligne. Le langage, bien sûr, devrait permettre de créer des fonctions récursives. Pour plus de clarté, je vais donner des exemples de code - imprimer des nombres impairs successifs et calculer leur somme:
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
Dans son esprit, c'est un langage de base. Je l'appellerai «mini-basique». Notre traducteur doit convertir le code donné en fonction Lisp suivante:
(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)))
J'aime vraiment le package itératif , qui est implémenté en tant que macro dans les packages Common Lisp professionnels. Dans HomeLisp, la fonction iter (qui implémente une grande partie des capacités de macro itération) est incluse dans le langage principal. C'est ma dépendance à l'iter qui a entraîné la traduction des cycles de notre «mini-basique» en appels iter.
Par où commencer la mise en œuvre? Commençons par sélectionner le fichier à diffuser et lisons et imprimons ce fichier ligne par ligne. Nous devrons démarrer le traducteur plusieurs fois, alors laissez ce début depuis le début être pratique. Voici à quoi pourrait ressembler cette fonction:
(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*))
La fonction a un paramètre facultatif fname - le nom du fichier dont le contenu sera diffusé. Lors de la saisie de la fonction, deux variables globales sont créées: numLine, numéro de ligne du fichier source et flagerr , l'indicateur d'état d'erreur. Avant la fin de la fonction, ces variables sont détruites (la fonction HomeLisp non définie détruit les variables globales).
Si le nom du fichier d'entrée est omis, la fenêtre de dialogue standard pour sélectionner le fichier (sysGetOpenName) est appelée. Le répertoire actuel (sysHome) est utilisé comme répertoire de démarrage. Ensuite, un caractère unique est créé pour le manipulateur de fichiers et le fichier est ouvert pour la lecture de texte. Ensuite, dans une boucle sans fin, le fichier est lu ligne par ligne (fonction getLine ). Après chaque opération, il est vérifié si une erreur s'est produite et si la fin du fichier est atteinte. Si une erreur se produit ou si la fin du fichier est corrigée, le cycle s'arrête, le fichier se ferme et s'il y a eu des erreurs, un message final s'affiche.
En fait, la lecture du fichier est effectuée par la fonction getLine :
(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)))))
Cette fonction accepte l'identifiant d'un fichier ouvert et, dans une boucle infinie, effectue les actions suivantes:
- vérifie l'état de fin de fichier. Dans ce cas, la boucle se rompt et la fonction renvoie une chaîne vide;
- le compteur de lignes de lecture augmente de un;
- la ligne suivante du fichier est lue;
- la ligne de lecture est imprimée avec la suppression des espaces possibles à droite;
- si la ligne de lecture n'est pas vide et ne contient pas d'astérisque en première position, alors elle
retourne de la fonction;
Ainsi, toutes les lignes du fichier dans leur forme d'origine tombent dans la liste de sortie.
Nous entrons dans les procédures
Maintenant, apprenons à notre code à diviser le flux d'entrée en procédures distinctes. Tout d'abord, la chaîne saisie devra être divisée en jetons (unités lexicales d'entrée indivisibles). Ce processus est appelé analyse; nous devons créer un analyseur. L'écriture d'analyseurs est un thème classique, il existe des bibliothèques d'analyseurs prêts à l'emploi et des outils spéciaux qui vous permettent de générer l'analyseur nécessaire ... Nous suivrons notre propre chemin.
Avant de décrire l'algorithme de l'analyseur, nous faisons attention au fait que tous les caractères de la chaîne d'entrée peuvent être divisés en deux classes:
- Caractères ordinaires;
- Caractères de séparation.
Ainsi, dans l'opérateur d'affectation «x = 15 + y ^ 2», les caractères x, 1,5, y et 2 sont des caractères ordinaires et les caractères «espace» , + , ^ sont des délimiteurs. En quoi un caractère normal est-il différent d'un séparateur? Séparateur - sépare toujours un jeton d'un autre. Notre opérateur d'affectation, divisé en jetons, ressemble à ceci: "x", "=", "15", "y", "^", "2" .
Comme vous pouvez le voir, tous les délimiteurs ne tombent pas dans le résultat de l'analyse (les espaces, en particulier, ne tombent pas). Nous appellerons les séparateurs qui ne tombent pas dans le résultat comme des séparateurs du premier type. Les autres séparateurs seront appelés séparateurs du deuxième type.
L'entrée de l'analyseur sera une chaîne, la sortie est une liste de jetons de chaîne. En tant que lecteur, une variable locale sera utilisée - la batterie. La batterie contient initialement une chaîne vide.
L'algorithme d'analyse peut être le suivant: nous lisons la ligne d'entrée caractère par caractère. Si vous rencontrez un personnage normal, concaténez-le avec la batterie. Si un délimiteur est trouvé, alors:
- Pour le séparateur du premier type, nous réinitialisons la valeur de la batterie (si elle n'est pas vide) dans la liste de sortie, effacez la batterie et lisons le caractère suivant;
- Pour le séparateur du deuxième type, nous vidons également la valeur d'une batterie non vide dans la liste de sortie, et après cela, nous entrons le séparateur accepté du deuxième type (en tant que jeton indépendant) dans la liste de sortie, effacez la batterie et passez à la lecture du caractère suivant.
Voici le code de l'analyseur:
(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))
En plus du paramètre requis, la fonction possède deux paramètres facultatifs: d1 contient une chaîne dont chaque caractère a un séparateur du premier type et la ligne d2 contient des séparateurs du deuxième type.
La logique du programme de la fonction analyseur est décrite ci-dessus. Il faut seulement noter qu'avant de commencer le travail, un séparateur est ajouté à la fin de la ligne d'entrée. Ceci est fait de sorte que le dernier jeton traité "se bloque" dans la batterie (la variable locale lex joue le rôle de la batterie).
Vérifions notre analyseur «en action»:
(parser "x = 15 + y^2") ==> ("x" "=" "15" "+" "y" "^" "2")
C'est vrai, non? Mais travailler avec des listes de chaînes n'est pas tout à fait Lisp. Passons de la liste des chaînes à la liste des atomes. Pour ce faire, nous avons besoin d'une fonction qui ... colle à nouveau tous les jetons dans une longue ligne (mais insère un espace entre les jetons), puis colle le crochet d'ouverture au début de cette ligne, ferme le crochet de fermeture jusqu'à la fin ... puis force Lisp à lire la liste:
(defun mk-intf (txt) (let ((lex (parser txt " ," "()+-*/\^=<>%")) (intf "")) (iter (for a in lex) (setq intf (strCat intf a " "))) (input (strCat "(" intf ")"))))
Maintenant, si nous soumettons l'opérateur d'affectation à l'entrée de la fonction mk-intf, nous obtenons:
(mk-intf "x = 15 + y^2") ==> (X = 15 + Y ^ 2)
Ce qui, vous voyez, est beaucoup plus agréable.
Modifions maintenant un peu la fonction de démarrage: cette fonction devra lire et traiter des procédures entières:
(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*))
Dans le corps de la boucle, la fonction action-proc est appelée (pour traiter la procédure), qui formera déjà le corps de la procédure acceptée sur Lisp. Le corps de la procédure, stocké en tant qu'expression S dans la variable curr-proc , est ensuite passé à l'entrée de eval . Et la fonction acceptée se «réincarne» dans l'environnement Lisp!
Que doit faire action-proc ? Cette fonction reçoit l'identifiant du fichier ouvert en paramètre. La fonction lit le fichier ligne par ligne à partir du fichier, saute les lignes vides et les commentaires, analyse le reste des lignes, le traduit sous forme de liste et génère le corps de la procédure.
Nous allons progressivement «apprendre» la génération d' action-proc . Et commençons par apprendre à notre fonction à reconnaître le début et la fin d'une procédure. Dans une mini-basique, le début de la procédure est:
proc name(p1,p2,p3)
essayez d'analyser une ligne comme celle-ci:
(mk-intf "proc name(p1,p2,p3)") ==> (PROC NAME (P1 P2 P3))
Comment la fonction action-proc doit -elle répondre à cette entrée? Naturellement, en vous assurant que la tête de la liste est un atome PROC , vous devez prendre le deuxième élément de la liste comme nom de la fonction et le troisième élément comme liste de paramètres. Le nom et la liste des paramètres doivent être stockés dans des variables locales. Lorsque l'opérateur end_proc est lu , vous devez alors former un formulaire defun avec un corps vide (jusqu'à présent) à partir du nom de la fonction et de la liste des paramètres, et renvoyer ce formulaire comme résultat. Voici à quoi ça ressemble:
(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))))
Pour la formation finale de la clause defun , un verrou inversé est utilisé. Notez que la procédure générée renverra un atome OK comme résultat.
Maintenant, nous pouvons vérifier notre code en action. Mettez le code suivant dans le fichier 0000.mbs:
proc f1(x,y) end_proc proc f2(x) end_proc
Exécutez la procédure de démarrage , sélectionnez 0000.mbs et voyez sur la console:
0001 proc f1(x,y) 0002 end_proc 0003 proc f2(x) 0004 end_proc
Si vous le souhaitez, vous pouvez vous assurer que la machine Lisp dispose désormais de deux fonctions (jusqu'ici inutiles) f1 et f2 :
(getd 'f1) ==> (EXPR (XY) (QUOTE OK)) (getd 'f2) ==> (EXPR (X) (QUOTE OK))
De plus! Ils peuvent déjà être démarrés:
(f1 1 2) ==> OK (f2 2) ==> OK
Notre traducteur a pris un premier souffle ...
Variables d'entrée, de sortie et locales
Il est maintenant temps d'enseigner à notre traducteur nouveau-né comment gérer la saisie , l' impression et les opérateurs locaux .
La façon la plus simple de gérer la saisie et l'impression. Les deux opérateurs ont la même structure syntaxique: mot-clé et variable. L' entrée opérateur x doit se transformer en une telle forme Lisp (setq x (lecture)) . En conséquence, l'opérateur print x se transforme en un formulaire (printline x) . Pour stocker ces formulaires, vous devez fournir le corps de variable local dans la fonction action-proc . Cette variable accumulera des formulaires qui effectuent des calculs de la fonction future. Alors tout est assez simple:
(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)))
Préparons maintenant ce code source sur un mini-basique:
proc f1(x,y) print x print y end_proc proc f2(x) input x print x end_proc
et essayez de le traduire ... Nous aurons deux fonctions Lisp f1 et f2 . Examinons leurs expressions de définition et vérifions qu'elles sont générées correctement:
(getd 'f1) ==> (EXPR (XY) (PRINTLINE X) (PRINTLINE Y)) (getd 'f2) ==> (EXPR (X) (SETQ X (READ)) (PRINTLINE X))
Vous pouvez appeler ces fonctions et vous assurer qu'elles fonctionnent exactement comme prévu. Que cela ne vous dérange pas que nous entrions la valeur dans la variable de paramètre - nous n'avons tout simplement pas encore de variables locales ... Ajoutons-les.
L'opérateur local peut être n'importe où dans la procédure et se produire plusieurs fois. Si l'opérateur local est rencontré lors du traitement d'une procédure, vous devez prendre une liste de variables et l'enregistrer dans une variable locale. Une fois que l'instruction end_proc est satisfaite, vous devez générer le formulaire let et y «enfermer» toutes les instructions exécutables (pour l'instant, seulement saisir et imprimer ). Voici à quoi ressemblera maintenant action-proc :
(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))))
La liste des variables locales est accumulée dans la variable loc-var . Une fois le traitement de la procédure terminé, une liste de paires du formulaire (nom 0) est construite à partir de cette liste. Dans ce cas, la duplication de noms identiques n'est pas souhaitable ... Comment l'empêcher? Bien sûr, il est possible de vérifier à chaque traitement de l'opérateur local s'il y a des noms en double (le cas échéant, donner un message d'erreur). Mais, me semble-t-il, il vaut mieux simplement éliminer les répétitions, c'est ce que les appels appellent . Maintenant, traduisons et exécutons ce programme:
proc f1(x,y) local a,b,c print x print y input a print a end_proc
Nous nous assurons que cela fonctionne exactement comme le suggère l'algorithme. Mais le plus intéressant est à venir!
De là, vous pouvez télécharger la version finale de ce que nous sommes sur w codé ...
À suivre!