Cours langages et compilation analyse syntaxique ascend...

Théorie des langages : Cours langages et compilation analyse syntaxique ascendante

Télécharger PDF

Analyse Syntaxique Ascendante

L'analyse syntaxique ascendante (ou analyse par décalage/réduction) part des feuilles (les termes terminaux) et remonte vers la racine de l'arbre de dérivation.

Construction de l'arbre de dérivation selon l'ordre postfixé

On utilise deux opérations :

• la création des feuilles par décalage
• la construction des nœuds internes par réduction.

Exemple d'analyse syntaxique ascendante

Considérons la grammaire suivante :

  E → E + T | T
  T → T * F | F
  F → id
  

Les opérations de décalage et de réduction s'effectuent dans l'ordre du parcours postfixé de l'arbre de dérivation.

Voici une suite d'opérations pour analyser le mot id + id * id :

1. Décaler id : pile = id
2. Réduire F → id : pile = F
3. Décaler id : pile = id * F
4. Réduire F → id : pile = F * F
5. Décaler * : pile = F * F
6. Réduire T → F * F : pile = T
7. Décaler id : pile = id + T
8. Réduire F → id : pile = F + T
9. Décaler + : pile = F + T
10. Réduire E → F + T : pile = E

Approche Non-Déterministe

En pratique, on utilise une pile pour réaliser une analyse ascendante par décalage/réduction. Cette pile contient au départ un marqueur particulier $.

L'analyse utilise le mot à analyser (complété par le marqueur $) de gauche à droite.

À chaque étape, on opère soit en décalant un caractère du mot vers la pile, soit en réduisant, à condition qu'il trouve au sommet de la pile une chaîne β correspondant à la partie droite d'une production A → β, qu'on remplace alors par A.

Exemple d'analyse non-déterministe du mot id * id

Mot : id * id$

Pile : $$

Arbre :

1. Décaler id : pile = id$
2. Réduire F → id : pile = F$
3. Décaler * : pile = F*$
4. Décaler id : pile = F*id$
5. Réduire F → id : pile = F*F$
6. Réduire T → F*F : pile = T$
7. Réduire E → T : pile = E$
8. Accepter.

Automate Caractéristique

L'analyseur doit identifier au sommet de la pile les chaînes qui sont la partie droite d'une production de la grammaire et agir de manière efficace.

Pour cela, on construit un automate caractéristique décrivant le comportement au sommet de la pile.

Une convention utile est d'augmenter la grammaire d'une nouvelle variable init et de la règle init → S, où init devient le nouvel axiome et remplace l'ancien axiome S.

Les éléments de l'automate

Un item de la forme X → α•β où • est un symbole particulier indiquant ce qui a déjà été analysé et ce qui reste à analyser.

Les items X → α• sont dits complets.

Pour la production A → abc, on a quatre items associés :

• A → •abc
• A → a•bc
• A → ab•c
• A → abc• (item complet).

Pour une ε-production A → ε, l'item associé est l'item complet A → •.

L'automate caractéristique

L'AFN avec ε-transitions qui caractérise les items valides :

• L'alphabet : Σ ∪ N (symboles terminaux et non terminaux).
• Les états : les items LR(0).
• Les états d'acceptation : les items LR(0) complets.
• L'état initial : l'item init → •S.
• La fonction de transition : trois types de transitions :
• Décalage : X → α•aβ → X → αa•β
• Réduction : X → α•Yβ → X → αY•β si Y → δ est une production.
• Prédiction : X → α•Yβ et Y → •δ si ε est dans Premier(βb).

Exemple de grammaire augmentée

  init → E
  E → E + T | T
  T → T * F | F
  F → id
  

Déterminisation de l'AFN avec ε-transitions

Les états de l'AFD sont des ensembles d'items LR(0).

On utilise l'opération de clôture pour supprimer les ε-transitions :

• Clôture(I) : l'ensemble des items accessibles à partir d'un item de I par des ε-transitions.

Pour chaque transition étiquetée par un terminal ou une variable, on définit δ(I, e) = Clôture({X → αe•β : X → α•eβ ∈ I}).

L'état initial est Clôture({init → •S}).

Seuls les états non vides accessibles à partir de l'état initial via la fonction δ sont construits.

Les états d'acceptation sont ceux qui contiennent un item complet.

Exemple d'états de l'AFD

  0: état initial
    init → •E
    E → •E + T
    E → •T
    T → •T * F
    T → •F
    F → •id

  1: δ(0, E)
    init → E•
    E → E• + T

  2: δ(0, T)
    E → T•
    T → T• * F

  3: δ(0, F)
    T → F•

  4: δ(0, id)
    F → id•

  5: δ(1, +)
    E → E + •T
    T → •T * F
    T → •F
    F → •id

  6: δ(2, *)
    T → T * •F
    F → •id

  7: δ(5, T)
    E → E + T•

  8: δ(6, F)
    T → T * F•
  

Construction de la Table d'Analyse LR(0)

La table a en ligne les états de l'automate et en colonne le marqueur $, les terminaux et les variables de la grammaire.

Pour chaque état I de l'automate :

• Pour chaque transition Ia → J étiquetée par un terminal a, ajouter l'action décaler J à l'entrée table[I, a].
• Pour chaque transition IX → J étiquetée par une variable X, enregistrer J à l'entrée table[I, X].

Pour chaque état d'acceptation I de l'automate :

• Si I contient l'item complet init → S•, ajouter l'action accepter à l'entrée table[I, $] et l'action rejeter à table[I, a] pour tout terminal a.
• Pour tout autre item complet X → α• de I, ajouter l'action réduire X → α aux entrées table[I, a] pour tout terminal a dans le mot.

Exemple de table d'analyse LR(0)

  init → E
  E → E + T | T
  T → T * F | F
  F → id

  État   id   +   *   F   $   eof
  0      d4  d5  d6  d7  -
  1      -   -   -   -   accepter
  2      -   rE→T  -   d8  -
  3      -   -   -   -   rT→F
  4      -   -   -   -   rF→id
  5      d4  -   -   -   rE→E+T
  6      -   -   -   -   rZ→Eeof
  7      -   -   -   -   rE→T
  8      -   -   -   -   rT→T*F
  

Grammaire LR(0)

Une grammaire est LR(0) s'il n'existe au plus qu'une action par entrée dans la table LR(0).

Une grammaire n'est pas LR(0) si l'on a :

• Soit un conflit décaler/réduire : un état de l'AFD caractéristique contient conjointement un item non complet X → α•aβ où a est un terminal et un item complet Y → γ•.
• Soit un conflit réduire/réduire : un état de l'AFD caractéristique contient deux items complets X → α• et Y → β•.

L'automate est déterministe et sans conflit décaler/décaler possible.

Exemple de grammaire LR(0)

  init → E
  E → E + T | T
  T → T * F | F
  F → id
  

Exemple de grammaire non LR(0)

  E → E + T | T
  T → T * F | F
  F → id
  

Analyseur LR(0)

Pour examiner un mot, l'analyseur LR(0) utilise la table d'analyse LR(0) et une pile.

Initialement, la pile contient l'état initial 0.

Le mot complété par le marqueur de fin $ est lu de gauche à droite.

À chaque étape, on examine le symbole courant c du mot analysé et l'état q au sommet de la pile.

• Si table[q, c] = décaler, alors empiler c puis r, et avancer dans la lecture du mot analysé.
• Si table[q, c] = réduire X → α, alors dépiler 2|α| symboles, étant donné l'état r au sommet de la pile, empiler X puis δ(r, X), et ajouter X → α•.
• Si table[q, c] = accepter, alors retourner SUCCÈS.
• Sinon, retourner ÉCHEC.

Exemple d'analyse LR(0)

  Mot analysé : id + id * id$
  Pile : 0
  Actions :
    1. décaler 4 : pile = 0id
    2. réduire F → id : pile = 0F
    3. réduire T → F : pile = 0T
    4. réduire E → T : pile = 0E
    5. décaler 5 : pile = 0E+
    6. décaler 4 : pile = 0E+id
    7. réduire F → id : pile = 0E+F
    8. réduire T → F : pile = 0E+T
    9. réduire E → E + T : pile = 0E
    10. décaler 6 : pile = 0ET*
    11. décaler 4 : pile = 0ET*id
    12. réduire F → id : pile = 0ET*F
    13. réduire T → T * F : pile = 0ET
    14. réduire E → E + T : pile = 0E
    15. décaler 7 : pile = 0E$
    16. accepter : SUCCÈS
  

Grammaire SLR

On parle d'analyse SLR lorsqu'on utilise les ensembles Suivant pour déterminer si une action réduire est possible ou non.

Une grammaire est dite SLR si tous les conflits peuvent être tranchés par l'examen des ensembles Suivant.

Exemple de grammaire SLR

  init → E
  E → E + T | T
  T → T * F | F
  F → id
  

Suivant :

  Suivant(init) = {$}
  Suivant(E) = {$ + ∗}
  Suivant(T) = {$ + ∗}
  Suivant(F) = {$ + ∗ id}
  

Construction de la Table d'Analyse SLR

La table a en ligne les états de l'automate et en colonne le marqueur $, les terminaux et les variables de la grammaire.

Pour chaque état I de l'automate :

• Pour chaque transition Ia → J étiquetée par un terminal a, ajouter l'action décaler J à l'entrée table[I, a].
• Pour chaque transition IX → J étiquetée par une variable X, enregistrer J à l'entrée table[I, X].

Pour chaque état d'acceptation I de