Scribd
Importer
191 vues38 pages

Analyse Syntaxique en Compilation

Transféré par

OUMAIMA ELMEJGARI
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
191 vues38 pages

Analyse Syntaxique en Compilation

Transféré par

OUMAIMA ELMEJGARI
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Faculté des Sciences Agadir

Département Informatique
Filière SMI
Semestre 5

Compilation
Pr. Mustapha Machkour
Chapitre 6
Analyse syntaxique 1
Objectifs
 Analyse syntaxique
 Grammaire non contextuelle
 Terminaux
 Non Terminaux
 Productions
 Axiome

Compilation FS Agadir SMI 20-21 3


 Définition de la syntaxe(rappel)
L'analyse syntaxique (parsing) est une tâche
fondamentale d'un compilateur, ses objectifs incluent:
- Réception des mots (lexèmes) fournis par l’analyseur
lexical
- Rassemblement de ces mots en phrases
(instructions) ;
- Vérification de la syntaxe de ces phrases ;
- Construction des représentations de ces phrases
(paires d'unités lexicales et lexèmes) correctes en
termes d'arbres syntaxiques ou arbres d'analyse.

Compilation FS Agadir SMI 20-21 4


 Syntaxe et analyseur syntaxique
Pour vérifier la syntaxe d'une phrase on utilise un
analyseur syntaxique = parser.

Compilation FS Agadir SMI 20-21 5


 Schéma simplifié d’un analyseur syntaxique

Analyseur Analyseur Arbre


Unités lexicales
syntaxique ou
lexical ,lexèmes syntaxique erreur

Table des
symboles

Compilation FS Agadir SMI 20-21 6


 Remarque
L’arbre syntaxique s'appelle aussi arbre de dérivation.

Compilation FS Agadir SMI 20-21 7


 Remarque
L’arbre syntaxique n’est pas l’arbre abstrait

Compilation FS Agadir SMI 20-21 8


 Différence arbres syntaxique et abstrait
 Arbre de syntaxique  Arbre abstrait

expression
+

+ a 1
expression expression

ID INT

a 1

Compilation FS Agadir SMI 20-21 9


 Analyseur syntaxique et grammaire
Pour construire un analyseur syntaxique (parser) d'un
langage, on doit décrire la syntaxe de ce langage de
manière précise.
 Utilisation d'une grammaire

Compilation FS Agadir SMI 20-21 10


 Objectifs d'une grammaire
Une grammaire est un ensemble de règles pour
décrire la manière de former des phrases
(instructions) et des programmes dans un langage.

Compilation FS Agadir SMI 20-21 11


 Pourquoi une grammaire? (1/3)
(1) Spécification

et

(2) Reconnaissance

Compilation FS Agadir SMI 20-21 12


 Pourquoi une grammaire?(2/3)
(1) Spécification

- Spécification précise de la syntaxe du langage de


programmation

- Spécification compréhensible et claire de la syntaxe du


langage de programmation

Compilation FS Agadir SMI 20-21 13


 Pourquoi une grammaire?(3/3)
(2) Reconnaissance

- Correction de la syntaxe (reconnaissance des chaînes


syntaxiques) conformément à la spécification déjà définie
en (1).

- Traduction du langage (arbre abstrait).

Compilation FS Agadir SMI 20-21 14


 Exemple introductif de grammaire
Considérons la grammaire suivante :
expr→ expr + expr
expr→ expr - expr
expr→ expr * expr
expr→ ID
expr→ INT

Compilation FS Agadir SMI 20-21 15


 Grammaire hors contexte=GHC
La syntaxe d’un langage de programmation est définie
par une grammaire dite Grammaire Hors Contexte
(GHC).

GHC=Grammaire qui ne dépend pas de sens ou de la


sémantique
- Context-Free Grammar = CFG
- Backus-Naur Form = BNF

Compilation FS Agadir SMI 20-21 16


 Exercice
Recherche sur Backus et Naur

Compilation FS Agadir SMI 20-21 17


- Grammaire hors contexte (GHC) (1)
Les éléments d’une GHC :
Terminaux (T), Non-terminaux (NT), Productions (P) et
axiomes (S)
GHC=Ensemble G de la forme
G=(T,NT,S,P) avec
- T=ensemble des mots du langage (mots)= Terminaux
Exemples
+, *, ID, INT, if, else, while…

Compilation FS Agadir SMI 20-21 18


 Remarque
Un terminal est un lexème ou unité lexicale.

Compilation FS Agadir SMI 20-21 19


 Exemple
Dans la grammaire suivante :
expr→ expr + expr
expr→ expr - expr
expr→ expr * expr
expr→ ID
expr→ INT
les terminaux sont :
T = {+, - , *, ID, INT}

Compilation FS Agadir SMI 20-21 20


 Remarque
Dans une grammaire les terminaux ne figurent pas à
gauche des règles.

Compilation FS Agadir SMI 20-21 21


 Exercice
Préciser les terminaux de la grammaire suivante :
S → (L) | a
L → L,S | S

Compilation FS Agadir SMI 20-21 22


 Réponse
T={ ( ) a , }

Compilation FS Agadir SMI 20-21 23


- Grammaire hors contexte (GHC) (2)
Les éléments d’une GHC :
Terminaux (T), Non terminaux (NT), Production(P) et
Axiomes (S)
- NT=ensembles des symboles Non Terminaux générés par la
grammaire (des phrases ou catégories syntaxiques)
Exemples
expr→ expr + expr
instr→ if (expr) instr else instr

Compilation FS Agadir SMI 20-21 24


 Remarque
Dans une grammaire un non terminal figure au moins
une fois à gauche d’une règle.

Compilation FS Agadir SMI 20-21 25


 Exercice
Préciser les non terminaux de la grammaire suivante :
S → (L) | a
L → L,S | S

Compilation FS Agadir SMI 20-21 26


 Réponse
NT={ S , L}

Compilation FS Agadir SMI 20-21 27


- Grammaire hors contexte (GHC) (3)
Terminaux(T), Non-Terminaux(NT), Production(P) et Axiomes
(S)
- P=Ensemble des règles qui servent à générer les
phrases du langage
On les appelle aussi des productions ou règles
d'écriture
Ces règles ont la forme :
s → s1 s2 s3…
avec si des terminaux ou de non terminaux
( i.e. les si appartiennent T U NT)
Pour produire s il faut avoir ou produire s1…

Compilation FS Agadir SMI 20-21 28


 Utilisation des règles
- La règle :
s → s1 s2 s3…
Signifie que, pour produire la syntaxe s il faut
avoir ou produire s1 suivi de s2…

- On peut aussi dire que s se dérive (de gauche à droire) en s1


s2…
- ou encore
s1 s2 s3 … se réduit (de droite à gauche) en s

Compilation FS Agadir SMI 20-21 29


 Exemples de règles
expr→ expr + expr
expr→ ID
expr→ INT

Compilation FS Agadir SMI 20-21 30


- Grammaire hors contexte (GHC) (4)

Terminaux(T), Non-Terminaux(NT),
Production(P) et Axiomes (S)

- Axiome (S)=Symbole de départ non terminal


représentant le langage (figurant à gauche
de la première production) =S

Compilation FS Agadir SMI 20-21 31


 Exemple d’axiome
Dans la grammaire suivante :
expr→expr + expr
expr→expr - expr
expr→expr * expr
expr→ID
expr→INT

l’axiome est : S ={expr}

Compilation FS Agadir SMI 20-21 32


 On considère la grammaire suivante :
S (L)|a
LL,S | S
Chercher l’axiome.

Compilation FS Agadir SMI 20-21 33


 Réponse
S={ S }

Compilation FS Agadir SMI 20-21 34


 Exercice de GHC
Considérons la grammaire définie par les productions
expr→expr + expr
expr→expr - expr
expr→expr * expr
expr→ID
expr→INT

Chercher les T,NT et S.

Compilation FS Agadir SMI 20-21 35


 Exemple de GHC(suite)
T={ ID, NB, +, -, *}
NT={expr}
S={expr}

Compilation FS Agadir SMI 20-21 36


 Une autre façon de représenter les productions
La représentation suivante, par
factorisation de expr:
expr→ expr+expr | expr – expr | expr*expr | ID | INT
remplace

expr→expr + expr
expr→expr - expr
expr→expr * expr
expr→ID
expr→INT

Compilation FS Agadir SMI 20-21 37


Résumé
 Analyse syntaxique
 Grammaire non contextuelle
 Terminaux
 Non Terminaux
 Productions
 Axiome

Compilation FS Agadir SMI 20-21 38

Vous aimerez peut-être aussi