Analyseur LR

En informatique théorique, un analyseur LR (en anglais : Left to right, Rightmost derivation) 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...