Skip to content

Latest commit

 

History

History
228 lines (192 loc) · 8.02 KB

readme.md

File metadata and controls

228 lines (192 loc) · 8.02 KB
Raw

Compilateur et machine virtuelle LISP

Réalisé en M1 AIGLE à l'Université Montpellier 2 par Thibaud Colas.

Ce projet contient un compilateur LISP -> Assembleur et une machine virtuelle exécutant le code assembleur généré.

Démarrage express

  • (load "go.lisp") Charge tout le code.
  • (make-machine) Créé la machine 'mv de taille 10000.
  • (run-express machine code code-optionnel) Charge et compile le code passé en paramètre et renvoie le contenu de R0.
  • Exemple : (run-express 'mv '(f 4) '(defun f (x) (+ 1 x)))

Arborescence du code source

Racine :

  • go.lisp charge le code de la machine et du compilateur et lance des tests.
  • Les répertoires /machine, /compilateur et /tests contiennent respectivement le code de la machine, du compilateur et des tests.

Répertoire machine:

  • machine.lisp contient les fonctions principales de la machine virtuelle.
  • instructions.lisp contient les instructions gérées par la machine.
  • fonctions.lisp et /fonctions contiennent les fonctions d'abstraction du fonctionnement de la machine, de gestion de ses composants mémoire / propriétés / étiquettes / pile / exécution.

Répertoire compilateur:

  • compilateur.lisp contient la fonction principale du compilateur ("compilation").
  • cas.lisp et /cas contiennent les différents cas de la compilation.

Répertoire test:

  • tests.lisp et /tests contiennent les tests de base livrés avec la MV.
  • fonctions.lisp contient les différentes fonctions de test.

Capacités du compilateur

  • Les opérations arithmétiques: +, -, *, /
  • Les opérateurs de comparaison: =, !=, <, >, <=, >=
  • Les structures de condition: if et cond
  • Les opérateurs booléens: and, or
  • La création de fonctions et lambda-expressions: defun, lambda
  • La déclaration de variables: setf, let
  • Les structures de contrôle: while, until, progn
  • La récursivité, double récursivité, récursivité terminale

Jeu d'instructions de la machine virtuelle

  • Transfert registres <> mémoire
    • MOVE source cible
  • Gestion de la pile
    • PUSH source
    • POP cible
  • Opérations arithmétiques entre registres
    • ADD source cible
    • SUB source cible
    • MULT source cible
    • DIV source cible
  • Opérations arithmétiques registres - valeurs
    • INC cible
    • DEC cible
  • Sauts
    • JMP cible
    • JSR etiquette
  • Sauts conditionnels
    • CMP un deux
    • JL cible
    • JEQ cible
    • JG cible
    • JLE cible
    • JGE cible
    • JNE cible
  • Gestion de la machine
    • RTN
    • NOP
    • ERR

Structure de la machine virtuelle

  • nom : Nom de la machine.
  • R0, R1, R2, R3 : Registres.
  • BP : Base Pointer initialisé à 100, pile montante.
  • SP : Stack Pointer, si pile vide SP = BP.
  • FP : Frame Pointer
  • DPP : Drapeau de comparaison "plus petit".
  • DE : Drapeau de comparaison "égalité".
  • DPG : Drapeau de comparaison "plus grand".
  • taille : Taille allouée à la mémoire (pile + tas + code).
  • memtab : Mémoire de la machine.
  • PC : Program Counter, compteur ordinal, position dans le code.
  • LC : Load Counter, position du chargement du code.
  • etiq : Table de hashage pour les étiquettes.
  • etiqNR : Table de hashage des étiquettes non résolues.

Guide d'utilisation

Depuis le répertoire racine, (load "go.lisp") charge le code de la machine et celui du compilateur. gotest.lisp y ajoute une mv 'mvtest et une batterie de tests.

Compilation:

  • (compilation '(code en lisp))
    Retourner du code ASM au format de la machine virtuelle.

Machine virtuelle:

  • (make-machine nom taille affmachine)
    Créé une machine, paramètres optionnels (nom par défaut : 'mv).

  • (print-machine nom)
    Affiche les valeurs principales de l'infrastructure de la machine.

  • (aff-zone nom deb fin)
    Affiche le contenu de la mémoire entre deb et fin.

  • (load-machine nom code)
    Charge le code ASM dans la machine à l'adresse du LC.

  • (run-machine nom)
    Lance la machine au PC et renvoie le contenu de R0.

Fonctions principales

Fonction principale du compilateur

    (defun compilation (exp &optional (env ()) (fenv ())  (nomf ()) )
      (let ((arg (if (atom exp) () (cdr exp))))
        (cond
         ((atom exp) (compilation-litt exp env fenv nomf))
         ((member (car exp) '(+ - * /)) (compilation-op exp env fenv nomf))
         ((member (car exp) '(< > = <= >= )) (compilation-comp exp env fenv nomf))
         ((is-cas exp 'and) (compilation-and arg (gensym "finAnd") env fenv nomf))
         ((is-cas exp 'or) (compilation-or arg (gensym "finOr") env fenv nomf))
         ((is-cas exp 'if) (compilation-if arg env fenv nomf))
         ((is-cas exp 'cond) (compilation-cond arg (gensym "fincond") env fenv nomf))
         ((is-cas exp 'progn) (compilation-progn arg env fenv nomf))
         ((is-cas exp 'loop) (compilation-boucle arg env fenv nomf))
         ((is-cas exp 'setf) (compilation-setf arg env fenv nomf))
         ((is-cas exp 'defun) (compilation-defun arg env fenv nomf))
         ((is-cas exp 'let ) (compilation-let arg env fenv nomf))
         ((is-cas exp 'labels) (compilation-labels arg env fenv nomf))
         ((and (consp (car exp)) (eql (caar exp) 'lambda)) (compilation-lambda exp env fenv nomf))
         (`(function ,(car exp)) (compilation-appel exp env fenv nomf))
        )
        )
      )

Fonction principale de la machine virtuelle

    (defun run-machine (&optional (nom 'mv) (aff ()))
      (set-mem-lc nom '(HALT))
      (let ((nbfun 0))
      (loop while (mv-running nom)
        do
        (if (in-fun nom) 
            (saut-fonction nom nbfun)
          (exec-inst nom (get-mem-pc nom) aff)
          )
        )
      )
      (if (mv-overflow nom) 
          (error "Débordement de pile")
        (get-reg nom :R0))
      )

    (defun exec-inst (mv exp &optional (aff ()))
      (let ((inst (car exp))
        (param (cadr exp))
        (param-bis (caddr exp)))
        (if (null exp)
        (mv-nop mv)
          (case inst
        ('MOVE (mv-move mv param param-bis))
        ('ADD (mv-add mv param param-bis))
        ('SUB (mv-sub mv param param-bis))
        ('MULT (mv-mult mv param param-bis))
        ('DIV (mv-div mv param param-bis))
        ('PUSH (mv-push mv param))
        ('POP (mv-pop mv param))
        ('INCR (mv-inc mv param))
        ('DECR (mv-dec mv param))
        ('JMP  (mv-jmp mv param))
        ('CMP  (mv-cmp mv param param-bis))
        ('JEQ (mv-jeq mv param))
        ('JL (mv-jl mv param))
        ('JLE (mv-jle mv param))
        ('JG (mv-jg mv param))
        ('JGE (mv-jge mv param))
        ('JNE (mv-jne  mv param))
        ('JSR (mv-jsr mv param))
        ('RTN (mv-rtn mv))
        ('FENTRY (mv-nop mv))
        ('FEXIT (mv-nop mv))
        ('ERR (mv-err mv))
        (otherwise (mv-err mv exp))
        )
          )
        (if (not (null aff)) (format t "~S~%" (get-mem-pc mv)))
        (dec-pc mv)
        )
      )

Benchmark de l'exécution du code généré

F : (DEFUN FACT (N) (IF (<= N 1) 1 (* N (FACT (- N 1)))))
Real time: 0.028569 sec.
Run time: 0.024159 sec.
Space: 58672 Bytes
OK : "Factorielle" : (FACT 9) = 362880

F : (DEFUN FACT-RT (N &OPTIONAL (ACC 1)) (IF (<= N 1) ACC (FACT-RT (- N 1) (* ACC N))))
Real time: 0.029055 sec.
Run time: 0.029024 sec.
Space: 72284 Bytes
OK : "Factorielle récursive terminale" : (FACT 11) = 39916800

F : (DEFUN FIBO (N) (IF (< N 2) N (+ (FIBO (- N 1)) (FIBO (- N 2)))))
Real time: 0.45251 sec.
Run time: 0.443046 sec.
Space: 1081392 Bytes
GC: 2, GC time: 0.021165 sec.
OK : "Fibonacci" : (FIBO 10) = 55

F : (DEFUN FIBO-RT (N) (LABELS ((CALC-FIB (N A B) (IF (= N 0) A (CALC-FIB (- N 1) B (+ A B))))) (CALC-FIB N 0 1)))
Real time: 0.040858 sec.
Run time: 0.039991 sec.
Space: 96176 Bytes
OK : "Fibonacci récursive terminale" : (FIBO-RT 12) = 144