Analyse LR

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

Figure 1. Architecture d'un analyseur syntaxique ascendant basé sur une table ("input" = "entrée", "stack" = "pile", "parser" = "analyseur syntaxique", "output" = "sortie", "action table" = "table des actions", "goto table" = "table des branchements").

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 :

1. La pile est initialisée avec [0]. L'état courant sera toujours l'état qui se trouve en haut de la pile.
2. 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
3. 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]

Construire des tables d'analyse syntaxique LR(0)

Items

La construction de ces tables d'analyse syntaxique est basée sur la notion d'items LR(0) (simplement appelés items ici) qui sont des règles de grammaire avec un point spécial ajouté quelque part dans la partie droite. Par exemple, la règle E → E + B a quatre items correspondants :

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Les règles de la forme A → ε ont un seul item A → •. Ces règles seront utilisées pour indiquer l'état de l'analyseur syntaxique. L'item E → E • + B, par exemple, indique que l'analyseur syntaxique a reconnu une chaîne correspondant à E sur le flot d'entrée, et qu'il attend un '+' suivi d'une autre chaîne correspondant à B.

Ensemble d'items

Il n'est pas toujours possible de caractériser l'état de l'analyseur syntaxique avec un seul item. En effet, il peut arriver qu'on ne sache pas d'avance quelle règle va être utilisée pour la réduction. Dans notre exemple, après la lecture d'une chaîne correspondant à un E, il y a deux items candidats à la réduction : E → E • * B et E → E • + B. Par conséquent, on caractérisera l'état par un ensemble d'items, c'est-à-dire { E → E • + B, E → E • * B } dans ce cas.

Fermeture des ensembles d'items

Un item avec un point devant un non-terminal, tel que E → E + • B, indique que l'analyseur syntaxique s'attend à trouver ce non-terminal (en l'occurrence B, dans cet exemple). Pour s'assurer que l'ensemble d'items contient toutes les règles possibles, l'analyseur syntaxique doit inclure tous les items décrivant comment ce non-terminal B sera analysé. Cela signifie que s'il y a des règles telles que B → 0 et B → 1, l'ensemble d'items doit aussi inclure B → • 0 et B → • 1. De manière générale, cela peut être formulé ainsi :

S'il y a un item de la forme A → v•Bw dans l'ensemble d'items, et s'il y a une règle de la forme B → w' alors l'item B → • w' doit également se trouver dans l'ensemble d'items.

Tous les ensembles d'items peuvent être étendus jusqu'à ce qu'ils satisfassent cette règle : continuer simplement d'ajouter les items appropriés jusqu'à ce que tous les non-terminaux précédés par des points soient pris en compte. L'extension minimale est appelée la fermeture d'un ensemble d'items et on l'écrira ferm(I) où I est un ensemble d'items. Ce sont ces ensembles d'items fermés qui seront considérés dans les états de l'analyseur syntaxique, bien que seuls ceux qui sont réellement accessibles à partir de l'état initial seront inclus dans les tables.

La grammaire augmentée

Avant de commencer à déterminer les transitions entre les différents états, la grammaire est augmentée de la règle suivante :

(0) S → E

où S est le nouveau symbole de départ et E l'ancien. L'analyseur syntaxique utilisera cette règle pour la réduction exactement quand il aura accepté la chaîne d'entrée.

Pour notre exemple, nous prendrons la même grammaire avec cette augmentation. Soit :

(0) S → E

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

C'est avec cette grammaire augmentée que nous déterminerons les ensembles d'items et les transitions entre eux.

Trouver les ensembles d'items accessibles et les transitions entre elles

La première étape de la construction des tables consiste à déterminer la transition entre les ensembles d'items fermés. Ces transitions seront déterminées comme si on considérait un automate fini qui pourrait lire des terminaux et des non-terminaux. L'état initial de cet automate est la fermeture du premier item de la règle ajoutée : S → • E :

Ensemble d'items 0

S → • E

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

Le '+' devant les items indique ceux qui ont été ajoutés pour la fermeture. Les items originaux sans '+' sont appelés le noyau de l'ensemble d'items.

En partant de l'état initial (S0), on déterminera tous les états qui peuvent être atteints en une étape. Les transitions possibles pour un ensemble d'items peuvent être trouvés en regardant les symboles (terminaux et non-terminaux) qui se trouvent juste après le point. Dans le cas de l'ensemble d'items 0, ce sont les terminaux '0' et '1' et les non-terminaux E et B. Pour trouver l'ensemble d'items auxquels conduit un symbole x, on suit la procédure suivante :

1. Prendre l'ensemble S de tous les items où il y a un point en face de ce symbole x.
2. Pour chaque item dans S, déplacer le point à la droite de x.
3. Compléter par fermeture l'ensemble des items.

Pour le terminal '0', le résultat est :

Ensemble d'items 1

B → 0 •

et pour le terminal '1' :

Ensemble d'items 2

B → 1 •

Pour le non-terminal E :

Ensemble d'items 3

S → E •

E → E • * B

E → E • + B

et pour le non-terminal B :

Ensemble d'items 4

E → B •

La fermeture n'ajoute pas de nouveaux items dans tous les cas. On continue la procédure jusqu'à ce qu'aucun autre ensemble d'items peut être trouvé. Pour les ensembles d'items 1, 2 et 4, il n'y aura pas de transition puisqu'aucun point ne se trouve devant un symbole. Pour l'ensemble d'items 3, on voit que le point se trouve devant les terminaux '*' et '+'. Pour '*', la transition donne :

Ensemble d'items 5

E → E * • B

+ B → • 0

+ B → • 1

et pour '+' elle donne :

Ensemble d'items 6

E → E + • B

+ B → • 0

+ B → • 1

Pour l'ensemble d'items 5, on doit considérer les terminaux '0' et '1' et le non-terminal B. Pour les terminaux, on voit que les ensembles d'items fermés sont égaux respectivement aux ensembles d'items 1 et 2 déjà construits. Pour le non-terminal B, la transition donne :

Ensemble d'items 7

E → E * B •

Pour l'ensemble d'items 6, il faut également considérer les terminaux '0' et '1' et le non-terminal B. Comme précédemment, les ensembles d'items résultats pour les terminaux sont égaux aux ensembles d'items 1 et 2 déjà construits. Pour le non-terminal B, la transition conduit à :

Ensemble d'items 8

E → E + B •

Ces ensembles d'items 7 et 8 n'ont pas de symboles derrière leurs points et, donc, c'est fini. La table de transitions pour l'automate ressemble maintenant à :

Ensemble d'items	*	+	0	1	E	B
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

Construire la table des actions et la table des branchements

À partir de cette table et de ces ensembles d'items, on construit la table des actions et la table des branchements de la manière suivante :

1. les colonnes des non-terminaux sont copiées dans la table des branchements
2. les colonnes des terminaux sont copiées dans la table des actions en tant qu'actions de décalage
3. une colonne supplémentaire est ajoutée pour '$' (fin de l'entrée) dans la table des actions, et chaque ensemble d'items qui contient S → E •, on y met un 'acc'.
4. si un ensemble d'items i contient un item de la forme A → w • où A → w est la règle numéro m avec m > 0, alors la ligne de l'état i dans la table des actions est remplie complètement avec la réduction rm.

Le lecteur peut vérifier que cela donne effectivement la table des actions et la table des branchements qu'on a vues plus tôt.

Note au sujet de LR(0) par rapport à SLR et LALR

Seule l'étape 4 dans la procédure ci-dessus produit des actions de réduction, et donc toutes les actions de réductions occupent des lignes entières de la table, ce qui fait que les réductions arrivent indépendamment du symbole suivant du flot d'entrée. C'est la raison pour laquelle ce sont les tables d'analyse syntaxique LR(0) : elles ne font aucune anticipation (c'est-à-dire qu'elles ne regardent aucun symbole d'avance) pour décider quelle réduction faire.

Une grammaire qui a besoin d'anticipation pour désambiguïser les réductions aurait besoin de lignes de la table d'analyse syntaxique contenant différentes actions de réductions dans les différentes colonnes, et la procédure ci-dessus n'est pas capable de créer de telles lignes.

Des raffinements de la procédure de construction de la table LR(0) (tels que SLR et LALR) peuvent construire des actions de réductions qui n'occupent pas des lignes entières. Ils peuvent donc analyser plus de grammaires que les analyseurs syntaxiques LR(0).

Conflits dans les tables construites

L'automate est construit d'une manière telle qu'il n'est pas garanti d'être déterministe. Cependant, quand les actions de réductions sont ajoutées dans la table des actions, il peut arriver qu'une cellule contienne déjà une action de décalage (conflit décalage-réduction) ou une action de réduction (conflit réduction-réduction). Cependant, on peut prouver que cela n'arrive que dans les grammaires qui ne sont pas LR(0).

Conflit décalage/réduction

Un petit exemple d'une grammaire non-LR(0) avec un conflit décalage-réduction est :

(1) E → 1 E

(2) E → 1

Parmi les ensembles d'items, on trouve celui-ci :

Ensemble d'items 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Il y a un conflit décalage-réduction dans cet ensemble d'items parce que dans la cellule de la table des actions correspondant à cet ensemble d'items et au terminal '1', il y aura en même temps une action de décalage vers l'état 1 et une action de réduction par la règle 2.

Conflit réduction/réduction

Un petit exemple d'une grammaire non-LR(0) avec un conflit réduction-réduction est :

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

Dans ce cas, on obtient l'ensemble d'items suivant :

Ensemble d'items 1

A → 1 •

B → 1 •

Il y a un conflit réduction-réduction pour cet ensemble d'items parce que dans les cellules de la table des actions pour cet ensemble d'items, il y aurait en même temps une réduction par la règle 3 et une autre par la règle 4.

Résolution

Les deux exemples ci-dessus peuvent être résolus en permettant à l'analyseur syntaxique d'utiliser un ensemble de suites (voir l'analyse LL) d'un non-terminal A pour décider s'il va utiliser une des règles de A pour une réduction ; il n'utilisera la règle A → w pour une réduction que si le symbole qui suit dans le flot d'entrée est dans l'ensemble des suites de A. Cette solution conduit à ce qu'on appelle l'analyse LR simple (SLR).

Références

• Compilateurs : principes, techniques et outils, Alfred V. Aho, Ravi Sethi et Jeffrey D. Ullman.