Sommaire Définition du langage d’expérimentation Compilateur pour le langage Z minimal Extensions du langage Z minimal
Chapitre 1 : Le langage Z Chapitre suivant
1.1.1 Généralités
1.1.2 Structure d’un algorithme
1.1.3 Définition d’une action
1.1.4 Définition d’une fonction
1.1.5 Exemple d’un algorithme
1.1.6 Objets
1.1.7 Expressions
1.1.8 Instructions
1.1.9 Machines abstraites
1.1.10 Opérations de haut niveau
1.1.11 Fonctions standards
1.2.1 Conventions
1.2.2 Déclarations
1.2.3 Instructions
1.2.4 Expressions
Chapitre 1 : Le langage Z
1.1 Description
1.1.1 Généralités
Un algorithme exprimé en Z est un ensemble de modules parallèles dont le premier est principal et les autres sont soient des actions composées (ACTION) soient des fonctions de type quelconque (FONCTION).
Les objets globaux sont déclarés dans le module principal.
La communication entre les modules se fait via les paramètres et les variables globales.
Les paramètres peuvent être de n’importe quel type.
Le langage permet l’affectation globale de tout type.
Quatre types standards sont autorisés : ENTIER, BOOLEAN, CAR et CHAINE.
Le langage est l'ensemble des algorithmes abstraits, écrits à base de modèles ou machines abstraites qui sont en fait des ensembles d’opérations.
On définit ainsi des machines de Turing : Machine-caractères et Machine-nombres permettant l’initiation à l’algorithmique.
On définit des machines abstraites sur les structures, vecteurs et les listes linéaires chaînées permettant l’initiation aux structures élémentaires de données.
On définit également une machine abstraite sur les fichiers permettant l’initiation aux structures simples de fichiers.
Le langage peut être étendu avec d'autres machines abstraites.
Le langage offre deux fonctions très utiles permettant de générer aléatoirement des chaînes de caractères (ALEACHAINE) et des entiers (ALEANOMBRE).
Le langage permet la lecture et l’écriture de scalaires, vecteurs de n’importe quelle dimension et des structures simples ou complexes.
Le format des instructions est libre.
Il n y a pas de distinction entre majuscule et minuscule.
1.1.2 Structure d’un algorithme
La structure d’un algorithme exprimé en Z est la suivante:
|
SOIENT { Objets locaux et globaux } { Annonce des modules } DEBUT { Instructions } FIN Module 1 Module 2 .... Module n |
Chaque module peut être soit une fonction soit une action.
1.1.3 Définition d’une action
Toute action ou procédure a la forme suivante :
|
ACTION Nom (P1, P2, ..., Pn) SOIT { Objets locaux et paramètres } DEBUT { Instructions } FIN |
Les paramètres P1, P2, ..., Pn sont appelés par ‘référence’. Ils ne sont pas protégés par l’action.
1.1.4 Définition d’une fonction
Une fonction est définie comme suit:
|
FONCTION Nom (P1, P2, ...,Pn) : Type { Objets locaux et paramètres } DEBUT { Instructions } FIN |
Type peut être quelconque.
Une fonction est utilisée dans une expression.
1.1.5 Exemple d’un algorithme
L’algorithme qui suit fait la reconnaissance des mots dans une chaîne de caractères.
|
SOIENT Mot : CHAINE; C : CAR; M : MACHINE_CAR; DEBUT CREER_MCAR(M, [' Jhh Jsthd Lkql ifd ']); LIRECAR(M, C); TANTQUE C <> '.' TQ (C=' ') ET (C <> '.') LIRECAR(M, C) FTQ ; Mot := ''; TQ (C <> ' ') ET (C <> '.') Mot := Mot + C ; LIRECAR(M, C) FTQ; SI Mot <> '' ECRIRE(Mot) FSI FINTANTQUE FIN |
1.1.6 Objets
Le langage Z manipule des objets. Ces derniers peuvent être des entiers (ENTIER), des booléens (BOOLEEN), des caractères (CAR) ou des chaînes de caractères ( CHAINE).
Les objets peuvent aussi être des machines abstraites : Machine-caractères, Machine-nombres, Vecteurs, Structures, Listes linéaires chaînées, et Fichiers.
La machine-caractères est un ruban composé d’un ensemble de cases défilant devant une tête de lecture. Chaque case renferme un caractère.
La machine-nombres est un ruban composé d’un ensemble de cases défilant devant une tête de lecture. Chaque case renferme un nombre.
Un tableau ou vecteur est un ensemble d’éléments ayant le même type. Il peut avoir plusieurs dimensions. Les éléments sont contigus en mémoire.
Une structure ou un enregistrement est composé de plusieurs champs de natures hétérogènes. Les champs sont contigus en mémoire.
Une liste linéaire chaînée est un ensemble de maillons. Chaque maillon est composé de deux champs: valeur et adresse. Les maillons sont éparpillés en mémoire.
Un fichier est un ensemble d’éléments de même type. Chaque élément peut être soit un bloc soit un article. Un bloc renferme des articles. Un article peut être un objet simple, un vecteur ou une structure. Un fichier peut posséder un entête contenant les caractéristiques du fichier (ENTETE). Il utilise aussi des buffers ou tampons pour les opérations de lecture et d’écriture. Les éléments d’un fichier sont rangés sur une mémoire externe.
Une structure peut être simple, c’est à dire composée uniquement de scalaires.
Une structure peut être complexe, c’est à dire composée de scalaires et|ou de vecteurs à une dimension de scalaires.
Les éléments d’un vecteur peuvent être des objets simples, des vecteurs ou des structures simples.
Exemples:
|
SOIENT A, B, C DES BOOLEENS ; I, J : ENTIER ; Ch UNE CHAINE ; C UN CAR ; SOIENT L1, L2 DES LISTES ; V1 UN VECTEUR(10, 60) ; SOIENT V1 UN VECTEUR(10, 60) DE (CAR, ENTIER); S UNE STRUCTURE (CHAINE, ENTIER); F UN FICHIER DE (CHAINE, VECTEUR(5) DE ENTIERS) BUFFER V1, V2; |
1.1.7 Expressions
Les expressions dans le langage Z sont exprimées comme dans les langages de programmation.
Exemples :
| (B+C)
/ F
NON Trouv (X # 5) ET NON Trouv F(x) <> 5 A OU B (A <= B) ET(A >5) |
1.1.8 Instructions
Afin de décrire les instructions du langage Z, nous utilisons les conventions suivantes:
V désigne une variable, E une expression.
[ ] désigne une partie facultative, { } un ensemble.
Nous disposons des instructions suivantes:
Affectation : V := E
Lecture : LIRE(V1, V2, .....)
Écriture : ECRIRE(E1, E2, .....)
Conditionnelle : SI E [ : ]
{ Instructions }
[ SINON
{ Instructions } ]
FSI
Appel: APPEL Idf [ ( E1, E2, ...) ]
Répétitive (Forme 1 ) : TQ E [ : ]
{ Instructions }
FTQ
Répétitive (Forme 2 ) : POUR V := E1, E2, E3
{ Instructions }
FPOUR
E3 désigne le pas.
1.1.9 Machines abstraites
Afin de faciliter et simplifier l’écriture des algorithmes, nous utilisons des machines abstraites sur les objets offrant des opérations élémentaires. Énonçons ci-après les machines abstraites considérées:
Machine-caractères : LIRECAR, NBRCAR
Machine-nombres : LIRENOMBRE, NBRNOMBRE
Listes linéaires chaînées : ALLOUER , LIBERER , VALEUR, SUIVANT, AFF_ADR, AFF_VAL
Vecteurs : ELEMENT, AFF_ELEMENT
Structures : STRUCT, AFF_STRUCT
Fichiers : OUVRIR, FERMER, LIRESEQ, ECRIRESEQ, LIREDIR, ECRIREDIR, RAJOUTER, FINFICH, ENTETE, AFF_ENTETE, ALLOC_BLOC
Toutes ces opérations sont définies juste après.
Machine-caractères
C'est l'ensemble des opérations suivantes :
- LIRECAR ( M, C)
Récupère dans la variable caractère C le prochain caractère de la machine M.
- NBRCAR (M)
Fournit le nombre total de caractères dans la machine M.
Machine-nombres
C'est l'ensemble des opérations suivantes :
- LIRENOMBRE ( M, Nombre)
Récupère dans la variable entière Nombre le prochain entier de la machine M.
- NBRNOMBRE (M)
Fournit le nombre total de nombres contenus dans la machine M.
Structures
C'est l'ensemble des opérations suivantes :
- STRUCT ( S, I)
Accès au I-ème champ de la structure S.
- AFF_STRUCT ( S, I, Exp )
Affecter à la structure S dans son I-ème champ l'expression Exp.
Exemple:
|
SOIT S UNE STRUCTURE ( CHAINE , BOOLEEN ) ; DEBUT AFF_STRUCT ( S , 1 , 'Abc' ) ; AFF_STRUCT ( S , 2 , VRAI ) ; ECRIRE ( STRUCT ( S , 1 ) , STRUCT ( S , 2 ) ) FIN |
Vecteurs (ou tableaux)
C'est l'ensemble des opérations suivantes :
- ELEMENT ( T [I, J, ...] )
Accès à l'élément T[I, J, ...] du vecteur T.
- AFF_ELEMENT ( T [I, J, ...], Val )
Affecter à l'élément T[I, J, ...] la valeur Val.
Exemple :
|
SOIT A UN TABLEAU ( 5 , 3 ) DE ENTIERS ; DEBUT AFF_ELEMENT ( A [ 1 , 1 ] , 599 ) ; ECRIRE ( ELEMENT ( A [ 1 , 1 ] ) ) FIN |
Listes linéaires chaînées
C'est l'ensemble des opérations suivantes :
- ALLOUER ( P )
Crée un maillon et retourne son adresse dans P.
- LIBERER ( P )
Libère le nœud d'adresse P.
- SUIVANT ( P )
Accès au champ ‘Adresse’ du nœud référencé par P.
- VALEUR ( P )
Accès au champ 'Valeur' du nœud référencé par P.
- AFF_ADR ( P, Q )
Affecter au champ 'Adresse' du nœud référencé par P, l'adresse Q.
- AFF_VAL( P, Val )
Affecter au champ 'Valeur' du nœud référencé par P, la valeur Val.
Fichiers
C'est l'ensemble des opérations suivantes :
- OUVRIR (Fl, Fp, Mode)
Ouvrir le fichier logique Fl et l'associer au fichier physique Fp en précisant le mode d’ouverture ( fichier nouveau('N') ou ancien( 'A') ).
- FERMER (Fl)
Fermer le fichier Fl.
- LIRESEQ (Fl, V)
Lire dans la variable tampon V le bloc (ou l'article) se trouvant à la position courante.
- ECRIRESEQ (Fl, V)
Écrire le contenu de la variable tampon V à la position courante du fichier Fl.
- RAJOUTER(Fl, V)
Écrire le contenu de la variable tampon à la fin du fichier Fl.
- LIREDIR (Fl, V, N)
Lire le N-ème bloc (ou article) du fichier Fl dans la variable tampon V.
- ECRIREDIR (Fl, V, N)
Écrire le contenu de la variable tampon V à la N-ème position du fichier
Fl.
- FINFICH (Fl)
Prédicat égal à Vrai si la fin du fichier Fl est rencontrée, Faux sinon.
- ALLOC_BLOC(Fl)
Fournit un bloc (ou article) du fichier Fl dans lequel on pourra écrire.
- ENTETE (Fl, I)
Récupérer la I-ème caractéristique du fichier Fl.
- AFF_ENTETE (Fl, I, Exp)
Affecter Exp comme la I-ème caractéristique du fichier Fl.
1.1.10 Opérations de haut niveau
Les opérations de haut niveau permettent de faire des créations ou des initialisations de machines abstraites. A chaque machine abstraite est associée une opération comme mentionné ci-après:
Machine-caractères : CREER_MCAR
Machine-caractères : CREER_MNOMBRE
Structures : INIT_STRUCT
Vecteurs : INIT_VECTEUR (ou INIT_TABLEAU)
Listes : CREER_LISTE
Toutes ces opérations sont définies juste après
Machine-caractères
CREER_MCAR (M, [' cccccc '])
Initialise la machine-caractères M avec la chaîne de caractères se trouvant entre crochets.
Exemple
| CREER_MCAR (M, [‘Réalisation d’’un compilateur pédagogique’]) |
Machine-nombres
CREER_MNOMBRE (M, [ Exp1, Exp2, ....])
Initialise la machine-nombres M avec les valeurs des expressions Exp1, Exp2, ...
Exemple
|
CREER_MNOMBRE (M, [22, 34, 78, 23, 55, 22, 0, 24]) |
Listes linéaires chaînées
CREER_LISTE( L, [Exp1, Exp2, ....] )
Crée la liste linéaire chaînée L avec les valeurs entre crochets dans l'ordre indiqué.
Exemple
|
CREER_LISTE ( L, [12, 34, I, I+J, 45] ) |
Structures
INIT_STRUCT ( S, [Exp1, Exp2, ....] )
Initialise la structure S avec les valeurs des expressions entre crochets dans l'ordre indiqué.
Exemple
|
INIT_STRUCT ( S, [120, VRAI, ‘Compilateur’] ) |
Vecteurs
INIT_VECTEUR( V, [Exp1, Exp2, ....] ) (ou INIT_TABLEAU)
Initialise le vecteur V avec les valeurs des expressions entre crochets dans l'ordre indiqué.
Exemple
|
INIT_VECTEUR ( V, [112, 340, 45, 44, 21, 34] ) |
1.1.11 Fonctions standards
On définit
- sur les nombres la fonction ALEANOMBRE(Exp) qui fournit un nombre aléatoire compris entre 0 et Exp-1.
- sur les chaînes de caractères les fonctions suivantes:
ALEACHAINE(Exp) : fournit une chaîne de caractères aléatoire de longueur Exp.
LONGCHAINE(Chaine): donne la longueur de la chaîne Chaine.
CARACT(Chaine, Exp) : rend le caractère de rang Exp contenu dans la chaîne Chaine.
Exemples
|
SOIT S UNE CHAINE ; I , J DES ENTIERS ; C UN CAR ; DEBUT S := ALEACHAINE ( 5 ) ; {donne par exemple 'bxrfd'} I := ALEANOMBRE ( 1000 ) ; { donne par exemple 675} J := LONGCHAINE ( 'bcdgfd' ) ; {donne 6} C := CARACT ( 'gfrd' , 3 ) {donne 'r'} FIN |
1.2 Grammaire du langage Z
1.2.1 Conventions
Nous exprimons la grammaire avec la notation EBNF (Extended Backus Normal Form). Dans tout le document, dans la description de la grammaire, nous utilisons les conventions suivantes:
- Symboles:
~ --- | --- ~ désigne un choix
[ ---- ] désigne une partie facultative
[[ Crochet ouvrant
]] Crochet fermant
{ --- }* Répétition ( ≥ 0 )
{ --- }+ Répétition ( > 0 )
- Unités lexicales:
Types dans {Entier, Booleen, Car, Chaine}
Sep dans {:, Un, Une, Des}
Cste désigne une constante numérique entière
Idf désigne un identificateur
Opr dans { <, <=, >, >=, =, <>,# }
Opa dans { +, -, Ou }
Opm dans { *, /, Et }
Sign dans {+, -}
Cstelog dans {Vrai, Faux}
Chaine désigne une chaîne de caractères
Tableau est synonyme de Vecteur
Init_tableau est synonyme de Init_vecteur
1.2.2 Déclarations
<Algo Z> → [ ~ Soit|Soient ~ <Ps> ] Debut <Lis> Fin [;] { ~ <Act> | <Fonct> ~ [;] }*
<Act> → Action Idf [ ( <Li> ) ] [;] [ ~ Soit|Soient ~ <Ps> ] Debut <Lis> Fin
<Fonct> → Fonction Idf ( <Li> ) : <Typ> [ ~Soit|Soient ~ <Ps> ] Debut <Lis> Fin
<Ps> → <S>;{ [ ~Soit|Soient ~ ] <S>;}*
<S> → <Li> Sep ~ <Typ>| ~Action|Fonction(<Typ>)~ ~
<Li> → Idf {, Idf}*
<Typ> → Types | <Structsimple> | <Structcomplexe> | Machine_car | Machine_nombre | [Pointeur vers [Sep] ] Liste [ De ~Types | <Structsimple>~ ] |
Tableau (<Lc>) [De~<Structsimple> | Types~ ] |
Fichier De ~ Types | Vecteur(Cste) [De Types] | <Structsimple> | <Structcomplexe> ~ [Entete (Types {, Types }*)] Buffer <Li>
<Structsimple> → [Structure ](Types {, Types }*)
<Structcomplexe>
→ [Structure ]( ~ Types | Vecteur(Cste)[De Types] ~ {, ~ Types | Vecteur(Cste) [ De Types] ~ }*)
<Lc> → Cste {, Cste}*
1.2.3 Instructions
< Lis > → < Inst > { ; < Inst > }*
<Inst> → Idf := <Exp> |
Tantque <Exp> [ : ] <Lis> Fintantque
Si <Exp> [:] <Lis> [Sinon <Lis>] Fsi |
Pour Idf:= <Exp>,<Exp> [, <Exp>][:] <Lis> Finpour |
Appel Idf [(Exp {,<Exp>}*)] |
Lire ( Idf {, Idf }* ) |
Ecrire (<Exp> {,<Exp>}* ) |
~Liberer | Allouer | Fermer~ ( <Exp> ) |
Ouvrir ((Idf, Chaine, Chaine) |
~Lirecar|Lirenombre|Lireseq|Ecrireseq|Rajouter~ (Idf, Idf) |
~ Aff_adr|Aff_val~ ( <Exp> , <Exp> ) |
~ Creer_liste |Init_vecteur | Creer_mnombre | Init_struct ~ ( Idf , [[ ~<Exp>|[[<Exp> {, <Exp>}*]] ~ {, ~<Exp>|[[<Exp> {, <Exp>}*]]~}* ]] ) |
Creer_mcar(Idf, [[ Chaine ]]) |
Aff_element ( <Exp> [[ <Exp> {, <Exp> }* ]] ,<Exp> ) |
~Aff_struct | Aff_entete~(Idf, Cste, <Exp>) |
~ Liredir | Ecriredir ~ (Idf, <Exp>, Idf)
1.2.4 Expressions
<Exp> → <Exps>[ Opr <Exps>]
<Exps> → [Sign] <Terme> { Opa <Terme> }* |
<Terme> → <Facteur>{Opm <Facteur>}*
<Facteur> → Idf [ ( <Exp> {, <Exp>} * ) ] | Cste | <Fonct> | NIL | ( <Exp>) | Chaine | Non <Facteur> | Cstelogic
<Fonct> → ~Valeur | Suivant~ ( <Fonct> ) |
Element ( <Fonct> [[ <Exp> {, <Exp> }* ]] ) |
~Struct | Entete~ ( Idf, Cste) |
Caract ( Idf, <Exp>) |
~ Aleachaine | Aleanombre | Longchaine~ ( <Exp> ) |
~Nbrcar | NbrNombre|Finfich|Alloc_bloc~ (Idf)
1.2.4 Compléments
Une chaîne de caractères est délimitée par le symbole ‘. Si ce dernier figure dans la chaîne, il est doublé.
Les commentaires sont entre les symboles /* et */ ou bien entre les symboles { et }. Ils sont insérés là où un espace peut figurer.
1.3 Expérimentation
Avant d’aller plus loin, il est conseillé de bien comprendre la grammaire en expérimentant le langage Z. Pour cela, vous pouvez utiliser le logiciel Khawarizm qui est libre d’utilisation.