Théorie des langages : Cours analyse syntaxique
Télécharger PDFL’Analyse Syntaxique
2.1 Le rôle de l’analyseur syntaxique
L’analyseur syntaxique joue un rôle central dans la partie frontale d’un compilateur ou d’un interpréteur. Ses principales fonctions sont :
- Activer l’analyseur lexical pour traiter le code source.
- Vérifier la conformité syntaxique du texte source.
- Construire l’arbre d’analyse syntaxique.
- Préparer ou anticiper la traduction du code.
- Gérer les erreurs syntaxiques courantes.
2.2 Les grammaires
La syntaxe d’un langage est spécifiée par des règles de grammaire hors contexte. Ces règles sont composées de :
- Symboles terminaux (unités lexicales) : un alphabet T.
- Symboles non terminaux (catégories grammaticales) : un alphabet V où V ∩ T = ∅.
- Productions : un ensemble P de règles de la forme A → w, où A ∈ V et w ∈ (T ∪ V)*.
Exemples de productions :
- instr → si expr alors instr sinon instr
- phrase → gsujet gverbe gcomplément
L’axiome S est le symbole de départ de la grammaire et appartient à V. Le langage engendré est l’ensemble des mots terminaux dérivant de l’axiome.
2.3 L’analyse descendante
L’analyse descendante (top-down) commence par le symbole de départ et dérive l’entrée en appliquant les règles de la grammaire. Elle utilise généralement une grammaire hors contexte.
Les parseurs descendants fonctionnent avec l’algorithme LL :
- Lecture de l’entrée de gauche à droite.
- Dérivation par la gauche.
2.4 L’analyse ascendante
L’analyse ascendante (bottom-up) part des unités lexicales et remonte vers le symbole de départ en appliquant les règles de la grammaire à l’envers. Elle utilise généralement une grammaire hors contexte et l’algorithme LR :
- Lecture de l’entrée de gauche à droite.
- Dérivation par la droite.
Détection des erreurs de syntaxe
L’analyseur syntaxique doit détecter les erreurs dans le texte source. Voici quelques exemples d’erreurs syntaxiques en C :
- a = 5 + 6 (point-virgule manquant).
- for i = 5; i < 12; i++ (parenthèse ouvrante manquante après for).
- a = b + c - 5 * (expression manquante après l’opérateur *).
- = 12 + 5 (identificateur manquant).
- a = = 3 (expression invalide).
Grammaires récursives à gauche
Une grammaire hors contexte (GHC) est dite immédiatement récursive à gauche si elle contient une production de la forme A → Aα. Elle est dite indirectement récursive à gauche si un symbole non terminal A permet une dérivation de la forme A ⇒* Aα.
Algorithmes d’élimination de la récursivité à gauche
Récursivité immédiate
Pour éliminer la récursivité immédiate, on remplace une règle de la forme A → Aα | β par :
- A → βA'
- A' → αA' | ε
La grammaire obtenue reconnaît le même langage que la grammaire initiale.
Récursivité indirecte
Pour éliminer la récursivité indirecte, on ordonne les non terminaux A₁, A₂, ..., Aₙ et pour chaque Aᵢ, on remplace les productions de la forme Aᵢ → Aⱼα (où Aⱼ → β₁ | ... | βₖ) par Aᵢ → β₁α | ... | βₖα. Ensuite, on élimine les récursivités immédiates.
Grammaires factorisables à gauche
Une grammaire est dite factorisable à gauche si elle ne contient pas de productions avec des préfixes communs. Pour factoriser une grammaire, on identifie le plus long préfixe commun α dans les alternatives d’un symbole non terminal A et on le remplace par :
- A → αA' | γ₁ | ... | γₚ (où les γᵢ ne commencent pas par α).
- A' → β₁A' | ... | βₙA' | ε.
On répète ce processus jusqu’à ce qu’il n’y ait plus de préfixes communs.
Grammaires LL(1)
Une grammaire hors contexte est dite LL(1) si elle satisfait les trois conditions suivantes :
- Elle n’est pas récursive à gauche.
- Pour toute règle A → αᵢ | αⱼ, PREMIER⁺(αᵢ) ∩ PREMIER⁺(αⱼ) = ∅.
- Si une alternative αᵢ peut dériver ε, alors PREMIER⁺(αⱼ) ∩ SUIVANT⁺(A) = ∅ pour toute autre alternative αⱼ.
Construction de la table d’analyse prédictive
La table d’analyse prédictive est un tableau M où chaque symbole non terminal X et chaque symbole terminal a ou $ indiquent la règle de production à appliquer.
Pour construire cette table, on suit ces étapes :
- Pour chaque production A → α, ajouter A → α dans la case M[A, a] pour tout a ∈ PREMIER(α).
- Si ε ∈ PREMIER(α), ajouter A → α dans la case M[A, b] pour tout b ∈ SUIVANT(A).
- Les cases vides correspondent à des erreurs syntaxiques.
Une grammaire est LL(1) si sa table d’analyse ne contient que des entrées simples.
Exemple d’analyseur prédictif
Voici un exemple de grammaire et sa table d’analyse LL(1) :
- S → aSbT | cT | d
- T → c | bS
La table d’analyse pour cette grammaire est :
| a | b | c | d | $ | |
|---|---|---|---|---|---|
| S | S → aSbT | S → cT | S → d | ||
| T | T → bS | T → c |
Analyse syntaxique ascendante
L’analyse syntaxique ascendante construit l’arbre syntaxique en partant des unités lexicales pour remonter vers l’axiome. Elle utilise généralement le modèle décalage-réduction.
Les opérations principales sont :
- Décalage (shift) : décaler une unité lexicale vers la pile.
- Réduction (reduce) : appliquer une règle de grammaire pour réduire une séquence de symboles à un symbole non terminal.
FAQ
Qu’est-ce qu’une grammaire récursive à gauche ?
Une grammaire récursive à gauche est une grammaire hors contexte où un symbole non terminal peut dériver une production commençant par lui-même (immédiate) ou par une autre règle qui le contient (indirecte).
Comment construire une table d’analyse prédictive ?
Pour construire une table d’analyse prédictive, on utilise les ensembles PREMIER et SUIVANT des symboles. Chaque case M[A, a] contient la règle à appliquer si le symbole non terminal est A et le symbole terminal suivant est a.
Quelle est la différence entre LL(1) et LR(1) ?
LL(1) est une méthode d’analyse descendante qui lit l’entrée de gauche à droite et prend la dérivation la plus à gauche en utilisant un symbole de prévision. LR(1) est une méthode d’analyse ascendante qui lit l’entrée de gauche à droite et prend la dérivation la plus à droite en utilisant un symbole de prévision.