UNIVERSITE FERHAT ABBES – SETIF 1
FACULTE DES SCIENCES
DEPARTEMENT D’INFORMATIQUE
Chapitre 3
Analyse Syntaxique
1
HAMMOUCHE Yassine
Compilation L/Ing 3A 15/10/2024
Plan
2
Grammaires
Dérivations
Ambiguïté
Analyse syntaxique
Compilation L/Ing 3A 15/10/2024
Plan
3
Grammaires
Dérivations
Ambiguïté
Analyse syntaxique
Compilation L/Ing 3A 15/10/2024
Grammaires
4
Un automate peut être vu comme une machine permettant de reconnaître
des mots. On fait entrer un mot dans la machine, et en résultat, on a comme
réponse “le mot appartient au langage” ou “le mot n’appartient pas au
langage”.
Avec une grammaire, on s’intéresse plus à la structure des mots du langage
pour expliquer comment ils se fabriquent. Une fois qu’on a les “règles de
fabrication” (appelées "règles de production"), on peut engendrer tel ou tel
mot.
Exemple: Par exemple, si on prend le ‘if ’ du C :
if ( expression ) statement else statement alors on peut exprimer ce fait a l’aide
d’une règle:
stmt → if ( expr ) stmt else stmt
Compilation L/Ing 3A 15/10/2024
Grammaires
5
Une grammaire algébrique (hors contexte) est un quadruplet G =
(Σ;N; P; S) où :
Σ est un alphabet, dit alphabet des terminaux ; les terminaux sont les
symboles de base à partir desquels les chaînes sont formées (unités
lexicales)
N est un alphabet, dit alphabet des non-terminaux ou des variables, (disjoint
de Σ)
P est un ensemble de règles de production où chaque règle est constituée
d’un non-terminal, appelé partie gauche, d’une flèche appelée partie
droite de la forme A → β avec A ϵ Σ et β ϵ (Σ U N)*
S est un élément de N appelé axiome de G (symbole initial). L'ensemble des
chaînes que l'on peut obtenir à partir de l'axiome est le langage défini par
la grammaire.
Compilation L/Ing 3A 15/10/2024
Grammaires
6
Toutes les chaines de la grammaire (mots) peuvent être
obtenues en appliquant des règles de production
successivement à partir de l’axiome.
Exemple:
les mots bien parenthésés
un mot sans parenthèse (le mot vide ε puisqu’on ne considère que le
langage des parenthèses),
la concaténation de deux mots bien parenthésés : ( ) ( ),
une parenthèse ouvrante, un mot bien parenthésé, une parenthèse
fermante : ( ( ) ).
S →ε , S → SS et S → (S)
Compilation L/Ing 3A 15/10/2024
Grammaires
7
La grammaire qui permet de définir le langage des “suites de chiffres
séparés par des signes d’addition ou de soustraction”, tels que 9-5+2,
3-1 et 7.
list → list + digit
list → list - digit
list → digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Compilation L/Ing 3A 15/10/2024
Grammaires
8
Une grammaire régulière est une classe de grammaires
formées des 2 sous-classes suivantes :
les grammaires linéaires droites, où toutes les règles sont
de la forme
A → wB A→w
les grammaires linéaires gauches, où toutes les règles
sont de la forme
A → Bw A→w
Compilation L/Ing 3A 15/10/2024
Plan
9
Grammaires
Dérivations
Ambiguïté
Analyse syntaxique
Compilation L/Ing 3A 15/10/2024
Dérivations
10
Mot dérivé directement. Soient u et v deux mots sur Σ U N. Le mot v se
dérive directement de u par la grammaire algébrique G = (Σ;N; P; S) s’il
existe des mots u1 et u2 et une règle de production X → w tels que u =
u1Xu2 et v = u1wu2.
Les mots ε, (S) et SS sont les seuls mots qui se dérivent directement de S par la grammaire bien
parenthésés
Mot dérivé. Soient u et v deux mots sur Σ U N. Le mot v se dérive de u par
la grammaire algébrique G = (Σ;N; P; S) s’il existe des mots w0;w1; … ;wn
tels que u = w0, v = wn et pour tout entier i (0 <= i < n), wi+1 se dérive
directement de wi .
Les mots (((S)S)(S)S), (S)(S)S, (S)S et S se dérivent de S par la grammaire des mots bien
parenthésés
Une dérivation s’écrit souvent : u = w0 → w1 → w2 → : : : → wn = v
Compilation L/Ing 3A 15/10/2024
Dérivations
11
Pour montrer qu’un mot appartient au langage, il faut et il suffit de
montrer qu’il s’obtient à partir d’une application de suite finie de
règles de production de la grammaire (en commençant par
l’axiome).
Une dérivation est dite a gauche si le non-terminal le plus a gauche
est remplacé
Une dérivation est dite a droite si le non-terminal le plus a droite est
remplacé
Compilation L/Ing 3A 15/10/2024
Dérivations
12
Chaque dérivation peut être représentée sous la forme d’un arbre
de dérivation.
Un arbre de dérivation est défini de la manière suivante :
Racine étiquetée par le symbole initial S
Feuilles étiquetées par les éléments de T U {ε} (les terminaux + ε)
Noeuds internes etiquetes par les elements de N (les non-terminaux). un
sommet interne étiqueté X a pour fils (dans cet ordre) x1; …; xn avec xi ϵ Σ U N,
si X → x1 … xn est une règle de production de la grammaire.
Un arbre de dérivation est traditionnellement dessiné la racine en haut
(parcours en profondeur). Sur un tel arbre dessiné, le mot dérivé s’obtient en
concaténant les étiquettes des feuilles de gauche à droite.
Compilation L/Ing 3A 15/10/2024
Dérivations
13
Arbre de dérivation du mot (())()
Compilation L/Ing 3A 15/10/2024
Plan
14
Grammaires
Dérivations
Ambiguïté
Analyse syntaxique
Compilation L/Ing 3A 15/10/2024
Ambiguïté
15
Une grammaire est ambiguë s’il existe un mot qui admet deux
arbres de dérivations distincts.
Théorème : Le problème de déterminer si une grammaire est
ambiguë est indécidable (i.e. il n’est pas possible d’élaborer un
algorithme qui soit capable de dire, après un temps fini, si une
grammaire est ambiguë ou non.).
on peut toutefois montrer qu’une grammaire donnée est ambiguë
en donnant un mot engendré par cette grammaire admettant
deux arbres de dérivations distincts.
Compilation L/Ing 3A 15/10/2024
Ambiguïté
16
Par exemple, on peut aussi bien générer les listes de chiffres séparés par des opérateurs `a l’aide de la
grammaire suivante:
string → string + string
string → string - string
string → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Il existe deux arbres de dérivation pour la chaîne 9-5+2:
Compilation L/Ing 3A 15/10/2024
PlAN
17
Grammaires
Dérivations
Ambiguïté
Analyse syntaxique
Compilation L/Ing 3A 15/10/2024
Analyse syntaxique
18
Donnes: grammaire G et un mot w (une suite de tokens)
But: reconstruire l'arbre syntaxique de la phrase w a partir de la
grammaire G. L'analyse de la chaîne se fait toujours de la gauche
vers la droite.
2 méthodes ou processus
analyse descendante. Cette analyse correspond a un parcours descendant
gauche (on lit de gauche a droite). Il s'agit de deviner a chaque étape la
règle qui sert a engendrer le mot qu'on lit. On part de S pour atteindre w.
(grammaires LL(k))
analyse ascendante. Dans cette analyse, on essaye d'appliquer le membre
droit d'une règle et a le remplacer par le non-terminal gauche correspondant.
On part de w pour atteindre S. (grammaires LR(k))
Compilation L/Ing 3A 15/10/2024
Analyse syntaxique
19
Pareil que l’analyse lexicale, des outil pour générer
directement un analyseur syntaxique.
Bison, ….
Compilation L/Ing 3A 15/10/2024
