Cours n° 20, 22 mars 2011

Jean-François Perrot

Analyseurs descendants & ascendants

Les deux types d'automates à pile associés à une grammaire CF
Grammaires et systèmes formels : stratégies de preuve
1. L'analyse descendante produit l'arbre de dérivation / arbre de preuve en marche arrière
  1. Principe de la démonstration en marche arrière
  2. L'analyse descendante comme démonstration en marche arrière
2. L'analyse ascendante produit l'arbre de dérivation / arbre de preuve en marche avant
  1. Principe de la démonstration en marche avant
  2. L'analyse ascendante réalise une variante
Rendre déterministe l'un des deux analyseurs canoniques
1. Les notations polonaises
2. Supériorité de l'analyse ascendante

Les deux types d'automates à pile associés à une grammaire CF

On peut associer canoniquement à une grammaire CF non pas un, mais bien deux automates à pile reconnaissant le langage qu'elle engendre.
Ces deux automates sont en général non-déterministes, donc impropres à fournir la base d'un parseur.
Toute la question va être à présent : sous quelles conditions (portant sur la grammaire) l'un d'entre eux sera-t-il déterministe ?

Ces deux automates ont pour principe la gestion dans une pile

de la dérivation gauche pour l'un (analyse descendante, en anglais top-down)
de la dérivation droite pour l'autre (analyse ascendante, en anglais bottom-up)

Là s'arrête la symétrie. Comme on va le voir, les deux modes de gestion sont assez différents.

Principe de l'analyse descendante
- Structure d'une dérivation gauche
  Considérons la dérivation gauche du mot x+y+z*2 dans la grammaire à précédences (forme de base) :
  E -> E+T -> E+T+T -> T+T+T -> F+T+T -> x+T+T -> x+F+T -> x+y+T -> x+y+T*F
  -> x+y+F*F -> x+y+z*F -> x+y+z*2
  
  Nous voyons que chacun des mots intermédiaires qui y paraissent peut se couper en deux au premier non-terminal :
  - du côté gauche une chaîne terminale, vide au départ, qui croît jusqu'à recouvrir le mot analysé tout entier :
    ε, ε, ε, ε, ε, x+, x+, x+y+, x+y+; x+y+, x+y+z*, x+y+z*2
  - du côté droit une chaîne comportant au moins un non-terminal (celui qui est réécrit à chaque pas)
    sauf à la dernière étape où cette chaîne se vide.
    E, E+T, E+T+T, T+T+T, F+T+T, T+T, F+T, T, T*F, F*F, F, ε
  De sorte que notre dérivation gauche peut s'écrire, en séparant les deux parties du mot par "/" :
  ε/E -> ε/E+T -> ε/E+T+T -> ε/T+T+T -> ε/F+T+T -> x+/T+T -> x+/F+T -> x+y+/T -> x+y+/T*F -> x+y+/F*F -> x+y+z*/F -> x+y+z*2/ε
- Observation
  - La séquence des facteurs gauches correspond à la lecture de gauche à droite du mot analysé :
    ils croissent de gauche à droite, chacun d'eux représente la partie (gauche) du mot qui a été lue à l'instant considéré.
  - Celle des facteurs droits a la particularité qu'à chaque pas seul le premier caractère du mot est réécrit
    (parfois effacé) ce qui se traduit en disant que cette suite est celle des états successifs d'une pile.
    Au début du calcul, cette pile contient l'axiome de la grammaire, à la fin du calcul elle est vide.
  Ce que nous traduisons en disant que la gestion des dérivations gauches peut être effectuée par un automate à pile.
Principe de l'analyse ascendante
- Structure d'une dérivation droite
  Considérons la dérivation droite du même mot x+y+z*2 dans la même grammaire :
  E -> E+T -> E+T*F -> E+T*2 -> E+F*2 -> E+z*2 -> E+T+z*2 -> E+F+z*2 -> E+y+z*2 -> T+y+z*2 -> F+y+z*2 -> x+y+z*2
  
  Elle aussi se prête à une division facteur gauche / facteur droit, mais c'est le facteur gauche qui est non-terminal et le facteur droit qui est terminal.
  
  E -> E+T/ε -> E+T*F/ε -> E+T/*2 -> E+F/*2 -> E/+z*2 -> E+T/+z*2 -> E+F/+z*2 -> E/+y+z*2 -> T/+y+z*2 -> F/+y+z*2 -> ε/x+y+z*2
- Observation
  Lisons-la à l'envers, non plus comme une suite de dérivations élémentaires, mais comme une suite de réductions.
  - la suite des facteurs droits x+y+z*2 , +y+z*2 , +z*2 , *2 , ε, correspond à la lecture de gauche à droite du mot analysé :
    mais chacun d'eux représente la partie du mot qui reste à lire.
  - la suite des facteurs gauches ε , F , T , E , E+F , E+T , E , E+F , E+T , E+T*F , E+T , E
    chacun lu de droite à gauche ε , F , >T , E , F+E , T+E , E , F+E , T+E , F*T+E , T+E , E
    présente la même particularité qu'à chaque pas seul le premier caractère du mot est réécrit
    (parfois effacé) ce qui se traduit en disant que cette suite est celle des états successifs d'une pile.
    Au début du calcul, cette pile est vide, à la fin du calcul elle contient l'axiome de la grammaire.
  Ce que nous traduisons en disant que la gestion des dérivations droites renversées (réductions) peut être effectuée par un automate à pile.

Les deux analyseurs canoniques

L'analyseur descendant

Commence son calcul avec le mot à lire et l'axiome seul dans la pile.
À chaque pas, si la pile n'est pas vide, selon la nature du symbole en sommet de pile :
- si c'est une lettre terminale, et que le prochain caractère à lire soit la même lettre
  alors le sommet de pile est écrêté, et on avance dans la lecture
  sinon, échec, l'automate se bloque ;
- si c'est un symbole non-terminal [appelons-le A], l'automate choisit (en principe, de manière non-déterministe)
  une des règles de grammaire dont ce non-terminal est la partie gauche,
  et il écrit au sommet de la pile le membre doit de la règle à la place de A.
Si la pile est vide
- si le mot a été entièrement lu : succès
- s'il reste des caractères à lire en entrée : échec.

De cette manière, s'il existe une dérivation gauche pour le mot à lire, l'automate "la trouvera" et le calcul se terminera avec

la pile vide
le mot entièrement lu.

mais s'il n'en existe pas l'automate cherchera peut-être indéfiniment...
D'ailleurs, même si la dérivation existe, rien ne dit que l'automate la touvera au bout d'un temps fini,
tout dépend de sa stratégie dans la gestion du non-déterminisme, et il peut fort bien boucler indéfiniment !
À strictement parler, on peut dire seulement qu'il existe un calcul de l'automate qui accepte le mot.

Illustration : la dérivation gauche de notre exemple

ε/E -> ε/E+T
-> ε/E+T+T -> ε/T+T+T
-> ε/F+T+T -> x+/T+T
-> x+/F+T -> x+y+/T -> x+y+/T*F 

-> x+y+/F*F -> x+y+z*/F -> x+y+z*2/ε

vue comme calcul de l'analyseur descendant canonique
(on a coloré en vert les configurations où la lecture avance, avec en gras le caractère éliminé simultanément du mot à lire et de la pile) :

Partie du mot d'entrée restant à lire	Contenu de la pile	Règle appliquée
`x+y+z*2`	`E`	`E -> E+T`
`x+y+z*2`	`E+T`	`E -> E+T`
`x+y+z*2`	`E+T+T`	`E -> T`
`x+y+z*2`	`T+T+T`	`T -> F`
`x+y+z*2`	`F+T+T`	`F -> x`
`x+y+z*2`	`x+T+T`
`+y+z*2`	`+T+T`
`y+z*2`	`T+T`	`T -> F`
`y+z*2`	`F+T`	`F -> y`
`y+z*2`	`y+T`
`+z*2`	`+T`
`z*2`	`T`	`T -> T*F`
`z*2`	`T*F`	`T -> F`
`z*2`	`F*F`	`F -> z`
`z*2`	`z*F`
`*2`	`*F`
`2`	`F`	`F -> 2`
`2`	`2`
`ε`	`ε`

On voit clairement que l'automate aurait fort bien pu boucler en continuant à dériver

E -> E+T
-> E+T+T -> E+T+T+T

...

L'analyseur ascendant

Commence son calcul avec le mot à lire et la pile vide.
À chaque pas il choisit (de manière non-déterministe)
- soit de lire un caractère en entrée et de l'empiler (transfert, en anglais shift, du mot lu vers la pile)
- soit de trouver au sommet de la pile le membre droit d'une règle de la grammaire écrit à l'envers,
  auquel cas il le remplace par le symbole non-terminal en partie gauche (réduction)
  ce qui donne un second niveau de non-déterminisme, car plusieurs règles peuvent avoir le même membre droit.
Le calcul réussit s'il arrive à
- lire tout le mot d'entrée
- avoir dans la pile l'axiome de la grammaire seul.

La suite renversée des réductions opérées au cours du calcul est une dérivation droite du mot d'entrée.
On note que cet automate ne boucle que si la grammaire contient un circuit A -> B -> C...-> A.

Illustration : la dérivation droite de notre exemple

E -> E+T/ε -> E+T*F/ε
-> E+T/*2 -> E+F/*2 -> E/+z*2 -> E+T/+z*2 -> E+F/+z*2
-> E/+y+z*2
-> T/+y+z*2 

-> F/+y+z*2 -> ε/x+y+z*2

vue comme calcul de l'analyseur ascendant canonique
(on a coloré en vert les configurations qui résultent du transfert d'un caractère du mot d'entrée sur la pile, avec en gras le caractère transféré) :

Partie du mot d'entrée restant à lire	Contenu de la pile	Règle réduite
`x+y+z*2`	`ε`
`+y+z*2`	`x`	`F -> x`
`+y+z*2`	`F`	`T -> F`
`+y+z*2`	`T`	`E -> T`
`+y+z*2`	`E`
`y+z*2`	`+E`
`+z*2`	`y+E`	`F -> y`
`+z*2`	`F+E`	`T -> F`
`+z*2`	`T+E`	`E -> E+T`
`+z*2`	`E`
`z*2`	`+E`
`*2`	`z+E`	`F -> z`
`*2`	`F+E`	`T -> F`
`*2`	`T+E`
`2`	`*T+E`
`ε`	`2*T+E`	`F -> 2`
`ε`	`F*T+E`	`T -> T*F`
`ε`	`T+E`	`E -> E+T`
`ε`	`E`

Grammaires et systèmes formels : stratégies de preuve
1. L'analyse descendante produit l'arbre de dérivation / arbre de preuve en marche arrière
  en anglais backward-chaining, souvent traduit en français par chaînage arrière.
  L'expression en marche arrière est due à Jacques Pitrat.
  On parle aussi de programmation dirigée par les buts (en anglais goal-directed ou goal-oriented).
  C'est la stratégie employée par les programmes récursifs.
  C'est celle de Prolog vu comme un démonstrateur de théorèmes.
  - Principe de la démonstration en marche arrière
    1. On part du but à atteindre [dans l'exemple du cours 2-2, la thèse (4, 2, ??)] et on choisit un moyen d'y parvenir,
      c'est-à-dire une règle de déduction du système susceptible d'avoir ce but comme conclusion.
      (Dans le cas d'un programme récursif, cette règle est unique ; dans le cas de Prolog on essaiera successivement toutes les règles.)
    2. La règle en question fait apparaître plusieurs buts intermédiaires ou sous-buts qu'il suffira d'atteindre pour compléter la preuve
      [dans l'exemple du cours 2-2, les thèses (3, 1, ??) et (3, 2, ??)].
    3. On relance le processus sur les sous-buts en question.
      Cette relance donne au processus un caractère récursif intrinsèque.
      Il paraît donc naturel de le réaliser par un programme récursif, mais ce n'est pas une obligation !
    L'arbre de preuve est ainsi construit en partant de sa racine (le but) pour arriver à ses feuilles (les faits élémentaires constatés,
    c'est-à-dire les axiomes du système, qui sont à la base de la démonstration).
  - L'analyse descendante comme démonstration en marche arrière
    Le but est de démontrer que la chaîne donnée toute entière appartient à la catégorie grammaticale de l'axiome.
    Le choix d'une règle de grammaire issue de l'axiome, qui est la première dans la dérivation,
    est aussi celui de la dernière déduction de l'arbre de preuve.
    Les non-terminaux du membre droit de cette règle sont autant de sous-buts.
    L'analyseur canonique les empile pour pouvoir les traiter l'un après l'autre, par un programme itératif.
    
    Voici le calcul de l'analyseur descendant sur l'expression "x+y+z*2", lu comme la construction d'un arbre de preuve,
    présentée comme au cours 19 :
    1. E + T ---------- E
    2. E + T ----- E + T ------------ E
    3. T --- E+ T ----- E + T ------------ E
    4. F --- T --- E + T ----- E + T ------------ E
    5. x --- F --- T --- E + T ----- E + T ------------ E
    6. x --- F --- T F --- --- E + T ----- E + T ------------ E
    7. x --- F y --- --- T F --- --- E + T ----- E + T ------------ E
    8. x --- F y --- --- T F --- --- E + T T * F ----- ----- E + T --------------- E
    9. x --- F y --- --- T F F --- --- --- E + T T * F ----- ----- E + T --------------- E
    10. x --- F y z --- --- --- T F F --- --- --- E + T T * F ----- ----- E + T --------------- E
    11. x --- F y z --- --- --- T F F 2 --- --- --- --- E + T T * F ----- ----- E + T --------------- E
  La manière la plus courante pour effectuer l'analyse descendante est justement la programmation récursive
  (technique dite de la descente récursive).
2. L'analyse ascendante produit l'arbre de dérivation / arbre de preuve en marche avant
  en anglais forward-chaining, souvent traduit en français par chaînage avant.
  L'expression en marche avant est due à Jacques Pitrat.
  On parle aussi de programmation dirigée par les données (en anglais data-directed ou data-oriented).
  Cette stratégie est très employée en intelligence artificielle par les moteurs d'inférence des systèmes à base de connaissances
  (autrefois appelés systèmes experts).
  1. Principe de la démonstration en marche avant
    1. On ne part pas du but à atteindre (thèse à démontrer), mais des faits avérés (les hypothèses),
      et on en déduit tous les énoncés possibles par application d'une des règles de déduction (une application pour chaque règle).
    2. Si le but à atteindre figure parmi ces énoncés, il est démontré.
      Sinon, on applique une nouvelle fois l'ensemble des règles à la collection des énoncés déduits des hypothèses,
      et ainsi de suite, par ue démarche intrinsèquement itérative.
    3. On s'arrête soit lorsque le but est atteint, soit lorsque l'application des règles ne produit plus d'énoncé nouveau
      (l'ensemble des énoncés déduits des hypothèses est alors saturé).
  2. L'analyse ascendante réalise une variante
    où toutes les règles ne sont pas appliquées par vagues successives, mais au fur et à mesure, dès qu'elles sont applicables.
    Les énoncés déduits sont gérés dans la pile.
    
    Voici le calcul de l'analyseur ascendant sur l'expression "x+y+z*2", lu comme la construction d'un arbre de preuve,
    présentée comme au cours 2-2 :
    1. x --- F
    2. x --- F --- T
    3. x --- F --- T --- E
    4. x --- F y --- ---
      T F --- E
    5. x --- F y --- ---
      T F --- --- E T
    6. x --- F y --- ---
      T F --- --- E + T --------- E
    7. x --- F y z --- --- --- T F F --- --- E + T --------- E
    8. x --- F y z --- --- --- T F F --- --- --- E + T T --------- E
    9. x --- F y z --- --- --- T F F 2 --- --- --- --- E + T T F --------- E
    10. x --- F y z --- --- --- T F F 2 --- --- --- --- E + T T * F --------- -------- E T
    11. x --- F y z --- --- --- T F F 2 --- --- --- --- E + T T * F --------- -------- E + T ------------- E

Rendre déterministe l'un des deux analyseurs canoniques

Vaste problème ! C'est le sujet connu en informatique comme l'analyse syntaxique (syntax analysis).
Ce domaine n'est plus à présent l'objet de recherches actives. Dans les cours suivants, nous reparlerons longuement de certains des résultats acquis.
Nous nous limiterons ici à deux exemples emblématiques et à des considérations de bon sens.

Les notations polonaises

Analyse descendante de la préfixée

Dans les dérivations gauches de cette grammaire, chaque règle laisse une trace (opérateur ou opérande),
et l'ordre de ces traces est exactement celui de l'application des règles.
L'examen du prochain caractère à lire suffit donc à éclairer l'analyseur descendant sur le choix de la règle...
Le calcul prend alors une forme particulière, où chaque application de règle est immédiatement accompagnée
de la consommation d'un caractère en entrée, ce qui permet de le programmer d'une manière concise.

Partie du mot d'entrée restant à lire	Contenu de la pile	Règle appliquée
`++xy*z2`	`S`	`S -> +SS`
`++xy*z2`	`+SS`
`+xy*z2`	`SS`	`S -> +SS`
`+xy*z2`	`+SSS`
`xy*z2`	`SSS`	`S -> x`
`xy*z2`	`xSS`
`y*z2`	`SS`	`S -> y`
`y*z2`	`yS`
`*z2`	`S`	`S -> *SS`
`*z2`	`*SS`
`z2`	`SS`	`S -> z`
`z2`	`zS`
`2`	`S`	`S -> 2`
`2`	`2`
`ε`	`ε`

Analyse ascendante de la postfixée

Dans les dérivations droites de cette grammaire, chaque règle laisse une trace (opérateur ou opérande),
et l'ordre de ces traces est exactement inverse de celui de l'application des règles.
La dérivation droite renversée est donc directement codée par le mot d'entrée.

En pratique, avec cette grammaire, l'analyseur ascendant n'a pas le choix : à chaque étape,

soit il trouve le membre droit d'une règle au sommet de sa pile,
auquel cas ce membre droit désigne une règle unique, il la réduit ;
soit il n'en trouve pas, et alors il transfère le prochain caractère à lire au sommet de la pile.

Partie du mot d'entrée restant à lire	Contenu de la pile	Règle réduite
`xy+z2*+`	`ε`
`y+z2*+`	`x`	`S -> x`
`y+z2*+`	`S`
`+z2*+`	`yS`	`S -> y`
`+z2*+`	`SS`
`z2*+`	`+SS`	`S -> SS+`
`z2*+`	`S`
`2*+`	`zS`	`S -> z`
`2*+`	`SS`
`*+`	`2SS`	`S -> 2`
`*+`	`SSS`
`+`	`*SSS`	`S -> SS*`
`+`	`SS`
`ε`	`+SS`	`S -> SS+`
`ε`	`S`

Analyse descendante de la postfixée ?
En tout cas pas directement, puisque la lecture de gauche à droite du mot d'entrée ne renseigne nullement sur les règles
employées dans la dérivation gauche ! Il va falloir changer de grammaire...

D'une manière générale, toute grammaire récursive à gauche, c'est-à-dire telle qu'un non-terminal A puisse se dériver en Aw
c-à-d. en un mot qui commence par A lui-même, est rebelle à l'analyse descendante déterministe.

Analyse ascendante de la préfixée ?

Pourquoi pas ?
Les remarques formulées pour la postfixée restent valables pour l'analyse ascendante de la préfixée !

Partie du mot d'entrée restant à lire	Contenu de la pile	Règle réduite
`++xy*z2`	`ε`
`+xy*z2`	`+`
`xy*z2`	`+``+`
`y*z2`	`x++`	`S -> x`
`y*z2`	`S++`
`*z2`	`yS++`	`S -> y`
`*z2`	`SS++`	`S -> +SS`
`*z2`	`S+`
`z2`	`*S+`
`2`	`z*S+`	`S -> z`
`2`	`S*S+`
`ε`	`2S*S+`	`S -> 2`
`ε`	`SS*S+`	`S -> *SS`
`ε`	`SS+`	`S -> +SS`
`ε`	`S`

Traduction de la préfixée vers la postfixée et vice-versa.

Si on établit une correspondance entre les règles des deux grammaires, celle de la préfixée et celle de la postfixée,
avec "S -> +SS" <==> "S -> SS+" etc,
on remarque que les deux analyses ascendantes conduisent à la même séquence de règles.
Or, nous avons vu plus haut que la notation postfixée n'est pas autre chose que la trace de la dérivation droite renversée.

Par conséquent, pour obtenir un traducteur de la préfixée vers la postfixée, il suffit de munir l'analyseur ascendant de la préfixée
d'une fonction de sortie : à chaque réduction, on écrit soit l'opérateur, soit la variable ou la constante de la règle.
Dans l'exemple ci-dessus, on obtient en sortie : "xy+z2*+" comme attendu.

Ceci montre que l'on peut traduire de la préfixée vers la postfixée avec une seule pile.
Quid de la traduction réciproque ?
Eh bien, il va falloir deux piles !
- L'une pour construire l'arbre de l'expression (construction ascendante),
- l'autre pour parcourir cet arbre de manière descendante et engendrer la notation préfixée.
Je crois bien que ça se démontre rigoureusement - mais je n'ai plus la référence.

Supériorité de l'analyse ascendante

La comparaison des deux modes d'analyse sur l'exemple de la préfixée met en lumière
- la fragilité de l'analyse descendante, obligée de prévoir la règle employée à partir du prochain caractère à lire,
  et de procéder a priori ;
- la robustesse de l'analyse ascendante, qui décide de réduire une règle au vu de son membre droit tout entier,
  en raisonnant a posteriori.
Cette intuition se transfère dans un démonstration rigoureuse, qui établit que toute grammaire analysable de manière déterministe descendante
est aussi analysable de manière déterministe ascendante, la réciproque n'étant pas vraie comme le montre l'exemple de la postfixée.

Cours n° 20, 22 mars 2011

Analyseurs descendants & ascendants

Grammaires et systèmes formels : stratégies de preuve