Techniques de compilation

par exemple si on dispose de la grammaire avec les règles

suivantes: DCL fi

Var L_ID : TYPE; | Var L_ID : TYPE; DCL | e | e

L_ID fi TYPE fi

id | id, L_ID

entier | réel

Les unité lexicales associées au mot (retournées par l’AL à l’AS):

Var a, b: entier; var c: réel;

Sont les suivantes :

Var

id

,

id

:

entier

;

Var

id

:

réel

;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

21

fi fi fi e e e e e e fi fi fi fi fi fi I.3. Phases de compilation

par exemple si on dispose de la grammaire avec les règles

suivantes: DCL fi

Var L_ID : TYPE; | Var L_ID : TYPE; DCL | e | e

L_ID fi TYPE fi

id | id, L_ID

entier | réel

Table des id de variables

N°

Lexème

Type

1

2 2

3

a

b b

c

entier

entier entier

réel

Si l’AL retourne un résultat à l’AS et l’Asem alors le résultat de

l’AL pour le mot Var a, b: entier; var c: réel; sera :

Var 0

Id 1

, 0

Id 2

: 0

entier 0

; 0

Var 0

Id 3

: 0

réel 0

; 0

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

22

fi fi fi e e e e e e fi fi fi fi fi fi I.3. Phases de compilation

Soit le mot a := c + 34; l’AL retourne Pour l’AS : id := id oparith nb; Pour l’Asem : 1 := 3 oparith nb;

Id 1

:= 0

Résultat de l’AL

Id 3

oparith +

nb 34

; 0

c-a-d entier := réel oparith entier

Pour le traducteur : @a := @c + 34; Pour le traducteur : @a := @c + 34;

N°

1

2

3

Table des id de variables

Lexème

a

b

c

Type

entier

entier

réel

Adresse

@a

@b

@c

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

23

I.3. Phases de compilation

par exemple si on dispose de la grammaire avec les règles

suivantes: P fi DCL fi

fi DCL L_I

Var L_ID : TYPE; | Var L_ID : TYPE; DCL | Var L_ID : TYPE; DCL | e

id | id, L_ID entier | réel

L_ID fi TYPE fi L_I fi

Table des id de variables

N°

Lexème

Type

1

2 2

3

a

b b

c

entier

entier entier

réel

id := nb; | id := id; | id := nb; L_I | id := id; L_I

Si l’AL retourne un résultat à l’AS, l’Asem et le traducteur alors le résultat de

l’AL pour le mot Var a, b: entier; var c: réel; b := 10; sera :

Var 0

Id 1

, 0

Id 2

: 0

entier 0

; 0

Var 0

Id 3

: 0

réel 0

; 0

id 2

:= 0

nb 10

; 0

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

24

fi fi fi fi fi I.3. Phases de compilation

Var a, b: entier; var c: réel; b := 10;

Table des id de variables

N°

Lexème

Type

1

2 2

3

a

b b

c

entier

entier entier

réel

Var 0

Id 1

, 0

Id 2

: 0

entier 0

; 0

Var 0

Id 3

: 0

réel 0

; 0

id 2

:= 0

nb 10

; 0

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

25

I.3. Phases de compilation

Analyse du programme source :

les

sont

unités

lexicales

– Phase2: analyse hiérarchique (ou syntaxique) au cours de regroupées

laquelle hiérarchiquement en structure grammaticale. L’analyse syntaxique consiste à vérifier que la suite d’unités L’analyse syntaxique consiste à vérifier que la suite d’unités lexicales est générée par la grammaire du langage. Ceci revient à construire un arbre d’analyse (ou syntaxique) dont les feuilles concordent avec la suite d’unités lexicales en les parcourant de gauche à droite.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

26

I.3. Phases de compilation

Analyse du programme source :

– Phase3: analyse sémantique au cours de laquelle on opère certain contrôle pour s’assurer que l’assemblage des constituants du programme a un sens. Une des opérations principales d’un Asem est le contrôle de type des le contrôle de type des principales d’un Asem est opérandes d’une opération, le contrôle de la portée des identificateurs sous programme, ….

au moment

l’appel

d’un

de

– Dans le contrôle de type,

l’analyseur sémantique peut insérer des opérations de conversion pour les expr d’entier vers réel.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

27

I.3. Phases de compilation

Analyse du programme source :

– Phase3: analyse sémantique Nous distinguons deux types d’erreurs sémantiques:

• sémantique statique, contrôlée au moment de la compilation telle

que : que :

– Variable non déclarée – l’incompatibilité de type, – la portée d’une variable…

• Sémantique dynamique, contrôlée au moment de l’exécution telle

que :

– la division par zéro – les boucles infinies – le débordement mémoire

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

28

I.3. Phases de compilation

Analyse du programme source :

– Phase4: traduction en code intermédiaire au cours de laquelle la séquence d’instructions du programme est traduite en une séquence d’instructions dans un langage intermédiaire. Par exemple : le langage pour machine à intermédiaire. Par exemple : le langage pour machine à pile, le langage C, …

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

29

I.3. Phases de compilation

Analyse du programme source :

– La table des symboles contient des informations sur les différents symboles et les attributs associés. Par exemple les identificateurs de les mots clés (ou réservés) et variables en spécifiant l’unité lexicale id et leurs attributs: variables en spécifiant l’unité lexicale id et leurs attributs: type, adresse, etc…

– A chaque fois qu’une unité lexicale id est trouvée par l’AL, le lexème associé est inséré dans la table des symboles s’il n’a pas été déjà inséré et l’AL retourne id et un pointeur vers une entrée de la table des symboles.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

30

I.3. Phases de compilation

Exemple

On veut illustrer les phases de compilation sur l’exemple

suivant :

Position := Initiale + Vitesse * 60;

id := Exp; id := Exp;

La grammaire est la suivante : P fi P fi Exp fi id | nb | (Exp) | Exp + Exp | Exp * Exp Une Contrainte sémantique doit être vérifiée :

L’opérateur de multiplication doit être appliqué à deux opérandes de même type (entier, entier) ou (réel, réel) Pour notre exemple, Vitesse est un réel et 60 est un nombre entier, il faut alors convertir 60 d’entier vers réel (60.0)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

31

I.3. Phases de compilation

• Analyse lexicale

id1 := id2 + id3 * nb;

• Analyse syntaxique

P

id := Exp

;

Exp + Exp

id Exp * Exp

id nb

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

32

I.3. Phases de compilation

• Analyse sémantique Comme vitesse est un réel, un compilateur peut convertir le nombre entier nb en réel pour pouvoir utiliser l’opérateur de multiplication

Var position, Initiale, Vitesse : réel;

P

Analyseur Sémantique

id := Exp

Table des id de variables

Exp + Exp

N°

Lexème

Type

1

2

3

Position

Initiale

Vitesse

Réel

Réel

Réel

id Exp * Exp

id 60

entier vers réel 60.0

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

33

I.3. Phases de compilation

• Génération de code intermédiaire Temp1 := Entier vers réel(60); Temp2 := Temp1*id3; Temp3 := id2 + Temp2; id1 := Temp3;

• Optimisation de code Analyse syntaxique • Optimisation de code Analyse syntaxique

Temp1 := id3*60.0; id1 := id2 + Temp1;

• Génération de code intermédiaire (Machine VON NEUMAN)

Machin à registres MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

34

I.4. Qualité d’un compilateur

–Fournir le maximum d’erreurs en

une seule compilation une seule compilation

–Rapidité

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

35

I.5. Outils pour la construction de I.5. Outils pour la construction de compilateurs compilateurs

– Assembleur – Assembleur – Ecriture en langage évolué – Constructeurs automatiques de compilateurs : LEX et YACC

Grammaire non Grammaire non contextuelle du langage

Description des unités lexicales du langage

Leila Jemni Ben Ayed

Générateur automatique d’analyseur syntaxique

Analyseur Syntaxique Écrit en C ou en LPascal

Générateur automatique d’analyseur lexical

Analyseur lexical Écrit en C ou en LPascal

Yacc

Lex

Cours Techniques de Compilation-2012- 2013

36

II. Analyse lexicale

Plan

II.1. Présentation générale II.2. Automates finis et expressions régulières II.2. Automates finis et expressions régulières II.3. Spécification des unités lexicales II.4. Reconnaissance des unités lexicales II.5. Conception d’un générateur d’un analyseur

lexical

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

37

II.1. Présentation générale

• L’analyseur

lexical constitue la première phase d’un compilateur. Sa tâche principale est de lire les caractères d’entrée et de produire comme résultat une suite d’unités lexicales que l’analyseur syntaxique va utiliser.

Programme Source

Lire caractère

Rendre caractère

Analyseur lexical

Passer unité lexicale et ses lexicale et ses attributs

Obtenir prochaine unité lexicale

Table des symboles

Analyseur syntaxique

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

38

II.1. Présentation générale

•

Rq. L’AL est un sous programme de l’AS. A la réception de « prochaine unité », l’AL lit les caractères d’entrée jusqu’à ce qu’il puisse identifier la prochaine unité lexicale.

Unité lexicale : produite la même pour un ensemble de chaines de caractères Modèle d’une unité lexicale : règle qui décrit une unité lexicale (Expression régulière) Lexème : une suite de caractères du PS qui concorde avec le modèle d’une unité

lexicale.

Unité Lexicale

Lexèmes

Description formelle des modèles

const

if

oprel

id

nb

const

if

const

If

< <= = <> > >=

(<+<=+=+<>+>+>=)

Pi compte D2

3 6.780 6.0

lettre(lettre+chiffre)*

Chiffre+ + chiffre+.chiffre+

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

39

II.2. Automates finis et expressions II.2. Automates finis et expressions régulières régulières • Un analyseur lexical est basé sur les systèmes de transition (ou bien les

automates finis)

Un diagramme de transition pour la reconnaissance de >=

Début

0

>

=

1

autre

2

3

return(oprel, PGE)

* return(oprel, PGQ)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

40

II.2. Automates finis et expressions II.2. Automates finis et expressions régulières régulières

Un diagramme de transition pour la reconnaissance

de >= Début

>

0

=

1

autre

2

3

return(oprel, PGE)

* return(oprel, PGQ)

Ce diagramme fonctionne comme suit: Son état de départ est l’état 0. Dans l’état 0, on lit le prochain caractère de l’entrée. On suit l’arc > depuis l’état 0 vers l’état 1 si le caractère d’entrée est >. Sinon, on n’a réussi à reconnaître ni > ni >=. En atteignant l’état 1, on lit le prochain caractère d’entrée. L’arc étiqueté = entre l’état 1 et l’état 2 doit être suivi si le caractère d’entrée est = et le diagramme reconnaît >= (PGE). Autrement, l’arc étiqueté autre conduit à l’état 3. Le diagramme reconnaît ainsi > (PGQ) et recule d’un caractère dans l’entrée. On utilise une * pour signaler les états dans lesquels ce recul dans l’entrée doit être fait.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

41

II.2. Automates finis et expressions II.2. Automates finis et expressions régulières régulières

Un diagramme de transition pour la

reconnaissance des opérateurs de relation

Début

0

<

1

=

>

=

>

autre

2

3

4

return(oprel, PPE)

return(oprel, DIF)

* return(oprel, PPQ)

5

return(oprel, EGA)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

6

=

autre

return(oprel, PGE)

* return(oprel, PGQ) 42

7

8

II.2. Automates finis et expressions II.2. Automates finis et expressions régulières régulières Un diagramme de transition pour la reconnaissance

des identificateurs et des mots clés

lettre, chiffre

Début

0

lettre

autre

1

* *

2

return(UnilexId(), RangerId())

L’action spécifiée par le symbole * permet de reculer d’une position sur le

fichier source après la consommation d’un symbole autre qu’une lettre ou un chiffre.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

43

II.2. Automates finis et expressions II.2. Automates finis et expressions régulières régulières

Les fonctions RangerId() et UnilexId()

-

-

La fonction RangerId() a accès au tampon où l’unité lexicale identificateur a été localisée. On examine la table des symboles et si on trouve le lexème avec l’identificateur mot clé, RangerId() rend 0. Si on trouve le lexème comme variable du programme, RangerId() rend un pointeur vers une entrée dans la table des symboles. Si on ne trouve pas le lexème dans la table des symboles, il y est placé en tant que variable et un pointeur vers cette nouvelle entrée est retourné. variable et un pointeur vers cette nouvelle entrée est retourné. La fonction UnilexId() recherche le lexème dans la table des symboles. Si le lexème est un mot clé, l’unité lexicale correspondante est retournée; autrement, l’unité lexicale id est retournée.

NB. 1)

2)

Le diagramme de transition ne change pas si on doit reconnaître de nouveaux mots clés; on initiale simplement la table des symboles avec les nouvelles chaines et les nouvelles unités lexicales. En pratique, la table des symboles peut être répartie sur deux tables: table des mots clés et table des identificateurs de variables.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

44

II.3. Spécification des unités lexicales

Expressions régulières Les expressions régulières sont une notation importante pour

spécifier des modèles d’unités lexicales.

Exemples: Soit L l’ensemble {A, B, …, Z, a, b, …z} et C l’ensemble {0, 1, …9} L+C ou(L ¨ C) est l’ensemble des lettres et des chiffres L+C ou(L ¨ C) est l’ensemble des lettres et des chiffres 1. 1. LC est l’ensemble des chaines formées d’une lettre suivie 2. d’un chiffre L4 est l’ensemble des chaines de quatre lettres L* est l’ensemble de toutes les lettres, y compris e , la chaine vide. L(L+C)* est l’ensemble de toutes les chaines de lettres et de chiffres commençant par une lettre. C+ est l’ensemble de toutes les chaines d’au moins un chiffre (représentations décimales des entiers naturels)

3. 4.

6.

5.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

45

II.3. Spécification des unités lexicales

Définitions régulières Soit S un alphabet de symboles de base, une définition régulière est une suite de

définitions de la forme :

r1 r2

d1 d2 …… dn Où chaque di est un nom distinct et chaque ri est une expression régulière sur les

rn

symboles de S

{d1, d2, …, di-1}

Exemples: Lettre fi chiffre fi id fi

A|B|…|Z|a|b|…|z 0|1|…|9

Lettre(Lettre + Chiffre)*

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

46

fi fi fi ¨ II.4. Reconnaissance des unités II.4. Reconnaissance des unités lexicales lexicales

Nous utilisons les diagrammes de transition pour reconnaître des unités lexicales Exemple: Considérons le fragment de la grammaire suivant: Instr fi

si expr alors instr

| si expr alors instr sinon instr | id opaff id pv | id opaff nb pv | id opaff nb pv

terme oprel terme

| terme

id | nb

expr fi

terme fi

Où si, alors, sinon, oprel, id et nb engendrent les ensembles de chaines données par

les définitions régulières suivantes: si fi si alors fi sinon fi oprel fi id fi

alors sinon < | <= | = | <> | > | >=

lettre(lettre|chiffre)*

nb fi opaff fi pv fi

chiffre+ :=

;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

47

II.4. Reconnaissance des unités II.4. Reconnaissance des unités lexicales lexicales

Le mot en entrée dans le fichier source est le suivant :

si a1 >= b alors a1

10;

:=

N°

lexème

type

Mots clés

1 1

2

3

a1 a1

b

…

… …

…

…

si si

alors

L’analyseur lexical retourne la séquence suivante d’unités lexicales avec leurs attributs:

si 0

id 1

oprel PGE

id 2

alors 0

id 1

opaff :=

nb 10

pv ;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

48

II.4. Reconnaissance des unités II.4. Reconnaissance des unités lexicales lexicales Rq. On suppose que les lexèmes sont séparés par un espace consistant d’une suite non vide de blancs, tabulations et fins de lignes. Notre analyseur lexical doit éliminer ces espaces en comparant une chaine avec la définition régulière suivante :

Délim fi Délim fi bl fi

délim+

blanc | tabulation | fin de ligne blanc | tabulation | fin de ligne

Si l’analyseur lexical trouve une correspondance avec bl, il ne retourne pas l’unité lexicale à l’analyseur l’unité syntaxique. lexicale qui suit le blanc et le retourne à l’analyseur syntaxique.

Il continue pour

rechercher

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

49

fi fi fi fi fi fi fi fi fi II.4. Reconnaissance des unités lexicales Système de transition associé à un analyseur lexical

bl, tab, \n

l

Début

0

Echec()

autre

EOF

l, c

3

1

5

c

< <

=

>

autre

c

2

autre

= =

>

autre

9

*

return(UnilexId(), RangerId())

4

* return(nb, val)

return(oprel, PPE) return(oprel, PPE)

return(oprel, DIF)

6

7

* return(oprel, PPQ)

8

return(oprel, EGA)

14

13

return(EOF, 0)

10

=

autre

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

return(oprel, PGE)

* return(oprel, PGQ) 50

11

12

II.4. Reconnaissance des unités lexicales Système de transition associé à un analyseur lexical

Init(Val)

bl, tab, \n

l

l, c

1

Début

0

Add(Val, c)

c

3

autre

2 Add(Val, c) c

autre

*

return(UnilexId(), RangerId())

4

* return(nb, conv(val))

return(oprel, PPE) return(oprel, PPE)

return(oprel, DIF)

6

7

Erreur()

autre

EOF

5

< <

=

>

= =

>

autre

9

* return(oprel, PPQ)

8

return(oprel, EGA)

14

13

return(EOF, 0)

10

=

autre

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

return(oprel, PGE)

* return(oprel, PGQ) 51

11

12

II.4. Reconnaissance des unités lexicales Code C d’un analyseur lexical

Unilex AnalLex() /* Unilex est une chaine si Alalex retourne uniquement l’unité lexicale*/

{

/* Unilex est un entier si Analex retourne l’unité lexicale et chaque unité est définie comme une

constante*/ While(1) /* Unilex est un enregistrement si Analex retourne l’unité lexicale et un attribut*/

{

Switch(etat) Switch(etat) {

case 0: Init(Chaine); car = carsuivant();

if(car == ‘ ‘ || car == ‘\t’ || car = ‘\n’) { etat = 0; debutlex ++; } else if( car == ‘<‘) etat = 5; else if (car == ‘=‘) etat = 9; else if (car == ‘>’) etat = 10; else if (isletter(car)) Ajouter(car, chaine); etat = 1; else if(isdigit(car)) Ajouter(car, chaine); etat = 3; else if(car == EOF) etat = 13; else Erreur();

case 1: car = carsuiv();

if(isletter(car) || isdigit(car))

ajouter(car, chaine);;

else etat = 2; break;

case 2: Reculer(1); RangerId(); return(UniLexId()); /* cas où l’analyseur lexical retourne uniquement cas où l’analyseur lexical retourne uniquement */l’unité lexicale sinon, il faut utiliser un enregistrement (symbole)*/

………….

case 3: car = carsuiv();

if(isdigit(car)) ajouter(car, chaine); else etat = 4; break;

case 4 : Reculer(1); Return(NB); case 6: Return(Oprel);

…………… case 13: Return(EOF); }

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

52

II.4. Reconnaissance des unités lexicales Code C d’un analyseur lexical (cas du retour d’un enregistrement dans une variable globale symbole à deux champs (UL, Att))

Unilex AnalLex() /* Unilex est une chaine si Alalex retourne uniquement l’unité lexicale*/

{

/* Unilex est un entier si Analex retourne l’unité lexicale et chaque unité est définie comme une

constante*/ While(1) /* Unilex est un enregistrement si Analex retourne l’unité lexicale et un attribut*/

{

Switch(etat) Switch(etat) {

case 0: Init(Chaine)car = carsuivant();

if(car == ‘ ‘ || car == ‘\t’ || car = ‘\n’) { etat = 0; debutlex ++; } else if( car == ‘<‘) etat = 5; else if (car == ‘=‘) etat = 9; else if (car == ‘>’) etat = 10; else if (isletter(car)) etat = 1; else if(isdigit(car)) etat = 3; else if(car == EOF) etat = 13; else Erreur();

case 1: car = carsuiv();

if(isletter(car) || isdigit(car))

ajouter(car, chaine);;

else etat = 2; break;

case 2: Reculer(1); symbole.att = RangerId(); case 2: Reculer(1); symbole.att = RangerId(); symbole.UL = UniLexId(); Return(Symbole); ………….

case 3: car = carsuiv();

if(isdigit(car)) ajouter(car, chaine); else etat = 4; break;

case 4 : Reculer(1); symbole.UL=NB; symbole.Att = toupper(chaine)); Return(symbole); case 6: symbole.UL = Oprel; symbole.att = PPE; Return(symbole); case 13: symbole.UL = EOF; symbole.att = 0; Return(symbole);} On peut retourner des numériques.

……………

53

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

II.4. Reconnaissance des unités lexicales II.4. Reconnaissance des unités lexicales Code C d’un analyseur lexical qui élimine les espaces et collecte les nombres les nombres

#include <stdio.h> #include <ctype.h> Int NumLigne = 1; Int Vallex = RIEN;

Int AnalLex() {

int T; While(1); { {

T = getchar(); if (T == ‘ ‘ || T == ‘\t’) ; else if (T == ‘\n’)

NumLigne ++;

else

if(isdigit(T)) {

Vallex = T-’0’;; T = getchar();

While (isdigit(T)) {

ValLex = ValLex*10+T-’0’; T = getchar(); T = getchar();

} ungetc(T, stdin); return NB;

} Else

ValLex = RIEN;

Return T;

}

}

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

54

II. Compilateur en une seule passe

Plan

II.1. Présentation générale II.2. Définition de la syntaxe II.3. Traduction dirigée par la syntaxe II.4. Un traducteur pour les expressions II.5. Analyse lexicale

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

55

II.1. Présentation générale

Un compilateur en une seule passe est un compilateur qui fait le

parcours du fichier source une seule fois.

L’analyseur lexical fournit un résultat aussi bien à l’analyseur

syntaxique, sémantique qu’au traducteur en code intermédiaire.

Il fournit ainsi: - - - -

Les unités lexicales à l’analyseur syntaxique Les unités lexicales à l’analyseur syntaxique Les types des identificateurs à l’analyseur sémantique et Les attributs des unités au traducteur en langage intermédiaire - Si l’unité est un nombre alors l’attribut est la valeur de ce nombre - Si l’unité est un opérateur arithmétique alors l’attribut est l’opérateur

en question (+, -, /, *)

- Si l’unité est oprel alors l’attribut est l’opérateur en question

(PPQ, PPE, PGQ, PGE, EGA, DIF)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

56

II.2. Définition de la syntaxe

• Consiste en une grammaire non contextuelle

– C’est une grammaire (V, T, S, R) où

• V est l’ensemble des symboles non terminaux • T est l’ensemble des terminaux • S est le symbole de départ où l’axiome de la grammaire • S est le symbole de départ où l’axiome de la grammaire • R est l’ensemble des règles de production de la forme A fi

u où u ˛

(V + T)*

• Un programme est syntaxiquement correct s’il peut être généré par

la grammaire associée au langage de programmation

•

Si le langage est l’ensemble des instructions d’affectation, alors un élément de l’ensemble est une instruction d’affectation Une grammaire possible est la suivante:

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

57

II.2. Définition de la syntaxe

Soit la grammaire non contextuelle G = (V, T, INST, R) où V = {INST, EXP} T = {id, :=, +, -, *, /, (, ), ;} INST fi R = { EXP fi | (EXP) | (EXP)

id := EXP; id | nb | EXP + EXP | EXP * EXP | EXP – EXP | EXP / EXP } }

INST est l’axiome de la grammaire. Un mot est généré par la grammaire si en

partant de l’axiome (le symbole de départ) et en appliquant successivement des règles de production, nous obtenons le mot (formé par une séquence de terminaux)

Par exemple le mot suivant est généré par la grammaire:

Id := id + (id*nb);

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

58

II.2. Définition de la syntaxe

Parce que on a: INST

id := EXP; id := EXP + EXP ; id := id + EXP ; id := id + EXP ; id := id + (EXP) ; id := id + (EXP * EXP) ; id := id + (id * EXP) ; id := id + (id * nb) ;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012- 2013

59

fi fi fi fi fi fi fi fi II.2. Définition de la syntaxe

Si le langage est formé par l’ensemble des séquences non vides d’instructions où chaque instruction est une instruction d’affectation alors une grammaire possible est la suivante :

LISTE_INST fi INST fi EXP fi EXP fi

INST | INST LISTE_INST

id := EXP; id | nb | EXP + EXP | EXP * EXP | EXP – EXP | EXP / EXP | (EXP) id | nb | EXP + EXP | EXP * EXP | EXP – EXP | EXP / EXP | (EXP)

LISTE_INST est l’axiome de la grammaire. Un mot est généré par la gramm