Analyse LL

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique
Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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) et en construit une dérivation à gauche (Leftmost derivation). 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.

Architecture d'un analyseur LL[modifier | modifier le code]

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

Cas général pour une analyse LL(1)[modifier | modifier le code]

L'analyseur est composé de :

  • un tampon d'entrée, une chaîne de caractères de la grammaire représentant le mot d'entrée;
  • 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.

Calcul de la table d'analyse[modifier | modifier le code]

Soit une Grammaire algébrique. Afin de calculer la table d'analyse, on introduit les fonctions , et .

Eps[modifier | modifier le code]

Pour toute expression , vaut vrai si est annulable, ce qui est équivalent à dire et vaut faux dans le cas contraire. Ce calcul correspond à celui des ε-règles, comme dans le cas de la conversion en Forme normale de Chomsky.

Premier[modifier | modifier le code]

Pour toute expression , on définit comme étant l'ensemble des terminaux susceptibles de commencer un mot dérivé de α. Plus formellement:

.

Si alors .

Suivant[modifier | modifier le code]

Pour toute expression , on définit comme étant l'ensemble des terminaux susceptibles de suivre un mot dérivé de α. Plus formellement:

.

Si , alors . On ajoute aussi le symbole '$' à tous les , de façon à pouvoir indiquer la fin du code.

Remplissage de la table d'analyse[modifier | modifier le code]

La table d'analyse est une matrice à deux dimensions, dont les lignes sont indicées par des Non-terminaux et les colonnes par des Terminaux. Le remplissage s'effectue comme tel :

  Pour toute règle de la forme X→α 
     Pour tout a∈Premier(α)
        Ajouter X→α à la case d'indice (a,X)
     Si Eps(α) vaut vrai Alors
        Pour tout b∈Suivant(α) 
           Ajouter X→α à la case d'indice (b,X)
        Fin pour
     Fin pour
  Fin pour

Exemple sans ε-règle.[modifier | modifier le code]

Initialisation[modifier | modifier le code]

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

et analyser la chaîne suivante

( 1 + 1 )

On calcule Eps:

Aucune règle ne donne , donc aucun Eps(α) vaut toujours faux.

On calcule Premier:

Premier( 1 ) = { 1 }
Premier( ( S + F ) ) = { ( }
Premier( F ) = { 1 }


On calcule la table d'analyse :

On prend S → F, Premier( F ) = { 1 } donc on ajoute '' à la case ( S , 1 ).
On prend S → ( S + F ), Premier( ( S + F ) ) = { ( } donc on ajoute '' à la case ( S  , ( ).
On prend F → 1, Premier( 1 )= { 1 } donc on ajoute '' à la case ( F , 1 ).
( ) 1 + $
S - - -
F - - - -
Exemple de l'analyse LL avec le mot, l'arbre de dérivation et la pile.
Analyse du mot

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 '' ; il doit maintenant réécrire le 'S' en '( S + F )' sur sa pile et écrire la règle appliquée sur la sortie. 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 '' puis la règle '' et les afficher 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', la règle '' va donc être écrite sur la sortie. Ensuite le '1' et le ')' 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 chaîne et afficher sur la sortie la liste suivante :

[ , , , ]

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

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

Remarques[modifier | modifier le code]

Comme on peut le voir, l'analyseur effectue trois 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 émis une erreur.

Exemple avec ε-règle.[modifier | modifier le code]

Initialisation[modifier | modifier le code]

Pour expliquer son fonctionnement, nous allons utiliser la grammaire simplifiée du langage LISP/Scheme[1] suivante:

et analyser la chaîne suivante

On calcule Eps:

Seul L est annulable, donc vrai et vaut faux dans les autres cas.

On calcule Premier:

Premier( a ) = { a }
Premier( ( L ) ) = { ( }
Premier( SL ) = { ( , a }
Premier( ε ) = ∅

On calcule Suivant:

Suivant( S ) = { $ }
Suivant( L ) = { $ , ) }

On calcule la table d'analyse :

On prend S → ( L ), Premier( ( L ) ) = { ( } donc on ajoute '' à la case ( S , ( ).
On prend S → a, Premier( a ) = { a } donc on ajoute '' à la case ( S , a ).
On prend L → SL, Premier( SL )={ ( , a } donc on ajoute '' aux cases ( L , ( ) et ( L, a ). 
On prend L → ε, Premier( ε ) = ∅ et Eps( ε ) = vrai et Suivant( L )={ $ , ) }, donc on ajoute '' aux cases ( L , $ ) et ( L , ) ).
Exemple de construction de l'arbre de dérivation lors de l'analyse LL
( ) a $
S - -
L
Analyse du mot
[ S, $ ] 

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 1 ; il doit maintenant réécrire le 'S' en '( L )' sur sa pile. La pile devient donc :

[ (, L, ), $ ] 

Il supprime ensuite le '(':

[ L, ), $ ]

Il lit le 'L' et la lettre 'a', il doit appliquer la règle 3; il réécrit le 'L' en 'SL':

[S, L, ), $ ]

Il lit le 'S' et la lettre 'a', il doit appliquer la règle 2; il réécrit le 'S' en 'a' puis supprime le 'a'. La pile devient :

[ L, ), $ ]

Il lit maintenant le 'L' et la lettre '(', il réécrit le 'L' en 'SL' (règle 3) puis le 'S' en '(L)' (règle 1), il peut ainsi supprimer le '('. La pile devient :

[ L, ), L, ), $ ] 

Il lit le 'L' et la lettre ')', il peut donc enlever le 'L' grâce à la règle 4, puis il peut supprimer le ')'. La pile devient :

[ L, ), $ ]

De la même façon que précédemment La règle 4 lui permet d'enlever le 'L' et il peut ensuite supprimer le ')'. La pile devient :

[ $ ] 

L'algorithme conclue donc positivement et en appliquant la suite de dérivation gauche :

.

Générateurs d'analyseur LL(k)[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Romain Legendre et François Schwarzentruber, Compilation : Analyse lexicale et syntaxique - du texte à sa structure en informatique, , 312 p. (ISBN 9782340003668)