John COLIBRI

Interprète d'Expression - John COLIBRI.

• mots clé:interprète - compilateur - analyse syntaxique et lexicale - grammaire - BNF, EBNF
  
• logiciel utilisé: Windows XP, Delphi 6.0
  
• matériel utilisé: Pentium 1.400Mhz, 256 M de mémoire
  
• champ d'application: Delphi 1 à 6 sur Windows, Kylix
  
• niveau: débutant en Pascal et Delphi
  
• uses:
  
• plan:
  
  • Introduction
    
  • Un premier interprète
    
  • Un interprète de fonction
    
  • Améliorations
    
  • Télécharger
    
  • Références
    

1 - Introduction

• un calcul direct
  
• un construction d'un arbre symbolique suivi de son interprétation
  

2 - Un premier interprète simple

2.1 - Principe

• description de la notation EBNF
  
• l'explication parallélisme entre EBNF et les procédure d'un analyseur
  
• le principe d'une machine à pile
  
• un programme effectuant l'analyse et l'exécution d'un petit programme
  

Ici nous partirons de la grammaire des expressions, puis nous générerons l'analyseur syntaxique et créerons l'interprète manuellement.

2.2 - Un Interprète direct simple

Il faudra:

• analyser la chaîne et isoler les symboles "3", "+", "4", "*" et "5". Ce travail sera réalisé par un analyseur lexical
  
• vérifier que l'expression est légale. Par exemple "3++ 5" serait illégal. La vérification sera effectuée par un analyseur syntaxique
  
• évaluer l'expression: l'expression est transformée en une structure ou un programme qui évalue le résultat.
  

• nous définissons un énuméré qui représente tous les symboles qui nous intéressent. Dans notre cas:

  Pour une expression plus complexe, nous pourrions ajouter:

  • d'autres types e_float_litteral, e_string_litteral
    
  • d'autres opérateurs: e_SHR_symbol
    
  • le concept de variable e_identifier_symbol
    
  • les instruction (e_IF_symbol), les sous-programmes (e_PROCEDURE_symbol...)
    
• nous isolons les symboles par une double boucle;
  
  • une boucle qui saute ce qui ne nous intéresse pas
    
  • une boucle qui concatène les caractères qui nous intéressent:
    
  • par exemple, pour récupérer un nombre entier:

    // -- throw away blanks           while (m_buffer_index< m_buffer_size) and (m_pt_buffer[m_buffer_index]= ' ') do             inc(m_buffer_index);           // -- concatenate digits           l_numeric_string:= '';           while (m_buffer_index< m_buffer_size) and (m_pt_buffer[m_buffer_index] in ['0'..'9']) do           begin             l_numeric_string:= l_numeric_string+  m_pt_buffer[m_buffer_index];             inc(m_buffer_index);           end;

    
    
• voici alors la procédure qui récupère le type du symbole et son contenu:

  procedure c_scanner.read_symbol;       const k_blanks= [' ', chr(9)];             k_returns= [chr(13), chr(10)];             k_blanks_returns= k_blanks+ k_returns;             k_digits= ['0'..'9'];       procedure get_blanks;         var l_start_index: Integer;         begin           l_start_index:= m_buffer_index;           while (m_buffer_index< m_buffer_size) and (m_pt_buffer[m_buffer_index] in k_blanks_returns) do             inc(m_buffer_index);         end; // get_blanks       procedure get_number;         var l_start_index: Integer;         begin           l_start_index:= m_buffer_index;           while (m_buffer_index< m_buffer_size) and (m_pt_buffer[m_buffer_index] in k_digits) do             inc(m_buffer_index);           m_symbol_type:= e_integer_symbol;           m_symbol_string:= f_extract_string_start_end(l_start_index, m_buffer_index- 1);           m_integer_value:= StrToInt(m_symbol_string);         end; // get_number       procedure get_operator(p_operator_type: t_symbol_type);         begin           m_symbol_type:= p_operator_type;           m_symbol_string:= m_pt_buffer[m_buffer_index];           Inc(m_buffer_index);         end; // get_operator       begin // read_symbol         get_blanks;         if m_buffer_index< m_buffer_size           then begin               case m_pt_buffer[m_buffer_index] of                 '0'..'9' : get_number;                 '(' : get_operator(e_opening_parenthesis_symbol);                 ')' : get_operator(e_closing_parenthesis_symbol);                 '+' : get_operator(e_plus_symbol);                 '-' : get_operator(e_minus_symbol);                 '*' : get_operator(e_times_symbol);                 '/' : get_operator(e_slash_symbol);                 else display_error('unknown character '+ m_pt_buffer[m_buffer_index]);               end; // case             end           else begin               m_symbol_type:= e_end_symbol;               m_symbol_string:= '';             end;       end; // read_symbol

  
  

• nous commencerons par utiliser la grammaire simple suivante:

  start= expression .     expression= [ '+' | '-' ] term { ( '+' | '-' ) term } .         term= factor { ( '*' | '/' ) factor } .             factor= NUMBER | '(' expression ')' .

  Sans rentrer dans le détail de ce formalisme, vous noterez que les règles les plus emboîtées sont exécutées en priorité. Dans le cas de l'expression:

  1+ 2* 3* 4

  le terme multiplicatif 2* 3* 4 est évalué en premier, puis l'expression additive 1+ 24. C'est le même principe que les boucles emboîtées:

  for pays:= 1 to 10 do   for ville:= 1 to 100 do     recense_population ;

  pour chaque pays, la boucle FOR ville est exécutée entièrement avant d'incrémenter pour le pays suivant. De même, pour notre grammaire, la multiplication a la précédence sur l'addition.

• nous créons les procédures qui analysent l'expression conforme à cette grammaire:

  PROCEDURE parse_start;      PROCEDURE parse_expression;          PROCEDURE parse_term;              PROCEDURE parse_factor;         BEGIN           CASE f_symbol_type OF             e_NUMBER_symbol :                  read_symbol;             e_opening_parenthesis_symbol :                  BEGIN                   // -- skip "("                   read_symbol;                   parse_expression;                   check(e_closing_parenthesis_symbol);                   // -- skip ")"                   read_symbol;                 END; // n             ELSE display_error('NUMBER, (');           END; // case            END; // parse_factor            BEGIN // parse_term         parse_factor;         WHILE f_symbol_type IN [e_times_symbol, e_divide_symbol] DO         BEGIN           read_symbol;           parse_factor;         END; // WHILE {       END; // parse_term        BEGIN // parse_expression       IF f_symbol_type IN [e_plus_symbol, e_minus_symbol]         THEN BEGIN             // -- unary "+" and "-"             read_symbol           END; // IF [       parse_term;       WHILE f_symbol_type IN [e_plus_symbol, e_minus_symbol] DO       BEGIN         read_symbol;         parse_term;       END; // WHILE {     END; // parse_expression   BEGIN // parse_start     parse_expression;   END; // parse_start

  Le parallélisme entre la grammaire et l'appel des procédures PASCAL est immédiat. Nous pouvons générer ce type de code manuellement, ou utiliser un "compilateur de compilateur", ce qui est le cas ici: à partir du texte de la grammaire, un con-compilateur génère automatiquement le texte ci-dessus.

  Dans ce texte:

  • read_symbol est une procédure qui appelle read_symbol de l'analyseur lexical
    
  • f_symbol_type est le type du symbole courant
    
  • check est une procédure qui vérifie que le symbole courant est bien du type souhaité et qui lit le symbole suivant si c'est le cas
    
  • display_error affiche l'erreur
    

Pour l'interprétation

• dans le cas de la grammaire simple, l'analyse syntaxique peut être accompagnée d'une évaluation:
  • chaque fois que nous trouvons une chaîne numérique nous calculons sa valeur binaire
    
  • ces valeurs numériques sont remontées par les procédures de l'analyseur qui retourne, en final, la valeur numérique:
    
• voici un exemple pour calculer un terme:

  procedure parse_term(var pv_term: Integer);           procedure parse_factor(var pv_factor: Integer);             begin               with p_c_scanner do               begin                 case m_symbol_type of                   e_integer_symbol :                       begin                         pv_factor:= StrToInt(m_symbol_string);                         read_symbol;                       end;                   e_opening_parenthesis_symbol :                       begin                         read_symbol;                         parse_expression(pv_factor);                         if m_symbol_type= e_closing_parenthesis_symbol                           then read_symbol                           else display_error('manque )');                       end;                   else display_error('attend fact: k, var, (: '+ m_symbol_string);                 end; // case               end; // with p_c_scanner             end; // parse_factor           var l_save_multiply_operator: t_symbol_type;               l_next_factor: Integer;           begin // parse_term             with p_c_scanner do             begin               parse_factor(pv_term);               while m_symbol_type in [e_times_symbol, e_slash_symbol] do               begin                 l_save_multiply_operator:= m_symbol_type;                 read_symbol;                 parse_factor(l_next_factor);                 case l_save_multiply_operator of                   e_times_symbol : pv_term:= pv_term* l_next_factor;                   e_slash_symbol : pv_term:= pv_term div l_next_factor;                 end; // case l_save_multiply_operator               end; // while m_symbol_type             end; // with p_c_scanner           end; // parse_term

  
  

3 - Un interprète plus complexe

3.1 - Objectif

Il faut donc ajouter:

• des opérateurs plus compliqués: "<", "<=" etc
  
• la notion de variable: nous désignons par un nom une valeur
  
• plusieurs types de variables: des entiers, des réels, des booléens
  
• une suite d'instructions d'affectation
  
• des fonctions prédéfinies, telles que SIN(30), EXP(3, 5)
  

start= { assignment } .   assignment= NAME ':=' expression ';' .     expression= simple_expression           [ ('=' | '<>' | '<' | '<=' | '>' | '>=' ) simple_expression ] .       simple_expression= [ '+' | '-' ] term { ('+' | '-' | OR ) term } .         term= factor { ('*' | '/' | DIV | AND ) factor } .           factor= NUMBER | TRUE | FALSE | NAME | NOT factor | '(' expression ')'               | [ SIN | COS ] '(' expression ')' | EXP '(' expression ',' expression ')' .

3.2 - Principe

• l'analyseur lexical est un peu plus complexe, puisqu'il doit à présent gérer le nom des variables, plusieurs types de valeurs littérales.
  
• l'analyseur syntaxique a été dérivé à nouveau de notre grammaire et ne présente pas de grande nouveauté.
  
• pour l'évaluation, cela se complique un peu:
  
  • il faut stocker les valeurs de nos variables
    
  • les opérations doivent tenir compte du type des données
    

• l'analyseur syntaxique produit un arbre syntaxique
  
• un évaluateur parcourt cet arbre et stocke les résultats dans une mémoire
  

notre arbre aurait l'allure suivante:

Si nous évaluons cet arbre de bas en haut,

• nous commençons à la racine "+"
  
• il faut évaluer les deux sous arbres
  
  • la valeur du sous arbre "4" est "4"
    
  • l'autre sous arbre est "*". Il faut évaluer d'abord ses sous-arbres
    
    • supposons que taille ait la valeur 5
      
    • l'autre sous-arbre a la valeur 3.14
      
    le noeud "*" a donc la valeur 15.7
    
  le noeud "+" a alors la valeur 19.7
  

• le nom de la variable à gauche de ":=" (left hand side, ou lhs)
  
• l'expression qui calcule la valeur de la variable (right hand side ou rhs)
  

est alors transformés par notre analyseur syntaxique en:

Pour gérer nos variables:

• nous créons une table qui va mémoriser la valeur de chaque variable
  
• chaque cellule contient
  
  • le nom
    
  • le type (entier, réel, booléen)
    
  • la valeur de la variable
    
• la structure permet:
  
  • l'ajout
    
  • le stockage du type et de la valeur
    
  • la recherche par nom
    

• nous balayons l'arbre syntaxique dans l'ordre des instructions
  
• si une variable n'existe pas, nous l'allouons dans la table des variables
  
• l'évaluation de l'expression de droite est effectués, exactement comme pour notre premier exemple, sauf que:
  • si un facteur est un nom de variable, nous allons chercher sa valeur dans la table
    
  • les calculs tiennent compte des types des variables:
    
    • + * etc ne sont permis que pour les valeurs numériques
      
    • AND OR NOT ne sont permis que pour les booléens
      
    • etc
      

Notez que:

• les types et les valeurs des deux premières instructions ont été calculés
  
• la troisième variable a été allouée, mais comme nous n'avons pas encore évalué la valeur du membre de droite, nous ne connaissons encore ni le type ni la valeur de la variable supérieur
  

Lors de l'évaluation, les valeurs sont stockées à la fois dans l'arbre et dans la mémoire des variables. Il faut pouvoir:

• stocker la valeur
  
• lire la valeur
  

• le type, défini comme un énuméré (e_integer_type, e_real_type, e_boolean_type)
  
• des membres m_integer_value, m_real_value, m_boolean_value
  
• les procédures de lecture (f_integer_value ...) et d'écriture (set_integer_value ...)
  

3.3 - Schéma du traitement

3.4 - Codage

• u_symbol_definition
  
• u_c_scanner
  
• u_c_data_value
  
• u_c_ast_tree
  
• u_c_instruction_list
  
• u_c_parser
  
• u_c_variable_list
  
• u_c_interpreter
  

3.4.1 - Les symboles: u_symbol_definition

• la conversion entre une ponctuation "+" en son symbole e_plus_symbol
  
• la conversion d'un mot clé DIV en son symbole e_DIV_symbol
  

3.4.2 - L'analyseur lexical: u_c_lexical

Prenons les deux instructions suivantes comme example:

la trace d'analyse est la suivante:

3.4.3 - L'arbre syntaxique: u_c_ast_tree

Les membres de c_node sont:

• m_name (situé dans c_basic_object) contient le symbole lu:
  
  • pour les valeur littérales, cette STRING permettra de récupérer la valeur binaire
    
  • pour les variables, le nom permettra de rechercher la valeur de la variable dans la table des variables
    
• m_node_type permettra de tester le type d'opération (plutôt que de comparer des chaînes)
  
• m_c_data_value ne sera utilisé que lors de l'évaluation des valeur
  

3.5 - La liste des instructions: u_c_instruction_list

Nous avons utilisé une liste chaînée, car c'est la classe que nous avions utilisé pour présenter le pattern INTERPRETER des Gof. Nous utiliserions actuellement plutôt une tStringList pour ce type de codage.

Dans les deux cas, chaque c_instruction contient:

• dans m_name le nom de la variable à gauche de ":="
  
• dans m_c_rhs_expression la racine de l'arbre syntaxique correspondant au membre à droite de ":="
  

3.5.1 - L'analyse syntaxique: u_c_parser

Nous ajoutons alors manuellement la création des noeuds de l'arbre syntaxique. Le code pour les expressions, par exemple, est le suivant: