Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



Chap.3 Compilation Version Finale (ULT) .pdf



Nom original: Chap.3 Compilation Version Finale (ULT).pdf
Titre: Structure de la mémoire auxiliaire
Auteur: Farouk JELIDI

Ce document au format PDF 1.5 a été généré par Microsoft® PowerPoint® 2013, et a été envoyé sur fichier-pdf.fr le 19/01/2017 à 00:33, depuis l'adresse IP 197.18.x.x. La présente page de téléchargement du fichier a été vue 430 fois.
Taille du document: 1.6 Mo (24 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Grammaires
(Chapitre 3)
Farouk JELIDI
farouk.jelidi@gmail.com

2016-2017

Plan du cours
1.

Introduction

2. Grammaires
3. Analyse Syntaxique

1

1.

Introduction


Tout langage de programmation possède des règles qui indiquent la
structure syntaxique d’un programme bien formé.
La syntaxe d’un langage peut être décrite par une grammaire.




Cette grammaire décrit comment les unités lexicales doivent être
agencées..

1.

Introduction


L’analyseur syntaxique reçoit une suite d’unités lexicales de la part de
l’analyseur lexical et doit vérifier que cette suite peut être engendrée par la
grammaire du langage.



Le principe est d’essayer de construire un arbre de dérivation.
Il existe deux méthodes pour cette construction :
 méthode (analyse) descendante.
 méthode (analyse) ascendante.

2

1.

Introduction

Figure 1: Analyseur Syntaxique

2.


Grammaires

Exemple 1 :

Une expression arithmétique peut être :
o
la somme de deux expressions arithmétiques,
o
la multiplication de deux expressions arithmétiques,
o
une expression arithmétique entre parenthèses,
o
un identificateur.
Ceci peut être décrit plus formellement par :
o
E → E + E | E * E | ( E ) | id
Avec cette description, nous pouvons générer une infinité d’expressions
arithmétiques :
o
(id + id) * id
o
(id + id) * id + id + id * id
o
….

3

2.


Grammaires

Exemple 2 :

Une phrase peut être :
o
Sujet suivi d’un verbe, suivi d’un complément,
o
Un sujet peut être Ali ou Sami ou Mourad,
o
Un verbe peut être aime ou déteste,
o
Un complément est un sujet.
Ceci se décrit par :
o
phrase → sujet verbe complément
o
sujet → Ali | Sami | Mourad
o
verbe → aime | déteste
o
complément → sujet
Avec cette grammaire nous pouvons générer plusieurs phrases :
o
Sami aime Sami
o
Sami aime Ali
o
….

2.1

Définition

 Une grammaire ou une grammaire à structures de phrases est un
quadruplet (T,V,S,P) où :
o T un ensemble fini non vide de symboles terminaux (alphabet terminal).
o V un ensemble fini non vide de symboles non terminaux (catégories
syntaxiques) tel que T ⋂ V = ɸ
o S ∈ V est le symbole de départ, appelé axiome
o P est un ensemble de règles de production (ou de réécriture) sous la forme
α→β

 précisant que la séquence de symboles α (α ∈ ( V ⋃ T )+) peut être remplacée
par la séquence de symboles β (β ∈ ( V ⋃ T )*)
 α est appelée partie gauche de la production, β est appelée partie droite de la
production
 Le côté droit peut être vide, on parle de règle-ԑ (B →ԑ).

4

2.2

Convention

 Les symboles non terminaux sont décrits par des lettres majuscules
 Les symboles terminaux sont décrits par des lettres minuscules
 S est utilisé comme symbole de départ, sauf indication contraire
 Les séquences de symboles terminaux et non terminaux sont décrites par
les lettres grecques (α, β, …)

2.2


Convention

Exemple 1 :

Soit G1 = (T,V,S,P)
o
T = {a,b,c}
o
V = {S,A,B,C}
o
P= {
S → ASC
S→ B
B → bB
B→ԑ
A→a
C→c
}

5

2.2


Convention

Exemple 2 :

Soit G2 = (T,V,PH,P)
o
P= {
PH → SU GV CO
SU → ali | sami | mourad | ils
GV → VE CO
VE → aime | déteste
CO → SU | SU qui GV
}
o
T = {ali, sami, mourad, ils, aime, déteste, qui}
o
V = {PH, SU, GV, CO, VE}

2.3

Dérivation

Une grammaire génère une séquence par dérivation

Une dérivation est une suite d’applications de règles de productions
permettant de générer une séquence.

Dérivation de la séquence aabbbcc par G1 (diapo. 10)

Rappel :
S → ASC | B
B → bB | ԑ
A→a
C→c
 S ⇒ASC ⇒ AASCC ⇒ aASCC ⇒ aaSCC ⇒ aaScC ⇒ aaScc ⇒ aaBcc
⇒aabBcc ⇒ aabbBcc ⇒ aabbbBcc ⇒ aabbbcc


6

2.3

Dérivation

Dérivation de la séquence « sami aime ali qui déteste mourad » à partir
de la grammaire G2 (diapo. 11)

Rappel :
PH → SU GV CO
SU → ali | sami | mourad | ils
GV → VE CO |VE
VE → aime | déteste
CO → SU | SU qui GV
 PH ⇒ SU GV CO ⇒ sami GV CO ⇒ sami VE CO CO ⇒ sami aime CO CO
⇒sami aime SU qui GV CO ⇒ sami aime ali qui GV CO ⇒ sami aime ali qui
VE CO ⇒ sami aime ali qui déteste CO ⇒ sami aime ali qui déteste SU ⇒
sami aime ali qui déteste mourad.
 Les grammaires permettent de dériver des séquences syntaxiquement
correctes mais qui n’ont pas de sens.


2.3

Dérivation

7

2.4

2.5




Proto-phrase

Arbre de Dérivation (arbre syntaxique)
Il peut exister plusieurs moyens de dériver une séquence donnée, selon
l’ordre d’application des règles :
o

Dérivation la plus à gauche.

o

Dérivation la plus à droite.

On appelle Arbre de Dérivation (ou arbre syntaxique) tout arbre tel que :
o

La racine est l’axiome (S)

o

Les feuilles sont des symboles terminaux formant la chaîne donnée

o

Les nœuds sont des symboles non-terminaux

o

Les fils d’un nœud X sont Y0,Y1…, Yn si et seulement si:
X → Y0,Y1…, Yn ∈ P, et Yi ∈ (T ⋃ V )

8

2.5

Arbre de Dérivation (arbre syntaxique)

Exemple :
Soit la grammaire ayant S pour axiome et pour règles de production
P=
S →aTb |c
T →cSS |S
Un arbre de dérivation pour le mot accacbb est :
S ⇒ aTb
⇒ acSSb
⇒ accSb
⇒ accaTbb
⇒ accaSbb
⇒ accacbb

2.5

(dérivations gauches)

Arbre de Dérivation (arbre syntaxique)

S ⇒ aTb
⇒ acSSb
⇒ acSaTbb
⇒ acSaSbb
⇒ acSacbb
⇒ accacbb

(dérivations droites)
c’est le même arbre de dérivation

9

2.6

Grammaire Ambigüe

 Une grammaire G est ambigüe s’il existe une chaîne du langage L(G) qui
possède plusieurs arbres de dérivations
 Exemple :
Soit la grammaire suivante :
expression → expression «+» expression | expression «*» expression |facteur
facteur →nombre | identificateur | «(» expression «)»

2.6

Grammaire Ambigüe

et

10

2.6

Grammaire Ambigüe

2.6

Grammaire Ambigüe

Une grammaire ambigüe n’est pas souhaitable lors de l’analyse syntaxique

Il n’existe aucun algorithme pour déterminer si une grammaire est ambigüe,
donc le problème est indécidable.

Il existe par contre des grammaires démontrées non ambigües

Exemple :
Soit G =(V,T,S,P) :
V= {E}
T={+,*,(,),id}
P={E → E + E | E * E | ( E ) | id}
La grammaire G est ambigüe, nous pouvons transformer cette grammaire G
pour qu’elle ne soit pas ambigüe :
Soit G =(V,T,S,P) :
V= {E,F,H}
T={+,*,(,),id}
P={
E→E+F|F
F→F*H|H
H → ( E ) | id}


11

2.7

Classification des Grammaires

En 1957, Noam CHOMSKY a classifié les grammaires selon les restrictions
imposées :

Grammaires de type 0 : aucune restriction sur les règles.

Grammaires de type 1 : grammaires contextuelles ou sensibles au contexte
(adéquates pour générer des langages naturels).

Grammaires de type 2 : grammaires hors contexte (adéquates pour les
langages de programmation).

Grammaires de type 3 : grammaires régulières (restreintes, langages
représentés par les ER).
Plus la grammaire est expressive plus il est difficile de décider si une séquence
appartient ou non au langage généré par la grammaire : il faut donc trouver un
compromis.

2.7.1

Grammaires Régulières

Une grammaire régulière G=(V,T,S,P) est une grammaire avec les restrictions
suivantes sur les règles α →β de P :


Le côté gauche des règles est un seul symbole non terminal : α ∈ V



Le côté droit des règles est :
o

Un terminal suivi d’un non terminal

o

Un terminal

o

ԑ

12

2.7.1

Grammaires Régulières

Théorème :
Pour tout alphabet Σ :
{L(G) : G est une grammaire régulière}
=
{L(M) : M est un automate fini}
Donc, chaque grammaire régulière peut être transformée en un automate fini,
et chaque automate fini peut être transformé en une grammaire régulière.

2.7.1

Grammaires Régulières

Démonstration :
 Transformer une grammaire régulière quelconque en un automate fini.
 Transformer un automate fini en une grammaire régulière.

13

2.7.1.1

Conversion Grammaire / Automate

 Soit G=(V,T,SG,P) une grammaire régulière sur Σ
 Transformons G en G’=(V’,T,SG,P’) telle que G’ n’a pas de règles dont le côté
droit consiste en un seul terminal :
o N →x devient N → xX, X → ԑ

 Définir M = (SM, Σ,ρ,e0,F) :
o SM=V’, Σ =T, e0=SG
o ρ ={(R,x,Q) telle que la règle R → xQ ∈ P’}
o F={X / X → ԑ ∈ P’}

2.7.1.2

Conversion Automate / Grammaire

 Soit un automate fini M = (SM, Σ,ρ,e0,F)
 Trouvons une grammaire régulière G =(V,T,SG,P) telle que L(G) = L(M) :
o V = SM
o T=Σ
o S G= e 0
o P ={ R → xQ : (P,x,Q) ∈ρ } ⋃ { X → ԑ : X ∈ F }

14

2.7.1.2

Conversion Automate / Grammaire

 Trouvez G =(V,T,SG,P) telle que L(G) = L(M) :

o V = SM
o T=Σ
o S G= e 0
o P ={ R → xQ : (P,x,Q) ∈ρ } ⋃ { X → ԑ : X ∈ F }

2.7.2

Grammaire Hors Contexte

Une grammaire hors contexte (GHC) ou non contextuelle, G=(V,T,S,P) est une
grammaire avec les restrictions suivantes sur les règles α →β de P :






Le côté gauche des règles est un seul symbole non terminal : α ∈ V
Le côté droit des règles est n’importe quelle combinaison de terminaux et
de non terminaux (β ∈ ( V ⋃ T )*)

La forme restreinte prise par α fait de sorte que la grammaire soit hors
contexte : aucune condition pour l’application d’une règle (absence de
contexte).

15

2.7.2

Grammaire Hors Contexte

La grammaire des palindromes sur {0,1} est hors contexte :
 G=(V,T,S,P)
 V={S}
 T={0,1}
 P={ S → ԑ| 0 | 1 | 0S0 | 1S1 }



Les grammaires hors contexte permettent de générer des langages hors
contexte

2.7.2.1

Forme Normale de CHOMSKY

 Pour optimiser l’analyse syntaxique, il est préférable de travailler sur des
grammaires normalisées.
 L’algorithme Cocke-Younger-Kasami (CYK) utilise des grammaires sous
forme normale de Chomsky pour l’analyse syntaxique. Il décide en un temps
polynomial si une séquence est générée par la grammaire.

16

2.7.2.1

Forme Normale de CHOMSKY

 Une grammaire G=(V,T,S,P) non contextuelle est dite sous forme standard
binaire de CHOMSKY ssi le côté droit des règles (β) consiste en :
 Deux symboles non terminaux X → RT
 Un symbole terminal X → x
Théorème :
 Soit G une grammaire hors contexte, telle que ԑ ∉ L(G), il existe alors une
grammaire hors contexte G’ sous forme normale de CHOMSKY telle que
L(G)=L(G’).

2.7.2.2

Élimination des règles-ԑ

17

2.7.2.2

Élimination des règles-ԑ

G=(V,T,S,R) et R={ S → cPcQc ; P → aPa | QN ; Q → bPb | ԑ ; N → aNb | ԑ }.
S→cPcQc

P→aPa

P→QN

N→aNb

Q→bPb

S→cPcc

P→aa

P→Q

N→ab

Q→bb

S→ccQc

P→N

S→ccc

P→ԑ

 étape 3 :

( suppression des règles-ԑ )

S → cPcQc | cPcc | ccQc | ccc
P → aPa | QN | aa | Q | N
Q → bPb | bb
N → aNb | ab

2.7.2.3

Mise sous forme normale de Chomsky

G=(V,T,S,R) et R = { S → cMc ;

M → N | bMb ;

N→a}

 étape 1 :
o Poser G’=G et pour tout x ∈ T, soit X ∉ V :
 Remplacer toutes les occurrences de x par X dans chaque règle de G
 Ajouter la règle X → x à G’
o Exemple : S → CMC ; M → N|BMB ; N → A ; B → b ; C → c ; A → a

 étape 2 :
o Dans G’ remplacer chaque règle de la forme N → N1N2…Nn par :
 N → N1R1
 R 1 → N2 R 2
 ....
 Rn-2 → Nn-1Nn
o Exemple : S→CR1 ; R1→MC ; M→N|BR2 ; R2→MB ;N →A ; B→b ; C→c ; A→a

18

2.7.2.3

Mise sous forme normale de Chomsky

Exemple: S→CR1 ; R1→MC ; M→a|BR2 ; R2→MB ;N →a ; B→b ; C→c ; A→a

2.7.2.4

Propriétés des grammaires hors contexte

 Les langages HC sont fermés par :
o Union (l’union de deux langages HC est un langage HC)
o Concaténation (la concaténation de deux langages HC est un langage HC)
o Fermeture transitive réflexive *.
o Fermeture transitive +.
o Image miroir.
 Les langages HC ne sont pas fermés par :
o Intersection : l’intersection de deux Langage HC n’est pas forcément HC.
o Complémentation.

19

2.7.2.4.1

Union de deux grammaires HC

 Soit G1 = (V1,T1,S1,R1) et G2 = (V2,T2,S2,R2) avec V1 ⋂ V2 = ɸ
Trouvons G=(V,T,S,R) telle que L(G) = L(G1) ⋃ L(G2 ) :
o V = V1 ⋃ V2 ⋃ { S }, avec S ∉ V1 ⋃ V2
o T = T1 ⋃ T2
o R = R1 ⋃ R2 ⋃ { S→ S1 | S2 }

2.7.2.4.2

Concaténation de deux grammaires HC

 Soit G1 = (V1,T1,S1,R1) et G2 = (V2,T2,S2,R2) avec V1 ⋂ V2 = ɸ
Trouvons G=(V,T,S,R) telle que L(G) = L(G1) . L(G2 ) :
o V = V1 ⋃ V2 ⋃ { S }, avec S ∉ V1 ⋃ V2
o T = T1 ⋃ T2
o R = R1 ⋃ R2 ⋃ { S→ S1 S2 }

20

2.7.2.4.3

Fermeture * de deux grammaires HC

 Soit G=(V,T,S,R)
Trouvons G’=(V’,T’,S’,R’) telle que L(G’) = L(G) * :
o V’ = V ⋃ { S’ }, avec S’ ∉ V
o R’ = R ⋃ { S’ → S S’ | ԑ }

2.7.2.4.4

Intersection de deux langages HC

 L’intersection de deux langages hors contexte n’est pas forcément un langage
hors contexte.
 Exemple :
o L1={ai bi ck / i,k  0} est hors contexte
o L2 ={ai bk ck / i,k  0} est hors contexte
o L1 ⋂ L2 = {ai bi ci / i  0} n’est pas hors contexte

21

2.7.2.4.5

Complément d’un langage HC

2.7.2.4.6

Existence des grammaires non HC

 L = {an bn cn / n  0} n’est pas hors contexte, c’est un langage dépendant du
contexte.
 Soit G / L(G) = L :
o G = ({S, S1, S2}, {a, b, c}, S, { S → aS1c
S1 → b|SS2,
cS2 → S2c
bS2 → bb } )

22

2.7.2.4.7

Exemples

 Langage régulier :
o L = {w / w ∈ {a,b}*}
 Langage non contextuel :
o L = {an bn / n ∈ ℕ }
 Langage contextuel :
o L = {an bn cn / n ∈ ℕ }
 Langage récursivement énumérable :
o L = {a2n / n ∈ ℕ }

2.7.2.4.8

Hiérarchie de CHOMSKY

23

Merci..
Farouk JELIDI
farouk.jelidi@gmail.com

2016-2017

24


Documents similaires


Fichier PDF td2
Fichier PDF chap 3 compilation version finale ult
Fichier PDF correction td2
Fichier PDF sujet thl 2016 2017
Fichier PDF etcd l2 2017 2018 thl
Fichier PDF corrige sujet thl


Sur le même sujet..