Implémentation des machines abstraites en PASCAL
Une déclaration de variable en PASCAL se fait par
VAR <Li> : Type;
où <Li> désigne une liste d'identificateurs.
SOIT (SOIENT) se traduit par VAR
Les objets simples
Equivalents des objets Z --> PASCAL
Z PASCAL
ENTIER INTEGER
CAR CHAR
CHAINE STRING
BOOLEEN BOOLEAN
Machines abstraites
Les listes linéaires chaînées
Pour définir des listes linéaires chaînées en PASCAL il faut choisir une implémentation.
Implémenter, c'est choisir une représentation mémoire ( généralement statique ou dynamique ) et traduire les opérations de la machine abstraite dans cette représentation.
Il suffit de remplacer LISTE par Pointeur et rajouter au niveau de l'en-tête du programme Pascal dans laquelle on définira le type Pointeur.
Les vecteurs
La déclaration Z
SOIT <Li> : VECTEUR (Limit1, Limit2, ...)
se traduit par
VAR <Li> : ARRAY [1..Limit1, 1..Limit2, ...] OF INTEGER;
La machine-caractères
Une façon d'implémenter la machine-caractères est de lui associer une chaine de caractères.
La machine-nombres
Une façon d'implémenter la machine-nombres est de lui associer un vecteur d'entiers.
-------Z--------- -------PASCAL------
TANTQUE Cond : WHILE ( Cond ) DO
BEGIN
{ instructions } ===> { Instructions }
END
FINTANTQUE
--------------Z---------------
POUR V:= Exp1, Exp2 [, Exp3] :
{ Instructions }
FINPOUR
Si Exp3 est absent ou égale 1
|
|
V
--------PASCAL---------
FOR V:= Exp1 TO Exp2 DO
BEGIN
{ Instructions }
END
Si Exp3 <> 1 :
|
|
V
----------PASCAL------
V := Exp1;
WHILE ( V <= Exp2 ) DO
BEGIN
{ Instructions } ;
V := V + Exp3
END;
----------Z---------- -------PASCAL---------
SI Cond : IF Cond
THEN
BEGIN
{ Instructions } { Instructions }
END
[SINON ===> [ELSE
BEGIN
{ Instruction } ] { Instructions }
FSI END]
La grammaire des Z-expressions est incluse dans la grammaire PASCAL.
--------Z-------- ------PASCAL------
LIRE(V1, V2, ...) ===> READLN(V1, V2, ...)
-----------Z----------- --------PASCAL----------
ECRIRE(Exp1, Exp2, ...) ===> WRITELN(Exp1, Exp2, ...)
Même syntaxe
------------Z-----------------
ACTION Nom ( P1, P2, ...)
SOIENT
{ Définition des objets locaux
et des paramètres }
DEBUT
{ Instructions }
END
|
|
V
--------------------PASCAL--------------------
PROCEDURE Nom ( VAR P1: typ; VAR P2:typ, ...);
VAR
{ Définition des objets locaux }
BEGIN
{ Instructions }
END
----------------Z-----------------
FONCTION Nom ( P1, P2, ...) : Type
SOIENT
{ Définition des objets locaux
et des paramètres }
DEBUT
{ Instructions }
END
|
|
V
---------------------PASCAL------------------------
FUNCTION Nom ( VAR P1: typ; VAR P2:typ, ...) : Type;
VAR
{ Définition des objets locaux }
BEGIN
{ Instructions }
END
--------------------Z-----------------
SOIENT
{ Objets locaux et globaux }
{ Annonce des modules }
DEBUT
{ Instructions }
FIN
Module 1
Module 2
...
Modules n
|
|
V
------------------PASCAL---------------
PROGRAM Pascal;
VAR
{ Objets locaux et globaux }
{ Définition des modules }
Module 1
Module 2
...
Module n
BEGIN
{ Instructions }
END.
Implémentation de la machine-caractères
TYPE Typemcar = RECORD
Chaine : STRING; % Chaine de caracatères %
Ind_mcar : BYTE % Indice %
END;
PROCEDURE Creer_mcar ( VAR Mcar : Typemcar; Chaine :STRING);
BEGIN
Mcar.Chaine := Chaine;
Mcar.Ind_mcar := 0
END;
PROCEDURE Lirecar (VAR Mcar: Typemcar; VAR C : CHAR );
BEGIN
Inc(Mcar.Ind_mcar);
C := Mcar.Chaine[Mcar.Ind_mcar]
END;
FUNCTION Nbrcar( Mcar : Typemcar) : INTEGER;
BEGIN
Nbrcar := LENGTH(Mcar.Chaine);
END;
Implémentation de la machine-nombres
TYPE T= ARRAY[1..255] OF INTEGER;
TYPE Typemnom = RECORD
V : T; % Tableau %
Ind_mnom : BYTE; % Indice %
Long : BYTE; % Nombre d'éléments %
END;
PROCEDURE Creer_mnombre ( VAR Mnombre : Typemnom; V :T; Nbr : BYTE);
BEGIN
Mnombre.V := V;
Mnombre.Ind_mnom := 0;
Mnombre.Long := Nbr;
END;
PROCEDURE Lirenombre (VAR Mnombre: Typemnom; VAR Nombre : INTEGER );
BEGIN
Inc(Mnombre.Ind_mnom);
Nombre := Mnombre.V[Mnombre.Ind_mnom]
END;
FUNCTION Nbrnombre( Mnombre : Typemnom) : INTEGER;
BEGIN
Nbrnombre := Mnombre.Long;
END;
Implémentation des listes linéaires chaînées
Dynamique
TYPE
Typeelem = INTEGER; % type du champ 'Valeur' %
Pointeur = ^Maillon; % type du champ 'Adresse' %
Maillon = RECORD
Val : Typeelem;
Suiv : Pointeur
END;
% Opérations du modèle %
PROCEDURE Allouer ( VAR P : Pointeur ) ;
BEGIN NEW(P) END;
PROCEDURE Liberer ( P : Pointeur ) ;
BEGIN DISPOSE(P) END;
PROCEDURE Aff_val(P : Pointeur; Val : Typeelem );
BEGIN P^.Val := Val END;
FUNCTION Valeur (P : Pointeur) : Typeelem;
BEGIN Valeur := P^.Val END;
FUNCTION Suivant( P : Pointeur) : Pointeur;
BEGIN Suivant := P^.Suiv END;
PROCEDURE Aff_adr( P, Q : Pointeur ) ;
BEGIN P^.Suiv := Q END;
Statique
Plusieurs listes dans un même tableau.
Le tableau est un ensemble de triplets : (Element, Suivant, Occupe)
Le champ "Occupe" est nécessaire pour les opérations Allouer et Libérer.
Une phase d'initialisation est obligatoire avant l'utilisation de ce tableau.
Donc le tableau est global.
Une liste est définie par l'indice de son premier élément
CONST Max = 100; % Taille arbitraire pour le tableau %
TYPE Typeqq = INTEGER;
TYPE Typeliste = RECORD
Element: Typeqq ;
Suivant : INTEGER;
Occupe : BOOLEAN
END;
% Le tableau %
VAR
Liste : ARRAY[1..Max ] OF Typeliste;
% initialisation %
PROCEDURE Init;
VAR
I : INTEGER;
BEGIN
FOR I:= 1 TO Max DO
Liste[I].Occupe := FALSE;
END;
PROCEDURE Allouer ( VAR I: INTEGER );
VAR
Trouv :BOOLEAN;
BEGIN
I:= 1;
Trouv := FALSE;
WHILE ( (I <= Max) AND NOT Trouv ) DO
IF Liste[I].Occupe
THEN I := I + 1
ELSE Trouv := TRUE;
IF NOT Trouv THEN I := -1;
END;
PROCEDURE Liberer ( I:INTEGER );
BEGIN
Liste[I].Occupe := FALSE ;
END;
FUNCTION Valeur ( I:INTEGER ) : Typeqq;
BEGIN
Valeur := Liste[I].Element;
END;
FUNCTION Suivant ( I:INTEGER ) : INTEGER;
BEGIN
Suivant := Liste[I].Suivant ;
END;
PROCEDURE Aff_val ( I:INTEGER; Val :Typeqq );
BEGIN
Liste[I].Element := Val;
END;
PROCEDURE Aff_adr (I:INTEGER; J: INTEGER);
BEGIN
Liste[I].Suivant := J;
END;
Exemple
VAR
E : INTEGER;
BEGIN
Init;
Allouer (E);
IF E <> -1
THEN
BEGIN
Aff_val (E, 25);
Aff_adr(E, -1);
END
ELSE
WRITELN('Pas d''espace ');
END.
CONST Max =100; { Taille arbitraire }
TYPE
Typeqq = % type d'un element du tableau % ;
Typevect = ARRAY[1..Max] OF Typeqq;
ELEMENT ( V, I )
FUNCTION Element ( VAR V:Typevect; I: INTEGER ) : Typeqq;
BEGIN
Element := V[I];
END;
AFF_ELEMENT ( V, I, Val )
PROCEDURE Aff_element ( VAR V :Typevect; I:INTEGER; Val : Typeqq );
BEGIN
V[I] := Val;
END;
Exemple
VAR
I : INTEGER;
V : Typevect;
BEGIN
Aff_element(V, 1, 34);
Aff_element(V, 2, 56);
Aff_element(V, 3, 89);
Aff_element(V, 4, 38);
Aff_element(V, 5, 156);
FOR I:=1 TO 5 DO
WRITELN(Element( V, I) );
Aff_element(V,3, 99);
FOR I:= 1 TO 5 DO
WRITELN(Element( V, I) );
END.
TYPE
Type1 = type du champ1;
Type2 = type du champ2;
...
Typen = type du champn;
Typestruct = record
Champ1 : Type1;
Champ2 : Type2;
....
....
Champ2 : Typen;
END;
VAR S : Typestruct;
STRUCT (S, I )
Si le type du champ I est un scalaire, STRUCT se
traduit par une fonction comme suit :
FUNCTION STRUCTI ( S:Typestruct ) : TypeI;
BEGIN
StructI := S.champI;
END;
Il ya donc autant de fonctions STRUCT que de champs
scalaires dans la structure.
Si le type du champ I est n'est pas scalaire, c'est à dire un vecteur une dimension de scalaires, STRUCT se traduit par une procédure comme suit :
PROCEDURE STRUCTI ( S:Typestruct; VAR Result : TypeI);
BEGIN
Result := S.champI;
END;
AFF_STRUCT (S, I, Exp)
PROCEDURE AFF_STRUCTI ( VAR S :Typestruct; Val : TypeI );
BEGIN
S.champI := Val;
END;
Il ya donc autant de fonctions Aff_struct que de champs scalaires dans la structure.
Exemple
Le Z-algorithme suivant :
SOIENT
S UNE STRUCTURE (ENTIER, VECTEUR(5) DE CHAINES);
V1, V2 DES VECTEURS(5) DE CHAINES;
I UN ENTIER ;
DEBUT
AFF_ELEMENT(V1[1],'1');
AFF_ELEMENT(V1[2],'2');
AFF_ELEMENT(V1[3],'3');
AFF_ELEMENT(V1[4],'4');
AFF_ELEMENT(V1[5],'5');
AFF_STRUCT(S, 1, 5);
AFF_STRUCT2(S, 2, V1);
ECRIRE('champ1 = ', STRUCT(S, 1) );
ECRIRE('champ2 =');
V2 = STRUCT(S, 2);
POUR I := 1, 5 ECRIRE( V2[I]) FPOUR
FIN
se traduit en PASCAL comme suit :
TYPE
Type1 = INTEGER;
Type2 = ARRAY[1..5] OF STRING;
Typestruct = RECORD
Champ1 : Type1;
Champ2 : Type2
END;
VAR S : Typestruct;
FUNCTION Struct1 ( S:Typestruct ) : Type1;
BEGIN
Struct1 := S.Champ1;
END;
PROCEDURE Struct2 ( S:Typestruct ; VAR Result : Type2);
BEGIN
Result := S.Champ2;
END;
PROCEDURE Aff_struct1 ( VAR S :Typestruct; VAL : Type1 );
BEGIN
S.Champ1 := VAL;
END;
PROCEDURE Aff_struct2 ( VAR S :Typestruct; VAL : Type2 );
BEGIN
S.Champ2 := VAL;
END;
VAR
I : INTEGER;
V1, V2 : Type2;
BEGIN
V1[1] := '1'; V1[2] :='2'; V1[3] := '3';
V1[4] := '4'; V1[5] := '5';
Aff_struct1(S, 5);
Aff_struct2(S, V1);
WRITELN('champ1 = ', Struct1(S) );
WRITELN('champ2 =');
Struct2(S, V2);
FOR I := 1 TO 5 DO
WRITELN(V2[I])
END.
TYPE
Type1 = Type du champ 1 de la structure du bloc (ou article);
Type2 = Type du champ 2 de la structure du bloc (ou article);
...
Typen = Type du champ n de la structure du bloc (ou article);
Typecaract1 = Type de la première caractéristique du fichier;
Typecaract2 = Type de la deuxième caractéristique du fichier;
...
Typecaractm = Type de la m-ième caractéristique du fichier;
{ Définition d'un bloc du fichier}
Sorte = (Caract, Art );
Typestruct = RECORD
CASE Id : Sorte OF
Caract : (
Champ1 : Type1;
Champ2 : Type2;
...
Champn : Typen;
);
Art :
(
Caract1 : Typecaract1;
Caract2 : Typecaract2;
...
Caractm : Typecaractm;
)
END;
Typefile = File OF Typestruct;
VAR
F : Typefile; { Fichier }
Buf_caract : Typestruct; { Buffer des caractéristiques }
{ Machine abstaite sur les fichiers }
OUVRIR ( Fl, Fp, Mode )
PROCEDURE Ouvrir (VAR Fl : Typefile ; Fp, Mode : STRING );
BEGIN
ASSIGN(Fl, Fp);
IF Mode = 'A'
THEN
BEGIN
RESET(Fl);
READ(Fl, Buf_caract);
END
ELSE
BEGIN
REWRITE(Fl);
Buf_caract.Id := Caract;
WRITE(Fl, Buf_caract)
END;
END;
FERMER ( Fl )
PROCEDURE Fermer ( VAR Fl : Typefile);
BEGIN
Buf_caract.Id := Caract;
SEEK(Fl, 0);
WRITE(Fl, Buf_caract);
CLOSE( Fl)
END;
ENTETE (Fl, i )
FUNCTION Entete1( VAR Fl : Typefile): Typecaract1;
BEGIN
Entete1 := Buf_caract.Caract1;
END;
{ Il ya donc autant de fonctions ENTETEi que de types scalaires définis dans la partie 'ENTETE'. }
AFF_ENTETE ( Fl, i, Exp )
PROCEDURE Aff_entete1 ( VAR Fl: Typefile; VAL : Typecaract1);
BEGIN
Buf_caract.Caract1 := VAL
END;
{ Il ya donc autant de fonctions AFF_ENTETEi que de types scalaires définis dans la partie 'ENTETE'. }
ECRIRESEQ ( Fl, Buf )
PROCEDURE Ecrireseq ( VAR Fl: Typefile; Buf : Typestruct );
BEGIN
Buf.Id := Art;
WRITE(Fl, Buf)
END;
ECRIREDIR ( Fl, Buf, N )
PROCEDURE Ecriredir ( VAR Fl: Typefile; Buf : Typestruct; N: INTEGER );
BEGIN
Buf.Id := Art;
SEEK(Fl, N);
WRITE(Fl, Buf)
END;
LIRESEQ ( Fl, Buf )
PROCEDURE Lireseq ( VAR Fl: Typefile; VAR Buf : Typestruct );
BEGIN
READ(Fl, Buf)
END;
LIREDIR ( Fl, Buf, N )
PROCEDURE Liredir ( VAR Fl: Typefile; VAR Buf : Typestruct; N: INTEGER );
BEGIN
SEEK(Fl, N);
READ(Fl, Buf)
END;
FINFICH ( Fl )
FUNCTION Finfich ( VAR Fl : Typefile): BOOLEAN;
BEGIN
Finfich := EOF(Fl)
END;
ALLOC_BLOC ( Fl )
FUNCTION Alloc_bloc ( VAR Fl : Typefile) : INTEGER;
BEGIN
Alloc_bloc := FILESIZE(Fl) ;
END;
Exemple
Le Z-algorithme suivant :
SOIENT
F UN FICHIER DE ( ENTIER , VECTEUR ( 5 ) DE CHAINES )
BUFFER B1 ENTETE ( ENTIER , ENTIER ) ;
{ fichier de blocs contenant le nombre d'articles et un tableau d'articles}
{ entête : nombre d'articles, nombre de blocs}
Creer , Imprimer DES ACTIONS ;
DEBUT
APPEL Creer ;
APPEL Imprimer ;
FIN
/***** Chargement de n articles avec un chargement 100% ****/
ACTION Creer ;
SOIENT
I , K , N , Nbblocs DES ENTIERS ;
DEBUT
OUVRIR ( F , 'f.pas' , 'N' ) ;
I := 0 ;
Nbblocs := 0 ;
N := 500 ;
AFF_ENTETE ( F , 1 , N ) ;
TQ I < N :
K := 0 ;
TQ ( K < 5 ) ET ( I < N )
K := K + 1 ;
I := I + 1 ;
AFF_ELEMENT ( STRUCT ( B1 , 2 ) [ K ] , ALEACHAINE )
FTQ ;
AFF_STRUCT ( B1 , 1 , K ) ;
Nbblocs := Nbblocs + 1 ;
ECRIRESEQ ( F , B1 ) ;
FTQ ;
AFF_ENTETE ( F , 2 , Nbblocs ) ;
FERMER ( F ) ;
FIN
/***** Impression des articles du fichier ****/
ACTION Imprimer ;
SOIENT
I , K DES ENTIERS ;
DEBUT
I := 0 ;
OUVRIR ( F , 'f.pas' , 'A' ) ;
TQ NON FINFICH ( F )
I := I + 1 ;
ECRIRE ( 'B L O C nø ' , I ) ;
LIRESEQ ( F , B1 ) ;
POUR K := 1 , STRUCT ( B1 , 1 )
ECRIRE ( ELEMENT ( STRUCT ( B1 , 2 ) [ K ] ) )
FPOUR
FTQ;
FERMER(f);
FIN
se traduit en PASCAL Comme suit :
TYPE
Type1 = INTEGER;
Type2 = ARRAY[1..5] OF STRING;
Typecaract1 = INTEGER;
Typecaract2 = INTEGER;
Sorte = (Caract, Art );
Typestruct = RECORD
CASE Id : Sorte OF
Caract : (
Champ1 : Type1;
Champ2 : Type2;
);
Art :
(
Caract1 : Typecaract1;
Caract2 : Typecaract2
)
END;
Typefile = File OF Typestruct;
VAR
F : Typefile;
{ Fichier de blocs contenant le nombre d'articles et un tableau d'articles}
B1 : Typestruct;
Buf_caract : Typestruct;
{ Machine abstaite sur les vecteurs }
FUNCTION Element ( VAR V:Type2; I: INTEGER ) : STRING;
BEGIN
Element := V[I];
END;
PROCEDURE Aff_element ( VAR V :Type2; I:INTEGER; VAL : STRING);
BEGIN
V[I] := VAL;
END;
{ Machine abstaite sur les structures }
FUNCTION Struct1( S : Typestruct): Type1;
BEGIN
Struct1 := S.Champ1;
END;
PROCEDURE Struct2(S: Typestruct; VAR Result : Type2);
BEGIN
Result := S.Champ2;
END;
PROCEDURE Aff_struct1( VAR S : Typestruct; VAL : Type1);
BEGIN
S.Champ1 := VAL;
END;
PROCEDURE Aff_struct2( VAR S : Typestruct; VAL : Type2);
BEGIN
S.Champ2 := VAL;
END;
{ Machine abstaite sur les fichiers }
PROCEDURE Ouvrir (VAR Fl : Typefile ; Fp, Mode : STRING );
BEGIN
ASSIGN(Fl, Fp);
IF Mode = 'A'
THEN
BEGIN
RESET(Fl);
READ(Fl, Buf_caract);
END
ELSE
BEGIN
REWRITE(Fl);
Buf_caract.Id := Caract;
WRITE(Fl, Buf_caract)
END;
END;
PROCEDURE Fermer ( VAR Fl : Typefile);
BEGIN
Buf_caract.Id := Caract;
SEEK(Fl, 0);
WRITE(Fl, Buf_caract);
CLOSE( Fl)
END;
FUNCTION Entete1( VAR Fl : Typefile): Typecaract1;
BEGIN
Entete1 := Buf_caract.Caract1;
END;
FUNCTION Entete2( VAR Fl : Typefile): Typecaract2;
BEGIN
Entete2 := Buf_caract.Caract2;
END;
PROCEDURE Aff_entete1 ( VAR Fl: Typefile; VAL : Typecaract1);
BEGIN
Buf_caract.Caract1 := VAL
END;
PROCEDURE Aff_entete2 ( VAR Fl: Typefile; VAL : Typecaract2);
BEGIN
Buf_caract.Caract2 := VAL
END;
PROCEDURE Ecrireseq ( VAR Fl: Typefile; Buf : Typestruct );
BEGIN
Buf.Id := Art;
WRITE(Fl, Buf)
END;
PROCEDURE Ecriredir ( VAR Fl: Typefile; Buf : Typestruct; N: INTEGER );
BEGIN
Buf.Id := Art;
SEEK(Fl, N);
WRITE(Fl, Buf)
END;
PROCEDURE Lireseq ( VAR Fl: Typefile; VAR Buf : Typestruct );
BEGIN
READ(Fl, Buf)
END;
PROCEDURE Liredir ( VAR Fl: Typefile; VAR Buf : Typestruct; N: INTEGER );
BEGIN
SEEK(Fl, N);
READ(Fl, Buf)
END;
FUNCTION Finfich ( VAR Fl : Typefile): BOOLEAN;
BEGIN
Finfich := EOF(Fl)
END;
FUNCTION Aleachaine : STRING;
VAR
K : BYTE;
Chaine : STRING;
BEGIN
Chaine := '';
FOR K:=1 TO 4 DO
CASE Random(2) OF
0 : Chaine := Chaine + CHR(97+Random(26) ) ;
1 : Chaine := Chaine + CHR(65+Random(26) )
END;
Aleachaine := Chaine;
END;
FUNCTION Alloc_bloc ( VAR Fl : Typefile) : INTEGER;
BEGIN
Alloc_bloc := FILESIZE(Fl) ;
END;
{***** Chargement de 50 blocs raison de 60% ****}
PROCEDURE Creer ;
VAR
I , K : INTEGER ;
V : Type2;
BEGIN
Ouvrir ( F , 'f.pas' , 'N' ) ;
FOR I := 1 TO 10 DO
BEGIN
FOR K := 1 TO 3 DO
Aff_element ( V , K , ALEACHAINE );
Aff_struct2( B1, V);
Aff_struct1 ( B1 , 3 ) ;
Ecrireseq ( F , B1 ) ;
END;
Fermer ( F ) ;
END;
{***** Impression des articles du fichier ****}
PROCEDURE Imprimer ;
VAR
K : INTEGER ;
V : Type2;
BEGIN
Ouvrir ( F , 'f.pas' , 'A' ) ;
WHILE NOT Finfich ( F ) DO
BEGIN
Lireseq ( F , B1 ) ;
Struct2(B1, V);
FOR K := 1 TO Struct1 ( B1 ) DO
WRITELN ( Element ( V , K ) );
READLN;
END;
END;
BEGIN
Creer ;
Imprimer ;
END.