Objectif : Mise en œuvre des techniques proposées dans ce document pour écrire un analyseur / interpréteur d’un micro-langage simple.
 

ENONCE :

On  donne la Grammaire Gµ suivante :

V_N = { áprog.ñ, áblocñ, áégalñ, ásuite1ñ, ásuite2ñ, ámembre droitñ, áplusñ, ásuite3ñ }
V_T = { ‘a’ , ‘b’ , ... , ‘z’ , ‘}‘ , ‘{‘ , ‘;’ , ‘L’, ‘E’ , ‘+’ , ‘*’ , ‘/’ , ‘-’ , ‘%’, ‘=’ }

 

Questions  :

1°) Construire une classe interpréteur de L(Gµ). On donne la sémantique suivante : 

(les spécifications sont fournies en langage algorithmique)

Lx correspond à lire(x) Ex correspond à ecrire(x) x = y correspond à x ¬ y a,b,c correspondent à des variables entiers relatifs + correspond à l’opérateur d’addition sur les entiers relatifs. - correspond à l’opérateur de soustraction sur les entiers relatifs. * correspond à l’opérateur de multiplication sur les entiers relatifs. / correspond à l’opérateur de quotient euclidien sur les entiers relatifs. % correspond à l’opérateur de reste euclidien sur les entiers relatifs.

On utilisera une mémoire centrale dans laquelle se trouveront les variables (dans un tableau) et une autre table contenant les noms des variables et leur adresse en mémoire centrale (table des symboles).

2°) Construire une IHM de calculatrice programmable fondée sur la classe précédente d'interpréteur du langage L(Gµ). calculatrice dans laquelle l'utilisateur peut entrer des lignes de programmes en L(Gµ) et les exécuter.
 

Interprétation des instructions Ex et Lx
Nous observons tout d’abord sur la portion de graphe de l’AEFD comment les instructions Ex et Lx sont reconnues.

Il nous faut une variable que nous nommerons etatavant qui mémorisera l’état précédent. Le symbole qui vient d’être analysé est stocké dans une variable que nous nommons symlu.

D’autre part, lorsque nous sommes en q₃, le symbole qui vient d’être analysé est un élément de {a,b,.., z}. Afin de décider s’il s’agit d’une instruction Ex ou bien Lx, il nous faut avoir mémorisé le symbole précédent qui a été analysé en passant de q₁ à q₂. Nous nommerons cette variable symprec.

Voici donc en pseudo-Delphi le code de lancement de l’interprétation de Lx ou de Ex. Ce code est à rajouter à l’AEFD précédent.
 

If (etat=q3)and(etatavant=q2)and(symprec=L)then begin {on interprète le Lx}  TabSymb[symlu] := adressecourante ;  adressecourante := adressecourante +1 ;  readln(MemC[TabSymb[symlu]]) end else {on interprète le Ex} begin  adressecourante := TabSymb[symlu];  writeln(MemC[adressecourante ]) end

 

Interprétation de l’instruction x = y oper z
Nous avons vu que l’autre façon d’arriver à l’état q₃ est d’avoir suivi l’arc q₇ à q₃.

Ce chemin correspond très exactement à l’analyse d’une instruction x=y oper z. Afin de pouvoir interpréter correctement cette instruction, nous devons avoir mémorisé les noms des variables x, y et z le long du chemin d’analyse : q1 à q4 à q5 à q6 à q7 à q3. Afin de ne pas rajouter trop de nouveaux états nous avons décidé de n'avoir qu'une transition sur un ensemble d'opérateurs  (q6 oper) à q7.

Nous regroupons alors les symboles +,-,*,/,% dans un même ensemble (Operat : set of Vt), que nous initialiserons dans la procédure d'initialisation :
Operat =['+', '-', '*', '/', '%' ]

Nous notons que :
x est connu lorsque l’AEFD est à l’état q₄ (à la fin de l’arc q₁à q₄)
y est connu lorsque l’AEFD est à l’état q₆ (à la fin de l’arc q₅à q₆)
z est connu lorsque l’AEFD est à l’état q₃ (à la fin de l’arc q₇à q₃)

Le stockage d’un troisième symbole de variable nécessite l’utilisation d’une nouvelle variable servant à le mémoriser. Nous la nommerons symavant.

En résumant la situation, nous aurons pour x=y oper z :

• z est stocké dans symlu, il est reconnu à l’état q₃.
• y est stocké dans symprec, il est reconnu à l’état q₆.
• x est stocké dans symavant, il est reconnu à l’état q₄.
• l'opérateur oper est reconnu à l’état q7,il est alors rangé dans une variable OperVar de type Vt servant à cet effet.
  

 

Interprétation de l’instruction x=y
Si nous observons la partie du graphe de l’AEFD correspondant à l’analyse de l’instruction x=y, nous remarquons que contrairement aux cas précédents ce n’est pas à l’état q₆ que nous pouvons prendre une décision.
 

Si l’état d’après q₆ est q₁, il s’agit d’une instruction x=y, si l’état d’après q₆ est q₇ il s’agit d’une instruction x=y+z.

Le chemin d’analyse d’une instruction x=y est :
q₁ à q₄ à q₅ à q₆ à q₁.

Comme dans l’analyse du problème précédent nous avons :

• ; est stocké dans symlu, il est reconnu à l’état q₁.
• y est stocké dans symprec, il est reconnu à l’état q₆.
• x est stocké dans symavant, il est reconnu à l’état q₄.

 

Voici ci-dessous les squelettes des méthodes Delphi d'une classe d'interpréteur InterpreteurLang permettant d'étendre l'analyseur en interpréteur :


type
   T_etat=imposs..fin;    Vt=char;

procedure InterpreteurLang.init_table;
{initialisation de la table des transitions de l'automate AEFD }
  
procedure InterpreteurLang.ClearMemC;
 // RAZ mémoire centrale
 
procedure InterpreteurLang.ClearTabSymb;
 // RAZ table des symboles
 
procedure InterpreteurLang.initialisations;
 // RAZ tout

{--------------------- INTERPRETEUR -------------------}

procedure InterpreteurLang.Interprete(chaine:string;var etat:T_etat);
{moteur d'analyse et d'interpretation de l'automate}

function InterpreteurLang.transition(q:T_etat;car:Vt):T_etat;
{par la table de transition :}
 
procedure InterpreteurLang.Symsuiv(var num:integer;var symlu:Vt);
{fournit le symbole suivant à analyser}

function InterpreteurLang.In_TabSymb(identif:Vt):boolean;
{indique si le symbole identif est deja dans TabSymb}



Comme notre interpréteur doit lire et analyser un texte de programme et écrire les resultats d'exécution, nous proposons d'écrire une classe qui contienne toutes spécifications nécessaires et utiles au fonctionnement d'un interpréteur, mais qui ne dépende pas de la façon dont on lit et dont on affiche les résultats. Pour cela nous construisons une classe abstraite TinterpretAbstr qui possède 2 méthodes abstraites (donc non implémentées) Lire et Ecrire.

Le soin d'expliquer comment lire ou écrire est délégué à une classe 'concrète' qui dérivera de TinterpretAbstr.

1°) Construction d’une classe abstraite d'interpréteur de L(G)

Nous reprenons toutes les procédures et fonctions du programme console et nous les transformons en méthodes de classe. Ci-dessous un diagramme UML-like de la signature de la classe TinterpretAbstr. Nous ajoutons à cette classe, en visibilité protected, les deux méthodes abstraites :

Nous reprenons dans une unit Delphi que nous nommons Uinterpreteur, les mêmes déclarations de constantes et de type que dans le programme console :

Ce qui nous donne dans Uinterpreteur la signature suivante pour la classe abstraite TinterpretAbstr :

Nous avons rajouté une méthode de filtrage du texte source permettant une saisie plus libre du texte (avec des blancs, des sauts de ligne,...) et épurant le texte entré de tous ces éléments :

Le texte suivant entré au clavier sur 8 lignes, soumis à la méthode de filtrage est restitué pour analyse une fois épuré :

Nous donnons ici la partie implementation de la unit Uinterpreteur avec les corps des méthodes : 

{ TinterpretAbstr }

   procedure  TinterpretAbstr.ClearMemC ;
   // RAZ mémoire centrale
  var  i : adresse ;
 begin
  for  i := 0  to  maxadresse  do
    MemC[i] := 0 ;
 end;
 
  procedure  TinterpretAbstr.ClearTabSymb ;
   // RAZ table des symboles
  var  i : Symbole ;
 begin
  for  i := chr(0)  to  chr(255)  do
    TabSymb[i] := 0 ;   {0 indique : variable non definie}
  end;
 
  procedure  TinterpretAbstr.init_table ;
   {initialisation de la table des transitions de l'automate AEFD }
  var
   i : t_etat ;   
   j : 0..255 ;   
   k :char ;
  begin
   for  i := imposs  to  fin  do
    for  j := 0  to  255  do
      table[i,chr(j)] := imposs ; {par défaut tout est non reconnu}
    table[0, '{' ] := 1 ;
    table[1, '}' ] :=  EtatFinal ;
   for  k := 'a' to 'z' do
   begin
     table[1,k] := 4 ;
     table[2,k] := 3 ;
     table[5,k] := 6 ;
     table[7,k] := 3 ;
   end;
    table[1, 'E' ] := 2 ;
    table[1, 'L' ] := 2 ;
    table[3, ';' ] := 1 ;
    table[4, '=' ] := 5 ;
    table[6, '+' ] := 7 ;
    table[6, '*' ] := 7 ;
    table[6, '-' ] := 7 ;
    table[6, '%' ] := 7 ;
    table[6, '/' ] := 7 ;
    table[6, ';' ] := 1 ;
  end;
  
  procedure  TinterpretAbstr.initialisations ;
   // RAZ tout
   begin
    ClearMemC ;
    ClearTabSymb ;
    init_table ;
    Operat  := [ '+' ,  '-' ,  '*' ,  '/' ,  '%'  ]
   end;
  
  function  TinterpretAbstr.transition(q :  T_etat ;  car :  Vt) :  T_etat ;
   {par la table de transition :}
   begin
   result := table[q,car] ;
  end;
  
  procedure  TinterpretAbstr.Symsuiv( var  num :integer ;var  symlu : Vt) ;
   {fournit le symbole suivant è analyser}
   begin
   if  num <= length(mot)  then
   begin
     symlu := mot[num] ;
     num := num + 1
    end
   else            {si on veut lire apres la fin}
     symlu := chr(0) ; {caractere NUL invisible     }
   end;
  
  function  TinterpretAbstr.In_TabSymb(identif : Vt) :boolean ;
   {indique si le symbole identif est deja dans TabSymb}
   begin
   if  tabsymb[identif] = 0  then
     in_tabsymb := false
    else
     in_tabsymb := true
   end;
  
  procedure  TinterpretAbstr.Exec(chaine : string ; var  etat :  T_etat) ;
   {moteur d'analyse et d'interpretation de l'automate}
  var
   symlu : Vt ;
   adressecourante : adresse ;
   symprec,symavant : Vt ;
   etavant : T_etat ;
  begin  {Interpreteur - Exec}
    numcar := 1 ;
    etat := 0 ;
    adressecourante := 1 ;   {on commence toujours a 1}
    mot :=  chaine ;
   while  (etat <> imposs) and (etat <> fin)  do
   begin
     Symsuiv(numcar,symlu) ;
     etavant := etat ;
     etat := transition(etat,symlu) ;
     {------------- partie due a l'interpretation ------------}
     if  (etat = 2) then
      symprec := symlu ;
    if  etat = 4  then
    begin
      symavant := symlu ;
     if  not  In_TabSymb(symlu) then
     begin
       TabSymb[symlu] := adressecourante ;
       adressecourante := adressecourante + 1
      end
    end;
    if  etat = 6  then
      symprec := symlu ;
    if  etat = 7  then
     if  symlu  in  Operat  then
       OperVar  :=  symlu ;
    if  (etat = 3) and (etavant = 2) and (symprec = 'L' )  then  { Lx; }
     begin
      TabSymb[symlu] := adressecourante ;
      adressecourante := adressecourante + 1 ;
      Lire(symlu,MemC[TabSymb[symlu]]) ;
    end
    else
     if  (etat = 3) and (etavant = 2) and (symprec = 'E' )  then  { Ex; }
      begin
       adressecourante := TabSymb[symlu] ;
       Ecrire(symlu,MemC[adressecourante]) ;
     end
     else
      if  (etat = 1) and (etavant = 6) then                 { x=y; }
       begin
        MemC[TabSymb[symavant]] := MemC[TabSymb[symprec]]
       end
      else
       if  (etat = 3) and (etavant = 7) then                 { x = y oper z; }
        case
         opervar  of
        '+' : MemC[TabSymb[symavant]] := MemC[TabSymb[symprec]] + MemC[TabSymb[symlu]] ;
     '-' : MemC[TabSymb[symavant]] := MemC[TabSymb[symprec]] - MemC[TabSymb[symlu]] ;
     '*' : MemC[TabSymb[symavant]] := MemC[TabSymb[symprec]] * MemC[TabSymb[symlu]] ;
     '/' : MemC[TabSymb[symavant]] := MemC[TabSymb[symprec]] div  MemC[TabSymb[symlu]] ;
     '%' : MemC[TabSymb[symavant]] := MemC[TabSymb[symprec]] mod  MemC[TabSymb[symlu]] ;
       end;
     {-------------------------------------------------------}
    end;
  end; {Interpreteur - Exec}
  
   function  TinterpretAbstr.Filtrage(Texte : string ) : string ;
   { filtrage du texte è interpréter :conservation des éléments
  du vocabulaire vt et élimination des autres 
  }
  var  s :string ;
   i :integer ;
  begin
    s := '';
   for  i := 1  to  length(Texte)  do
    if  Texte[i]  in  [ 'a' .. 'z' , ';' , '{' , '}' , 'L' , 'E' , '=' ,finmot] + Operat   then
      s := s +  Texte[i] ;
   result := s
   end;
  
  
  procedure  TinterpretAbstr.Lancer(prog : string ) ;
   { uniquement pour appeler la méthode privée Exec
   et envoyer des messages è l'utilisateur selon 
   la manière dont s'est passée l'exécution.
  }
  var  q : T_etat ;
 begin
   Exec(prog,q) ;
  if  q = imposs  then
    MessageDlg( 'Blocage, erreur de syntaxe !' +
   #13 + #10 + copy(prog,1,numcar) + '<<--' , mtError ,[mbOk], 0)
   else
   if  q = fin  then
     MessageDlg( 'Exécution terminée !' , mtInformation  ,[mbOk], 0) ;
 end;
 
  {----  le constructeur TinterpretAbstr ----}
   constructor  TinterpretAbstr.Create(fin  :  T_etat)  ;
  begin
   if  fin  in  [1..20]  then
     etatfinal := fin
    else
     etatfinal := 20 ;
    initialisations ;
  end;
  
end.  {----  fin de la unit  ----}

2°) Construction de deux classes héritant de TinterpretAbstr

Application IHM - première classe dérivée

Nous voulons écrire une application IHM utilisant la classe d'interpréteur que nous venons de construire, selon par exemple le modèle ci-dessous :

Nous afficherons les résultats par une surcharge dynamique (redéfinition) de la méthode Ecrire à travers un TMemo : 

Nous saisirons les valeurs par une redéfinition de la méthode Lire à travers une inputBox :

 
Soit la classe Tinterpreteur héritant de notre classe abstraite, qui reçoit lors de la construction d'un objet d'interpréteur la référence d'un Tmemo déjà instancié dans l'IHM afin d"afficher les résultats :

{ Tinterpreteur cas de Delphi en mode application-IHM }

Tinterpreteur = class (TinterpretAbstr)
  protected
   Affiche : Tmemo ;
  procedure  Lire(symb : Vt ;var  x :integer ) ; override;
  procedure  Ecrire(symb : Vt ; x :integer ) ; override;
 public
  constructor  Create(sortie : TMemo) ;
end;
  procedure  Tinterpreteur.Ecrire(symb : Vt ; x :integer ) ;
  begin
    Affiche.Lines.Append( '>> ' + symb + ' = ' + inttostr(x))
   end;
  
procedure  Tinterpreteur.Lire(symb : Vt ;var  x : integer ) ;
 var  InputString :string ;
 begin
   InputString :=  InputBox( 'Saisie des valeurs' ,  'Entrez : ' + symb,  '(un entier)' ) ;
  try
    x := strtoint(InputString) ;
  except
    x := 1 ;
  end
 end;
 
  {----  le constructeur Tinterpreteur ----}
   constructor  Tinterpreteur.Create(sortie :  TMemo) ;
  begin
   inherited  Create ;
    Affiche := sortie
   end;

Terminons en livrant le code source et l'organisation de l'IHM de saisie et de traitement (exe et projet complet) :