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 Syntaxique — Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur syntaxique (parser, en… …   Wikipédia en Français

  • Analyse syntaxique — Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur syntaxique (parser, en… …   Wikipédia en Français

  • Analyse LR — En informatique, un analyseur LR (pour Left to right, Rightmost derivation) est un analyseur pour les grammaires non contextuelles qui lit l entrée de gauche à droite et produit une dérivation droite. On parle aussi d analyseur LR(k) où k… …   Wikipédia en Français

  • LL.M. — LL.M. (lat. Legum Magister, wobei LL. die lateinische Abkürzung für den Plural „Rechte“ ist) ist die Abkürzung für den akademischen Grad eines (engl.) Master of Laws (zu deutsch: Meister der Rechte). Dieser Postgraduierten Abschluss kann von… …   Deutsch Wikipedia

  • LL.M. oec. — LL.M. (lat. Legum Magister, wobei LL. die lateinische Abkürzung für den Plural „Rechte“ ist) ist die Abkürzung für den akademischen Grad eines (engl.) Master of Laws (zu deutsch: Meister der Rechte). Dieser Postgraduierten Abschluss kann von… …   Deutsch Wikipedia

  • LL-Parser — Im Compilerbau ist ein LL Parser ein Top Down Parser, der die Eingabe von Links nach rechts abarbeitet, um eine Linksableitung der Eingabe zu berechnen.[1] Ein LL Parser heißt LL(k) Parser, wenn er während des Parsens k Tokens vorausschauen kann… …   Deutsch Wikipedia

  • LL(k)-Grammatik — Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. Eine LL(k) Grammatik (im Kontrast zu LF(k) Grammatik auch schwache LL(k) Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage… …   Deutsch Wikipedia

  • I'll Get You — Single par The Beatles Face A She Loves You Face B I ll Get You Sortie …   Wikipédia en Français

  • That'll Teach 'Em — Infobox Television show name = That ll Teach Em caption = genre = Documentary series creator = director = developer = presenter = starring = voices = narrated = theme music composer = opentheme = endtheme = composer = country = Flag|United… …   Wikipedia

  • Théorème de Cesàro (analyse) — Lemme de Cesàro En analyse réelle ou complexe, la moyenne de Cesàro d une suite (an) est la suite obtenue en effectuant la moyenne arithmétique des n premiers termes de la suite. Le nom de Cesàro provient du mathématicien italien Ernesto Cesàro.… …   Wikipédia en Français

Share the article and excerpts

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