Worldlex Wiki analyseur pour les langages informatiques. C'est une version simplifiée d'un analyseur LR canonique .
L'analyseur LALR a été inventé par Java [ que les grammaires de référence de nombreux langages ne soient pas LALR en raison de leur ambiguïté .
La thèse originale ne proposait aucun algorithme pour construire un tel analyseur syntaxique à partir d'une grammaire formelle. Les premiers algorithmes de génération d'analyseurs LALR ont été publiés en 1973 En 1982, DeRemer et Tom Pennello ont publié un algorithme générant des analyseurs LALR très économes en mémoire . Les analyseurs LALR peuvent être générés automatiquement à partir d'une grammaire par un générateur d'analyseurs LALR tel que Yacc ou GNU Bison . Le code généré automatiquement peut être complété par du code écrit manuellement afin d'accroître les performances de l'analyseur résultant.
Donald Knuth inventa l' analyseur LR ( de gauche à droite, dérivation la plus à droite ). Cet analyseur peut reconnaître tout langage déterministe hors contexte en temps linéaire. La dérivation la plus à droite exigeait une très grande quantité de mémoire, et la mise en œuvre d'un analyseur LR était impraticable en raison de la mémoire limitée des ordinateurs de l'époque. Pour pallier cette limitation, en 1969, Frank DeRemer proposa deux versions simplifiées de l'analyseur LR : l'analyseur LR à anticipation (LALR) et l' analyseur LR simple (SLR), qui nécessitaient beaucoup moins de mémoire, mais au prix d'une puissance de reconnaissance de langage moindre. L'analyseur LALR était l'alternative la plus performante. En 1977, des optimisations de mémoire pour l'analyseur LR furent inventées , mais celui-ci restait moins économe en mémoire que les alternatives simplifiées.En 1979, Frank DeRemer et analyse ascendante correcte en un seul parcours de gauche à droite du flux d'entrée, car il n'a pas besoin de retour arrière . Étant par définition un analyseur à anticipation, il utilise toujours une anticipation, règles de production . La simplification introduite par l'analyseur LALR consiste à fusionner les règles ayant des ensembles d'éléments de noyau identiques , car les assertions anticipées sont inconnues lors de la construction de l'état LR(0). Ceci réduit la puissance de l'analyseur, car l'ignorance des symboles d'assertion anticipée peut l'induire en erreur quant à la règle grammaticale à choisir ensuite, entraînant des conflits de réduction . Tous les conflits survenant lors de l'application d'un analyseur LALR(1) à une grammaire LR(1) non ambiguë sont des conflits de réduction. L'analyseur SLR(1) effectue une fusion supplémentaire, introduisant ainsi des conflits additionnels.
L'exemple standard d'une grammaire LR(1) qui ne peut pas être analysée avec l'analyseur LALR(1), présentant un tel conflit reduce/reduce, est :
S → un E c → un F d → b F c → b E d E → e F → e
Lors de la construction de la table LALR, deux états seront fusionnés en un seul, et il apparaîtra ultérieurement que les prédictions sont ambiguës. L'état concerné est :
E → e. {c,d} F → e. {c,d}Un analyseur LR(1) crée deux états distincts (avec des prédictions non conflictuelles), dont aucun n'est ambigu. Dans un analyseur LALR, cet état présente des actions conflictuelles (étant donné une prédiction c ou d, la réduction se fait vers E ou F), un « conflit de réduction ». La grammaire ci-dessus sera déclarée ambiguë par le générateur d'analyseur LALR et les conflits seront signalés.
Pour lever cette ambiguïté, on choisit E, car cette valeur précède F dans la grammaire. Cependant, l'analyseur syntaxique résultant ne pourra pas reconnaître la séquence d'entrée valide b e c, puisque la séquence ambiguë e cest réduite à (E → e) cE au lieu de la séquence correcte (F → e) c, or E b E cne figure pas dans la grammaire.
Analyseurs LL
Les analyseurs LALR( j ) sont incomparables aux analyseurs LL( k ) : pour tous j et k supérieurs à 0, il existe des grammaires LALR( j ) qui ne sont pas des grammaires LL( k ) et réciproquement. En fait, il est indécidable de déterminer si une grammaire LL(1) donnée est LALR( k ) pour tout j . 0" 
Selon la présence ou l'absence de dérivations vides, une grammaire LL(1) peut être égale à une grammaire SLR(1) ou LALR(1). Si la grammaire LL(1) ne possède aucune dérivation vide, elle est SLR(1) ; si tous les symboles ayant des dérivations vides possèdent des dérivations non vides, elle est LALR(1). Si la grammaire ne possède qu'une seule dérivation vide, elle peut être ou non LALR(1).