En informatique théorique, un analyseur LR (en anglais : ) est un analyseur pour les grammaires non contextuelles qui lit l'entrée de gauche à droite (d'où le L de Left to right) et produit une dérivation droite (d'où la dénomination Rightmost qui signifie que les motifs spécifiés par la grammaire sont recherchés parmi les suffixes de la séquence de mots lue, donc sur la partie la plus à droite de cette séquence). Comme tout analyseur grammatical (ou analyseur syntaxique), un analyseur LR vise à vérifier si une chaîne de caractères (typiquement contenue dans un fichier) possède bien la structure d'une grammaire spécifiée à l'avance. Cette vérification s'accompagne généralement d'actions. Une action typique est la génération d'une autre chaîne de caractères ou encore d'un arbre d'analyse. Ainsi l'analyse grammaticale est généralement utilisée pour la compilation (transformation d'un code source en code machine). Cette analyse a été inventée en 1965 par Donald Knuth (l'auteur du célèbre ouvrage: The art of programming). On parle aussi d'analyseur LR(k) où k représente le nombre de symboles « anticipés » (examinés dans la chaîne analysée sans être consommés) qui sont utilisés pour prendre des décisions d'analyse syntaxique. Comme usuellement k vaut 1, il 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.
Bien que la confusion soit fréquente, on ne doit pas confondre un analyseur LR avec un générateur d'analyseurs LR. Par exemple l'outil Yacc qui vient d'être cité n'est pas un analyseur LR à proprement parler mais bien un générateur d'analyseurs LR. Les deux notions se distinguent par leurs entrées-sorties. Un générateur d'analyseurs LR prend en entrée une grammaire et produit le code source de l'analyseur LR pour cette grammaire (et/ou des alertes/erreurs portant sur l’ambiguïté intrinsèque de la grammaire donnée en entrée). Tandis qu'un analyseur LR proprement dit prend en entrée une chaîne de caractères et produit en sortie un verdict (portant sur la conformité de cette chaîne à la grammaire ayant servi à produire cet analyseur) et éventuellement un produit de génération (un arbre d'analyse, une autre chaîne).
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
Exemple Introductif
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.
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): [ 1 ] 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).
alt=|vignette|82x82px 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: [ B ] vignette|103x103px 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: [ E ]
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: [ + ][ E ]