Analyseur LR

Pour expliquer comment procède un analyseur grammatical LR, nous utiliserons la petite grammaire constituées des règles (1) à (5) ci-dessous, en supposant que le symbole de départ est E. Pour rappel, dans des règles telles que ci-dessous, les majuscules désignent des symboles non terminaux ; les autres symboles (les minuscules, la ponctuation, les chiffres) désignent des symboles terminaux. Les symboles terminaux sont les unités syntaxiques insécables à partir desquelles le texte donné en entrée de l'analyseur est construit. Ces entités sont fournies à notre analyseur grammatical LR par un autre analyseur, dit analyseur lexical (que nous ne traitons pas ici) qui a pour fonction de découper le texte donné en entrée en une séquence de symboles terminaux. Le flot de traitement est donc le suivant: le texte donné en entrée est découpé en symboles terminaux par l'analyseur lexical (lexer en anglais) lequel envoie ces symboles à l'analyseur LR que nous nous proposons d'étudier. Pour simplifier la présentation nous supposerons que les symboles terminaux produits en sortie du lexer sont disponibles dans une mémoire tampon (dit buffer). Pour l'exemple ci-dessous les terminaux sont les symboles +, *, - , 0, 1. Au contraire des symboles terminaux, les symboles non terminaux dénotent des séquences de symboles (terminaux ou non). Ces séquences sont définies au travers de règles non contextuelles (comme les suivantes) qui, ensemble, forment une grammaire:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Les règles (4) (5) signifient que B peut être un 0 ou 1. La règle E → E + B signifie qu'un E peut être une séquence de la forme E + B. On peut noter le caractère récursif de cette règle. Le symbole E intervient dans sa propre définition. D'une façon générale il y a récursion quand un symbole non terminal est à la fois à gauche et à droite d'une règle. Une grammaire (un ensemble de règles) peut être donc être mal formée s'il y a circularité. Typiquement une règle E → E induit une circularité, ou bien par exemple E → F avec F → E. Dans notre exemple il n'y a pas circularité problématique car E peut être de la forme B et lui-même de la forme 0 ou 1, ce qui permet de sortir de la boucle.

Nous allons nous intéresser à savoir si l'entrée 1+1 est bien une instance de notre grammaire en utilisant une approche de type LR.

Pour procéder selon cette approche LR, d'abord nous ajoutons à la grammaire la règle (0) ci-dessous pour formaliser que le départ de la grammaire est E.

(0) ACCEPT → E$

On obtient ainsi une grammaire enrichie. Noter que les symboles ACCEPT et $ sont des symboles génériques (non spécifiques à notre grammaire). Le symbole $ est un symbole de fin de chaîne (pour les programmeurs: il s'agit du fameux EOF .. End Of File). Quant au symbole ACCEPT il est introduit de manière à pouvoir conclure de façon automatique le processus de reconnaissance. Dans la littérature, comme dans l'exposé du cas général plus bas, le symbole ACCEPT est souvent appelé S (pour Start).

La règle (0) permet donc à la fois de formaliser que E est le vrai symbole de départ et aussi de fonder le critère final d'acceptation qui est: à la fin de l'analyse la pile de l'analyseur doit ne contenir que ACCEPT et le buffer contenant la chaîne à analyser doit être vide (ceci sera illustré plus bas).

Finalement se demander si la chaîne 1+1 est une dérivation de la grammaire constituée des règles (1) à (5), avec E comme symbole de départ, revient à se demander si la chaîne 1+1$ est une dérivation de la grammaire enrichie constituée des règles (0) à (5) mais avec ACCEPT comme symbole de départ.

Donc notre analyseur LR utilise une pile (stack en anglais) qui obéit donc à une logique LIFO (Last In First Out). Il utilise aussi un buffer contenant les symboles terminaux de la chaîne à analyser. Au départ la pile de l'analyseur est vide et son buffer contient l'entrée à analyser soit ici:

1+1$

Le symbole le plus à gauche du buffer (d'où le L pour Left dans la dénomination LR) est retiré du buffer. Ici ce symbole est 1. Ce symbole est placé dans la pile. La tête de lecture du buffer se positionne sur le symbole suivant, donc sur le symbole +. La pile se présente ainsi (dans cette représentation de pile on suppose que les symboles entrent par le haut):

Comme à chaque étape, l'analyseur regarde la pile comme un motif M formé par la suite de symboles présents dans la pile en partant du bas de pile vers le haut. Il cherche si un suffixe s de ce motif M est identique à la partie droite d'une règle N → s de la grammaire. Si c'est le cas cela signifie que le symbole non terminal N a été reconnu. L'analyseur effectue alors cette action: il dépile les symboles formant le suffixe s puis il empile N à la place. Ainsi on aura remplacé dans la pile tous les symboles de s par l'unique symbole N. Cet aspect ressortira plus clairement ci-dessous quand la pile contiendra davantage de symboles. On peut remarquer que cette opération, appelée réduction, s'effectue sur le ou les symboles du sommet de pile, c'est-à-dire sur le ou les dernier(s) symboles lu(s) / reconnu(s) ; c'est-à-dire sur la partie la plus à droite de la chaîne qui est en train d'être analysée. C'est en cela que la dérivation se fait le plus à droite (d'où le R pour Rightmost dans la dénomination LR).

Pour l'instant on peut voir que le motif de pile M se résume au seul symbole 1 qui est exactement la partie droite de la règle (5). Ce symbole 1 peut donc être vu comme une dérivation de B selon la règle (5). L'analyseur remplace le 1 par B dans la pile (plus exactement il dépile 1, partie droite de (5) et empile B partie gauche de (5)). Cette opération effectuée par l'analyseur s'appelle une réduction. Elle produit l'arbre d'analyse ci-contre. La pile devient:

Le motif B, en tant que partie droite de la règle (3), est une dérivation de E par (3). L'analyseur effectue encore une réduction en dépilant B puis en empilant E ainsi que spécifié par la règle (3). L'arbre d'analyse est donné par la figure ci-contre. La pile devient:

Le motif de pile, constitué du seul symbole E, ne contient pas de suffixe matchant avec la partie droite d'une règle. Il n'y a donc pas de réduction possible. L'analyseur retire alors un nouveau caractère du buffer, soit le symbole + (sur lequel se tenait la tête de lecture). Cette tête de lecture passe au symbole suivant, qui est le deuxième et dernier 1. La pile devient:

Ici le motif de pile est E+. Aucun suffixe de ce motif ne correspond à la partie droite d'une règle. Donc aucune réduction n'est possible. Dès lors un nouveau symbole, le dernier 1, est retiré du buffer et est empilé dans la pile. La tête de lecture du buffer se positionne sur $, symbole de fin. La pile devient:

Ici le motif de pile est E+1. Le seul suffixe de ce motif correspondant à une partie droite est, comme plus haut le suffixe constitué du seul symbole 1. C'est la partie droite de (3). Ce 1 est remplacé par B selon la même réduction.

Ici le motif est E+B. Or E+B est lui-même un suffixe de E+B. En tant que suffixe E+B est identique à la partie droite de (2). Ce suffixe (donc le motif complet ) est dépilé. L'analyseur dépile donc 3 symboles. Il empile à la place E, symbole gauche de la règle (2). La pile devient:

Comme ci-dessus le motif de pile constitué du seul symbole E ne contient pas de suffixe matchant avec une partie droite de règle. Il n'y a donc pas de réduction possible. L'analyseur retire du buffer le dernier symbole, soit $. Le buffer est maintenant vide. La pile est dans l'état suivant:

Le motif de pile est E$ qui est partie droite de la règle (0). L'analyseur réduit selon la règle (0):

Ici la pile ne contient que le symbole d'acceptation ACCEPT ; par ailleurs le buffer est vide. Cette situation signifie que notre fichier 1+1$ est bien de la forme E$ et que donc vérifie la grammaire enrichie. De ce fait la chaîne 1+1 est bien une dérivation des règles de la grammaire initiale constituée des règles (1) à (5). L'analyseur s'arrête en notifiant l'acceptation de la chaîne donnée en entrée.

Dans le chapitre qui suit l'approche LR que l'on vient de décrire est formalisée avec un automate. Au lieu d'empiler les symboles, ce sont, de manière équivalente, des états d'un automate qui sont placés dans la pile.

L'analyseur syntaxique est une machine à états. Elle consiste en :

• un tampon d'entrée ;
• une pile dans laquelle sont stockés des états (le calcul de ces états à partir de la grammaire est étudié plus loin) ;
• 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 LR fonctionne comme suit :

1. la pile est initialisée avec l'état initial 0. Elle est donc de la forme [0]. L'état courant sera toujours l'état qui se trouve en haut de la pile (situé à droite dans les illustrations),
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 :
   • cas 1, 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,
   • cas 2, 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,
   • cas 3, une acceptation : la chaîne d'entrée est acceptée,
   • cas 4, 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.

Les deux tables d'analyse syntaxique LR(0) de cette grammaire se présentent comme suit :

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 (et donc qu'il faut empiler 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.

D'après la table ci-dessus, si on est dans l'état 0 et que le symbole courant du buffer est le symbole terminal 1 alors il faut effectuer un shift vers l'état 2 ce qui signifie que l'état 2 est empilé sur la pile des états (et ainsi devient l'état courant). Dans le même temps le buffer passe au symbole suivant.

D'après cette table si on est dans l'état 4 alors, quel que soit le symbole courant du buffer, il faut effectuer une réduction selon la règle 3 (qui est E → B). Cela signifie que les derniers symboles lus correspondent à la séquence à droite de cette règle (séquence se réduisant ici à B) et donc que l'on vient de reconnaître le symbole de gauche (ici E). On doit alors dépiler de la pile des états autant d'états que de symboles présents à droite de la règle (ici un seul puisqu'il n'y a que B), ce qui conduit à obtenir un nouveau sommet de pile s qui est brièvement l'état courant. Mais aussitôt l'analyseur doit considérer qu'il a reconnu le symbole de gauche de la règle, soit ici E. L'analyseur doit alors utiliser la table de branchement pour se positionner dans l'état indiqué à la ligne s et selon la colonne E de la table de branchement. Par exemple, si s est l'état 0, la table de branchement indique l'état 3 pour le couple (0,E). L'état 3 est alors aussitôt empilé et devient l'état courant (tout se passe comme si E avait été un symbole ajouté momentanément devant dans le buffer et aussitôt consommé).

La table ci-dessous illustre chaque étape du processus pour l'analyse de l'expression: 1+1$. 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/branchements ci-dessus. Un $ est ajouté au bout de la chaîne d'entrée pour indiquer la fin du flot.

Construction de l'arbre de dérivation, des feuilles à la racine.

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 2 ]

Le haut de la pile, qui est l'état courant de l'analyseur, se trouve sur la droite, donc ici il s'agit de 2. Pour une meilleure compréhension adjoignons aux états de la pile, entre parenthèses et en italique, la partie de l'arbre de dérivation qui lui est attachée. Cela donne la notation suivante pour la même pile:

[ 0() 2(1) ]

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. 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. Le sommet de pile devient 0 et l'on vient de reconnaître un B. L'analyseur applique aussitôt la table de branchement. Pour le couple (0,B) celle-ci indique alors l'état 4. Cet état est empilé, comme si nous venions de lire un B depuis 0. La pile qui résulte de ces opérations est :

[0() 4(B -1) ]

Dans l'état 4, la table des actions indique qu'il faut faire une réduction par la règle 3 (pour le suivi, le numéro de cette règle, 3, est produit sur le flot de sortie). L'analyseur enlève de la pile autant d'états que de symboles présents à droite de la règle de réduction. Donc ici un seul puisque la règle 3 n'a qu'un seul symbole à droite. Le nouveau sommet de pile devient temporairement l'état 0. L'analyseur utilise aussitôt la partie "branchements" de la table. Pour l'état 0 et le symbole E qui vient d'être reconnu, il est indiqué que l'état où se positionner est l'état 3. Cet état est empilé (comme pour un shift) et devient le nouvel état courant :

[0() 3(E - B -1) ]

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() 3(E - B -1) 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() 3(E - B -1) 6(+) 2(1) ]

Tout comme le '1' précédent, celui-ci est réduit vers B ; mais le branchement pour le couple (6,B) est 8 ; cet état est empilé, ce qui donne la pile suivante :

[0() 3(E - B -1) 6(+) 8(B-1) ]

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 une réduction par la règle 2. Celle-ci comporte trois symboles à droite. On dépile les trois états du haut de la pile qui correspondent aux trois symboles de la partie droite de la règle 2. Le sommet de pile est temporairement 0. Aussi on vient de reconnaître la partie gauche de la règle 2, soit un E. La table de branchement pour le couple (0,E) indique l'état 3. Celui-ci est empilé, la pile devient:

[0() 3((E - B -1) + (B-1)) ]

Au bout du compte, le symbole '

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, ce point spécial représentant un état possible de l'analyseur (une situation courante possible). Par exemple, pour la règle E → E + B on peut avoir les quatre items (situations) suivantes :

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Chaque item représente un état (une situation) 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 s'attend à lire le symbole terminal + suivi d'une autre chaîne correspondant au non-terminal B.

Un item comme E → E + B • où le marqueur • est situé tout à droite de la partie droite de la règle, signifie que toute la partie droite a été reconnue comme une dérivation du symbole de gauche. Un tel item commande donc de faire une réduction.

Les règles de la forme A → ε ont un seul item A → •. En effet, puisque ε désigne une chaîne vide, il suit que •ε est équivalent à ε• qui est équivalent à •.

Il n'est pas toujours possible de caractériser l'état courant de l'analyseur syntaxique avec un seul item. Dans notre exemple, après la lecture d'une chaîne correspondant à un E, il y a bien deux situations possibles représentées par les items: E → E • * B et E → E • + B.

Par conséquent, on caractérisera l'état de l'analyseur non par un seul item mais par un ensemble d'items.

Pour notre exemple, après avoir reconnu E, l'état courant est l'ensemble { E → E • + B, E → E • * B } qui indique que l'analyseur est en situation de lire le symbole + ou bien le symbole *.

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. En d'autres termes on ajoute des items jusqu'à atteindre un point fixe (tout ajout selon la règle ci-dessus laisse l'ensemble inchangé). L'extension minimale (le point fixe minimal) est appelée la fermeture d'un ensemble d'items et on l'écrira ferm(I) où I est un ensemble d'items. On verra plus bas qu'un état de l'analyseur syntaxique d'une grammaire est une fermeture d'items. Seules les fermetures accessibles depuis l'état initial (la fermeture initiale) seront considérées dans la table des actions et branchements. L'état initial est introduit par l'ajout d'une règle générique ainsi que décrit dans le chapitre qui suit.

Afin de disposer d'une fermeture initiale constituant l'état initial de l'analyseur, 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.

La première étape de la construction d'une table des actions et branchements consiste à déterminer les états (ensembles d'items fermés) ainsi que les transitions entre ces états de l'automate de l'analyseur. La méthode consiste à déterminer l'état initial de cet automate, puis à calculer de proche en proche tous les états accessibles. Les transitions sont déterminées comme si cet automate pouvait lire des terminaux et des non-terminaux.

État initial. 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 (Ensemble d'items 0), on déterminera tous les états qui peuvent être atteints par une transition (successeurs). On obtient alors un nouvel ensemble d'états duquel on repart pour déterminer de nouveaux successeurs. Ceci est répété jusqu'à l'obtention d'un point fixe (qui est forcément atteint puisque le nombre de fermeture est fini). Détaillons le processus de calcul des transitions et des successeurs.

Calcul d'une transition de l'état successeur.

Les transitions possibles à partir d'un ensemble d'items Q peuvent être trouvées en regardant, dans cet ensemble d'items, les symboles (terminaux et non-terminaux) qui se trouvent juste après le point. S'il existe un tel symbole, disons x, pour trouver l'état (ensemble d'items) auquel conduit le symbole x à partir de l'état Q on procède comme suit :

1. Prendre l'ensemble I de tous les items de Q où il y a un point juste à gauche de ce symbole x
2. Créer l'ensemble I' en déplaçant, pour chaque item i de I, le point à droite du symbole x
3. Ajouter l'ensemble I'' = ferm( I' ) comme état de l'automate
4. Ajouter I – x → I'' comme transition de l'automate

Dans le cas de l'ensemble d'items 0, les symboles se trouvant juste après le point sont les terminaux '0' et '1' et les non-terminaux E et B. Les transitions qui en découlent sont les suivantes ...

Pour le terminal '0', la transition atteint l'état successeur:

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 puisse être trouvé. À partir des ensembles d'items 1, 2 et 4, il n'y aura pas de transitions puisque aucun point ne se trouve devant un symbole. En revanche pour l'ensemble d'items 3, on voit que le point se trouve devant les terminaux '*' et '+'. À partir de ensembles d'items 3 (ou état 3), pour le symbole '*', la transition conduit à l'état 5:

Ensemble d'items 5

E → E * • B

+ B → • 0

+ B → • 1

et pour '+' elle mène à l'état 6:

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, on a atteint un point fixe. La table de transitions pour l'automate ressemble maintenant à :

À 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 '