Analyse LR - Définition

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).