Techniques de Compilation

Ch2: Analyse syntaxique

Année Universitaire 2023 / 2024

Introduction
⚫ But de l’analyse syntaxique : transformer un flot d’unités lexicales en arbre abstrait.

⚫ Langage de programmation : règles prescrivant la structure syntaxique des

programmes bien formés.

⚫ Langage C , Programme = ensemble de Fonctions.

⚫ Fonction : formée de blocs.
⚫ Un bloc : formé d’instructions.
⚫ Une instruction : formée d’expressions.
⚫ Une expression : formée d’unités lexicales.
⚫ Etc.

⚫ La syntaxe d’un langage peut être décrite par des grammaires non contextuelles
(notation BNF – Backus-Naur Form).

⚫ Grammaire : spécification syntaxique précise et facile à comprendre d’un langage

de programmation.
 Rôle de l’analyseur syntaxique

⚫ L’analyseur syntaxique obtient une chaîne d’unités lexicales de l’analyseur lexical.

⚫ Il vérifie que la chaîne peut être engendrée par la grammaire du langage source.
⚫ Il signale chaque erreur de syntaxe de manière intelligible.
⚫ Supporte les erreurs les plus communes de façon à pouvoir continuer l’analyse du
code restant.

Unité lexicale
Reste de la
Analyseur Analyseur Arbre d’analyse Représentation
Programme source lexical Syntaxique
partie
Unité lexicale frontale intermédiaire
suivante

Table de
symboles

3
Rôle de l’analyseur syntaxique
⚫ Deux types d’analyses sont retenues pour les compilateurs : Ascendante ou
Descendante.

⚫ Analyseurs descendants construisent les arbres d’analyse de haut (ROOT) en bat

(LEAF).

⚫ Analyseurs ascendants partent des feuilles et remontent à la racine.

⚫ Dans les deux cas l’entrée de l’analyse syntaxique est explorée par convention de la
gauche vers la droite un symbole à la fois.

⚫ Le gestionnaire d’erreurs doit :

⚫ Indiquer la présence d’erreurs de façon claire et précise.
⚫ Traiter chaque erreur pour pouvoir détecter les erreurs suivantes.

⚫ Le gestionnaire d’erreurs ne doit pas pénaliser l’exécution des programmes

correctes.
4
Analyse SYNTAXIQUE descendante

Analyse descendante

avec rebroussement sans rebroussement

(analyse descendante récursive) (analyse prédictive)

1. Non ambigue

2. Factorisée à gauche

3. Non récursive à gauche

5
Factorisation à gauche

Algorithme factorisation à gauche

Données : Une grammaire G sans cycles et sans productions vides

Résultat : Une grammaire équivalente à G factorisée à gauche

Pour chaque non terminal A trouver le plus long préfixe  au moins à deux de ses
alternatives.
Si    alors remplacer toutes les A-productions :
A → 1 |2 | … | n | 
 Représente toutes les alternatives ne commençant pas par  par :
A → A’ | 
A’ →1 | 2 | … | n

Répéter jusqu’à ce qu’aucune des alternatives d’un même non-terminal n’ait de préfixe
commun.
6
 Exemple
S

𝑆 → 𝑐𝐴𝑑
ቊ c A d échec
𝐴 → 𝑎𝑏 | 𝑎
backtrack retour au choix précédent
𝑤 = 𝑐𝑎𝑑
a b
𝑆 →𝑐Ad
cad
X
S
𝑆 →𝑐Ad→cabd
c A d 𝑆 →𝑐Ad→cad
retour
Succès
a

Dans cet exemple, nous traitons une forme générale d'analyse descendante où des
retours arrières sont possibles avec passages répétés sur le texte source. Dans la
pratique, le rebroussement est rarement nécessaire, on peut adapter les grammaires
pour effectuer une analyse descendante sans rebroussement
7
Exemple

𝑖𝑛𝑠𝑡𝑟 → si expr alors instr Quelle alternative choisir après

| 𝑠𝑖 𝑒𝑥𝑝𝑟 𝑎𝑙𝑜𝑟𝑠 𝑖𝑛𝑠𝑡𝑟 𝑠𝑖𝑛𝑜𝑛 𝑖𝑛𝑠𝑡𝑟 lecture du si ?
ቐ
| 𝑎𝑢𝑡𝑟𝑒 instr
𝑖𝑛𝑠𝑡𝑟 backtrack

si expr alors instr

𝑤 = 𝑠𝑖 𝑣𝑖𝑡𝑒𝑠𝑠𝑒 ≥ 110 𝑎𝑙𝑜𝑟𝑠 𝑎𝑚𝑒𝑛𝑑𝑒 = 𝑡𝑟𝑢𝑒 𝑠𝑖𝑛𝑜𝑛 𝑎𝑚𝑒𝑛𝑑𝑒 = 𝑓𝑎𝑙𝑠𝑒

retour

8
 Exemple Quelle est la cause du problème ?

S S
𝑆 → 𝑐𝐴𝑑
ቊ
𝐴 → 𝑎𝑏 | 𝑎
𝑤 = 𝑐𝑎𝑑 c A d c A d
backtrack
a b a
échec 𝑆 →𝑐Ad

X
retour au choix précédent
𝑆 →𝑐Ad→cabd
𝑖𝑛𝑠𝑡𝑟 → si expr alors instr
ቐ | 𝑠𝑖 𝑒𝑥𝑝𝑟 𝑎𝑙𝑜𝑟𝑠 𝑖𝑛𝑠𝑡𝑟 𝑠𝑖𝑛𝑜𝑛 𝑖𝑛𝑠𝑡𝑟 𝑆 →𝑐Ad→cad
| 𝑎𝑢𝑡𝑟𝑒

Le problème c’est la factorisation à gauche

Proposer une grammaire équivalente qui dénote le même langage tout en éliminant le problème ?

9
 Factorisation à gauche

exemple

X
Factorisation à gauche 𝑆 → 𝑐𝐴𝑑
𝑆 → 𝑐𝐴𝑑 𝑆 → 𝑐𝐴𝑑
ቊ
𝐴 → 𝑎𝑏 | 𝑎 ቊ ቐ 𝐴 → 𝑎𝐴′
𝐴 → 𝑎(𝑏 | 𝜀)
𝐴′ → 𝑏 | 𝜀

𝑤 = 𝑐𝑎𝑑 c A d Succès
𝑆 → 𝑐 A d → c a A’ d → 𝑐 𝑎 𝑑
a A’

Proposer une grammaire équivalente qui dénote le même langage tout en éliminant le problème ?

10
Factorisation à gauche

exemple S
Factorisation à gauche 𝑆 → 𝑐𝐴𝑑
𝑆 → 𝑐𝐴𝑑 c A d
ቊ
𝐴 → 𝑎𝑏 | 𝑎 ቐ 𝐴 → 𝑎𝐴′
𝐴′ → 𝑏 | 𝜀
a A’

𝜀
Pour généraliser : si
Factorisation à gauche
′ |𝛾 | ⋯ |𝛾
𝑆 → 𝛼𝛽1 |𝛼𝛽2 | ⋯ |𝛼𝛽𝑛 |𝛾1 | ⋯ |𝛾𝑚 𝑆 → 𝛼𝑆 1 𝑚
ቊ ′
𝑆 → 𝛽1 |𝛽2 | ⋯ |𝛽𝑛

𝑆 → 𝑎𝑆 ′
𝑆 → 𝑎𝑅𝑏𝑐 | 𝑎𝑏𝑐 Factorisation à gauche 𝑆 ′ → 𝑅𝑏𝑐 | 𝑏𝑐
ቐ𝑅 → 𝑎𝑅𝑇𝑏 | 𝑎𝑇𝑏
𝑅 → 𝑎𝑅 ′
𝑇 → 𝑏𝑏 | 𝑐𝑐
𝑅′ → 𝑅𝑇𝑏 | 𝑇𝑏
𝑇 → 𝑏𝑏 | 𝑐𝑐
11
récursivité à gauche et à droite

⚫ Une grammaire est récursive si elle contient un non terminal A qui se dérive en une
production contenant A.
⚫ Une production d’une grammaire est récursive à gauche si le symbole le plus à
gauche de la partie droite de la production est le même que le non terminal de la
+
partie gauche de la production (il existe une dérivation A  A ( une chaîne
quelconque).

Exemple : A → A

⚫ Une production d’une grammaire est récursive à droite si le symbole le plus à droite
de la partie droite de la production est le même que le non terminal de la partie
gauche de la production.

Exemple : A→A
 est une suite de terminaux et non terminaux ne contenant pas A.

12
Suppression de la récursivité à gauche

⚫ Les méthodes d’analyse descendante ne fonctionnent pas avec les grammaires

récursives à gauche.
⚫ L’analyseur par descente récursive peut boucler indéfiniment.
⚫ Pour les analyseurs descendants, il faut éliminer la récursivité à gauche.
⚫ Des règles de réécriture pour éliminer la récursivité à gauche.
⚫ A est non terminal dans les deux productions suivantes :

A → A | 

 et  sont des suites de terminaux et non terminaux ne contenant pas A.

Exemple : expression → expression + term | term

13
 récursivité à gauche

Exemple
S
𝑆 → 𝑐𝐴𝑑
ቊ
𝐴 → 𝐴𝑎 | 𝑎
𝑤 = 𝑐𝑎𝑑 c A d

A a
cad
𝑆 →𝑐Ad
A a
𝑆 →𝑐Ad→cAad
Boucle infinie 𝑆 →𝑐Ad→cAad→𝑐𝐴𝑎𝑎𝑑

⋯
Le problème c’est que la grammaire est récursive à gauche

Parfois même les retours arrières ne sont possibles !

14
récursivité à gauche

Exemple

X
Proposez des mots du langage ?
𝐴 → 𝐴𝛼 | 𝛽 𝛽 𝛼
𝛽𝛼 ⋯ 𝛼 𝛼⋯𝛼
𝛼 ⋯ 𝛼𝛽
𝐴 → 𝐴𝛼 → 𝐴𝛼𝛼 → 𝐴𝛼𝛼𝛼 → 𝛽𝛼𝛼𝛼

Proposez une grammaire qui dénote le même langage sans quelle ne soit récursive à
Gauche ?

𝐴 → 𝛽𝐴′
ቊ ′
𝐴 → 𝛼𝐴′ | 𝜀

Si on généralise :
Après élimination de la récursivité
′ | ⋯ |𝛽 𝐴′
൛𝐴 → 𝐴𝛼1 | 𝐴𝛼2 | ⋯ |𝐴𝛼𝑛 |𝛽1 | ⋯ |𝛽𝑚 𝐴 → 𝛽 1 𝐴 𝑚
ቊ ′
𝐴 → 𝛼1 𝐴 𝛼2 𝐴′ ⋯ |𝛼𝑛 𝐴′| 𝜀
′

15
 récursivité à gauche
S
Exemple
c A d 𝑆 →𝑐Ad
𝑆 → 𝑐𝐴𝑑
ቊ
𝐴 → 𝐴𝑎 | 𝑎 A a 𝑆 →𝑐Ad→cAad
𝑤 = 𝑐𝑎𝑑
A a 𝑆 →𝑐Ad→cAad→𝑐𝐴𝑎𝑎𝑑
cad ⋯
Boucle infinie
S

Après élimination de la récursivité :

c A d Succès
𝑆 → 𝑐𝐴𝑑
ቐ 𝐴 → 𝑎𝐴′ a 𝐴′
𝐴′ → 𝑎𝐴′ | 𝜀
𝜀

16
récursivité à gauche

Exemple

Si on généralise :
Après élimination de la récursivité
′ ′
൛𝐴 → 𝐴𝛼1 | 𝐴𝛼2 | ⋯ |𝐴𝛼𝑛 |𝛽1 | ⋯ |𝛽𝑚 𝐴 → 𝛽 1 𝐴 | ⋯ |𝛽𝑚 𝐴
ቊ ′
𝐴 → 𝛼1 𝐴′ 𝛼2 𝐴′ ⋯ |𝛼𝑛 𝐴′| 𝜀

Après élimination de la récursivité

𝑆 → 𝑎𝑆𝑆 ′ |𝑐𝑆 ′
𝑆 → 𝑎𝑆 𝑆𝑏 𝑐
ቊ ൞𝑆 ′ → 𝑏𝑆 ′ | 𝜀
𝑎𝑆𝑏 → 𝑆𝑎 | 𝑏𝑆
𝑎𝑆𝑏 → 𝑆𝑎 | 𝑏𝑆

17
récursivité à gauche

Exemple

Si on généralise :
Après élimination de la récursivité
′ ′
൛𝐴 → 𝐴𝛼1 | 𝐴𝛼2 | ⋯ |𝐴𝛼𝑛 |𝛽1 | ⋯ |𝛽𝑚 𝐴 → 𝛽 1 𝐴 | ⋯ |𝛽𝑚 𝐴
ቊ ′
𝐴 → 𝛼1 𝐴′ 𝛼2 𝐴′ ⋯ |𝛼𝑛 𝐴′| 𝜀

Après élimination de la récursivité

𝛼 𝛽 𝐸 → 𝑇𝐸′′
𝐸 ′ → 𝑇𝐸 ′
𝐸 →𝐸+𝑇|𝑇 𝐸 → +𝑇𝐸′ | 𝜀
𝐸 ′ → +𝑇𝐸 |𝜀
ቐ𝑇 → 𝑇 ∗ 𝐹 | 𝐹 𝑇 → 𝐹𝑇 ′
𝑇 ′→ 𝑇 ∗ 𝐹′ | 𝐹
𝐹 → 𝐸 | 𝑖𝑑 𝑇 →∗ 𝐹𝑇 | 𝜀
𝐹 → 𝐸 | 𝑖𝑑
𝐹 → 𝐸 | 𝑖𝑑

18
Suppression de la récursivité à gauche
cachée

Règles pour l’élimination de la récursivité à gauche immédiate

⚫ Grouper les A-productions comme suit :

A → A1 | A2 | … | Am | 1 | 2 | … | n Aucun i ne commence par un A
⚫ On remplace les A-productions par :
A → 1 A’ | 2 A’ | … | n A’
A’ → 1 A’ | 2 A’ | … | m A’ | 
⚫ Cet algorithme élimine toutes les récursivités à gauche immédiates.
⚫ Il n’élimine pas les récursivités à gauche impliquant des dérivations contenant au
moins deux étapes.
S → Aa | B
A → Ac | Sd | 
Le non terminal S est récursif à gauche (mais pas immédiatement) car
S  Aa  Sda

19
Suppression de la récursivité à gauche
cachée

Algorithme D’élimination de la récursivité à gauche

Données : Une grammaire G sans cycles et sans productions vides

Résultat : Une grammaire équivalente à G sans récursivité à gauche

BEGIN
Ordonner les non terminaux A1, A2, … , An;

FOR i  1 TO n DO
FOR j  1 TO i – 1 DO
remplacer chaque production de la forme Ai → Aj par les productions
Ai → 1 | 2 | … | k (Aj → 1 | 2 | … | k sont des productions courantes)
END FOR
éliminer les récursivités immédiates des Ai-productions
END FOR
END

20
Suppression de la récursivité à gauche
cachée

Exemple :
S → Aa | b
A → Ac | Sd | 
⚫ On classe les non terminaux dans l’ordre S, A

⚫ Il n’y a pas de récursivité à gauche immédiate dans les S-productions. Rien ne se

produit durant l’exécution de l’étape 2 pour i = 1.
⚫ Pour i = 2, on substitue les S-productions dans A → Sd pour obtenir les A-
productions suivantes :
A → Ac | Aad | bd | 
⚫ En éliminant les récursivités à gauche immédiates, on obtient la grammaire suivante :

S → Aa | b
A → bdA’ | A’
A’ → cA’ | adA’ | 

21
Analyse SYNTAXIQUE descendante

Analyse descendante

avec rebroussement sans rebroussement

(analyse descendante récursive) (analyse prédictive)

1. Non ambigue

2. Factorisée à gauche

3. Non récursive à gauche

22
Analyse syntaxique descendante

Analyseurs prédictifs

⚫ Étant donné un symbole a en entrée et un non terminal A à développer, déterminer

si une alternative de la production A → 1 | 2 | … | n est l’unique alternative
pouvant dériver en une chaîne commençant par a.

instruction → if expression then instruction else instruction

| while expression do instruction
| begin instructions_list end

Dans ce cas de figure, les mots clés if, while et begin nous prédisent quelle alternative
est à prendre pour développer l’instruction.

23
Analyse prédictive
flot d’entrée id + id * id $

Programme Flot de sortie

axiome S d‘analyse (indique la suite des
règles utilisées)
$ prédictive

Pile M Table d’analyse

id + * $
E R1 Erreur
T R2

24
Calcul du premier

Soit la grammaire G suivante :

𝑆 → 𝑎𝐴 | 𝑏𝐵
𝐴 → 𝐵𝑐 | 𝐵𝐶
𝑊 = 𝑎⋯? 𝑊 = 𝑏⋯?
X
𝑊 = 𝑐⋯?

𝐵 → 𝑏𝑐 | 𝑎
𝐶 → 𝑐| 𝜀
X
𝑆 →∗ 𝑐 ⋯
Le premier ?

Pr(S) = ሼ𝑎,𝑏ሽ
𝑆 →∗ 𝑙𝑒 𝑝𝑟𝑒𝑚𝑖𝑒𝑟 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 ⋯

Pr(A) = ?Pr B = ሼ𝑏,𝑎ሽ 𝑆 → 𝑎𝐴 → 𝑎𝐵𝑐 ⋯

Pr(B) = ?ሼ𝑏,𝑎ሽ

Pr(C) = ?ሼ𝑐,𝜀 ሽ

25
Calcul du premier

Soit la grammaire G suivante :

𝑆 → 𝑎𝐴 | 𝑏𝐵
𝐴 → 𝐵𝑐 | 𝐵𝐶 𝑒
𝐵 → 𝑏𝑐 | 𝑎 | 𝜀
𝐶 → 𝑐| 𝜀

Pr(S) = ሼ𝑎,𝑏ሽ 𝐴 → 𝐵𝐶 → 𝜀𝐶 → 𝜀

Pr(A) = Pr B = ሼ𝑏,𝑎ሽ Pr(A) = ?Pr 𝐵 ∖ 𝜀 ∪ 𝑐 ∪ Pr

Pr(𝐵) 𝐶 ∖= 𝜀𝑏,?∪
Pr(𝐶)? 𝑎, 𝑐,𝑒𝜀 = 𝑏, 𝑎, 𝑐, 𝑒

Pr(B) = ሼ𝑏,𝑎ሽ Pr(B) = ሼ𝑏,𝑎, 𝜀 ሽ

Pr(C) = ሼ𝑐,𝜀 ሽ

26
Exemple d’application

Soit la grammaire 𝐺1 suivante :

𝑆 → 𝑎𝑆𝑏 𝑐𝑑 𝑏𝑆𝐴𝑒 Pr(S) = 𝑎, 𝑐, 𝑏

𝐴 → 𝑎𝐴𝑑𝐵 | 𝜀 Pr(A) = 𝑎, 𝜀
𝐵 → 𝑏𝑏 Pr(B) = 𝑏

Soit la grammaire 𝐺2 suivante :

𝑆 → 𝐴𝐵𝐶𝑒 Pr(S)
Pr(S)
= Pr(A)\ 𝜀 ∪
= Pr(A)\
Pr(A) !𝜀Pr∪ 𝐵Pr \𝐵𝜀 \! ∪𝜀Pr∪ 𝐶Pr \𝐶𝜀 =
!∪ 𝑎,
𝑒 𝑏,=𝑐, 𝑑
𝑎, 𝑏, 𝑐, 𝑑, 𝑒
𝐴 → 𝑎𝐴 | 𝜀 Pr(A) = 𝑎, 𝜀
𝐵 → 𝑏𝐵 𝑐𝐵 𝜀 Pr(B) = 𝑏, 𝑐, 𝜀
𝐶 → 𝑑𝑒 𝑑𝑎 𝑑𝐴 | 𝜀 Pr(C) = 𝑑,
𝑑𝜀

27
Calcul du suivant

Soit la grammaire G suivante :

Le suivant ?
𝑆 → 𝐴𝑎 | 𝐵𝑆𝑏
𝐴 → 𝐵𝑐 | 𝐵𝐶𝑑
𝐷
𝑆 →∗ ⋯ 𝐴𝑎 ⋯ 𝑆 → 𝐴𝑎 → 𝐵 𝑐 𝑎 ⋯
𝐵 → 𝑏𝑐 | 𝑎
𝐶 → 𝑐| 𝜀
Le premier 𝑆 → 𝐴𝑎 → 𝐵𝐶𝑎 ⋯
Sui(S) = ?𝑏,𝑏,$ S$

=? 𝑎
Sui(A) = A a

Sui(B) = Pr(S)
? ∪ 𝑐 ∪ Pr 𝐶 ∖? 𝜀 ∪ Pr(𝐷)
𝑑
𝑆𝑢𝑖(𝐴) B C

Sui(C) = Sui(A)
? = 𝑎 𝜀

28
Exemple d’application

Soit la grammaire 𝐺1 suivante :

𝑆 → 𝑎𝑆𝑏 𝑐𝑑 𝑏𝑆𝐴𝑒 Pr(S) = 𝑎, 𝑐, 𝑏

𝐴 → 𝑎𝐴𝑑𝐵 | 𝜀 Pr(A) = 𝑎, 𝜀 𝑆𝑢𝑖(𝐴) = 𝑒, 𝑑
𝐵 → 𝑏𝑏 Pr(B) = 𝑏 𝑆𝑢𝑖 𝐵 = 𝑆𝑢𝑖(𝐴) = 𝑒, 𝑑
𝑆𝑢𝑖 𝑆 = $, 𝑏 ∪ Pr 𝐴 \ 𝜀 ∪ 𝑒 = $, 𝑏, 𝑎, 𝑒
Soit la grammaire 𝐺2 suivante :

𝑆 → 𝐴𝐵𝐶𝑒 Pr(S) = Pr(A)\ 𝜀 ∪ Pr 𝐵 \ 𝜀 ∪ Pr 𝐶 = 𝑎, 𝑏, 𝑐, 𝑑

𝐴 → 𝑎𝐴 | 𝜀 Pr(A) = 𝑎, 𝜀
𝐵 → 𝑏𝐵 𝑐𝐵 𝜀 Pr(B) = 𝑏, 𝑐, 𝜀
𝐶 → 𝑑𝑒 𝑑𝑎 𝑑𝐴 Pr(C) = 𝑑
𝑆𝑢𝑖 𝑆 = $
𝑆𝑢𝑖 𝐴 = Pr 𝐵 \ 𝜀 ∪ Pr 𝐶 ∪ 𝑆𝑢𝑖 𝐴 ∪ 𝑆𝑢𝑖(𝐶) = 𝑏, 𝑐, 𝑑, 𝑒
𝑆𝑢𝑖 𝐵 = Pr 𝐶 ∪ 𝑆𝑢𝑖 𝐵 = 𝑑
𝑆𝑢𝑖 𝐶 = 𝑒
29
Exemple d’application

Soit la grammaire G suivante :

𝐸 → 𝑇𝐸 ′ 𝑆𝑢𝑖 𝐸 = $ , )
𝐸 ′ → +𝑇𝐸 ′ | 𝜀
𝑆𝑢𝑖 𝐸 ′ = 𝑆𝑢𝑖 𝐸 ∪ 𝑆𝑢𝑖(𝐸 ′ ) = $ , )
𝑇 → 𝐹𝑇 ′
𝑇 ′ →∗ 𝐹𝑇 ′ | 𝜀 𝑆𝑢𝑖 𝑇 = Pr 𝐸 ′ \ 𝜀 ∪ 𝑆𝑢𝑖 𝐸 ∪ 𝑆𝑢𝑖 𝐸 ′ = + , $ , )
𝐹 → 𝐸 | 𝑖𝑑
𝑆𝑢𝑖 𝑇 ′ = 𝑆𝑢𝑖 𝑇 ∪ 𝑆𝑢𝑖(𝑇 ′ ) = +, $ , )
𝑆𝑢𝑖 𝐹 = Pr 𝑇 ′ \ 𝜀 ∪ 𝑆𝑢𝑖 𝑇 ∪ 𝑆𝑢𝑖 𝑇 ′ = ∗, + , $ , )
Pr E = Pr(T) = Pr(F) = (, 𝑖𝑑
Pr 𝐸 ′ = +, 𝜀
Pr T = Pr(F) = (, 𝑖𝑑
Pr 𝑇 ′ = ∗, 𝜀
Pr(F) = (, 𝑖𝑑

30
Table d’analyse

Soit la grammaire G suivante :

𝐸 → 𝑇𝐸 ′ 𝑆𝑢𝑖 𝐸 = $ , )
𝐸 ′ → +𝑇𝐸 ′ | 𝜀
𝑇 → 𝐹𝑇 ′ 𝑆𝑢𝑖 𝐸 ′ = 𝑆𝑢𝑖 𝐸 ∪ 𝑆𝑢𝑖(𝐸 ′ ) = $ , )
𝑇 ′ →∗ 𝐹𝑇 ′ | 𝜀 𝑆𝑢𝑖 𝑇 = Pr 𝐸 ′ \ 𝜀 ∪ 𝑆𝑢𝑖 𝐸 ∪ 𝑆𝑢𝑖 𝐸 ′ = + , $ , )
𝐹 → 𝐸 | 𝑖𝑑
𝑆𝑢𝑖 𝑇 ′ = 𝑆𝑢𝑖 𝑇 ∪ 𝑆𝑢𝑖(𝑇 ′ ) = +, $ , )
𝑆𝑢𝑖 𝐹 = Pr 𝑇 ′ \ 𝜀 ∪ 𝑆𝑢𝑖 𝑇 ∪ 𝑆𝑢𝑖 𝑇 ′ = ∗, + , $ , )
Pr E = Pr(T) = Pr(F) = (, 𝑖𝑑
Pr 𝐸 ′ = +, 𝜀 + * ( ) id $

Pr T = Pr(F) = (, 𝑖𝑑
E Erreur Erreur 𝐸 → 𝑇𝐸 ′ Erreur 𝐸 → 𝑇𝐸 ′ Erreur

′ 𝐸′ 𝐸 ′ → +𝑇𝐸 ′ Erreur Erreur 𝐸′ → 𝜀 Erreur 𝐸′ → 𝜀

Pr 𝑇 = ∗, 𝜀
T Erreur Erreur 𝑇 → 𝐹𝑇 ′ Erreur 𝑇 → 𝐹𝑇 ′ Erreur
Pr(F) = (, 𝑖𝑑
𝑇′ 𝑇′ → 𝜀 𝑇 ′ →∗ 𝐹𝑇 ′ Erreur 𝑇′ → 𝜀 Erreur 𝑇′ → 𝜀

F Erreur
31
Erreur 𝐹→ 𝐸 Erreur 𝐹 → 𝑖𝑑 Erreur
Table d’analyse 𝑇′ → 𝜀 ?
Soit 𝑊 = 𝑖𝑑 + 𝑖𝑑 ? 𝐸 → 𝑇𝐸 ′ → 𝐹𝑇 ′ 𝐸 ′ → 𝑖𝑑𝑇 ′ 𝐸 ′ → 𝑖𝑑𝐸 ′ → 𝑖𝑑 + 𝑇𝐸 ′
Soit la grammaire G suivante :
𝐸 → 𝑇𝐸 ′ 𝑆𝑢𝑖 𝐸 = $ , )
𝐸 ′ → +𝑇𝐸 ′ | 𝜀
𝑇 → 𝐹𝑇 ′ 𝑆𝑢𝑖 𝐸 ′ = 𝑆𝑢𝑖 𝐸 ∪ 𝑆𝑢𝑖(𝐸 ′ ) = $ , )
𝑇 ′ →∗ 𝐹𝑇 ′ | 𝜀 𝑆𝑢𝑖 𝑇 = Pr 𝐸 ′ \ 𝜀 ∪ 𝑆𝑢𝑖 𝐸 ∪ 𝑆𝑢𝑖 𝐸 ′ = + , $ , )
𝐹 → 𝐸 | 𝑖𝑑
𝑆𝑢𝑖 𝑇 ′ = 𝑆𝑢𝑖 𝑇 ∪ 𝑆𝑢𝑖(𝑇 ′ ) = +, $ , )
𝑆𝑢𝑖 𝐹 = Pr 𝑇 ′ \ 𝜀 ∪ 𝑆𝑢𝑖 𝑇 ∪ 𝑆𝑢𝑖 𝑇 ′ = ∗, + , $ , )
Pr E = Pr(T) = Pr(F) = (, 𝑖𝑑
Pr 𝐸 ′ = +, 𝜀 + * ( ) id $

Pr T = Pr(F) = (, 𝑖𝑑
E Erreur Erreur 𝐸 → 𝑇𝐸 ′ Erreur 𝐸 → 𝑇𝐸 ′ Erreur

′ 𝐸′ 𝐸 ′ → +𝑇𝐸 ′ Erreur Erreur 𝐸′ → 𝜀 Erreur 𝐸′ → 𝜀

Pr 𝑇 = ∗, 𝜀
T Erreur Erreur 𝑇 → 𝐹𝑇 ′ Erreur 𝑇 → 𝐹𝑇 ′ Erreur
Pr(F) = (, 𝑖𝑑
𝑇′ 𝑇′ → 𝜀 𝑇 ′ →∗ 𝐹𝑇 ′ Erreur 𝑇′ → 𝜀 Erreur 𝑇′ → 𝜀

F Erreur
32
Erreur 𝐹→ 𝐸 Erreur 𝐹 → 𝑖𝑑 Erreur
Analyse prédictive
flot d’entrée id + id * id $

Programme Flot de sortie

axiome E d‘analyse (indique la suite des
règles utilisées)
$ prédictive

Pile M Table d’analyse

id + * $
E R1 Erreur
T R2

33
 Analyse syntaxique descendante

Analyse prédictive non récursive

⚫ Tableau d’analyse à deux dimensions M[A, a], A est non-terminal, a est terminal ou $.
⚫ Initialement la pile contient l’axiome de la grammaire au dessus du symbole $.
⚫ X est le symbole au sommet de la pile et a le symbole d’entrée courant déterminent
l’action de l’analyseur. Trois possibilités :
⚫ Si X = a = $, Arrêt de l’analyseur et fin réussi de l’analyse.
⚫ Si X = a  $, l’analyseur enlève X de la pile et avance son pointeur vers le symbole suivant.
⚫ Si X est un non-terminal, le programme consulte l’entrée M[X, a] de la table d’analyse M qui
est soit une X-production soit une erreur.
⚫ Si X-production, remplacer X au sommet de la pile par la X-production (*).
⚫ Si erreur, appeler la procédure de récupération sur erreur.

(*) M[X, a] = {X → UVW}, remplacer X au sommet de la pile par WVU (avec U au

sommet)

34
Analyse syntaxique descendante

Algorithme D’analyse prédictive non récursive

Données : Une chaîne w et une table d’analyse M pour une grammaire G

Résultat : Si w est dans L(G), une dérivation gauche pour w, erreur sinon.
Positionner le pointeur source ps sur le premier symbole de w$;
WHILE X  $ DO
soit X le symbole en sommet de la pile et a le symbole pointé par ps:
IF X est un terminal THEN
IF X = a THEN
enlever X de la pile et avancer ps;
ELSE
error ();
END IF
ELSE /* X est un non-terminal */
IF M[X, a] = X → Y1Y2 … Yk THEN
placer Yk, Yk-1, … Y1 sur la pile avec Y1 au sommet;
émettre en sortie la production X → Y1Y2 … Yk
ELSE
error ();
END IF
END IF
END WHILE

35
 + * ( ) id $
E Erreur Erreur 𝐸 → 𝑇𝐸 ′ Erreur 𝐸 → 𝑇𝐸 ′ Erreur

𝐸′ 𝐸 ′ → +𝑇𝐸 ′ Erreur Erreur 𝐸′ → 𝜀 Erreur 𝐸′ → 𝜀

Analyse DESCENDANTE
T Erreur Erreur 𝑇 → 𝐹𝑇 ′ Erreur 𝑇 → 𝐹𝑇 ′ Erreur
Soit 𝑊 = 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ ?
𝑇′ 𝑇′ → 𝜀 𝑇 ′ →∗ 𝐹𝑇 ′ Erreur 𝑇′ → 𝜀 Erreur 𝑇′ → 𝜀

Symbole de F Erreur Erreur 𝐹→ 𝐸 Erreur 𝐹 → 𝑖𝑑 Erreur

Sommet fin de chaine
de la pile
Pile Entrée Sortie
$𝐸 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐸 → 𝑇𝐸 ′
Rq : On empile à l’envers
$𝐸 ′ 𝑇 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇 → 𝐹𝑇 ′
$𝐸 ′ 𝑇 ′ 𝐹 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹 → 𝑖𝑑
$𝐸 ′ 𝑇 ′ 𝑖𝑑 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$
$𝐸 ′ 𝑇 ′ +(𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇′ → 𝜀
$𝐸 ′ +(𝑖𝑑 ∗ 𝑖𝑑)$

36
 + * ( ) id $
E Erreur Erreur 𝐸 → 𝑇𝐸 ′ Erreur 𝐸 → 𝑇𝐸 ′ Erreur

𝐸′ 𝐸 ′ → +𝑇𝐸 ′ Erreur Erreur 𝐸′ → 𝜀 Erreur 𝐸′ → 𝜀

Analyse descendante
T Erreur Erreur 𝑇 → 𝐹𝑇 ′ Erreur 𝑇 → 𝐹𝑇 ′ Erreur
Soit 𝑊 = 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ ?
𝑇′ 𝑇′ → 𝜀 𝑇 ′ →∗ 𝐹𝑇 ′ Erreur 𝑇′ → 𝜀 Erreur 𝑇′ → 𝜀

F Erreur Erreur 𝐹→ 𝐸 Erreur 𝐹 → 𝑖𝑑 Erreur

Pile Entrée Sortie

$𝐸 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐸 → 𝑇𝐸 ′
$𝐸 ′ 𝑇 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇 → 𝐹𝑇 ′
$𝐸 ′ 𝑇 ′ 𝐹 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹 → 𝑖𝑑
$𝐸 ′ 𝑇 ′ 𝑖𝑑 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$
$𝐸 ′ 𝑇 ′ +(𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇′ → 𝜀
$𝐸 ′ +(𝑖𝑑 ∗ 𝑖𝑑)$ 𝐸 ′ → +𝑇𝐸 ′
$𝐸 ′ 𝑇 + +(𝑖𝑑 ∗ 𝑖𝑑)$
$𝐸 ′ 𝑇 (𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇 → 𝐹𝑇 ′
$𝐸 ′ 𝑇 ′ 𝐹 (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹→ 𝐸
$𝐸 ′ 𝑇 ′ )𝐸( (𝑖𝑑 ∗ 𝑖𝑑)$
37
 + * ( ) id $
E Erreur Erreur 𝐸 → 𝑇𝐸 ′ Erreur 𝐸 → 𝑇𝐸 ′ Erreur

Pile 𝐸′ 𝐸 ′ → +𝑇𝐸 ′
Erreur
Entrée Erreur 𝐸′ → 𝜀
Sortie Erreur 𝐸′ → 𝜀
analyse
$𝐸 T 𝑖𝑑 Erreur
+ (𝑖𝑑 ∗ 𝑖𝑑)$
Erreur 𝑇𝐸 →′ 𝑇𝐸 ′ Erreur
→ 𝐹𝑇 𝑇 → 𝐹𝑇 ′ Erreur
Soit 𝑊 = 𝑖𝑑 + (𝑖𝑑′∗ 𝑖𝑑)$ ?
$𝐸 𝑇 𝑇′ 𝑖𝑑 𝑇+′ →(𝑖𝑑
𝜀 ∗𝑇 ′
𝑖𝑑)$→∗ 𝐹𝑇 ′ 𝑇→
Erreur 𝐹𝑇 ′𝑇 ′ → 𝜀 Erreur 𝑇′ → 𝜀

$𝐸 ′ 𝑇 ′ 𝐹 F 𝑖𝑑 Erreur Erreur
+ (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹𝐹
→→𝐸 𝑖𝑑 Erreur 𝐹 → 𝑖𝑑 Erreur

$𝐸 ′ 𝑇 ′ 𝑖𝑑 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$
$𝐸 ′ 𝑇 ′ +(𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇′ → 𝜀
$𝐸 ′ +(𝑖𝑑 ∗ 𝑖𝑑)$ 𝐸 ′ → +𝑇𝐸 ′
$𝐸 ′ 𝑇 + +(𝑖𝑑 ∗ 𝑖𝑑)$
$𝐸 ′ 𝑇 (𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇 → 𝐹𝑇 ′
$𝐸 ′ 𝑇 ′ 𝐹 (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹→ 𝐸
$𝐸 ′ 𝑇 ′ )𝐸( (𝑖𝑑 ∗ 𝑖𝑑)$
38
$𝐸 ′ 𝑇 ′ )𝐸 𝑖𝑑 ∗ 𝑖𝑑)$ 𝐸 → 𝑇𝐸 ′
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇 → 𝐹𝑇 ′
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ 𝐹 𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹 → 𝑖𝑑
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ 𝑖𝑑 𝑖𝑑 ∗ 𝑖𝑑)$
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ ∗ 𝑖𝑑)$ 𝑇 ′ →∗ 𝐹𝑇 ′
 $𝐸 ′ 𝑇 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇 → 𝐹𝑇 ′
+ * ( ) id $
$𝐸 ′ 𝑇 ′ 𝐹 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹 → 𝑖𝑑
′ ′
E Erreur Erreur 𝐸 → 𝑇𝐸 ′ Erreur 𝐸 → 𝑇𝐸 ′ Erreur
$𝐸 𝑇 𝑖𝑑 𝑖𝑑 + (𝑖𝑑 ∗ 𝑖𝑑)$
′
𝐸 𝐸 ′ → +𝑇𝐸 ′ Erreur Erreur 𝐸′ → 𝜀 Erreur 𝐸′ → 𝜀
analyse
$𝐸 𝑇 ′ ′
+(𝑖𝑑 ∗ 𝑖𝑑)$ ′
𝑇 →𝜀
′ T Erreur Erreur 𝑇 → 𝐹𝑇 ′
′
Erreur
′
𝑇 → 𝐹𝑇 ′ Erreur
$𝐸 ∗ 𝑖𝑑)$ ?
Soit 𝑊 = 𝑖𝑑 + (𝑖𝑑 +(𝑖𝑑 ∗ 𝑖𝑑)$ 𝐸 → +𝑇𝐸
′
𝑇 ′
𝑇 →𝜀 ′
𝑇 →∗ 𝐹𝑇 ′
Erreur 𝑇′ → 𝜀 Erreur 𝑇′ → 𝜀
$𝐸 ′ 𝑇 + +(𝑖𝑑 ∗ 𝑖𝑑)$
F Erreur Erreur 𝐹→ 𝐸 Erreur 𝐹 → 𝑖𝑑 Erreur
$𝐸 𝑇′
(𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇→ 𝐹𝑇 ′
$𝐸 ′ 𝑇 ′ 𝐹 (𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹→ 𝐸
$𝐸 ′ 𝑇 ′ )𝐸( (𝑖𝑑 ∗ 𝑖𝑑)$
39
$𝐸 ′ 𝑇 ′ )𝐸 𝑖𝑑 ∗ 𝑖𝑑)$ 𝐸 → 𝑇𝐸 ′
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 𝑖𝑑 ∗ 𝑖𝑑)$ 𝑇 → 𝐹𝑇 ′
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ 𝐹 𝑖𝑑 ∗ 𝑖𝑑)$ 𝐹 → 𝑖𝑑
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ 𝑖𝑑 𝑖𝑑 ∗ 𝑖𝑑)$
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ ∗ 𝑖𝑑)$ 𝑇 ′ →∗ 𝐹𝑇 ′
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ 𝐹 ∗ ∗ 𝑖𝑑)$
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ 𝐹 𝑖𝑑)$ 𝐹 → 𝑖𝑑
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ 𝑖𝑑 𝑖𝑑)$
$𝐸 ′ 𝑇 ′ )𝐸 ′ 𝑇 ′ )$ 𝑇′ → 𝜀
$𝐸 ′ 𝑇 ′ )𝐸 ′ )$ 𝐸′ → 𝜀
Grammaire LL(1)

⚫ Pour certaines grammaires, la table d’analyse peut avoir des entrées définies de
façon multiple.

⚫ La grammaire dont la table d’analyse n’a aucune entrée définie de façon multiple
est dite LL(1).
un seul symbole d’entrée de prévision

Leftmost derivation : dérivation à gauche

Left to right scanning : parcours de l’entrée de gauche vers l’entrée de droite

Une grammaire est LL(1) ➔

⚫ Factorisée à gauche
⚫ Non récursive à gauche
⚫ Non ambigüe
40