Analyse LR - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
En informatique, un analyseur LR (pour Left to right, Rightmost derivation) est un analyseur pour les grammaires non contextuelles qui lit l'entrée de gauche à droite et produit une dérivation droite. On parle aussi d'analyseur LR(k) où k représente le nombre de symboles "anticipés" et non consommés qui sont utilisés pour prendre des décisions d'analyse syntaxique. D'habitude, k vaut 1 et est souvent omis. Une grammaire non contextuelle est appelée LR(k) s'il existe un analyseur syntaxique LR(k) pour elle.
On dit qu'un analyseur syntaxique LR réalise une analyse ascendante car il essaye de déduire les productions du niveau du haut de la grammaire en les construisant à partir des feuilles.
De nombreux langages de programmation sont décrits par des grammaires LR(1), ou du même genre, et, pour cette raison, les analyseurs syntaxiques LR sont souvent utilisés par les compilateurs pour faire l'analyse syntaxique de code source.
Typiquement, quand on se réfère à un analyseur syntaxique LR, on parle d'un analyseur syntaxique capable de reconnaître un langage particulier spécifié par une grammaire non contextuelle. Cependant, dans l'usage courant, on utilise le terme pour parler d'un programme pilote qui peut être appelé avec une certaine table et qui produit un large éventail d'analyseurs syntaxiques LR différents. On devrait plutôt appeler ces programmes générateurs d'analyseurs syntaxiques.
L'analyse syntaxique LR a plusieurs avantages :
- De nombreux langages de programmation peuvent être analysés en utilisant une variante d'analyseur syntaxique LR. Une exception notable est C++.
- Les analyseurs syntaxiques LR peuvent être implémentés très efficacement.
- De tous les analyseurs syntaxiques qui parcourent leur entrée de gauche à droite, les parseurs LR détectent les erreurs de syntaxe (c'est-à-dire quand les entrées ne sont pas conformes à la grammaire) le plus tôt possible.
Les analyseurs syntaxiques LR sont difficiles à produire à la main ; ils sont généralement construits par des générateurs d'analyse syntaxique ou des compilateurs de compilateurs. Suivant la manière dont la table d'analyse syntaxique est générée, ces analyseurs syntaxiques sont appelés analyseurs syntaxiques LR simples (SLR pour "Simple LR parser"), analyseurs syntaxiques LR avec anticipation (LALR pour "Look-Ahead LR parser"), et analyseurs syntaxiques canoniques. Ces types d'analyseurs syntaxiques peuvent traiter des ensembles de grammaires de plus en plus grands ; les analyseurs syntaxiques LALR peuvent traiter plus de grammaires que les SLR. Les analyseurs syntaxiques canoniques fonctionnent sur davantage de grammaires que les analyseurs syntaxiques LALR. Le très connu Yacc produit des analyseurs syntaxiques LALR.
Architecture des analyseurs syntaxiques LR
Conceptuellement, un analyseur syntaxique LR est un programme récursif qui peut être prouvé correct par calcul direct, et qui peut être implémenté efficacement par un analyseur syntaxique ascendant, lequel est un ensemble de fonctions mutuellement récursives, de la même manière qu'un analyseur syntaxique descendant. Cependant, par convention, les analyseurs syntaxiques LR sont présentés et implémentés par des machines à pile basées sur des tables, dans lesquelles la pile d'appels du programme récursif sous-jacent est manipulée explicitement.
Un analyseur syntaxique ascendant basé sur une table d'analyse syntaxique peut être représenté schématiquement par la figure 1. La suite montre une dérivation droite obtenue par cet analyseur syntaxique.
Cas général
L'analyseur syntaxique est une machine à états. Elle consiste en :
- un tampon d'entrée
- une pile dans laquelle est stockée la liste des états où elle est passée
- une table des branchements qui indique vers quel état elle doit aller
- une table des actions qui donne la règle de grammaire à appliquer en fonction de l'état courant et du terminal courant du flot d'entrée
L'algorithme d'analyse syntaxique
L'algorithme d'analyse syntaxique LR fonctionne comme suit :
- La pile est initialisée avec [0]. L'état courant sera toujours l'état qui se trouve en haut de la pile.
- En fonction de l'état courant et du terminal courant du flot d'entrée, une action est cherchée dans la table des actions. Quatre cas se présentent :
- un décalage (shift) sn :
- le terminal courant est retiré du flot d'entrée
- l'état n est mis sur la pile et devient l'état courant
- une réduction (reduce) rm :
- le nombre m est écrit dans le flot de sortie
- pour chaque symbole de la partie droite de la règle numéro m, un état est retiré de la pile
- en fonction de l'état qui est maintenant en haut de la pile et de la partie gauche de la règle m, un nouvel état est recherché dans la table des branchements, lequel est mis sur la pile et devient donc l'état courant
- une acceptation : la chaîne d'entrée est acceptée
- pas d'action : une erreur de syntaxe est rapportée
- un décalage (shift) sn :
- L'étape 2 est répétée jusqu'à ce que la chaîne soit acceptée ou qu'une erreur de syntaxe soit rapportée.
Exemple concret
Pour expliquer son fonctionnement, nous utiliserons la petite grammaire suivante dont le symbole de départ est E :
- (1) E → E * B
- (2) E → E + B
- (3) E → B
- (4) B → 0
- (5) B → 1
et nous analyserons l'entrée suivante :
- 1 + 1
Les tables des actions et des branchements
Les deux tables d'analyse syntaxique LR(0) de cette grammaire se présentent comme suit :
| état | action | branchement | ||||||
| * | + | 0 | 1 | $ | E | B | ||
| 0 | s1 | s2 | 3 | 4 | ||||
| 1 | r4 | r4 | r4 | r4 | r4 | |||
| 2 | r5 | r5 | r5 | r5 | r5 | |||
| 3 | s5 | s6 | acc | |||||
| 4 | r3 | r3 | r3 | r3 | r3 | |||
| 5 | s1 | s2 | 7 | |||||
| 6 | s1 | s2 | 8 | |||||
| 7 | r1 | r1 | r1 | r1 | r1 | |||
| 8 | r2 | r2 | r2 | r2 | r2 | |||
La table des actions est indexée par l'état de l'analyseur syntaxique et par un terminal (dont le terminal spécial $ qui indique la fin du flot d'entrée). Elle contient trois types d'actions :
- décalage (shift), qui est écrite 'sn' et qui indique que l'état suivant est n
- reduction (reduce), qui est écrite 'rm' et qui indique qu'il faut faire une réduction par la règle de grammaire numéro m
- acceptation, qui est écrite 'acc' et qui indique que l'analyseur syntaxique accepte la chaîne du flot d'entrée.
La table des branchements est indexée par l'état de l'analyseur syntaxique et par un non-terminal. Elle indique quel est l'état suivant de l'analyseur syntaxique s'il a effectivement reconnu ce non-terminal.
Procédure d'analyse syntaxique
La table ci-dessous illustre chaque étape du processus. Dans cette table, l'état représente l'élément en haut de la pile (l'élément le plus à droite), et l'action suivante est déterminée en se référant à la table des actions ci-dessus. Un $ est ajouté au bout de la chaîne d'entrée pour indiquer la fin du flot.
| État | Flot d'entrée | Flot de sortie | Pile | Action suivante |
|---|---|---|---|---|
| 0 | 1+1$ | [0] | Décalage 2 | |
| 2 | +1$ | [0,2] | Réduction 5 | |
| 4 | +1$ | 5 | [0,4] | Réduction 3 |
| 3 | +1$ | 5,3 | [0,3] | Décalage 6 |
| 6 | 1$ | 5,3 | [0,3,6] | Décalage 2 |
| 2 | $ | 5,3 | [0,3,6,2] | Réduction 5 |
| 8 | $ | 5,3,5 | [0,3,6,8] | Réduction 2 |
| 3 | $ | 5,3,5,2 | [0,3] | Acceptation |
Description
Quand l'analyseur syntaxique démarre, il part toujours avec l'état 0 dans la pile :
- [0]
Le premier terminal que l'analyseur syntaxique voit est le '1'. D'après la table des actions, il doit aller à l'état 2. Ce qui donne pour la pile :
- [0 '1' 2]
Le haut de la pile se trouve sur la partie droite. (pour une meilleure compréhension, nous montrons également le symbole (par exemple '1', ou B) qui est à l'origine de la transition vers le nouvel état bien que, strictement parlant, il ne fait pas partie de la pile.)
Dans l'état 2, la table des actions dit que quel que soit le terminal suivant, dans le flot d'entrée, il faut faire une réduction par la règle de grammaire numéro 5. Si la table est correcte, cela signifie que l'analyseur syntaxique vient juste de reconnaître la partie droite de la règle numéro 5, ce qui est effectivement le cas.
Donc dans ce cas, nous écrivons 5 dans le flot de sortie, retirons un état de la pile, et y ajoutons à la place l'état correspondant à la table des branchements pour l'état 0 et le non-terminal B, c'est-à-dire l'état 4. La pile résultante est :
- [0 B 4]
Cependant, dans l'état 4, la table des actions dit que nous devons maintenant faire une réduction par la règle 3. Donc, nous écrivons 3 sur le flot de sortie, enlevons un état de la pile, et trouvons le nouvel état dans la pile des branchements pour l'état 0 et le non-terminal E, ce qui donne l'état 3. La pile est maintenant :
- [0 E 3]
Le terminal suivant que l'analyseur syntaxique voit dans le flot d'entrée est un '+'. D'après la table des actions, il doit aller vers l'état 6 :
- [0 E 3 '+' 6]
La pile résultante peut être interprétée comme l'historique d'un automate fini qui vient juste de lire un non-terminal E suivi par un terminal '+'. La table de transition de cet automate est définie par les actions de décalages dans la table des actions ainsi que par les actions de branchements dans la table des branchements.
Le terminal suivant est maintenant '1'. Cela signifie que nous faisons un décalage et allons à l'état 2 :
- [0 E 3 '+' 6 '1' 2]
Tout comme le '1' précédent, celui-ci est réduit vers B, ce qui donne la pile suivante :
- [0 E 3 '+' 6 B 8]
La pile correspond à une liste d'états d'un automate fini qui a lu un non-terminal E suivi d'un '+' et d'un non-terminal B. Dans l'état 8, nous faisons toujours une réduction par la règle 2. Les trois états du haut de la pile correspondent avec les trois symboles de la partie droite de la règle 2.
Au bout du compte, nous lisons un '$' sur le flot d'entrée qui signifie, d'après la table des actions (l'état courant étant 3), que l'analyseur syntaxique accepte la chaîne d'entrée.
Les numéros des règles qui ont été écrites sur le flot de sortie sont [5, 3, 5, 2] ce qui est effectivement une dérivation droite de la chaîne "1 + 1" à l'envers.
- [0 E 3]
