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

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.

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

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

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

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[s_i, a] peut contenir 'shift sj où s_j est un état, ou reduce rk où r_k est une règle de grammaire, ou “erreur”.
  • une table GOTO indexée par les états (lignes) et non-terminaux (colonnes). GOTO[ s_i, A] est intuitivement le nouvel état à empiler.

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

A chaque itération, on examine l'élément ACTION[s_m, a] où s_m 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).

<= Analyse LL(1) -\- Analyse SLR(1) cours suivant =>