Grenoble INP I.

Introduction Spécifications du langage

Année Spéciale Informatique
1. Présentation du projet a) Lexicographie ([Link] page B-1)
La lexicographie définit les mots (ou unités lexicales) du
Buts du projet : langage Cas.
écrire un compilateur « zéro-défaut » pour le
langage Cas ; Exercice
utiliser des générateurs d’analyseurs lexical et Les chaînes suivantes sont-elles des identificateurs du
syntaxique (Aflex et Ayacc) ; langage Cas ?
travailler en équipe. toto, toto_1, toto__1, 2_a, _toto

Les chaînes suivantes sont-elles des constantes entières

2. Le langage Cas du langage Cas ?
12, -12, 12e2, 12.5e2, 12e+2
Projet Compilation « Cas » signifie « Compilation Année Spéciale ».
Les chaînes suivantes sont-elle des constantes réelles du
Exemple de programme Cas langage Cas ?
-- Calcul de la factorielle 0.12, .12, 1.5e+3, 1.5e-3, 1e-2, 12, 1.2e++2
program
n, fact : integer ;
begin
write("Entrer un entier : ") ;
b) Syntaxe hors-contexte ([Link] page B-3)
read(n) ; La syntaxe hors-contexte définit les phrases du langage
fact := 1 ;
while n >= 1 do Cas.
fact := fact * n ;
n := n – 1 ; Exercice
Matthieu Moy end ; Ecrire un programme Cas qui ne fait rien.
write("fact(", n, ") = ", fact) ;
(Transparents originaux de Catherine Oriat) new_line ;
Ensimag/Laboratoire Verimag end.
[Link]@[Link]

1 2 3

3. Vue d’ensemble du compilateur

c) Syntaxe contextuelle ([Link] page B-6) Analyse syntaxique
Le compilateur Cas comporte trois passes Consiste à déterminer si une suite de mots est une
La syntaxe contextuelle (ou sémantique statique) du (le programme va être parcouru trois fois). phrase du langage et à construire un arbre abstrait
langage Cas définit : du programme.
Cela permet de bien décomposer les problèmes.
les règles de déclaration des identificateurs ;
les règles d’utilisation des identificateurs ; Construction de l’arbre abstrait du programme
a) Passe 1
les règles de typage des expressions.
Analyse lexicale Arbre abstrait correspondant à l’instruction
Consiste à décomposer un programme Cas, donné x := 2 * (a + b) ;
sous la forme d’une suite de caractères, en une suite
Exercice
de mots (ou unités lexicales).
Faire la liste de tous les messages d’erreurs Noeud_Affect
A chaque unité lexicale reconnue est associée un
contextuelles. Pour chaque message d’erreur, donner un
lexème (ou « token »).
exemple de programme Cas incorrect. Noeud_Ident Noeud_Mult
"x"
Exemple
La suite de caractères « x := 2 * (a + b) ; »
correspond à la suite de lexèmes : Noeud_Entier Noeud_Plus
Idf_Lex ("x") 2
Affect_Lex
Constent_Lex (2)
‘*‘ Noeud_Ident Noeud_Ident
‘(‘ "a" "b"
Idf_Lex ("a")
‘+‘
Idf_Lex ("b")
‘)‘
‘;‘

Le type Token, qui déclare les différents « tokens »,

est défini dans syntax_tokens.ads page C-24.

4 5 6

b) Passe 2 : vérifications contextuelles et Dans le langage Cas, on distingue

décoration de l’arbre abstrait c) Passe 3
les identificateurs de types ;
les identificateurs de constantes ;
But de la passe 2 La passe 3 consiste à parcourir l’arbre abstrait décoré
les identificateurs de variables.
vérifier qu’un programme Cas est contextuellement une seconde fois et à produire du code exécutable.
correct ; Les identificateurs de types et de constantes sont
décorer l’arbre abstrait du programme. uniquement des identificateurs prédéfinis On produit du code pour une machine abstraite proche
(on ne peut déclarer que des identificateurs de variable). du 68000 (Machine_Abstraite.txt page B-18).
On décore les identificateurs avec leur définition et
les expressions avec leur type. Intérêts d’utiliser une machine abstraite :
Vérifications contextuelles
faire abstraction des particularités de bas niveau des
Exemple langages assembleurs (comme par exemple les
Les vérifications contextuelles sont réalisées par un
(var, integer) problèmes d’alignement en 68000) ;
parcours de l’arbre abstrait du programme.
program
(type, integer) permettre la production de code assembleur réel
x : integer ; Le parcours des déclarations permet de construire pour plusieurs machines similaires
begin l’environnement. (écrire facilement plusieurs « back-ends » de
x := x + 1 ; compilateurs).
end ;
integer Le parcours des instructions permet de vérifier que les
identificateurs sont utilisés conformément à leur
déclaration, et que les expressions sont bien typées.

Principe Lors de ce parcours, l’arbre abstrait est décoré, afin de

préparer la passe 3.
On construit un environnement, qui associe à tout
identificateur sa définition.

7 8 9
Exemple de gcc Commandes du projet
4. Environnement de programmation

C Compilation
Passe 1 ([Link] page A-2)
make
C++ Projet est développé en binômes (pour les passes 1 et 2) make clean
arbre
sur ensisun. (à ne pas faire avant chaque compilation !)
Ada abstrait
Organisation des répertoires Vérification des accolades dans un fichier Aflex ou
Java Sur ensisun :
Ayacc
accolades
/usr/local/PCas
Passes 2 et 3
Pentium Extraction des commentaires
PCas
Sparc commentaire

68000 Global Cas

RTL Debug
adastack ou adadebug
Bin Doc Common Syntaxe Verif Gencode exemple : adastack test_synt [Link]
Le compilateur gcc peut compiler des programmes
écrits en C, C++, Ada ou Java. Src Src Test Commandes auxiliaires (utilisées dans les makefiles)
gcc utilise une structure d’arbre unique pour tous ces
gnatmake –g –gnato –I bibliothèques
langages.
gnaflex
gcc produit du code « RTL » (Register Transfer Répertoire à récupérer via Git.
Language), code pour une machine abstraite dont la gnayacc
syntaxe est proche du Lisp.
Il y a plusieurs « back-ends » pour différentes Mise en place de l’environnement
machines. [Link] page A-4.

10 11 12

5. Planning II. Passe 1 : analyse lexicale et syntaxique, Dans [Link] se trouve la fonction principale de
construction de l’arbre abstrait l’analyseur lexical, qui permet de lire le lexème
Les programmes sont ramassés automatiquement via suivant :
Git. 1. Aflex
function YYLex return Token ;
Fin de la semaine de stage : terminer la passe 1, a) Introduction
commencer la passe 2. Token est un type énuméré, défini soit par
Passe 1 à rendre le mercredi 15 février 2012, 18h00 Aflex : générateur d’analyseur lexical pour Ada (dans la l’utilisateur, soit par l’outil Ayacc (comme c’est le
lignée de Lex, générateur d’analyseur lexical pour C). cas dans le projet).
15 février - 4 avril : terminer la passe 2. Token contient au minimum les valeurs Error et
Passe 2 à rendre le 4 avril 2012, 18h00. Aflex permet, à partir d’un fichier d’entrée qui décrit la End_Of_Input.
forme d’un ensemble d’unités lexicales, de générer un
analyseur lexical. La fonction YYLex lit des caractères sur l’entrée
Fin du stage de mai : terminer la passe 3. standard, les partitionne en unités lexicales, exécute
Commande : gnaflex fich.l les actions correspondantes et retourne un lexème
correspondant à l’unité lexicale reconnue.
Cette commande produit 5 fichiers :
[Link] : unité Ada correspondant à fich.l Dans fich_dfa.ads, on trouve la fonction
fich_dfa.ads, fich_dfa.adb :
function YYText return String ;
paquetage Fich_DFA
fich_io.ads, fich_io.adb :
qui retourne la chaîne qui vient d’être reconnue.
paquetage Fich_IO.

13 14 15

Expressions régulières Définitions

b) Forme du fichier fich.l
x Le caractère ‘x’ Dans la partie « Définitions », on associe à des noms
"(" Le caractère ‘(’ des expressions régulières.
\( Le caractère ‘(’
":=" Le caractère ‘:’ suivi du Exemple
Définitions = macros
caractère ‘=’
CHIFFRE [0-9]
LETTRE [A-Za-z]
%% Ensemble des caractères spéciaux (appelés IDF {LETTRE}({LETTRE}|{CHIFFRE}|"_")*
« opérateurs » dans Aflex) :
" \ { } [ ] ^ $ < > ? . * + | ( ) / Remarques
Règles = expression régulière { actions } Les expressions régulières ne doivent pas contenir
{IDF} La définition IDF d’espaces.
x* x répété 0, 1, ... n fois Dans les noms, les minuscules/majuscules sont
%% x+ x répété 1, 2, ... n fois significatives : CHIFFRE et chiffre sont deux noms
différents.
x? x optionnel (0 ou 1 fois)
x|y x ou y
Contexte utilisateur = procédure ou paquetage
[abc] ‘a’, ‘b’ ou ‘c’
Ada qui utilise la fonction YYLex. Règles
[A-Za-z] caractères entre ‘A’ et ‘Z’ et ‘a’ et ‘z’
## -- emplacement de la fonction YYLex [^abc] tout caractère sauf ‘a’, ‘b’ et ‘c’ Une règle est une expression régulière suivie d’une suite
\n retour à la ligne d’actions :
\t tabulation
\040 espace expression régulière { actions }
\041 ‘!’
\042 ‘"’ Une règle associe à une expression régulière des actions
\134 ‘\’ à effectuer.
\176 ‘~’
. Tout caractère sauf \n Les actions sont des instructions Ada.

16 17 18
 ----------------------------------------------- 2. Mise en oeuvre de l’analyse lexicale
-- Exemple simple d’utilisation de Aflex
Exemple -- Ecrit les commentaires d’un programme Cas
----------------------------------------------- a) Les types de base
":=" { return Affect_Lex ; } Le paquetage Types_Base (page C-2) définit :
"/=" { return Diff_Lex ; } -- Caractères imprimables
CAR_IMP [\040-\176] le type Entier, pour les littéraux entiers qui
Reconnaissance du préfixe le plus long possible -- Commentaires apparaissent dans un programme Cas ;
COMMENT "--"({CAR_IMP}|\t)* le type Reel, pour les littéraux réels qui
Lorsqu’il y a une ambiguïté sur la règle à appliquer, -- Caractères d’une chaîne
comme CHAINE_CAR [\040\041\043-\176] apparaissent dans un programme Cas ;
-- Chaîne de caractères le type Chaine, pour les littéraux chaînes et les
toto { action1 ; } CHAINE \"({CHAINE_CAR}|\"\")*\" identificateurs qui apparaissent dans un programme
tototi { action2 ; } Cas.
%%

on reconnaît le préfixe le plus long possible. Si la chaîne {CHAINE} { null ; }

{COMMENT} { Put_Line(YYText) ; Remarque sur le type Chaine
d’entrée est tototi, on applique action2, si la chaîne return Comm ; }
d’entrée est totota, on applique action1. .|\n { null ; } On Ada, on a le type String qui est un tableau non
%% contraint de caractères.
Lorsque les deux chaînes sont de la même longueur, on
applique la première règle : with Ada.Text_IO ; type String is
use Ada.Text_IO ; array(Positive range <>) of Character ;
toto { action1 ; } procedure Comment is
tot. { action2 ; } Pour déclarer une variable de type String, on doit en
-- Type Token, contenant les valeurs connaître la taille.
-- End_Of_Input et Error.
Si la chaîne d’entrée est toto, on applique action1. type Token is (End_Of_Input, Error, Comm) ; S : String(1 .. 10) ;
Tok : Token ; S : String(T’Range) ;
Exemple ## -- La fonction YYLex sera générée ici -- où T est de type String.
Affichage des commentaires d’un programme Cas.
begin Dans le projet, pour faciliter la manipulation de chaînes
loop
Remarque Tok := YYLex ;
de différentes tailles, on utilise le type abstrait Chaine.
write("-- Ceci n’est pas un commentaire") ; exit when Tok = End_Of_Input ;
end loop ;
end Comment ;

19 20 21

Ayacc fournit le type YYStype, et la variable

package Types_Base is b) Paquetage Tables
-- ... YYLVal : YYStype ;
type Chaine is private ;
Chaine_Indef : constant Chaine ; Le paquetage Table permet d’associer des informations qui permet :
private à des chaînes de caractères (page C-6). 1. de stocker des informations supplémentaires
type Structure_Chaine ; associées aux lexèmes ;
type Chaine is access Structure_Chaine ;
Chaine_Indef : constant Chaine := null ; Le corps du paquetage est implémenté à l’aide d’une 2. de stocker des informations nécessaires associées
end ; table à adressage dispersé. aux non-terminaux de la grammaire (lors de
l’analyse syntaxique).
Les conversions entre les types String et Chaine se font Ce paquetage sert :
à l’aide de deux fonctions : en passe 1 pour implémenter le dictionnaire, qui Le type YYSType est défini dans le fichier
sert à associer aux mots réservés leur token ; syntax_token.ads, page C-24.
function Creation_Chaine(S : String) en passe 2 pour implémenter l’environnement, qui
return Chaine ; Le type YYSType est un type article avec discriminant
function Acces_String(C : Chaine) sert à associer aux identificateurs leur définition.
(certains champs sont présents ou non suivant la valeur
return String ;
du champ discriminant).
c) Implémentation de l’analyse lexicale
Quand on rencontre une String, on la convertit Le discriminant est de type Type_Valeur.
immédiatement en une Chaine. Ensuite, on ne manipule L’analyse lexicale est réalisée par la fonction type Type_Valeur is
que des Chaine, sauf lors d’un affichage : function YYLex return Token ;
(Lex_Idf, --> pour les identificateurs
Lex_Entier, --> pour les entiers
C : Chaine ; Lex_Reel, --> pour les réels
C := Creation_Chaine("toto") ;
générée par Aflex. Cette fonction est utilisée par Lex_Chaine, --> pour les chaînes de caract.
Put_Line(Acces_String(C)) ; l’analyseur syntaxique, généré par l’outil Ayacc Lex_Autre, --> pour les autres lexèmes
NT) ; --> pour les non-terminaux
(générateur d’analyseur syntaxique).
type YYSType ...
Le type Token est produit par Ayacc. ...
when Lex_Idf =>
Num_Ligne_Idf : Natural ;
Un Token ne contient pas toute l’information nécessaire -- No de ligne où apparaît l’identificateur
contenue dans un lexème (chaînes de caractères, Val_Idf : Chaine ;
-- Chaîne de caractères qui correspond à
numéros de lignes). -- l’identificateur

22 23 24

[Link] (spécification page C-13, corps page

Exemple de valeur de type YYStype : d) Traitement des mots réservés dans l’analyse C-14).
lexicale
(Lex_Idf, Ligne_Courante, C) ; -- Ajoute l’association (S -> Tok) dans le
-- dictionnaire.
Une solution procedure Ajouter_Mot_Reserve
où : On écrit une règle par mot réservé.
Ligne_Courante : Natural ; (S : in String ; Tok : in Token);
C : Chaine ;
IF { YYLVal :=
(Lex_Autre, Ligne_Courante) ; -- Retourne :
return If_Lex ; } -- - le token associé à C, si C fait partie
Finalement, les actions de l’analyse lexicale : WHILE { YYLVal := -- du dictionnaire
(Lex_Autre, Ligne_Courante) ; -- - le token Idf_Lex, sinon.
1. modifient la valeur de YYLVal ; return While_Lex ; } function Acces_Token(C : Chaine) return Token ;
2. renvoient une valeur de type Token.
Aflex crée alors un gros automate.
Exemples de règles Reconnaissance des identificateurs (dans lexico.l)
Autre solution
[ \t] { null ; } {IDF} { declare
\n { Ligne_Courante := Code : Token ;
Ligne_Courante + 1 ; } On utilise un dictionnaire, qui stocke tous les mots C : Chaine ;
{COMMENT} { null ; } réservés avec leur token correspondant. begin
":=" { YYLVal := Chercher_Dict(YYText, Code, C) ;
(Lex_Autre, Ligne_Courante) ; Au départ : on initialise le dictionnaire avec tous les if Code = IDf_Lex then
return Affect_Lex ; } mots réservés. YYLVal :=
".." { YYLVal : = (Lex_Idf, Ligne_Courante, C) ;
(Lex_Autre, Ligne_Courante) ; On reconnaît alors les mots réservés comme des else
return Doublepoint_Lex ; } identificateurs et on consulte ensuite le dictionnaire YYLVal :=
{ENTIER} { YYLVal := (Lex_Entier, pour savoir s’il s’agit d’un mot réservé. (Lex_Autre, Ligne_Courante) ;
Ligne_Courante, end if ;
Valeur_Entier(YYText)) ; return Code ;
-- fonction Valeur_Entier à définir end ;
return Constent_Lex ; } }

Regarder les fichiers [Link] page C-15 et lexico.l Définir Chercher_Dict (qui consulte le dictionnaire,
page C-16. après avoir mis la chaîne de caractères en minuscules).

25 26 27
Le paquetage [Link] 3. Les arbres b) Spécification du paquetage Arbre (page C-8)

contient la fonction a) Syntaxe abstraite ([Link] page B-11) Le paquetage Arbre définit :
function To_Lower(Item : String)
return String ;
Syntaxe abstraite du langage Cas un type énuméré pour les différents noeuds
définit la représentation intermédiaire utilisée par les possibles : Noeud_Affect, Noeud_Chaine,
qui permet de passer une chaîne de caractères en compilateurs (ou interprètes) du langage. Cette syntaxe Noeud_Plus, Noeud_Moins...
minuscules. abstraite est définie par une grammaire d’arbres.
un type Arbre ;
Exercice
Travail à effectuer : compléter lexico.l la constante Arbre_Indef : arbre indéfini.
Donner les arbres abstraits correspondant aux Lorsqu’on construit un arbre, on peut utiliser
Programme de test fourni : test_lex page C-25. programmes Cas suivants : temporairement Arbre_Indef. Lorsqu’on a fini de
construire l’arbre, celui-ci ne doit plus contenir de
program
a : integer ;
valeurs indéfinies.
b, c : boolean ;
begin des constructeurs d’arbres, qui permettent de
a := 1 ; construire des arbres connaissant ces fils. Les
b := a + 1 ;
end ; constructeurs sont préfixés par Creation_.

program Exemples :
t : array[1..10] of array[1..5] of A1 := Creation_Ident(C, Num_Ligne) ;
integer ; A2 := Creation_Entier(4, Num_Ligne) ;
begin A3 := Creation2(Noeud_Plus, A1, A2, N) ;
t[10][5] := 0 ;
end ;

28 29 30

4. Ayacc
des sélecteurs, qui permettent de décomposer un c) Implantation des arbres, «sémantique de partage»
arbre. Les sélecteurs sont préfixés par Acces_. a) Introduction
Un arbre est un pointeur, ce qui implique qu’on a une
Exemples : « sémantique de partage ». Ayacc
Acces_Entier(A2) → 4
Exemple Générateur d’analyseurs syntaxiques pour Ada, dans la
Acces_Fils1(A3) → A1 lignée de Yacc, générateur d’analyseurs syntaxiques
Acces_Fils2(A3) → A2 A, B, C : Arbre ;
A := Creation2(Noeud_Plus,
pour C.
Creation_Entier(1),
des mutateurs, qui permettent de modifier un arbre. Creation_Entier(2)) ; A partir d’une grammaire hors-contexte, accompagnée
Les mutateurs sont préfixés par Changer_. B := A ; d’un ensemble d’actions Ada, Ayacc produit une
Changer_Fils1(B, Creation_Entier(4)) ;
procédure YYParse.
Exemples :
Changer_Fils1(A3, Creation_Entier(3)) ; Acces_Fils1(A) → Noeud_Entier(4)
YYParse réalise l’analyse syntaxique et effectue les
Donc la modification de l’arbre B a modifié l’arbre A.
des décors, qui serviront lors de la passe 2. actions associées aux règles de la grammaire.
L’affectation entre deux arbres est une affectation
des procédures d’affichage. La procédure YYParse utilise
entre pointeurs.
function YYLex return Token ;
procedure Afficher_Arbre C := Creation2(Noeud_Plus,
(A : in Arbre; Niveau : in Natural := 0);
qui peut être soit définie explicitement, soit être
Creation_Entier(4), Creation_Entier(2)) ;
produite par Aflex ;
A = B → true
permet d’afficher un arbre, avec un certain niveau A = C → false procedure YYError(S : String) ;
de détail pour les décors. Si niveau = 0, les décors qui sera appelée chaque fois qu’une erreur de
ne sont pas affichés. syntaxe est détectée.
L’égalité entre deux arbres est une égalité entre
procedure Decompiler pointeurs (et non une égalité structurelle).
(A : in Arbre; Niveau : in Natural := 0);
permet de « décompiler » un arbre abstrait, c’est-à- La plupart des types abstraits utilisés dans le projet sont
dire d’afficher le programme Cas correspondant. implémentés à l’aide de pointeurs. Pour tous ces types,
on a donc une « sémantique de partage ».

31 32 33

En pratique : b) Structure du fichier syntax.y c) Principe de l’analyse syntaxique

[Link] Analyse ascendante
gnayacc syntax_goto.ads
syntax.y syntax_shift_reduce.ads On reconnait des parties droites de règles et on essaie de
syntax_tokens.ads Définitions des tokens, remonter vers l’axiome de la grammaire.
du type YYSType,
des opérateurs et de l’axiome Exemple 1.
Grammaire pour le langage xn a yn.
[Link] : fichier principal, qui contient la
%% A : ‘x’ A ‘y’ { Put_Line("A -> x A y") ; }
procédure YYParse et le code Ada correspondant | ‘a’ { Put_Line("A -> a") ; }
aux actions à effectuer.
On considère la chaîne d’entrée : x x a y y
Dans le projet, ce fichier contient le corps du Règles { actions }
paquetage Syntax. On a des « empilements » et des « réductions ».
(shift/reduce en anglais)
%% y
syntax_tokens.ads : contient les déclarations des
a A y
types Token et YYSType, et des variables YYLVal et x x A
YYVal. Contexte utilisateur : A
x x x
procédure ou paquetage Ada
syntax_goto.ads et syntax_shift_reduce.ads ## -- emplacement de la fonction YYParse
contiennent des tables utilisées par YYParse. Les flèches correspondent à des « réductions ».

Lorsqu’on réduit, l’action correspondante est effectuée.

On affiche donc :
A -> a
A -> x A y
A -> x A y

34 35 36
La chaîne est reconnue si, après avoir empilé tous les Exemple 2. On peut reconnaître le même langage avec une
caractères et effectué toutes les réductions, la pile ne Soit le langage a b* c, engendré par la grammaire : grammaire récursive à gauche :
contient que l’axiome de la grammaire.
A : ‘a’ B A : B ‘c’
B : ‘b’ B | ‘c’ B : B ‘b’ | ‘a’
Arbre de dérivation
On considère la chaîne d’entrée : a b b b c On reprend la même chaîne d’entrée : a b b b c
A

c B b b b c
x A y b b B a B B B B A
b b b B
b b b b B
a a A Les réductions ont lieu au fur et à mesure des
a a a
x A y empilements.

a On doit empiler toute la chaîne d’entrée avant de Conclusion

commencer à réduire. En analyse ascendante, on utilise de préférence des
Analyse ascendante : on effectue d’abord les règles règles récursives à gauche (pour des raisons de place
associées aux feuilles de l’arbre de dérivation, puis on Problème mémoire).
remonte vers l’axiome. La pile utilisée par Ayacc a une taille limitée ; donc si la
chaîne d’entrée est très longue, la pile déborde. Par exemple, dans le projet, on a la règle :

La grammaire est récursive à droite. liste_inst : liste_inst inst ‘;’

| inst ‘;’

Rappel : en analyse descendante, on utilise des règles

récursives à droite. En effet lorsqu’une règle est
récursive à gauche, la grammaire n’est pas LL(1).

37 38 39

d) Attributs Dans l’action associée à cette règle, on calcule la valeur Dans syntax_tokens.ads sont définies deux variables
de $$ en fonction des $i: globales :
A chaque terminal et non terminal de la grammaire est YYLVal, YYVal : YYSType ;
program : PROGRAM_Lex liste_decl BEGIN_Lex
associé un attribut synthétisé (c’est-à-dire un attribut liste_inst END_Lex
transmis du fils vers le père dans l’arbre de dérivation). { $$ := (NT, Creation2(Noeud_Programme,
YYLVal correspond à la valeur de l’attribut des
$2.Val_Arbre, terminaux ($i pour les XXX_Lex)
Pour les terminaux, l’attribut est la valeur YYLVal mise à $4.Val_Arbre, YYVal correspond à l’attribut de l’axiome de la
$1.Num_Ligne_Autre)) ; grammaire ($$ de program).
jour dans lexico.l : }
(Lex_Autre, Num_Ligne_Autre)
(Lex_Idf, Num_Ligne_Idf, Val_Idf) idf : IDF_Lex Dans syntax.y, on trouve la procédure principale de
... { $$ := (NT, Creation_Ident($1.Val_Idf, l’analyseur syntaxique :
$1.Num_Ligne_Idf)) ;
Pour les non-terminaux, l’attribut est de la forme : } procedure Analyser_Construire_Arbre
(NT, Val_Arbre). (A : out Arbre) is
const : CONSTENT_Lex begin
{ $$ := (NT, Creation_Entier($1.Val_Entier, YYParse ;
Ces valeurs permettent de construire l’arbre abstrait $1.Num_Ligne_Entier)) ; A := YYVal.Val_Arbre ;
associé au programme. } end ;

exp : exp ‘+’ exp

Considérons par exemple la règle : { $$ := (NT, Creation2(Noeud_Plus,
$1.Val_Arbre, Travail à effectuer : compléter syntax.y
program : PROGRAM_Lex liste_decl BEGIN_Lex $3.Val_Arbre,
$$ $1 $2 $3 $2.Num_Ligne_Autre)) ;
liste_inst END_Lex Programme de test fourni : test_synt, page C-27.
}
$4 $5

$1 ≡ (Lex_Autre, No_Ligne1) exp : facteur

$2 ≡ (NT, A2) A2 == $2.Val_Arbre { $$ := $1 ;
$3 ≡ (Lex_Autre, No_Ligne2) }
$4 ≡ (NT, A4) A4 == $4.Val_Arbre
$5 ≡ (Lex_Autre, No_Ligne3)

40 41 42

III. Passe II : vérifications contextuelles réel, qui correspond à un sous-ensemble de ℝ. Equivalence de types
équivalence structurelle ( équivalence de nom).
booléen, qui correspond à l’ensemble {vrai, faux}
Buts de la passe 2 : On a deux constantes de type booléen : true Exemple :
vérifier qu’un programme Cas est contextuellement (valeur vrai) et false (valeur faux). v1 : array[1..10] of integer ;
correct ; m : array[1..5] of array[1..10] of integer;
enrichir et décorer l’arbre abstrait pour préparer la string. Pas de syntaxe dans le langage Cas. On ne v2 : array[1..10] of integer ;
passe 3. peut donc pas déclarer de variable de type string.
m[1], m[2], ... v1 et v2 sont de même type.
On a uniquement des littéraux de type string
1. Contraintes contextuelles comme dans l’instruction : v1 := v2 ; -- ok
write( ok ) ; m[1] := v1 ; -- ok
Les contraintes contextuelles du langage Cas sont m := v1 ; -- interdit
définies dans [Link] page B-6. tableau
Syntaxe : array[ type_intervalle ] of type
a) Les types du langage Cas Exemples :
array[1..10] of integer
Les types du langage Cas sont les suivants : intervalle array[1..10] of array[1..5] of boolean
d’entiers, réel, booléen, string et tableau.
Grammaire de types du langage Cas
intervalle d’entiers
Exemple : 1..10 représente l’intervalle des entiers EXP_TYPE INTERVALLE
de 1 à 10, noté interval(1,10). | real
max_int est une constante qui représente l’entier | boolean
maximal du langage Cas, de valeur valmax. | string
Le type integer représente | array(INTERVALLE, EXP_TYPE)
interval(-valmax, valmax).
INTERVALLE interval(entier, entier)

43 44 45
 L’environnement associe à chaque identificateur une c) Profils de opérateurs
b) Règles de visibilité définition.
integer : type interval(-valmax, valmax)
Les règles de visibilités du langage Cas sont les Au début de l’analyse du programme, l’environnement interval : un type intervalle quelconque interval(a,b).
suivantes : contient uniquement les identificateurs prédéfinis.
On ne peut pas re-déclarer un identificateur déjà not : boolean boolean
déclaré. Environnement prédéfini :
and, or : boolean, boolean boolean
Tout identificateur apparaissant dans un programme
Cas doit être déclaré, sauf les identificateurs boolean (type, boolean) =, <, >, /=, <=, >= : interval, interval boolean
prédéfinis. false (const(faux), boolean) interval, real boolean
Les identificateurs prédéfinis ne peuvent pas être true (const(vrai), boolean) real, interval boolean
redéfinis. integer (type, integer) real, real boolean
max_int (const(valmax), integer)
Les identificateurs d’un programme Cas sont de +, - : interval integer
real (type, real)
différentes natures : real real
identificateurs de constantes (de type intervalle,
booléen, réel ou chaîne) ; +, - , *: interval, interval integer
identificateurs de type ; interval, real real
identificateurs de variable. real, interval real
real, real real
Nature = {const, type, var}.
div, mod : interval, interval integer
Seuls des identificateurs de variables peuvent être / : interval, interval real
déclarés dans un programme Cas. Les seuls interval, real real
identificateurs de constante et de type sont donc des
real, interval real
identificateurs prédéfinis.
real, real real
La nature des identificateurs doit être vérifiée.
[ ] (indexation) array(interval, type) type

46 47 48

d) Vérifications de type 2. Enrichissement et décoration de l’arbre

Noeud_Affect
abstrait
Intervalles exp_const1 .. exp_const2
exp_const1 et exp_const2 doivent être de type L’enrichissement et la décoration de l’arbre abstrait a
interval. pour but de préparer la passe 3 (génération de code).
Affectations place := expression cf. [Link] page B-14. Noeud_Ident Noeud_Plus
Le type de place et le type de expression doivent r
être compatibles pour l’affectation, c’est-à-dire : a) Ajouts de Noeud_Conversion
o place et expression de type interval (pas
forcément avec les mêmes bornes) ; Le langage Cas autorise l’ajout d’un entier et d’un réel,
o place et expression de type real ; ou l’affectation d’un entier à un réel. Noeud_Ident Noeud_Reel
o place et expression de type boolean ; i 0.5
o place de type real et expression de type On ne peut pas réaliser cela directement en assembleur :
interval ; il faut commencer par convertir l’entier en réel.
o place et expression de type array, les types des
indices étant identiques (de type interval, avec Un Noeud_Conversion représente la conversion d’un
les mêmes bornes), et les types des éléments entier vers un réel (et non l’inverse !) Noeud_Affect
compatibles pour l’affectation.
Instructions if et while : la condition doit être de Exemples :
type boolean.
r : real ; Noeud_Ident Noeud_Plus
Instruction for : la variable de contrôle, ainsi que i : integer ;
les deux expressions doivent être de type interval. r
Instruction read : la place doit être de type interval r := i + 0.5 ;
r := i + 1 ;
ou real.
Instruction write : les expressions doivent être de Pour ajouter les Noeud_Conversion, on utilise les Noeud_Conversion Noeud_Reel
type interval, real ou string. procédures Changer_Fils1 et Changer_Fils2 du 0.5
Les places et expressions doivent être bien typées paquetage Arbre.
vis-à-vis des déclarations et des profils des
opérateurs.
Noeud_Ident
i
49 50 51

b) Décoration de l’arbre abstrait

3. Mise en œuvre de la passe 2
Noeud_Affect A chaque nœud de l’arbre est associé un décor. Un
décor est un triplet : a) Paquetages fournis
(Def: Defn, Type: Exp_Type, Info_Code: Integer) Exp_Types : paquetage permettant de manipuler des
types du langage Cas ;
Noeud_Ident Noeud_Plus Def est associé aux Noeud_Ident. Defns : paquetage permettant de manipuler des
r Type est associé aux Noeud_Affect, définitions.
Noeud_Conversion et à tous les nœuds qui dérivent Remarque : une Defn est un triplet
(String, Nature_Defn, Exp_Type).
de EXP dans la grammaire d’arbres.
Info_Code servira en passe 3 pour calculer le
Decors : paquetage permettant de manipuler des
Noeud_Ident Noeud_Entier décors.
i 1 nombre de registres nécessaires pour évaluer une
expression.
b) Implémentation de la passe 2
Sémantique de partage : les Defn et Exp_Type sont La passe 2 est un parcours de l’arbre abstrait du
partagées. programme. Lors de ce parcours :
on vérifie que le programme Cas est
Noeud_Affect Par exemple, tous les Noeud_Ident correspondant au contextuellement correct ;
même identificateur sont décorés avec la même Defn. on ajoute des Noeud_Conversion ;
on décore les différents nœuds de l’arbre.
Noeud_Ident Noeud_Conversion Noeud_Affect Pour implémenter ce parcours d’arbre, on suit
r
exactement la grammaire d’arbres. On écrit (au
minimum) une procédure par non-terminal de la
Noeud_Ident Noeud_Plus grammaire d’arbres.
Noeud_Plus i
procedure Verif_PROGRAMME(A : in Arbre) ;
(var, integer) procedure Verif_LISTE_INST(A : in Arbre) ;
Noeud_Ident Noeud_Entier procedure Verif_DECL(A : in Arbre) ;
Noeud_Ident Noeud_Entier i 1 ...
i 1
52 53 54
Pour les identificateurs, il faut distinguer les Exercice Ecrire la procédure de construction de
déclarations et les utilisations d’identificateurs. Pour cette étape, il est important de l’environnement prédéfini.
procedure Verif_IDENT_Decl(A : in Arbre; ...) ; bien décomposer les problèmes en écrivant des
procedure Verif_IDENT_Util(A : in Arbre; ...) ; procédures courtes ; A faire
factoriser les éléments communs (pas de copié- Erreur : paquetage définissant une procédure qui
On peut également définir d’autres procédures pour les
collé !) ; affiche un message d’erreur.
différents nœuds de l’arbre.
Environ : paquetage qui définit l’environnement.
regrouper les procédures dans plusieurs paquetages
Exemple : Règles_Typage : paquetage définissant des
(ex : déclarations, instructions, expressions).
prédicats indiquant si deux types sont compatibles
procedure Verif_LISTE_INST(A : in Arbre) is Dans les spécifications des paquetages, on déclare
begin (pour une affectation, pour un opérateur binaire,
case Acces_Noeud(A) is uniquement ce qui est utilisé par d’autres pour un opérateur unaire).
when Noeud_Vide => paquetages (types, fonctions, procédures) Verif : paquetage principal de la vérification
null ;
when Noeud_Liste_Inst => compiler et tester au fur et à mesure ; contextuelle.
Verif_LISTE_INST(Acces_Fils1(A)) ; Autres paquetages de vérifications.
Verif_INST(Accces_Fils2(A)) ; conserver et documenter tous les fichiers de test :
when others => o tests de non régression ; scripts permettant A Rendre
Erreur_Interne(
"Arbre incorrect dans Verif_LISTE_INST") ; d’enchaîner les tests ; Programmes
end case ; o commentaire indiquant le résultat du test Jeux de tests
end ;
(passe, erreur contextuelle ligne n) Documentation décrivant :
procedure Verif_INST(A : in Arbre) is o les messages d’erreurs,
begin o l’architecture de la passe 2,
case Acces_Noeud(A : in Arbre) is o compte rendu sur l’utilisation de Gcov (tests
when Noeud_Nop => null ;
when Noeud_Affect => Verif_Affect(A) ; ajoutés, couverture obtenue).
when Noeud_Pour => Verif_Pour(A) ;
... Temps : deux fois plus que pour la passe 1.
when others => Passe 1 : 200 lignes pour lexico.l
Erreur_Interne(
"Arbre incorrect dans Verif_INST") ; 500 lignes pour syntax.y
end case ; Passe 2 : 1500 lignes
end ;

55 56 57