Compilation : 5. LR, sémantique et préparation aux examens

De la descente aux réductions

Un analyseur ascendant reconstruit une dérivation droite à l’envers. Il décale des tokens sur une pile puis réduit une partie droite β par son non-terminal A. Un item LR(0), tel que E → B · = F, indique la position atteinte dans une production. La fermeture ajoute B → · γ quand le point précède B ; GOTO déplace le point sur un symbole puis recalcule la fermeture.

Grammaire augmentée : Z → S ; S → a S | b
I0 : Z → · S ; S → · a S ; S → · b
GOTO(I0,a) : S → a · S ; S → · a S ; S → · b

Une collection canonique regroupe tous les ensembles d’items accessibles. Dans une table LR(0), les réductions terminées ne dépendent pas du prochain token. SLR(1) limite les réductions A → β aux symboles de SUIVANT(A). Des conflits peuvent subsister.

Reconnaître un conflit SLR(1)

E → B = F | F
F → B
B → + F | a

Un état contient : E → B · = F
                  F → B ·

Ici SUIVANT(F) = {=,$}. Sur =, le premier item demande un décalage et le second une réduction : conflit. La grammaire n’est pas SLR(1). Une grammaire non SLR(1) peut néanmoins engendrer un langage analysable autrement ; le conflit n’établit pas à lui seul une ambiguïté.

La page du premier examen donne les dix états LR(0), toutes les transitions et la table SLR candidate calculée.

Attributs et vérifications sémantiques

Un attribut synthétisé se calcule à partir des attributs des enfants et des informations locales de la production. Un attribut hérité peut dépendre du parent et de frères selon les dépendances autorisées. La table des symboles associe notamment un nom, une portée et un type à une déclaration.

E → E1 + T   : E.val = E1.val + T.val
E → T        : E.val = T.val
T → nombre   : T.val = nombre.val

Pour 3 + 4 : T.val = 4 ; E1.val = 3 ; E.val = 7

La vérification sémantique contrôle, par exemple, qu’une variable est déclarée avant utilisation et que les types sont compatibles. La traduction en code intermédiaire est une étape distincte, même si un compilateur peut organiser certaines opérations ensemble.

x = a + b * c
t1 = b * c
t2 = a + t1
x = t2

Méthode de révision

• Avant un calcul, écrire l’alphabet, l’axiome, les productions et la convention de pile.
• Pour LL(1), traiter les branches ε avec SUIVANT et donner une cellule précise en cas de conflit.
• Pour les automates, noter l’état initial, les états finaux, puis vérifier les cas ε et les mots courts.
• Pour LR, conserver une numérotation unique des états et des productions ; distinguer ACTION et GOTO.
• Pour chaque réponse, justifier le résultat par un invariant, une transition ou une dérivation.

Exemples de sujets d’examen

Terminez le cours en conditions chronométrées avec les quatre sujets du parcours. Le sujet 1 adapte le corrigé de 2023 ; les sujets 2 et 3 sont des créations pédagogiques ; le sujet 4 adapte les thèmes du sujet INF321 2024–2025. Chaque sujet propose un barème sur 20 et une correction repliable.