Compilation/Analyse syntaxique

Rôles de l'analyse syntaxique

Cette phase à plusieurs objectifs :

• déterminer si la suite de tokens est conforme à la grammaire définissant le langage source ;
• repérer les erreurs de nature syntaxique ;
• définir une structure hièrarchique (un arbre).

En pratique, d'autres tâches sont réalisées simultanément pendant l'analyse syntaxique :

• ajouter des informations à la table des symboles ;
• effectuer des vérifications de type ;
• produire du code intermédiaire.

Méthodes d'analyse syntaxique

La plupart des méthodes d'analyse syntaxique tombent dans deux classes :

1. les méthodes d'analyse descendantes (top-down parsingModèle:En) sont les plus populaires car les analyses correspondants sont faciles à mettre en œuvre à la main ;
2. les méthodes d'analyse ascendantes (bottom-up parsingModèle:En) sont les plus puissantes et sont celles utilisées par les outils qui génèrent automatiquement un analyseur à partir d'une grammaire (exemple : yacc).

Pour illustrer les différences entre ces méthodes nous utilisons l'exemple du langage des expressions arithmétiques.

Ce langage peut être décrit par la grammaire algébrique suivante :

E → E + T | T
T → T × F | F
F → ( E ) | id

Note : par convention, les symboles en capitale comme E, T et F sont des non-terminaux et les autres symboles comme +, ×, (, ) et id sont des terminaux (les identifiants des tokens).

Dans la suite de la leçon nous allons considérer l'analyse de la chaîne ( id + id ) * id avec les deux approches méthodologiques précédemment cités..

Analyses descendantes

Dans les analyses descendantes :

• l'arbre est construit en partant de la racine et en allant jusqu'au feuilles ;
• l'analyse s'appuie sur une dérivation gauche de la chaîne, c'est-à-dire qu'on remplace toujours en premier le non-terminal le plus à gauche.

On présente ci-dessous la dérivation de la chaîne depuis la racine et l'arbre d'analyse qui en résulte. Pour bien faire resortir le parallèle entre les deux on y numérote chaque étape.

E	(Étape 0)
E ⇒g T	(Étape 1)
⇒g T * F	(Étape 2)
⇒g (E) * F	(Étape 3)
⇒g (E+T) * F	(Étape 4)
⇒g (T+T) * F	(Étape 5)
⇒g (F+T) * F	(Étape 6)
⇒g (id+T) * F	(Étape 7)
⇒g (id+F) * F	(Étape 8)
⇒g (id+id) * F	(Étape 9)
⇒g (id+id) * id	(Étape 10)

E (Étape 0)
│
│
└──T (Étape 1) 
   │
   ├──F (Étape 2)
   │  │
   │  └──id (Étape 10)
   │
   ├──* (Étape 2)
   │
   └──T (Étape 2)
      │
      ├──) (Étape 3)
      │
      ├──E (Étape 3)
      │  │
      │  ├──T (Étape 4)
      │  │  │
      │  │  └──F (Étape 8)
      │  │     │
      │  │     └──id (Étape 9)
      │  │ 
      │  ├──+ (Étape 4)
      │  │
      │  └──E (Étape 4)
      │     │
      │     └──T (Étape 5)
      │        │
      │        └──F (Étape 6)
      │           │
      │           └──id (Étape 7)
      │
      │
      │
      │
      └──( (Étape 3)

À chaque étape, on sélectionne une règle qui permet de dériver la chaîne. Cela peut entraîner des développement d'impasse et donc nécessiter retours arrières (ce n’est pas le cas dans notre exemple ou nous avons fait les bons choix).

On peut limiter les retours arrières en utilisant l'information des premiers symboles terminaux qui dérivent d'une règle.

Pour les analyses ascendantes

On agit inversement :

• l'arbre est construit en remontant à la racine depuis les feuilles ;
• l'analyse s'appuie sur une dérivation droite de la chaîne c'est-à-dire qu'on remplace toujours en premier le non-terminal le plus à droite.

(id+id)*id	(Étape 0)
⇐d(F+id)*id	(Étape 1)
⇐d(T+id)*id	(Étape 2)
⇐d(E+id)*id	(Étape 3)
⇐d(E+F)*id	(Étape 4)
⇐d(E+T)*id	(Étape 5)
⇐d(E)*id	(Étape 6)
⇐dF*id	(Étape 7)
⇐dT*id	(Étape 8)
⇐dT*F	(Étape 9)
⇐dT	(Étape 10)
⇐dE	(Étape 11)

( id + id ) * id (Étape 0)
│ │ │ │ │ │ │
│ F │ │ │ │ │ (Étape 1)
│ │ │ │ │ │ │
│ T │ │ │ │ │ (Étape 2)
│ │ │ │ │ │ │
│ E │ │ │ │ │ (Étape 3)
│ │ │ │ │ │ │
│ │ │ F │ │ │ (Étape 4)
│ │ │ │ │ │ │
│ │ │ T │ │ │ (Étape 5)
│ │ │ │ │ │ │
│ └─┼──┘ │ │ │
│ E │ │ │ (Étape 6)
│ │ │ │ │
└────┼────┘ │ │
     │      │ │
     F      │ │    (Étape 7)
     │      │ │
     T      │ │    (Étape 8)
     │      │ │
     │      │ F    (Étape 9)
     │      │ │
     └──────┼─┘
            │
            T      (Étape 10)
            │
            E      (Étape 11)

Note : dans l'arbre ci-dessus les longueur des branches ne sont pas significatives, elles font resortir les étapes de façon commode mais arbitraire. L'arbre suivant est tout à fait équivalent :

( id + id ) * id 
│ │ │ │ │ │ │
│ F │ F │ │ F 
│ │ │ │ │ │ │
│ T │ T │ │ │
│ │ │ │ │ │ │
│ E │ │ │ │ │ 
│ └─┼──┘ │ │ │
│ │ │ │ │
│ E │ │ │
└────┼────┘ │ │
     │      │ │
     F      │ │ 
     │      │ │
     T      │ │
     └──────┼─┘
            │
            T
            │
            E

À chaque étape, on sélectionne une partie au début de la chaîne qui dérive d'un non-terminal et on le remplace par ce non-terminal.

L'inverse de la suite des règles utilisées est une dérivation droite de la chaîne.

On constate que nos algorithmes sont imprécis, ils demandent de faire des choix, ils sont non-déterministe.

Analyse syntaxique descendante

Exemple

Considérons la grammaire suivante : S→cAd A→ab|a

Analysons la chaîne « cad » et construisons l'arbre correspondant.

Étape	Arbre	Explication
0	S cad ↑ ↑	S est la racine de notre arbre, cad notre chaîne et les flèches (↑) représentent la position de deux pointeur, ici sur le S de l'arbre et le c du début de la chaîne.
1	S cad ┌─┼─┐ ↑ c A d │ ↑ │ └─────────────┘	le pointeur de l'arbre pointe sur un non-terminal, on développe l'arbre à cette position d’après la grammaire ; on positionne le pointeur de l'arbre sur le terminal extrême gauche dans l'arbre ; on compare les deux symboles pointés respectivement dans l'arbre et la chaîne ; ici les deux symboles correspondent, on avance les deux pointeurs.
2	S cad ┌─┼─┐ ↑ c A d │ ┌┴┐ │ a b │ ↑ │ └─────────────┘	* le pointeur de l'arbre pointe sur un non-terminal, on développe l'arbre à cette position d’après la grammaire, qui ici permet plusieurs possibilité, on choisi le premier qu'elle propose ; on positionne le pointeur de l'arbre sur le terminal extrême gauche dans l'arbre ; on compare les deux symboles pointés respectivement dans l'arbre et la chaîne ; ici les deux symboles correspondent, on avance les deux pointeurs.
3	S cad ┌─┼─┐ ↑ c A d │ ┌┴┐ │ a b │ ↑ │ └────────────┘	on compare les deux symboles pointés respectivement dans l'arbre et la chaîne ; les deux symboles diffèrent ; le choix de développement par A→ab à l'étape 2 n'était pas bon ; on « dépile » le précédent développement.
2’	S cad ┌─┼─┐ ↑ c A d │ │ │ a │ ↑ │ └────────────┘	* les pointeurs sont replacés comme en fin d'étape 1 et on développe le non-terminal avec la règle alternative A→a ; on positionne le pointeur de l'arbre sur le terminal extrême gauche dans l'arbre ; on compare les deux symboles pointés respectivement dans l'arbre et la chaîne ; ici les deux symboles correspondent, on avance les deux pointeurs.
3’	S cad ┌─┼─┐ ↑ c A d │ │ ↑ │ a └───────────┘	on compare les deux symboles pointés respectivement dans l'arbre et la chaîne ; ici les deux symboles correspondent, on est arrivé au bout de la chaîne, on à donc terminé avec succès.

Algorithme naïf

Décrivons plus formellement l'algorithme que nous venons d’utiliser :

• à chaque étape, on examine le nœud courant de l'arbre en parcourant les feuilles de gauche à droite ;
• si le nœud courant de l'arbre est un non-terminal A, on sélectionne une règle avec A en partie gauche ;
  • si cette règle est A→ε (où ε désigne le mot vide), on passe au nœud suivant de l'arbre ;
  • sinon on développe le nœud courant avec la règle ;
• si le nœud courant est un terminal, on le compare avec l'élément courant de la chaîne:
  • s'il y a égalité, on passe au nœud suivant et on avance le pointeur dans la chaîne ;
  • sinon on reviens au dernier choix de règle, ce qu'on nomme « retour arrière » ou « dépilage ».

Problèmes rencontrés avec l'algorithme naïf

Un retour-arrière coûteux

Les retours-arrière sont coûteux en termes de calcul. Ils sont dus à la présence de grammaire avec un même début en partie droite, de la forme : $A\to \alpha {\mathrm{B}}_1|\alpha {\mathrm{B}}_2|\dots |\alpha {\mathrm{B}}_n|$.

Pour ces règles on ne sait pas choisir sans risque d'erreur.

La solution consiste à éliminer ces règles par substitution. Ainsi $A\to \alpha B$ sera remplacé par $B\to {\mathrm{B}}_1|{\mathrm{B}}_2|\dots |{\mathrm{B}}_n|$.

Bouclages infinis

Des grammaires peuvent conduire à des phénomènes de bouclage infini, dus à la présence de règles de grammaire récursives gauche, de la forme :

• $A\to A\alpha$ (récursivité directe) ;
• $A\to B\alpha$ et $B\to AB$ (récursivité indirecte) ;

La solution consiste à remplacer ces règles en supprimant la récursivité à gauche. Cela ne pose pas de problème puisque nous disposons d'un théorème qui dit que : Modèle:Théorème

Le principe de remplacement fonctionne ainsi :

• en cas de récursivité directe $A\to A\alpha |\mathrm{B}$ sera remplacé par $A\to \mathrm{B}{A}^{\prime }$ et

$A^{\prime }\to \alpha A^{\prime }|ϵ$

• en cas de récursivité indirecte

$A\to B\alpha$	remplacé par	$A\to A\mathrm{B}\alpha$
$B\to A\mathrm{B}$		$B\to A\mathrm{B}$

L'algorithme comporte des opérations coûteuses

En effet la recherche d'une règle de grammaire, les opérations de manipulation, le parcours de l'arbre, sont autant d'opérations rallongeant le temps de calcul.

Deux solutions sont possible pour résoudre ces problèmes :

1. utiliser l'analyse par descente récursive ;
2. utiliser l'analyse itérative, LL(1) (ce terme sera expliqué plus loin dans le cours).

Analyse par descente récursive

En utilisant cette méthode que nous avons précédemment présenté, on peut associer une procédure à chaque non-terminal.

procédure S
   match(c);A;match(d)
end
procédure A
   match(a);if curent_token = b then match(b)
end
procédure B
   if curent_token = t then curent_token = next_token
                       else error
end
analyse d'une chaîne :
    initialement
       curent_token = first_token
       call S

La suite des appels de procédure définit l'arbre d'analyse. Dans le cas général, les procédures sont mutuellement récursives.

Il nous faut passer à une analyse itérative, par exemple LL(1). Pour ce faire on utilise une pile, ce qui permet de supprimer la récursivité.

Analyse itérative, LL(1)

Cette méthode consiste à utiliser une pile, ce qui permet de supprimer la récursivité.

Cette méthode est ainsi nommée car :

• l'analyse de la chaîne s'effectue de gauche à droite (le L venant de Modèle:En, gauche en anglais) ;
• on construit un dérivation gauche ;
• on lit 1 token en avance (on parle alors d'analyse prédictive).

Principe de l'analyse LL

Cette algorithme utilise :

• un pointeur sur l'élément courant dans la chaîne à analyser (sufixée par $\mathrm{\$}$, le marqueur de fin) ;
• une pile qui peut contenir des terminaux, des non-terminaux ou $\mathrm{\$}$ ;
• une table d'analyse $T$, indexée par :
  • les non-terminaux (lignes) ;
  • les terminaux Modèle:Union$\mathrm{\$}$ (chaînes).

Chaque élément $T[A,a]$ contient la règle de grammaire à utiliser lorsque A est l'élément courant de la chaîne.

Initialement, le pointeur pointe sur le premier élément de la chaîne et la pile contient $\mathrm{\$}$ et $S$ ; $S$ se situant au sommet de la pile.

À chaque itération, l'analyseur examine l'élément $X$ au sommet de la pile et l'élément $a$ courant de la chaîne et réalise le traitement suivant :

• si $X$ est un terminal ou $\mathrm{\$}$ :
  • si $X=a=\mathrm{\$}$, terminer avec succès ;
  • si $X=a\ne \mathrm{\$}$, dépiler $X$ et avancer le pointeur ;
  • sinon terminer avec erreur ;
• si $X$ est un non-terminal :
  • si $T[X,a]$ contient $X\to Y_1,Y_2,\dots ,Y_n$ dépiler $X$ et empiler $Y_n,Y_{n-1},\dots ,Y_1$ dans cet ordre ;
  • sinon terminer avec erreur.

Exemple

Considérons la grammaire ${G_0}^{\prime }$ obtenue à partir de $G_0$ en supprimant la récursivité gauche.

$G_0$	${G_0}^{\prime }$
E → E + T E → T T → T × F T → F F → ( E ) F → id	E → TE' E' → +TE'|ε T → FT' T' → ×FT'|ε F → ( E ) F → id

Une table d'analyse pour cette grammaire est :

	id	+	×	(	)	$
E	E → TE'			E → TE'
E'		E' → TE'			E' → ε	E' → ε
T	T → FT'			T → FT'
T'		T' → ε	T' → ×FT'	T' → ε	T' → ε
F	F → id			F → ( E )

Note : les cases vides représentes les cas d'erreur (token inattendu)

Utilisons le tableau pour faire l'analyse de la chaîne id + id × id.

Chaîne	Pile	Règle	Arbre
id + id × id $	$ E		à faire
id + id × id $	$ E' T	E Modèle:To T E'
id + id × id $	$ E T' F	T Modèle:To FT'
id + id × id $	$ E' T' id	F Modèle:To id
+ id × id $	$ E' T'
+ id × id $	$ E'	T' Modèle:To Modèle:Epsilon
+ id × id $	$ E' T +	E' Modèle:To +TE'
id × id $	$ E' T
id × id $	$ E' T' F	TModèle:ToFT'
id × id $	$ E' T' id	FModèle:Toid
× id $	$ E' T'
× id $	$ E' T' F ×	T'Modèle:ToF × FT'
id $	$ E' T' F
id $	$ E' T' id	FModèle:Toid
$	$ E' T'
$	$ E' T'	T'Modèle:ToModèle:Epsilon
$	$ E'	E'Modèle:ToModèle:Epsilon
$	$

La table d'analyse peut être remplie en utilisant 2 fonctions associées à la grammaire : les fonctions FIRST et FOLLOW.

Soit Modèle:Alpha, une chaîne contenant des terminaux ou des non-terminaux.

Soit A, un non terminal

Par définition :

• FIRST(Modèle:Alpha) = ensemble de terminaux qui peuvent se trouver au début des chaînes dérivées de Modèle:Alpha ;
• FOLLOW(A) = ensemble des terminaux qui peuvent se trouver immédiatement après A dans une chaîne de dérivation.

Construction de la table d'analyse avec FIRST et FOLLOW

L'idée est que pour toute règle de grammaire AModèle:ToModèle:Alpha

• si a ∈ FIRST(Modèle:Alpha), alors l'analyseur va utiliser cette règle quand l'élément courant dans la chaîne est a. La seule complication est lorsque Modèle:Alpha=ε ou bien Modèle:Alpha→ ε dans ce cas on doit également développer A par Modèle:Alpha.
• si l'élément courant dans la chaîne appartient à FOLLOW(A)

G = (Vt, Vn, P, S)
Vt: Ensemble des terminaux
Vn: Ensemble des non terminaux
P: Ensemble des règle de production
S: Axiome

pour toute production X → γ ∈ P

 faire pour tout a ∈ First (γ)
   faire ajouter X → γ ` Table[X , a] fait
   si ε ∈ First(γ) alors pour tout b ∈ Follow(X )
     faire Table[X , b] = X → γ
     fait
   finsi

fait

Calcul des ensemble FIRST et FOLLOW

Pour un grammaire G=(V,Σ,R,S)

• FIRST(α) = $\{a\in \mathrm{\Sigma }|\mathrm{\exists }\beta \cdot \beta {\to }^{*}a\alpha \}$
• FOLLOW(A) = $\{a\in \mathrm{\Sigma }|\mathrm{\exists }\alpha ,\beta \cdot S{\to }^{*}\alpha Aa\beta \}$