Algorithme d'analyse

La première phase est la construction de la liste des catégories des mots de la phrase à analyser. A l'aide des prédicats mot et categorie, on construit une liste dont chaque élément est la définition de la catégorie du mot correspondant. L'analyse se fera sur les deux listes en parallèle : la phrase et la liste des catégories.

C'est un simple parcours de liste en Prolog, réalisé par le prédicat liste_categories/2.

La deuxième phase est l'analyse ascendante. Une fois la liste des catégories construite, on peut appliquer les deux règles syntaxiques suivantes pour reconstruire l'axiome :

• $(x/y).y \to x$
• $y.(x\backslash y) \to x$

Le principal problème est de savoir dans quel ordre appliquer ces règles. On retrouve deux actions classiques en analyse syntaxique ascendante : le décalage et la réduction. Dans le cas de cet analyseur, on tentera toutes les réductions possibles avant de continuer l'analyse sur la suite de la phrase. L'algorithme est donc le suivant :

1.

Si l'une des règles est applicable, on l'applique et on poursuit l'analyse sur la nouvelle structure produite.  

2.

Si 1. a échoué (pas de règle applicable, ou poursuite de l'analyse impossible), on poursuit l'analyse sur le reste de la phrase, puis, on recommence en réintégrant la partie de la phrase mise temporairement de coté.

Puisque les deux règles s'appliquent sur deux éléments, il faut traiter le cas particulier correspondant au dernier mot de la phrase. Dans ce cas, le prédicat de réduction doit retourner le mot et la catégorie inchangés.

On notera au passage qu'à chaque application de règle, on mémorise le calcul effectuer, pour pouvoir le restituer à la fin de l'analyse.

Le prédicat reduire/4 prend quatre arguments :

• La phrase à analyser
• La liste des catégories correspondant aux mots de la phrase
• La phrase structurée après analyse
• La catégorie obtenue (`s' à la fin de l'analyse)

Lors des calculs, le point permet de marquer les deux catégories qui vont se simplifier. Les simplifications se font de la manière suivante :

• Réduction par la règle $(x/y).y \to x$ :

  reduire([A,B|LM],[(X/Y),Y|LC],NPH,NLC):-
      	memoriser([A,'.',B],[(X/Y),'.',Y]),
      	reduire([[A,B]|LM],[X|LC],NPH,NLC).
  

• Réduction par la règle $y.(x\backslash y) \to x$ :

  reduire([A,B|LM],[Y,(X\Y)|LC],NPH,NLC):-
      	memoriser([A,'.',B],[Y,'.',(X\Y)]),
      	reduire([[A,B]|LM],[X|LC],NPH,NLC).
  

• Analyse du reste de la phrase :

  reduire([A|LM],[X|LC],NPH,NLC):-
      	reduire(LM,LC,LM1,LC1),
      	LC\=LC1,         % sinon, ça boucle sur des morceaux irréductibles
      	reduire([A|LM1],[X|LC1],NPH,NLC).
  
  reduire(X,C,X,C).
  

Il faut aussi prévoir la mémorisation des étapes de calcul. On mémorise les calculs dans une pile dans l'espace de travail, pour ne pas alourdir le passage de paramètres dans la pile de Prolog. Pour cela, le prédicat liste_calculs possède un argument qui est la liste des calculs effectués depuis le début de l'analyse. Avant de commencer, le prédicat raz_calcul vide cette liste. Ensuite, à chaque étape, le prédicat memoriser permet d'empiler un couple (liste de mots, liste de catégories) correspondant à l'application d'une règle. Cependant, ce prédicat doit être réversible lorsqu'il y a plusieurs possibilités. Ainsi, un deuxième passage dans memoriser dépile la pile courante, et se termine par fail pour éviter de refaire la même analyse.