Compilation : 4. Grammaires et analyse LL(1)

Décrire une syntaxe

Une grammaire hors contexte G = (N,T,P,S) distingue non-terminaux N, terminaux T, productions P et axiome S. Chaque production a un seul non-terminal à gauche. Le langage contient les suites de terminaux dérivables de S. Une dérivation gauche réécrit à chaque étape le non-terminal le plus à gauche.

S → a S b | ε
S ⇒ a S b ⇒ a a S b b ⇒ a a b b

Cette grammaire engendre {aⁿbⁿ | n ≥ 0}. Un arbre de dérivation représente les productions ; un arbre abstrait peut omettre des détails comme les parenthèses et certains non-terminaux.

Préparer la grammaire

Une grammaire est ambiguë si un même mot possède deux arbres de dérivation distincts. E → E+E | E*E | id est ambiguë : id+id*id autorise (id+id)*id et id+(id*id). Introduire les niveaux E, T, F impose la priorité de * sur +.

Récursion gauche immédiate : A → A α | β
Transformation (α non vide) : A → β R ; R → α R | ε
Factorisation : A → u v | u w devient A → u R ; R → v | w

La suppression de récursion gauche immédiate ne traite pas à elle seule les cycles indirects. La factorisation ne garantit pas LL(1). Pour réduire une grammaire, supprimer d’abord les non-terminaux improductifs, puis les inaccessibles. Pour supprimer les ε-productions, calculer les symboles annulables et ajouter les variantes où ils sont omis ; préserver ε avec un nouvel axiome si nécessaire.

Calculer PREMIER et SUIVANT

• PREMIER(α) contient les terminaux qui peuvent commencer un mot dérivé de α, et ε si α est annulable. Parcourir la séquence tant que ses symboles sont annulables.
• Ajouter $ à SUIVANT(S). Pour A → α B β, ajouter PREMIER(β) privé de ε à SUIVANT(B). Si β est annulable, ajouter aussi SUIVANT(A).
• Répéter jusqu’à stabilisation. ε ne figure jamais dans un ensemble SUIVANT.

E → T E′
E′ → + T E′ | ε
T → F T′
T′ → * F T′ | ε
F → ( E ) | id

Construire et utiliser la table

Pour A → α, placer la production en M[A,a] pour chaque a de PREMIER(α) privé de ε. Si α est annulable, la placer aussi pour chaque symbole de SUIVANT(A). La grammaire est LL(1) si aucune cellule ne possède plusieurs productions. LL(1) signifie lecture de gauche à droite, dérivation gauche et un token de prévision.

Un terminal en sommet doit égaler le token courant. Un non-terminal est remplacé par la partie droite de la production choisie, placée en ordre inverse sur la pile. ε n’empile rien ; une cellule vide signale une erreur. Accepter seulement quand la pile et l’entrée atteignent toutes deux $.