Analyse LL

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.

Sommaire

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)


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Analyse LL de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Analyse — Analyse …   Deutsch Wörterbuch

  • analyse — [ analiz ] n. f. • fin XVIe; gr. analusis « décomposition, résolution » I ♦ (Idée de « décomposition »). 1 ♦ Action de décomposer un tout en ses éléments constituants. Faire l analyse d un roman, d une pièce de théâtre. ⇒ compte rendu, 2.… …   Encyclopédie Universelle

  • Analyse [1] — Analyse, chemische, die Ermittlung der Zusammensetzung eines Körpers. Durch die qualitative Analyse [1] werden die einzelnen Bestandteile eines Körpers nachgewiesen. Hierbei werden die einzelnen Körper in der Regel nicht als solche abgeschieden,… …   Lexikon der gesamten Technik

  • Analyse — «Analyse» Сингл The Cranberries Выпущен 2001 Формат CD Жанр Альтернативный рок Длительность 4:07 Лейбл MCA Records …   Википедия

  • Analyse — Sf Zergliederung, Untersuchung erw. fach. (15. Jh., Form 18. Jh.) Entlehnung. Zunächst in der Form analysis entlehnt aus ml. analysis, aus gr. análysis, einem Nomen actionis zu gr. analӯein zergliedern, auflösen , zu gr. lӯein lösen und gr. ana… …   Etymologisches Wörterbuch der deutschen sprache

  • Analyse — may refer to:*Analyse, to undertake procedures analysis (also spelled Analyze in American English) * Analyse (song), a song on Thom Yorke s 2006 album The Eraser …   Wikipedia

  • Analyse — heißt die Auflösung einer Sache in ihre einzelnen Theile, z. B. wird mit einer Arzenei eine Analyse vorgenommen, wenn ich sie durch die Scheidekunst (Chemie) in ihre Bestandtheile auflöse. Ebenso spricht man von der Analyse eines Begriffs, wenn… …   Damen Conversations Lexikon

  • analyse — UK US UK (US analyze) /ˈænəlaɪz/ verb [T] ► to study or examine something in detail, in order to discover more about it: »Researchers analysed the purchases of 6300 households. analyse data/results/information »Management requires enthusiasm and… …   Financial and business terms

  • Analyse [3] — Analyse , biologische. Während man bisher Gifte fast ausschließlich auf chemischem Wege nachwies, nimmt neuerdings der Nachweis derselben auf biologischem Wege ein erhöhtes Interesse in Anspruch. Bei der biologischen Analyse wird die Einwirkung… …   Lexikon der gesamten Technik

  • analyse — (v.) chiefly British English spelling of ANALYZE (Cf. analyze) (q.v.). Analyse is better than analyze, but merely as being the one of the two equally indefensible forms that has won. The correct but now impossible form would be analysize (or… …   Etymology dictionary

  • Analyse — »Auflösung; Zergliederung, Untersuchung«: Der in dieser Form seit dem 18. Jh. bezeugte wissenschaftliche Terminus geht zurück auf griech. mlat. análysis »Auflösung; Zergliederung«. Dies gehört zu griech. ana lȳ̓ein »auflösen«, eine… …   Das Herkunftswörterbuch

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”