Utilisateur:Timothée Anne/Brouillon

Cette page est un brouillon appartenant à Timothée Anne

Conseils de rédaction

→ N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
→ Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.

Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :

Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
Indiquez les éléments démontrant la notoriété du sujet (aide).
Liez chaque fait présenté à une source de qualité (quelles sources – comment les insérer).
Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).

→ Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.

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).

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

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

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

Cas général[modifier | modifier le code]

L'analyseur est composé de :

un tampon d'entrée, une chaîne 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.

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

Afin de calculer la table d'analyse, il faut avoir les fonctions $Eps$ , $Premier$ et $Suivant$ .

Eps[modifier | modifier le code]

Pour toute expression $\alpha \in (V\cup A)^{+}$ , $Eps(\alpha )$ vaut vrai si $\alpha$ est annulable, ce qui est équivalent à dire $\alpha {\xrightarrow {*}}\varepsilon$ 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 $\alpha \in (V\cup A)^{+}$ , on définit $Premier(\alpha )$ comme étant l'ensemble des terminaux susceptibles de commencer un mot dérivé de α. Plus formellement:

 $Premier(\alpha )=\{a\in A^{*}\mid \exists \beta \in (V\cup A)^{*},\alpha {\xrightarrow {*}}a\beta \}$ .

Si $\alpha =\varepsilon$ alors $Premier(\alpha )=\varnothing$ .

Suivant[modifier | modifier le code]

Pour toute expression $\alpha \in (V\cup A)^{+}$ , on définit $Suivant(\alpha )$ comme étant l'ensemble des terminaux susceptibles de suivre un mot dérivé de α. Plus formellement:

 $Suivant(\alpha )=\{a\in Premier(\gamma )\mid \exists \beta ,\gamma \in (V\cup A)^{*},S{\xrightarrow {*}}\beta \alpha \gamma \}$ .

Si $\alpha =\varepsilon$ , alors $Suivant(\alpha )=\varnothing$ . On ajoute aussi le symbole '$' à tous les $\{\alpha \in (V\cup A)^{+}\mid \exists \beta \in (V\cup A)^{*}S{\xrightarrow {*}}\beta \alpha \}$ , 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 telle :

  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 petite grammaire suivante :

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

et analyser la chaîne suivante

( 1 + 1 )

On calcul Eps:

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

On calcul 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 1 à la case (S,1).
On prend S → ( S + F ), Premier( ( S + F ) ) = { ( } donc on ajoute 2 à la case (S,()).
On prend F → 1, Premier( 1 )= { 1 } donc on ajoute 3 à la case (F,1).

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

Analyse du mot $(1+1)$
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 chaîne et afficher sur la sortie la liste suivante : [ 2, 1, 3, 3 ] 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:

S\to (L)

S\to a

L\to SL

L\to \varepsilon

et analyser la chaîne suivante

(a())

On calcule Eps:

Seul L est annulable, donc $EPS(\epsilon )=EPS(L)=$ 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 calcul la table d'analyse :

On prend S → ( L ), Premier( ( L ) ) = { ( } donc on ajoute 1 à la case ( S , ( ).
On prend S → a, Premier( a ) = { a } donc on ajoute 2 à la case ( S , a ).
On prend L → SL, Premier( SL )={ ( , a } donc on ajoute 3 aux cases ( L , ( ) et ( L, a ). 
On prend L → ε, Premier( ε ) = ∅ et Eps( ε ) = vrai et Suivant( L )={ $ , ) }, donc on ajoute 4 aux cases ( L , $ ) et ( L , ) ).

	(	)	a	$
S	1	-	2	-
L	3	4	3	4

Analyse du mot $(a())$
[ 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 applique les règles dans cet ordre : $1\rightarrow 3\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 4\rightarrow 4$ .

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

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

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

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

[1]