Analyse LL

L'analyse LL est une analyse descendante pour un sous-ensemble de grammaire non contextuelle. Il analyse l'entrée de gauche à droite (Left to right) et en construit une dérivation à gauche (Leftmost derivation). Les grammaires analysables de cette façon sont nommées grammaires LL.

Une analyse LL est appelée analyse LL(k) lorsqu'elle utilise k lexèmes d'avance.

Architecture d'un analyseur LL

Ce qui suit décrit une analyse descendante à dérivation à gauche basé sur une table d'analyse.

Cas général

L'analyseur est composé de :

• un tampon d'entrée, une chaine de caractères de la grammaire.
• une pile sur laquelle poser les terminaux et non terminaux de la grammaire prêts à être analysés.
• une table d'analyse qui dit quelle règle utiliser (s'il y en a une) en fonction des symboles au sommet de sa 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 terminal spécial indiquant le bas de la pile et la fin du tampon d'entrée, et 'S' le symbole de départ 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.

Exemple

Initialisation

Pour expliquer son fonctionnement, nous allons utiliser la petite grammaire suivante:

1. S → F
2. S → ( S + F )
3. F → 1

et analyser la chaine suivante

( 1 + 1 )

La table d'analyse de cette grammaire ressemble à ceci:

	(	)	1	+	$
S	2	-	1	-	-
F	-	-	3	-	-

Analyse

L'analyseur lit le premier '(' du tampon d'entrée et le sommet de la pile (le 'S'). En regardant la table il sait qu'il doit appliquer la règle 2; Il doit maintenant réécrire le 'S' en '( S + F )' sur sa pile et écrire le numéro de la règle appliquée sur la sortie (ici '2'). La pile devient donc:

[ (, S, +, F, ), $ ]

Étape suivante, il supprime le '(' du tampon d'entrée et de sa pile:

[ S, +, F, ), $ ]

Maintenant l'analyseur voit un '1' donc il sait qu'il doit appliquer la règle 1 puis la règle 3 et afficher leur nombre sur la sortie. La pile devient donc:

[ F, +, F, ), $ ]

puis:

[ 1, +, F, ), $ ]

Pendant les deux étapes suivantes, l'analyseur lit le '1' et le '+' et, comme ils correspondent aux deux éléments suivants sur la pile, les supprime de la pile. Ce qui donne:

[ F, ), $ ]

Pour les 3 dernières étapes, le 'F' va être remplacé sur la pile par '1', le nombre '3' va donc être écrit sur la sortie et ensuite le '1' et le ')' qui sont retirés du tampon d'entrée et de la pile. L'analyse se termine donc car il n'y a plus que '$' dans la pile et le tampon d'entrée.

Dans ce cas, il va dire qu'il a accepté la chaine et afficher sur la sortie la liste suivante:

[ 2, 1, 3, 3 ]

Ce qui est effectivement une dérivation à gauche de la chaine de départ. Nous voyons qu'une dérivation à gauche de la chaine est:

S → ( S + F ) → ( F + F ) → ( 1 + F ) → ( 1 + 1 )

Remarques

Comme on peut le voir, l'analyseur effectue 3 types d'étapes dépendant du haut de la pile (non terminal, terminal, symbole '$'):

• Si le sommet de la pile est un symbole non terminal, alors il regarde dans la table d'analyse sur la base de ce symbole non terminal et du symbole dans le tampon d'entrée quelle règle utiliser pour le remplacer sur la pile. Le numéro de la règle est écrit sur la sortie. Si la table d'analyse dit qu'il n'y a pas de règle correspondante, alors il émet une erreur et s'arrête.
• Si le sommet de la pile est un symbole terminal, il le compare avec le symbole dans le tampon d'entrée. S'ils sont égaux, il les supprime, sinon il émet une erreur et s'arrête.
• Si le sommet de la pile est '$' et que le tampon d'entrée contient aussi '$' alors l'analyseur dit qu'il a correctement analysé la chaîne, sinon il émet une erreur. Dans les deux cas il s'arrête.

Ces étapes sont répétées jusqu'à ce que l'analyseur s'arrête; il aura soit analysé correctement la chaîne et écrit une dérivation à gauche de la chaîne sur la sortie, soit il aura émis une erreur.

Générateurs d'analyseur LL(k)

• ANTLR : (en) Site officiel
• Coco/R : (en) Site officiel
• JavaCC : (en) Site officiel
• PCCTS : ancien nom de ANTLR, (en) site archivé
• Ocaml Genlex Module : (en) Site officiel

• Portail de l’informatique