Analyse LL

En informatique, l'analyse LL est une analyse syntaxique descendante pour certaines grammaires non contextuelles, dites grammaires LL. Elle analyse un mot d'entrée de gauche à droite (Left to right en anglais) et en construit une dérivation à gauche (Leftmost derivation en anglais). L'arbre syntaxique est construit depuis la racine puis en descendant dans l'arbre. L'analyse LL réalise une seule passe sur le mot d'entrée. Une analyse LL est appelée analyse LL(k) lorsqu'elle utilise une fenêtre de k lexèmes pour décider comment construire l'arbre syntaxique du mot d'entrée. Ce qui suit décrit une analyse descendante à dérivation à gauche fondée sur une table d'analyse. La notion de dérivation à gauche signifie que lors du processus d'application des règles c'est le non-terminal le plus à gauche qui est choisi et réécrit. Cet aspect se traduit par l'utilisation d'une pile dans l'algorithme de l'analyseur. L'analyseur est composé de : un tampon d'entrée, contenant la chaîne de caractères à analyser et doté de deux opérations : lecture du caractère courant et passage au caractère suivant ; une pile sur laquelle poser les terminaux et non terminaux de la grammaire qui restent à analyser ; une table d'analyse qui dit quelle règle utiliser (s'il y en a une) en fonction des symboles au sommet de la pile et du lexème suivant. L'analyseur applique la règle trouvée dans la table en faisant correspondre le sommet de la pile (ligne) avec le symbole courant dans le tampon d'entrée (colonne). Quand l'analyse commence, la pile contient deux symboles : [ S, $] Où '$' est un symbole de fond de pile et de la fin du tampon d'entrée, et 'S' l'axiome de la grammaire. L'analyseur va essayer de réécrire le contenu de sa pile en ce qu'il voit dans le tampon d'entrée. Cependant, il ne garde sur la pile que ce qui nécessite d'être réécrit. Soit une grammaire algébrique (où V désigne l'ensemble des variables ou symboles non terminaux, A l'alphabet terminal ou ensemble des symboles terminaux, P l'ensemble des règles, S l'axiome de la grammaire qui est une règle de P).