Analyse Syntaxique (2)

Analyse Ascendante

Ceci conduit à des analyseurs plus puissants au sens où elle réussit avec un sur-ensemble stricte de grammaires.

Exemple

La grammaire G0 mais sans la multiplication

  1. E → E + T
  2. E → T
  3. T → (E)
  4. T → id

Analyse de la chaine id + (id + id ) On s'aide d'un pile pour mémoriser les parties de l'arbre en cours de construction.

FIXME page de l'exemple à saisir (28/9 # 4)

Algorithme naïf

… par décalages et réductions.

A chaque étape on examine les premeiers éléments au sommet de la pile ; ce doit être le préfixe de la partie droite d'une ou plusieurs règles (notion de préfixe viable).

  • Si aucun préfixe n'est la partie droite d'une règle de grammaire, alors “shift” : on avance dans la chaine et on empile le token courant.
  • Sinon, on choisit entre shift et reduce. Si on choisit reduce, on choisit un préfixe qui est la partie droite d'une règle, on dépile la partie droite de cette règle et on empile la partie gauce.
  • on repète ceci avec des retours arrières jusqu'à ce que la pile ne contienne que S et qu'il n'y ait plus de token à lire.

Problèmes Rencontrés

  • Comment choisir entre shift et reduce?
  • Comment choisir entre redue et reduce?

La décision entre shift et reduce doit prendre en compte non seulement le token courant–le sommet de la pile–mais aussi le contenu de toute la pile! Solution : on introduit des états qui représentent l'information de toute la pile.

Principe de l'analyse LR

L'algorithme (famille d'algorithmes) utilise

  • un pointeur sur la chaine (suffixée par $)
  • une pile avec des états : un état est une description du contenu de la pile pour que la question du choix shift/reduce ne se pose plus. Le contenu de la pile (à l'horizontale) est :
    s_0 x_1 s_1 x_2\ldots x_m sm
    où les s_i sont des états, et les x_i sont des éléments de V \cup \Sigma \cup\left\{ $ \right\}
  • une table d'analyse qui comporte 2 parties
    • une table ACTION indexée par les états (en ligne) et les terminaux (y compris $) en colonne. ACTION[si, a] peut contenir 'shift sj où sj est un état, ou reduce rk où rk est une règle de grammaire, ou “erreur”.
    • une table GOTO indexée par les états (lignes) et non-terminaux (colonnes). GOTO[ si, A] est intuitivement le nouvel état à empiler.

Initialement le pointeur pointe sur le 1° élément de la chaine et la pile contient s0.

A chaque itération, on examine l'élément ACTION[sm, a] où sm est l'état au sommet de la pile, a est l'élément courant de la chaine. On réalise le traitement suivant :

  • si cet élément est shift s alors on empile a pis s et on avance le pointeur dans la chaine.
  • si cet élément est “reduce k”” alors on trouve la longueur l de la partie droite de la règle #k et on dépile 2*l éléments de la pile puis empile A puis GOTO[sm-l, A].
  • sinon : terminer : cet élément est soit “accepté” soir “erreur”.

Tous les analyseurs LR fonctionnent selon ce principe. Ils ne diffèrent entre eux que par la facons de définir et calculer les états (et tables). Nous verrons par la suite:

  • l'analyse SLR (simple LR) ainsi nommé parce qu'elle est simple à implémenter et elle est la moins puissante. Les autres utilisent de l'information de prévision.
  • l'analyse LR(1), la plus puissante mais aussi la plus couteuse.
  • l'analyse LALR(1) offre un bon compromis puissance/cout. Yacc et bison créent des analyseurs LaLR(1).

Navigation

 
m1ilc/compil_3.txt · Dernière modification: 2010/01/05 06:39 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki