Best viewed in 24pt and full-screen

Prolog et grammaires logiques

L'expérience montre que les constituent un outil de programmation simple d'emploi, puissant et flexible. Cela vient de ce que le langage des est celui des grammaires sans contexte avec attributs, que ces grammaires sont traduites en un programme qui peut fonctionner comme un analyseur ou comme un générateur, et que tout le langage Prolog peut être utilisé pour décrire les attributs. Nous avons voulu transposer cet outil à Prolog et plus généralement étudier ce que pourrait être une grammaire logique fondée sur les formules héréditaires de Harrop*.

Il faut noter que la traduction de en Prolog est un exemple de métaprogrammation* en Prolog où la tradition utilise la représentation non-close* des grammaires et des programmes objet (voir la section «Métaprogrammation en Prolog et Prolog»*). La première version publiée de ce traducteur [Clocksin et Mellish 81], qui en a influencé beaucoup d'autres, contenait une erreur de manipulation de métavariable qui causait, rarement, la génération d'un programme faux. Notre travail de transposition des à Prolog a donc d'abord porté sur le métaprogramme de traduction de à Prolog (en Prolog), puis sur la définition d'une variante de pour Prolog, et enfin sur la traduction de cette variante en Prolog.

Le résultat est un formalisme appelé * (pour Higher-order Hereditary Harrop Grammar -- grammaire de Harrop héréditaire d'ordre supérieur) qui intègre les formules de Harrop au niveau grammatical et au niveau du calcul des attributs [Le Huitouze et al. 93a]. Au niveau grammatical, l'implication correspond à la faculté d'ajouter à la grammaire de nouvelles règles pendant la durée du dépliement d'un non-terminal. Au niveau du calcul des attributs, l'implication correspond à la faculté d'ajouter au programme de nouvelles règles de calcul pendant la durée du dépliement d'un non-terminal, et la quantification universelle correspond à la faculté de construire une structure sémantique (un attribut) qui est une fonction de la variable universellement quantifiée. Un nouveau connecteur permet d'établir le lien entre une occurrence d'un non-terminal et le mot qu'il engendre en cette occurrence.

L'augmentation locale de la grammaire permet de décrire aisément des déclarations locales de symboles, ou des phénomènes d'extraposition en langue naturelle. Par exemple, la règle suivante décrit l'effet à distance du pronom relatif sur la structure de la phrase relative qu'il introduit.

relative --> $ ["dont"] ( groupe_nom --> $ [] ==> phrase ) .

Dans la syntaxe des , --> est le signe de production, est le signe de concaténation, le signe $ introduit des terminaux du langage engendré et ==> est le signe d'introduction dynamique de nouvelles règles. Cette règle se lit donc de la manière suivante : le pronom relatif «dont» marque le début d'une phrase dans laquelle un groupe nominal est vide. La règle présentée n'est qu'un schéma. Une règle plus complète a des attributs pour contrôler l'accord en mode du groupe nominal vide (complément introduit par un «de») et construire une représentation sémantique pour la relative (une fonction dont le pronom est le paramètre formel).

La production de structures sémantiques fonctionnelles est le corollaire de la représentation par abstraction* utilisée en métaprogrammation en Prolog. C'est aussi le codage naturel des grammaires de Montague pour la langue naturelle [Montague 74, Warren 83b, Miller et Nadathur 86a, Coupet-Grimal et Ridoux 95]. Par exemple, la règle suivante est une variante de la règle précédente qui décrit en plus une partie des structures sémantiques associées aux non-terminaux.

relative REL --> $ ["dont"] all compl( groupe_nom compl --> $ [] ==> phrase (REL compl) ) .

On y voit que la structure sémantique REL est une fonction d'un type qui lui permet d'être appliquée à la structure sémantique d'un groupe nominal.

En , on ne peut vérifier qu'une séquence de terminaux obéit à une contrainte donnée qu'en construisant la contrainte au fur et à mesure de la génération des terminaux. Cela nuit au partage des règles de grammaires puisque des segments obéissant à la même syntaxe, mais vérifiant des conditions sémantiques différentes doivent être décrits par des non-terminaux différents. On a besoin d'une construction qui permet de capturer une séquence engendrée par un non-terminal, pour vérifier sa sémantique à part. Nous avons appelé ce connecteur delta. Il relie un non-terminal et un prédicat, et engendre ce que le non-terminal engendre et qui vérifie le prédicat. On peut penser que ce connecteur manquait déjà en . Par exemple, la règle suivante décrit des mots engendrés par le non-terminal nt1 et qui sont de longueur L.

nt0 L --> delta entréesortie(dlength entrée sortie L) nt1 .

La traduction de en Prolog par Prolog est très régulière et concentre la manipulation des variables objet dans la définition d'un petit nombre de combinateurs (un par connecteur). Cela rend improbable l'erreur commise dans la première version des . Par exemple, le traitement de la concaténation consiste en les déclarations et définitions suivantes.

La déclaration de type

type '' ((list A)->(list A)->o) -> ((list A)->(list A)->o) -> ((list A)->(list A)->o) .

donne le type du connecteur de concaténation. Pour fixer les idées, nous avons adopté pour la représentation des mots la technique des listes en différence*, qui est aussi la plus souvent employée dans les . Les mots sont représentés par des paires de listes qui correspondent, l'une à leur début, l'autre à ce qui suit leur fin. Un non-terminal est un prédicat sur les mots (donc de type ), et le connecteur de concaténation joint deux non-terminaux pour en construire un troisième. Une déclaration d'opérateur spécifie que la concaténation a une notation infixe associative à droite.

La déclaration de macro

#define CONC gauchedroitees( sigma Lien(gauche e Lien, droite Lien s) )

donne la sémantique de la concaténation sous la forme d'un combinateur qui construit la jointure des prédicats gauche et droite par la variable Lien. Celle-ci est une variable objet représentée par une -variable (Lien(...)). C'est la seule mention de variable objet. Noter aussi l'usage de l´ordre supérieur* : gauche et droite quantifient des prédicats. Cette déclaration n'est pas strictement nécessaire, mais elle permet de donner un nom à un combinateur qui pourra servir plusieurs fois.

La clause

(Item1 Item2) Entrée Sortie :- CONC Item1 Item2 Entrée Sortie .

donne la sémantique de la concaténation en utilisant le combinateur CONC dans une règle d'interprétation. Il n'est plus question de variable objet. Cette clause n'est nécessaire que parce que toute la traduction ne peut pas être faite pendant la compilation. En effet, il est possible d'avoir des non-terminaux inconnus lors de la traduction de la grammaire, et ceux-ci ne seront connus que pendant l'exécution. C'est le cas lorsque l'on code en l'étoile de Kleene.

opt NT --> ( $ [] : NT ) .

etoile NT --> opt ( NT etoile NT ) .

Le non-terminal NT n'est pas connu lors de la traduction de la grammaire.

Enfin, la clause

type trad_item ((list A)->(list A)->o) -> (o->o->o) -> o .

trad_item (Gauche0 Droite0) (CONC Gauche Droite) :- trad_item Gauche0 Gauche , trad_item Droite0 Droite .

donne la sémantique de la concaténation en utilisant le combinateur CONC dans une règle de traduction vers un programme Prolog. Là encore, il n'est plus question de variable objet. Cette clause serait la seule utile si tous les non-terminaux étaient connus à la compilation.