16 avril 2013 : Écriture en C++ d'un analyseur ascendant

Jean-François Perrot

On explicite le discours tenu au cours du 4 avril sur le principe de l'analyse ascendante,
sous la forme d'un programme C++ qui produit

  1. Projet

    Appliquer ce principe à la grammaire non-ambiguë proposée au cours 19 pour les systèmes de parenthèses.

    1. S -> ε
    2. S -> (S)S 
    3. S -> [S]S 
    4. S -> {S}S 
    5. S -> <S>S

    Exemple : le mot <<<>[(())]<{[]}>>>
    est engendré par la dérivation droite inverse de la chaîne 1112121131415351515

    La construction d'un arbre binaire associé à un système de parenthèses sera abordée au cours suivant.

  2. Principe de réalisation

    1. Scruter la pile

      Alors que l'analyse descendante se contente des opérations élémentaires sur sa pile (push, top, pop et empty),
      l'analyse ascendante doit à chaque pas scruter sa pile pour déterminer si elle ne contient pas un membre droit de règle.
      Dans les analyseurs en usage normal, cet examen est réalisé par un automate fini dont l'état courant est logé également dans la pile.
      On a donc affaire à une pile dont les éléments sont des objets complexes (caractère, état).
      Un autre réalisation, aujourd'hui périmée, utilisait deux piles, une pour chaque composante (caractère, état).

      Pour simplifier la programmation, nous remplacerons ici l'automate fini réglementaire par une fonction auxiliaire areduire chargée de scruter la pile, sans la modifier, en utilisant la ressource que nous offre C++ de l'appel par valeur sur des objets-pile "directs" (et non sur des pointeurs). En cas de succès, cette fonction renvoie le numéro de la règle dont elle a trouvé le membre droit, en cas d'échec elle renvoie 0. Elle fait  elle-même appel à quelques fonctions de service.

      L'opération de réduction du membre droit trouvé sur la pile sera effectuée au moyen d'une procédure reduire, dont le paramètre et passé par référence.

    2. Test de succès

      À la fin de la lecture du mot-candidat, l'analyse descendante réussit si sa pile est vide. L'analyse ascendante réussit si sa pile ne contient plus que l'axiome de la grammaire.
      L'écriture du test de succès fait donc appel à un prédicat auxiliaire axiomeSeulDanslaPile, dont le paramètre est appelé par valeur, ce qui laisse la voie ouverte à des diagnostics d'erreur plus raffinés.


  3. Le programme écrit en cours

    dûment débogué : fichier pa1.cpp

  4. Programme pédagogique avec affichage des mouvements de la pile

    fichier pa.cpp
    jfp$ ./pp
    Donnez un mot candidat
    <<<>[(())]<{[]}>>>
    i = 1 carvu = < - <
    i = 2 carvu = < - < <
    i = 3 carvu = > - < < <
    i = 3 carvu = > - S < < <
    i = 4 carvu = [ - > S < < <
    i = 5 carvu = ( - [ > S < < <
    i = 6 carvu = ( - ( [ > S < < <
    i = 7 carvu = ) - ( ( [ > S < < <
    i = 7 carvu = ) - S ( ( [ > S < < <
    i = 8 carvu = ) - ) S ( ( [ > S < < <
    i = 8 carvu = ) - S ) S ( ( [ > S < < <
    i = 8 carvu = ) - S ( [ > S < < <
    i = 9 carvu = ] - ) S ( [ > S < < <
    i = 9 carvu = ] - S ) S ( [ > S < < <
    i = 9 carvu = ] - S [ > S < < <
    i = 10 carvu = < - ] S [ > S < < <
    i = 11 carvu = { - < ] S [ > S < < <
    i = 12 carvu = [ - { < ] S [ > S < < <
    i = 13 carvu = ] - [ { < ] S [ > S < < <
    i = 13 carvu = ] - S [ { < ] S [ > S < < <
    i = 14 carvu = } - ] S [ { < ] S [ > S < < <
    i = 14 carvu = } - S ] S [ { < ] S [ > S < < <
    i = 14 carvu = } - S { < ] S [ > S < < <
    i = 15 carvu = > - } S { < ] S [ > S < < <
    i = 15 carvu = > - S } S { < ] S [ > S < < <
    i = 15 carvu = > - S < ] S [ > S < < <
    i = 16 carvu = > - > S < ] S [ > S < < <
    i = 16 carvu = > - S > S < ] S [ > S < < <
    i = 16 carvu = > - S ] S [ > S < < <
    i = 16 carvu = > - S > S < < <
    i = 16 carvu = > - S < <
    i = 17 carvu = > - > S < <
    i = 17 carvu = > - S > S < <
    i = 17 carvu = > - S <
    i = 18 carvu = $ - > S <
    i = 18 carvu = $ - S > S <
    i = 18 carvu = $ - S
    1112121131415351515
    jfp$ ./pp
    Donnez un mot candidat
    (([[]{{<<>(([[]{{<<>
    i = 1 carvu = ( - (
    i = 2 carvu = [ - ( (
    i = 3 carvu = [ - [ ( (
    i = 4 carvu = ] - [ [ ( (
    i = 4 carvu = ] - S [ [ ( (
    i = 5 carvu = { - ] S [ [ ( (
    i = 6 carvu = { - { ] S [ [ ( (
    i = 7 carvu = < - { { ] S [ [ ( (
    i = 8 carvu = < - < { { ] S [ [ ( (
    i = 9 carvu = > - < < { { ] S [ [ ( (
    i = 9 carvu = > - S < < { { ] S [ [ ( (
    i = 10 carvu = ( - > S < < { { ] S [ [ ( (
    i = 11 carvu = ( - ( > S < < { { ] S [ [ ( (
    i = 12 carvu = [ - ( ( > S < < { { ] S [ [ ( (
    i = 13 carvu = [ - [ ( ( > S < < { { ] S [ [ ( (
    i = 14 carvu = ] - [ [ ( ( > S < < { { ] S [ [ ( (
    i = 14 carvu = ] - S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 15 carvu = { - ] S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 16 carvu = { - { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 17 carvu = < - { { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 18 carvu = < - < { { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 19 carvu = > - < < { { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 19 carvu = > - S < < { { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 20 carvu = $ - > S < < { { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 20 carvu = $ - S > S < < { { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    i = 20 carvu = $ - S < { { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    erreur S < { { ] S [ [ ( ( > S < < { { ] S [ [ ( (
    jfp$