Évaluateur Mini-BASIC
Version de base

2000-01






<< BASIC >> est l'acronyme de Beginner's All purpose Symbolic Instruction Code. C'est un langage de programmation apparu en 1964 si l'on en croit http://www.fys.ruu.nl/~bergmann/history.html.



Le but de ce projet est de réaliser un évaluateur (ou un interpréteur pour une version trés minimale de ce langage. Un interpréteur et un programme écrit dans un langage donné(pour nous, ce sera Objective Caml) qui permet d'exécuter d'autres programmes écrits dans un autre langage (pour nous, ce sera BASIC). Le monde informatique fourmille de tel genre d'applications : Il s'agit dans tous ces cas d'un programme écrit dans un langage L1 chargéde réaliser les calculs ou les instructions décrits dans un second langage L2.

Dans le cadre de notre projet, L1 est Objective Caml et L2 est une version trés simplifiée de BASIC.



En supposant que le programme réalisant notre interpréteur BASIC s'appelle basic, que l'invite (le prompt) de notre système soit shell%, voici un petit exemple d'utilisation : 
shell% basic
Hello, Mini-BASIC v0.0

> 1 REM Saisie d'un nombre strictement positif
> 10 PRINT "Valeur de N"
> 11 INPUT N
> 12 IF N > 0 GOTO 20
> 13 PRINT "Valeur negative ou nulle, recommencez"
> 14 GOTO 11
> 20 PRINT "Bravo"
> RUN
Valeur de N
-123
Valeur negative ou nulle, recommencez
0
Valeur negative ou nulle, recommencez
123
Bravo
> QUIT
Bye bye, Mini-BASIC
shell%
Et voici une brève description de ce que contient cette session.

Principes généraux d'interprétation

Le mécanisme d'interprétation que nous allons mettre en oeuvre, aussi bien pour ce qui concerne les commandes que les programmes BASIC, prend en entrée une suite de caractères et produit l'effet attendu décrit par cette ``phrase''. Un interpréteur obéit donc aux ordres de son utilisateur, mais il n'obéit pas àn'importe quel ordre. Il y a peu de chances que la suite de caractères Patron, la même chose produise l'effet attendu. Pour exécuter correctement une commande ou une instruction, l'interpréteur doit savoir analyser le contenu des suites de caractères et y reconnaître un ordre dont il possède la procédure (ou fonction) d'exécution. De son côté, l'utilisateur se fera bien comprendre si, et seulement si, il obéit lui-même àcet ensemble de règles.

En un mot, l'interpréteur et l'utilisateur doivent parler un langage commun : langage de commande et langage de programmation. Un langage est définit par un lexique (le vocabulaire) et une syntaxe (engencement des unités lexicales entre elles).

Les suites de caractères contenant des commandes ou instructions s'appelle leur syntaxe concrète. L'interpréteur analyse cette syntaxe concrète en deux temps : il commence par isoler les unités lexicales (c'est l'analyse lexicale) pour contrôler ensuite la correction de la syntaxe (c'est l'analyse syntaxique). Cette double phase d'analyse réussit si et seulement si la suite de caractère proposée appartient bien au langage attendu.

Àl'issue de cette analyse, l'interpréteur produit une structure, en g'enéral arborescente, appellée syntaxe abstraite. C'est cette structure qui est traitée par les fonction d'exécution des commandes ou des programmes BASIC.



Description du langage BASIC

Un programme BASIC est une suite de lignes. Chaque ligne est constituée d'un numéro suivi d'une instruction. Il n'y a donc qu'une seule instruction par ligne de programme.

Jeu d'instructions
Notre version microscopique de BASIC ne connaîtra qu'un jeu trés restreint d'instruction.
  1. Une instruction d'affectation permettant d'attribuer àune variable la valeur d'une expression.
  2. Une instruction de saut inconditionnel permettant de poursuivre l'exécution du programme àune ligne choisie.
  3. Une instruction de saut conditionnel permettant de poursuivre l'exécution du programme àune ligne choisie si un test est satisfait ; àla ligne suivante du programme sinon.
  4. Une instruction d'entrée permettant la saisie et la mémorisation dans une variable d'une valeur.
  5. Trois instructions de sortie permettant l'affichage de la valeur d'une expression, d'une suite de caractères ou d'un retour-chariot.
  6. Une instruction vide qui permet d'inserer des commentaires dans les programmes sous forme d'une suite de caractères.
  7. Une instruction d'arrêt indiquant la fin de l'exécution.
Syntaxe
Pour noter chaque instruction, on utilise une ensemble de symboles et mots réservés :


= pour l'affectation
GOTO pour le saut inconditionnel
IF et GOTO pour le saut conditionnel
INPUT pour l'entrée
PRINT et PRINTLN pour les sorties
REM pour les commentaires
END pour l'arrêt
Àl'exception de l'instruction d'arrêt, les instructions du langage BASIC manipulent d'autres éléments du langage tels les variables, les expressions, les numéros de ligne, etc. Pour définir plus précisément la syntaxe des instructions, les tableau ci-dessous introduit une dénomination générique pour ces autres éléments.


dénomination désignation
num numéro de ligne
ident (nom de) variable ou identificateur
exp expression (arithmétique)
test test (comparaison)
string chaîne de caractères
any suite (presque) quelconque de caractères

En utilisation ces désignations générique, nous pouvons donner une définition plus précise du lexique et de la syntaxe des instructions. Le lexique est définit selon le formalisme des expressions régulières. La syntaxe est définie selon le formalisme des grammaires BNF.



Syntaxe formelle du langage

Lexique

   
Symboles réservés: \n = ( ) + - * / < > <> <= >= "
   
Mots clé: END GOTO IF INPUT LET PRINT PRINTLN REM
   
Constantes entières (num): [0-9]+
   
Identificateurs (ident): [A-z]+
   
Chaînes de caractères (str): " [^ "]* "
   
Commentaire (any) [^ \n]*
   

Implantation
l'analyseur lexical du langage sera implantéen utilisant l'outil ocamllex.



Grammaire

Expressions arithmétiques

     
exp ::= num
     
  | ident
     
  | exp + exp
     
  | exp - exp
     
  | exp * exp
     
  | exp / exp
     
  | - exp
     
  | ( exp )
     


Expressions booléennes (tests)

     
test ::= test = test
     
  | test <> test
     
  | test > test
     
  | test < test
     
  | test <= test
     
  | test >= test
     


Instructions

     
inst ::= END
     
  | GOTO num
     
  | IF test GOTO num
     
  | INPUT ident
     
  | LET ident = exp
     
  | PRINT exp
     
  | PRINTLN
     
  | REM any
     

Implantation
l'analyseur syntaxique du langage sera implantéen utilisant l'outil ocamlyacc.



Syntaxe abstraite

La syntaxe abstraite est définie comme une structure O'Caml permettant de représenter sous forme de valeurs manipulables par des fonctions O'Caml les construstions syntaxiques définies par la grammaire.



Expressions arithmétiques

Les quatres opérateurs arithmétiques sont représentés par

 
type bin_op = PLUS | MINUS | MULT | DIV
Les arbres d'expressions sont représentés par le type somme
 
type exp =
    ExpInt of int 
  | ExpVar of string
  | ExpOpp of exp
  | ExpBin of exp * bin_op * exp

Tests

Les relations de comparaisons sont représentés par
 
type bin_rel = EQ | NEQ | LE | LT | GE | GT
Les tests sont simplement des triplets
 
type test = exp * bin_rel * exp

Instructions

Dans la syntaxe abstraite des instructions, les identificateurs redeviennent des chaînes de caractères et les constantes numériques ont étéconverties en entiers binaires. On distingue aussi, pour raison de typage, entre l'instruction d'affichage de la valeur d'une expression d'avec l'instruction d'affichage d'une chaînes de caractères.
 
type inst = 
    Rem of string
  | Goto of int
  | Gosub of int
  | Print_e of exp
  | Print_s of string
  | Println
  | Input of string 
  | If of test * int 
  | Let of string * exp
  | Return
  | End

Syntaxe des commandes

Chaque commande est terminée par un retour-charriot.

     
cmd ::= num inst \n
     
  | LIST \n
     
  | LOAD str \n
     
  | QUIT \n
     
  | RUN \n
     

La syntaxe abstraite des commandes est simplement donnée par
 
type cmd = 
  Quit
| List
| Run
| Load of string
| PLine of (int * inst)

Principe et description de l'interpréteur

L'interpréteur est une boucle d'interaction (avec un utilisateur) qui attend une commande et l'exécute jusqu'à ce que la commande soit QUIT. L'interpréteur maintient l'état d'une variable contenant un programme BASIC dit programme courant.

Le tableau ci-dessous décrit l'exécution de chacune des commandes.

   
num inst insérer (àsa juste place) la ligne de programme dans le programme courant. Si la ligne num existe déjà, elle est remplacée.
   
LIST afficher les lignes du programmes courant précédées chacune de leur numéro.
   
LOAD str ouvrir, lire et interpréter le contenu du fichier de nom str.
   
QUIT quitter l'interpréteur.
   
RUN exécuter le programme courant.
   

Implantation
La fonction ins_line insère une nouvelle ligne dans la liste contenant le programme courant. Elle assure que la liste reste triée.

La fonction print_prog implante l'affichage du programme courant.

La fonction exec_prog implante la fonction d'interprétation du programme BASIC courant selon les principes exposés au paragraphe suivant.

La fonction load_prog implante le chargement de lignes de programmes àpartir d'un fichier.



Interprétation des programmes

Environnement

Les calculs programmés en BASIC manipulent des variables. Chacune de ces variables est sensée être liée à une valeur (entiére, dans notre cas). Pour réaliser cette liaison, on utilise un environnement. D'un point de vue abstrait, on peut voir un environnement comme une fonction des l'ensemble des (noms de) variables dans l'ensemble des valeurs (entiéres). Cette fonction peut n'être pas partout définie. Si s est un environnement et x un nom de variable, s(x) désigne la valeur associée à x.
Les environnements évoluent au fur et à mesure de l'exécution des instrutions d'un programme BASIC. On notera s(x)¬v l'environnement obtenu en rajoutant la nouvelle liaison entre la variable x et la valeur v. Si une valeur de x était déjàdéfinie par s alors l'ancienne valeur est oubliée au profit de la nouvelle.

Type de données abstrait
L'environnement et ses fonctions de manipulations sont implentés selon la discipline des types de données abstraits. C'est-à-dire que l'on définit la structure d'environnement et ses fonctions de manipulation dans un module et que l'on masque, par le mécanisme des fichiers d'interface, ne laissant accessible àl'utilisateur du module que les déclarations.

env.mli 
(* -- types *)
type value 

type env

(* -- primitives *)
val new_env : unit -> env

val get_int_value : string -> env -> int

val add_value : string -> value -> env -> unit 

val value_of_int : int -> value

Évaluation des expressions

Si e est une expression, on note || e ||s sa valeur compte tenu de la valeur des variables donnée par l'environnement s. Soient n une constante numérique, x une variable et e1 et e2 deux epressions. La valeur de || e ||s est définie selon la forme de e par les équations récursives suivantes :
|| n ||s = n
|| x ||s = s(x)
|| e1 + e2 ||s = || e1 ||s + || e2 ||s
|| e1 - e2 ||s = || e1 ||s - || e2 ||s
|| e1 * e2 ||s = || e1 ||s × || e2 ||s
|| e1 / e2 ||s = || e1 ||s / || e2 ||s
|| - e1 ||s = - || e1 ||s
 

Implantation
La fonction d'évaluation des expressions est implantée par la fonction (O'Caml) eval\_exp de type exp -> env -> int.



Évaluation des tests

Le principe d'évaluation des tests est analogue à celui des expressions. Soit r une des comparaisons permettant d'écrire un test, on a
|| e1 r e2 ||s = || e1 ||s r || e2 ||s
 

Implantation
La fonction d'évaluation des tests est implantée par la fonction (O'Caml) eval\_test de type env -> test -> bool.



Interprétation des instructions

Outre l'environnement nécessaire à la gestion des variables, les instructions d'un programme BASIC manipule un canal d'entrée et un canal de sortie. On modélise ces canaux par des listes. La notation n®stdout modélisera l'écriture (i.e. l'affichage) de l'entier n ; la notation n¬stdin modélisera la lecture (i.e. la saisie) de l'entier n.

Chaque instruction a des incidences sur l'environnement ou les canaux d'entréou de sortie. De plus chaque instruction détermine quelle sera sa suivante dans la poursuite de l'exécution. On modélise l'exécution d'un programme par une table de transition, donnée fonction de la forme de l'instruction courante.
(Inst. cour.) (Num. lig.) (Env.) (Entrée) (Sortie)
         
LET x = e i s stdin stdout
  i+1 s(x)¬|| e ||s stdin stdout
         
         
GOTO n i s stdin stdout
  n s stdin stdout
         
         
IF t GOTO n
(1)
 
i s stdin stdout
  n s stdin stdout
(1) si || t ||s = true        
         
IF t GOTO n
(2)
 
i s stdin stdout
  i+1 s stdin stdout
(2) si || t ||s = false        
         
INPUT x i s n¬stdin stdout
  i+1 s(x)¬n stdin stdout
         
         
PRINT e i s stdin stdout
  i+1 s stdin || e ||s®stdout
         
         
PRINTLN i s stdin stdout
  i+1 s stdin \n®stdout
         
L'exécution s'arrète lorsque l'instruction courante est END.



Représentation abstraite des programmes

Un programme est une suite de lignes composée chacune d'un numéro de ligne et d'une instruction. On utilisera deux façons de représenter le programmes :
  1. une liste de couples de type (int * inst) list qui sera la structure manipulée par les commandes d'éditions de programme. Cette liste est supposée toujours triée par ordre croissant de numéros de lignes ;
  2. un tableau de type inst array qui sera créée par la commande d'exécution et sera utilisée par la fonction d'interprétation.
Àchaque demande d'exécution du programme courrant, les instructions contenues dans la liste sont recopiées dans un tableau. L'ordre est lignes doit, bien entendu, être respectéet les numéros de lignes sont remplacés, dans les instructions de saut, par l'indice correspondant dans le tableau.
La prétraitement des programmes est réaliséen deux passes :
  1. la liste est parcourue pour recopie des instructions dans le tableau ET construction d'une liste d'association entre numéros de lignes originaux et indice dans le tableau ;
  2. le tableau est parcouru pour remplacement des numéros de lignes par les indices associés pour chaque instruction de saut.
Implantation
La fonction ld_prog, de type (int * Syntabs.inst) list -> Syntabs.inst array implante ce prétraitement.

La fonction exec_inst, de type bool ref -> Env.env -> int ref -> Syntabs.inst -> unit, implante chacune des transitions décrites dans la table ci-dessus, àl'exception de l'instruction End qui fait passer la valeur du premier argument (de type bool ref) àvrai.

La fonction exec_prog, de type (int * Syntabs.inst) list -> unit, implante sous forme d'une boucle while l'itération des transitions décrites dans la table ci-dessus. La boucle cesse àl'occurence de l'instruction END.



Organisation et compilation des source de l'application

On peut classer les divers types de données et fonctions nécessaire àla réalisation de l'interprète par thèmes : Ce classement reflète la structure générale du logiciel. On organisera l'ensemble des sources de l'application en différents modules respectant cette structure.

Pour créer un module, on rassemble dans un fichier ses différents composants : définitions de types et de fonctions. Si l'on ne désire pas que l'utilisateur d'un module ait accés aux définitions des composants d'un module, mais seulement aux déclarations de quelques uns d'entre eux, on rassemble les déclarations de ce que l'on veut rendre visible dans un fichier d'interface. Nous utiliserons ce mécanisme dans le cas de la définition et de la gestion des valeurs et environnements.

Les fichiers contenant les définition, dits fichiers d'implanation, ont l'extension .ml, les fichiers d'interface, contenant des déclaration, ont l'extension .mli. Un module est constituéd'un fichier d'implantation et d'un fichier d'interface portant le même nom et différenciés par leur extension. Le fichier d'interface peut être absent si l'on ne désire pas restreindre la visibilités descomposants du module. Le nom d'un module est le nom des fichiers constituant le module, privéde leur extension et oùl'initiale est mise en majuscule.
Par exemple, le module de gestion des environnements est constituédes fichiers env.ml et env.mli, le nom de ce module est Env.



Organisation

Voici les différents modules composant notre application. Les éléments constituant chacun ont déjàétédécrits. Nous ne mentionnerons donc ici que l'organisation générale, les noms de fichier et de modules correspondant.



Syntaxe abstraite

Module: Syntabs

Fichiers: syntabs.ml, pas de fichier d'interface.

Types définis: bin_op exp bin_rel test inst cmd.



Analyse lexicale

Module: Lexer

Fichiers: lexer.mll

Dépendances: module Parser (voir ci-dessous)

Règles définies: lexer



Analyse syntaxique

Module: Parser

Fichiers: parser.mly

Dépendance: module Syntabs

Règle définie: cmd_line, de type Syntabs.cmd



Valeurs et environnement

Module: Env

Fichiers: env.ml env.mli

Dépendances: aucune

Types abstraits exportés: value et env

Fonctions exportées: 
val new_env : unit -> env
val get_int_value : string -> env -> int
val add_value : string -> value -> env -> unit 
val value_of_int : int -> value

Évaluation

Module: Eval

Fichiers: eval.ml, pas de fichier d'interface

Dépendances: modules Syntabs Env

Principales fonctions définies : 
val eval_exp : Syntabs.exp -> Env.env -> int
val eval_test : Env.env -> Syntabs.exp * Syntabs.bin_rel * Syntabs.exp -> bool
val exec_inst :
  bool ref -> Env.env -> int ref -> int Stack.t -> Syntabs.inst -> unit
val ld_prog : (int * Syntabs.inst) list -> Syntabs.inst array
val exec_prog : (int * Syntabs.inst) list -> unit

Affichages

Module: Printer

Fichiers: printer.ml, pas de fichier d'interface

Dépendances: Syntabs

Principales fonctions définies: 
val print_exp : Syntabs.exp -> unit
val print_test : Syntabs.exp * Syntabs.bin_rel * Syntabs.exp -> unit
val print_inst : Syntabs.inst -> unit
val print_prog : (int * Syntabs.inst) list -> unit

Commandes

Module: Cmd

Fichiers: cmd.ml, pas de fichier d'interface

Dépendances: Syntabs Eval Printer Lexer Parser

Fonctions définies: 
val ins_line : 'a * 'b -> ('a * 'b) list -> ('a * 'b) list
val load_prog : (int * Syntabs.inst) list ref -> string -> unit
val exec_cmd : (int * Syntabs.inst) list ref -> Syntabs.cmd -> bool ref -> unit

Programme principal

Fichier: basic.ml

Source:
basic.ml 
open Cmd ;;
open Lexer ;;
open Parser ;;

let loop () =
  let lp = ref [] in
  let x = ref false in
    print_string "\nHello, Mini-BASIC v0.0\n\n";
    flush stdout;
    while not !x do 
      print_string "> "; flush stdout;
      let c = 
        cmd_line lexer (Lexing.from_string ((input_line stdin)^"\n")) 
      in
        try
          Printexc.print (exec_cmd lp c) x
        with _ -> ()
    done;
    print_string"\nBye bye, Mini-BASIC\n"
;; 

loop()
;;
Notez l'appel àla fonction loop en fin de fichier.



Compilation

Pour compiler l'exécutable de notre interpréteur, plutôt de d'avoir àinvoquer le compilateur ocamlc, ou les outils ocamllex et ocamlyacc, pour chacun des fichiers intervenant dans l'application, nous utiliserons la commande make.

Cette commande permet de décrire dans un fichier un ensemble de commande àinvoquer ainsi que l'ordre dans lequel ce doit être fait. Par défaut, le nom du fichier contenu la informations nécessaires àla commande make est Makefile (notez la majuscule initiale). Voici un fichier Makefile permettant de compiler l'exécutable basic :
Makefile 
SYNTABS = syntabs.cmo

PARSER = parser.ml parser.cmi parser.cmo lexer.ml lexer.cmo

OTHERS = env.cmi env.cmo eval.cmo printer.cmo cmd.cmo

ALLCMO = syntabs.cmo parser.cmo lexer.cmo env.cmo eval.cmo printer.cmo cmd.cmo

all: $(SYNTABS) $(PARSER) $(OTHERS)
        ocamlc -o basic $(ALLCMO) basic.ml

clean:
        rm *.cmi *.cmo parser.ml parser.mli lexer.ml

# regles explicites pour O'Caml
.SUFFIXES : .mll .mly
.SUFFIXES : .mli .ml .cmi .cmo 

.mll.ml:
        ocamllex $<
.mly.ml:
        ocamlyacc $<
.mly.mli:
        ocamlyacc $<
.mli.cmi:
        ocamlc -c $<
.ml.cmo:
        ocamlc -c $<
This document was translated from LATEX by HEVEA.