Retour
LFCInter - A C interpreter

 

Voir la documentation qui est en Français.
Les distributions sont disponibles à la fin de cette page.

This is release 1.0 of a C interpreter I have developped as final learning project of my master.

It has the following features :

Unfortunatly, it is quite slow because it tokenizes the source code on the fly. A future version (???) may include a first pass tokenizer ...

all using GCC-2.7.0,
All files are copyrighted by me but are fully PUBLIC DOMAIN. So you can use it as you want. But PLEASE, keep my name somewhere and FULLY documents all changes you have made.

Download ...

 

Présentation

Ce programme est un Domaine Public: Il peut être diffusé librement temps que tous les fichiers de cette distribution sont inclus, sans que mon copyright n'ait été modifié. Toutes les modifications faites pour supprimer un bug ou pour porter ce code vers une autre plateforme DOIVENT ETRE CLAIREMENT IDENTIFIEES DANS LE CODE. De plus, je vous serais reconnaissant de m'avertir de telles modifications...

Voici donc le résultat de 6 mois de programmation, pendant mes heures de loisir...

Le développement :
Le langage C++ a été choisi. "L'approche objet" a été utilisée lorsqu'elle simplifiait la programmation comme pour la gestion des mots clefs ou des erreurs. Une programmation plus classique a été utilisée lors de certaines tâches afin de diminuer le code: Par exemple, les opérateurs des calculs, comme '+', '-', ... auraient pu être des opérateurs surchargés pour chaque classe de représentation des valeurs mais le code nécessaire était trop important !
Afin de garantir la portabilité sur plusieurs plate-formes, GCC a été utilisé (version 2.7.0 disponible sur le CD Fresh Fish 10 pour Amiga). Ce compilateur du 'Domaine Public', donc gratuit, est disponible sur toutes les machines, du simple PC jusqu'aux plus puissantes mainframes. En plus de suivre correctement la norme, le code généré comporte peu de bugs...

Le développement a été fait sur :

Portabilité :

LFCInter a principalement été écrit pour les systèmes où les entiers et les pointeurs ont la même taille (indispensable lors de convertions entier <-> pointeur mais aussi nécessaire aux opérateurs de comparaison)... C'est le cas de tous les systèmes 32 bits, certains 64 bits. Comme d'habitude, le problème se pose sur PC où certains modes de compilation autorisent des entiers sur 16 bits et des pointeurs sur 32 bits.
L'utilisation de l'option '-fatal' permet un test en temps réel de tels débordements et provoque une erreur en cas de perte de précision.
MICRO-SUCKER est encore passé par là !!

La compilation sur le MicroVaxII m'a permis de tester la portabilité vers les plate-formes UNIX (aucun problème supplémentaire sur le code par rapport à la compilation sur Amiga, sauf pour quelques fonctions comme expliqué plus loin). Les environnements ciblés lors du développement ont toujours été l'AmigaDOS et UNIX.
La compilation sous MS-DOS par le BORLAND C++ 4.52 n'a été nécéssaire que pour la démonstration sur un portable PC. Les modifications nécessaires ont été faites uniquement lorsqu'elles n'entraînaient pas des incompatibilités avec les autres environnements, sinon les portions de codes ont été supprimés (#ifndef __BCPLUSPLUS__). De plus, n'ayant pas de machine sous cet OS insipide et anachronique chez moi, il est évident que cette version a été moins testée et comporte, sans doute, plus de bugs que les autres.
Sur les systèmes plus ou moins apparentés à UNIX, en utilisant GCC, le seul problème potentiel est l'inexistence de certaines fonctions (par exemple isiso() sur le VAX) ou encore des noms différents pour une même fonction (stricmp() qui devient strcasecmp() pour les compilateurs 'POSIX compliant').

Structures et classes importantes

    class _token {
    public:
        _token(const char *x);
        _token();

        int operator * ();
        operator const char * ();
        _token operator ++ ();
        _token operator ++ (int);
        void saute(const char *);
        string obj();

        bool definition();
        bool interne();

        int hash;

    protected:
        const char *ptr;
        short int val;
        size_t len;

    private:
        void construit( bool );
    };

Cette classe, dont les instances peuvent être utilisées comme on le ferait avec des pointeurs, implémente en elle-même le 'parser'. Son champ principal
const char *ptr;
pointe sur le premier caractère de l'objet en cours d'évaluation. Il est 'protected' et, en aucun cas, il ne doit être modifié directement car lui sont associés les champs
size_t len;
qui contient la longueur de l'objet, et
short int val;
qui contient la 'valeur symbolique' correspondante. Cette valeur entière, définie sous forme d'énumération dans le fichier "Token.h", accélère les tests de syntaxe par la suite.
On distingue les valeurs 'smbl_id' qui indique que l'objet est un identificateur et 'smbl_icn' pour signifier la fin du fichier source ou que l'instance n'est pas initialisée. A chaque modification de 'ptr' ces champs sont mis-à jour par la méthode construit().
Dans cette classe, se trouve aussi

    class _rep {
    public:
        _repval val;
        const char type() const;

        _rep();
        _rep(const int , const char );
        _rep(const long );
        _rep(const char );
        _rep(void *, const char, const string vers);

        string info;

        bool nonnull(const char *);
    protected:
        char typebase;
    };

Cette classe de "représentation de valeurs", contient, en plus des valeurs en elles-mêmes, son type. Le 'type de base', c'est à dire celui qui caractérise comment la valeur est mémorisée, est accessible par la méthode type() et peut prendre les valeurs suivantes

    struct _var {
        _var(_var *, const string &, const string &, const int);
        ~_var();

        virtual void operator = (_rep )=0;
        virtual _rep repval(const char *)=0; // Retourne la valeur stockée
        virtual void *refval()=0; // Retourne une reférence sur cette valeur
    protected:
        void veriftype(_rep &);
        _var *succ;

    public:
        string nom;     // Nom du symbole
        string type;    // Type de ce symbole
        int h;      // Hash code pour ce symbole

        friend _var *trouve_symbole( const _var *, const string &, int);
    };

struct _var et ses dérivées _var_int, _var_char, _var_fonc, _var_ptr permettent de mémoriser les variables. La structure de base contient les champs permettant d'identifier la variable (nom, type,...) ainsi que la définition des méthodes utilisée pour obtenir la valeur mémorisée ou une référence sur celle-ci. Chaque classe dérivée contient un champ 'val' qui est l'espace de stockage pour le contenu de la variable. Le champ 'succ' sert à lier les symboles ensemble (voir la structure _tablesmb) et 'h' contient le hash code du nom pour accélérer les recherches.

    class _resallouee {
    void *data;
    _resallouee *succ;

     public:
    _resallouee( _resallouee *, void * );
    ~_resallouee();

    friend _var *ajoute_symbole( _var **, const string &,
            const string &,  const char *, void *, int);
    };

Cette classe mémorise les différents blocs de mémoire associés à un tableau. Ainsi, ils seront libérés lors de sa destruction.
Cette classe ne comporte que 2 champs :

 
    struct _tablesmb {
    _tablesmb( _tablesmb * );
    ~_tablesmb();

    _var *var;      // premier symbole de la liste
    _tablesmb *parent;  // Tds précedente
    };

Plutôt que d'utiliser des tables de symboles statiques comme le font la plupart des compilateurs ou des interpréteurs, j'utilise des tables dynamiques constituées d'une liste simplement chaînée, gérée par cette structure. La fonction trouve_symbole() permet de trouver un symbole dans la table courante, dans celle des blocs parents ou enfin dans la table des symboles globaux.

   template  class LFDynaStack {
     private:
      /*
       *  Segments de données
       */
      struct LFDSData {
          LFDSData *suivant, *precedent;
          T *data;
      } *premier, *dernier, *courant;

      /*
       * Index
       */
      int nbreparseg; // Nombre d'objets par segment
      int maxidx;     // Nombre d'objets dans la pile
      int cidx;       // Idx de l'objet courrant

     public:
      LFDynaStack(int);
      ~LFDynaStack();

      bool Push(T);
      T Pop();

      T &operator[](int);

      int length();
      int current();
    };

Cette classe implémente une pile de données homogènes. Au lieu d'allouer les données une par une comme il faudrait le faire avec une liste doublement chaînée, ce qui a tendance à fragmenter la mémoire (et à faire ramer les PC !), elles sont regroupées en blocs. Le nombre d'allocation/libération étant diminué, l'exécution des fonctions utilisant des piles, comme lors de calcul, est accélérée...
Les blocs sont chaînés entre eux (structure LFDSData). Le champ 'cidx' mémorise quelle est la dernière donnée accédée et 'courant' dans quel bloc elle se trouve. Comme la majorité des accès à ce genre de pile est séquenciel, ces champs évitent de nombreuses recherches de blocs.
Note : Lorsque l'on tente d'accéder à une donnée qui n'existe pas (index hors limite), une donnée créée par le constructeur par défaut est renvoyée.
Cette classe dispose des méthodes et des opérateurs suivants:

 

Comment est interprété le source?

Voici les différentes étapes effectuées lors du lancement d'LFCInter :

  1. Décodage et mémorisation des arguments de l'interpréteur,
  2. Lecture et stockage dans le buffer du fichier à interpréter,
  3. Parcours rapide du buffer à la recherche des symboles globaux qui sont stockés dans la table globale,
  4. Construction des paramètres de la fonction main(), argc et argv grâce aux arguments restant dans la ligne de commande,
  5. interprétation de la fonction main(), qui provoquera l'interprétation des fonctions qu'elle appelle...

L'interprétation est elle-même assurée par les fonctions :

Les calculs

Cette B.N.F. est une adaptation de celle fournie dans la documentation du BORLAND C++ 4.0 (entre parenthèses se trouve la priorité de chaque 'couche'.)
  (-11) expression ::= exp_affect {[, exp_affect ]}
    Le résultat de l'expression est la valeur de la derniere exp_affect.

  (-10) exp_affect ::= exp_un opp_aff exp_affect
           ::= expr_cond

    avec opp_aff '=','*=','/=','%=','+=','-=','&=','^=','|=','<<=','>>='
     exp_un doit être une référence.

  (-9)  expr_cond ::= exp_OU_log ? exp_OU_log : expr_cond
           ::= exp_OU_log

  (-8)  exp_OU_log ::= exp_OU_log || exp_ET_log
        ::= exp_ET_log

  (-7)  exp_ET_log ::= exp_ET_log && exp_OU_incl
           ::= exp_OU_incl

  (-6)  exp_OU_incl ::= exp_OU_incl | exp_OU_excl
            ::= exp_OU_excl

  (-5)  exp_OU_excl ::= exp_OU_excl ^ exp_ET
            ::= exp_ET

  (-4)  exp_ET ::= exp_ET & exp_egal
           ::= exp_egal

  (-3)  exp_egal ::= exp_egal == exp_rel
         ::= exp_egal != exp_rel
         ::= exp_rel

  (-2)  exp_rel ::= exp_rel opp_rel exp_dcl
        ::= exp_dcl

    avec opp_rel '<','>','<=','>='

  (-1)  exp_dcl ::= exp_dcl >> exp_add
        ::= exp_dcl << exp_add
        ::= exp_add

  (0)   exp_add ::= exp_add + exp_mul
        ::= exp_add - exp_mul
        ::= exp_mul

  (1)   exp_mul ::= exp_mul   exp_un
        ::= exp_mul / exp_un
        ::= exp_mul % exp_un
        ::= exp_un

  (2)   exp_un ::= opp_un exp_un
           ::=  exp_posf

    avec opp_un '++','--','&','*','+','-','~','!'

  (3)   exp_posf ::= exp_prim
         ::= exp_posf++
         ::= exp_posf--
         ::= exp_posf [expr_cond]{[expr_cond]}
                        Valeur d'un tableau

  (4)   exp_prim ::= valeur_littéral
         ::= variable
         ::= fonction (...)     Appel de fonction
         ::= ( exp_affect )

L'entête du fichier LFCI_Cal.cxx contient plus d'informations sur les différences entre cette BNF et celle du BORLAND (généralement des erreurs dans la BNF incluse dans la documentation de ce compilateur !).
Si cette BNF permet de décrire formellement le langage, la transposer directement en code C est totalement inadapté à un interpréteur. Par exemple, prenons le cas de la couche de niveau 0:
      (0)   exp_add ::= exp_add + exp_mul
            ::= exp_add - exp_mul
            ::= exp_mul
Si l'on suit la BNF "à la lettre", le programme doit rechercher le DERNIER signe '+' ou '-' pour séparer 'exp_add' et 'exp_mul'.
Dans le cas de l'expression "2+5*-3", il trouvera d'abors le '-' et devra déterminer s'il s'agit bien du '-' binaire ou du '-' unaire. Pour ce faire, il doit avoir 'parsé' tout le début de l'expression ! Dans ce cas c'est non, donc le programme recherche le symbole précédent et trouve le '+', et à nouveau, il doit à nouveau chercher si cet opérateur est binaire. En plus, s'il n'y a aucune optimisation, il reparsera une nouvelle fois l'expression depuis le début, et la même chose se passera pour toutes les couches... Quelle perte de temps !
Plutôt que d'utiliser ce genre de code, j'ai préféré utiliser un 'remix' entre une BNF restreinte et du code utilisant la méthode des "priorités des opérateurs". Voici donc cette BNF restreinte, codée dans les fichiers LFCI_Cal.cxx et LFCI_icl.cxx :
    reponse ::= exp_aff {, exp_aff}
    codé dans la fonction eval().

    exp_aff ::= reférence {oppaff exp_cond}
    exp_aff ::= exp_cond
    codé dans la fonction affectation().

    exp_cond ::= exp_binaire ? exp_cond : exp_cond
    exp_cond ::= exp_binaire
    codé dans la fonction conditionnel().

    exp_binaire ::= exp_un {[opérateur_binaire exp_un]}
    codé dans la fonction binaire().

    exp_un ::= [{pré-opérateur}] exp_posf
    codé dans la fonction lectunaire().

    exp_posf ::= exp_prim [{post-opérateur}]
    codé dans la fonction lectunaire().

    exp_prim ::= valeur_littéral
         ::= variable
         ::= fonction (...)     Appel de fonction
         ::= ( exp_affect )
    codé dans la fonction CalcLexer().

Les limitations de la version actuelle

Il est évident qu'un tel projet est complexe et demande beaucoup de temps. C'est pourquoi, cet interpréteur comporte certaines limitations par rapport au C standard :

Bugs connus

Conclusion

Il est évident qu'un tel projet ne peut être parfait en si peu de temps de développement, et il doit rester encore quelques bugs. Même si LFCInter 1.0 n'est pas un produit terminé, beaucoup des objectifs sont atteints :

La réalisation de ce projet m'a aussi apporté des connaissances nouvelles :

Annexe A: Description des fichiers sources

Annexe B: Liste des fonctions supportées

Note: Certaines fonctions ne sont pas disponnibles sur certaines plate-formes (si l'OS hôte ne les possèdent pas...).

Fonctions d'entrées sorties

printf(), sprintf(), scanf(), putchar(), puts(), gets(), getchar(), flushstdout(),

Fonctions de types

isdigit(), islower(), isspace(), ispunct(), isupper(), isalpha(), isxdigit(), isalnum(), isprint(), isgraph(), iscntrl(), isascii(), isiso(), toupper(), tolower(), toiso(),

Fonctions de chaînes

strcat(), strchr(), strcmp(), strcpy(), strerror(), strlen(), strncat(), strncmp(), strncpy(), strrchr(), strdup(), stricmp(), strnicmp(), strcasecmp(), strncasecmp(), strpbrk(), strstr(), strcoll(), strcspn(), strspn(), strtok(), strtol(),

Fonctions de gestion de la mémoire

realloc(), malloc(), free(), swab(), memchr(), memcmp(), memcpy(), memmove(), memset(), memccpy(),

Autres fonctions

atexit(), atoi(), time(), ctime(), clock(), sleep(), system(),

 

Attention, ce sont des archives : si votre navigateur affiche des caractères bizards, demandez lui de sauvegarder le contenu de ce qui est pointé (généralement, il suffit d'appuiller sur [SHIFT] en même temps que vous cliquez sur un lien).
Warning, following links point to archives files : if your browser display stranges characters, save the content of the link (Hold [SHIFT] key when clicking on a link).

Code source (tgz, 34 Kb)
Les commentaires du code sont en Français.
Code's comments are only in French, but I think the code itself is easy to understand.

Documentation & exemples (tgz, 12kb)
La documentation est uniquement en Français.
The documentation is only in French, but examples may be usefull.

exécutable Amiga (lha, 83kb)
Exécutable pour Amiga 68k : testé sur mon 1000 et mon 4000. L'ixemul.library v41.2+ est requise ainsi que sans doute un Workbench 2.0+ (il me semble que c'est nécessaire à l'ixemul.library mais je n'ai jamais testé sous 1.x).
Executable for Amiga 68k computers : tested on my 1000 & 4000. ixemul.library v41.2+ is need (and I think a 2.0+ system too).

exécutable pour Sparc/Solaris7 (tgz, 119 kb). Exécutable pour station Sparc sous Solaris 7(ben, si ca ne fonctionne pas sur votre station (OS différent par exemple), recompilez les sources)
Executable for SparcStation under Solaris7 (if it doesn't work on your station, you should recompile source code).