Outils pour utilisateurs

Outils du site


glossaire:lr

LR

Left-to-right, Rightmost-derivation with k symbols of lookahead

En informatique, un analyseur LR (LR Parser) 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.

Voir:

glossaire/lr.txt · Dernière modification: 19/05/2012 00:18 (modification externe)