Prolog
TD n°4
But du TD
Réaliser une « analyse syntaxique » rudimentaire des questions de la forme « qui est le/la père/mère/frère/soeur... [du/de la père/mère/frère/soeur...[...]] de andré/augustine/bernard... » (les crochets designent ce qui est facultatif, les barres obliques « / » désignent les choix multiples) sachant que :
- on a le droit d'emboîter autant de relations de parenté que l'on veut ;
- les noms à la fin sont ceux présents dans votre arbre généalogique (du TD n°1) ;
- une question sera codée sous la forme d'une liste de mots ;
- l'analyse a pour but de tester la grammaticalité de la question indépendamment de son sens, elle vérifie simplement que la question est correctement posée (en particulier ses accords en genre et en nombre devront être vérifiés), pas qu'elle a une réponse dans l'arbre !
Autrement dit, on vise l'écriture d'un prédicat analyse(L) qui est vrai si L est une liste de la bonne forme, faux sinon.
Problème
Ces questions sont construites sur un vocabulaire fini mais il y en a une infinité possible à cause des appels successifs non bornés autorisés. Il va falloir utiliser de la récursivité !
Solution
L'analyse syntaxique va être réalisée par un dispositif très utile en informatique : un automate fini.
Automates
Définition
Un automate est un dispositif constitué de :
- un vocabulaire fini : ici, ce sera l'ensemble des mots autorisés dans les questions ;
- un ensemble fini d'états, parmi lesquels :
- au moins un état initial,
- au moins un état final ;
- un ensemble fini de transitions : une transition est une flèche dont le point de départ et le point d'arrivée sont des états (éventuellement le même) et portant une étiquette prise dans le vocabulaire.
Un chemin dans un automate commence nécessairement à partir d'un état initial, suit les transitions et aboutit à un état final. Une suite de mots est reconnue par l'automate s'il existe un chemin dans cet automate dont les transitions successives coincident avec cette suite de mots.
Un automate réalise exactement ce que l'on veut, à savoir trier un suite de mots en correcte ou pas correcte.
Remarques
- Un automate est un cas particulier de machine de Turing La seule différence est qu'il n'a pas de ruban associé (pas de mémoire, donc) et que les étiquettes des transitions sont, de ce fait, plus simples.
- Si vous avez des notions de théorie des graphes, un automate est aussi un cas particulier de graphe.
- Pour ceux d'entre vous qui connaissent les grammaires formelles : un automate est aussi un cas particulier de grammaire formelle :
- le vocabulaire, ici constitué de mots, coincide avec le vocabulaire terminal d'une grammaire ;
- les états jouent le rôle de symboles non terminaux ;
- s'il existe une transition entre un état correspondant au symbole non terminal A et aboutissant à un état final, avec l'étiquette a, cela correspond à une règle de la forme A --> a ;
- s'il existe une transition entre un état correspondant au symbole non terminal A et aboutissant à un état correspondant au symbole non terminal B avec l'étiquette a, cela correspond à une règle de la forme A --> aB.
Exercices sur papier : l'automate
- Écrire (sur papier) un automate qui reconnaît tous les groupes nominaux masculins singuliers possibles des questions, sans emboîtement : le père/frère/grand-père... de andré/augustine/bernard.
Attention aux cas particuliers « oncle », « enfant » et « ancêtre » : comme ils commencent par une voyelle, ils sont précédés de « l' » et non de « le ».
- Écrire maintenant la même chose pour les groupes nominaux féminins singuliers, puis assembler les deux, et compléter pour avoir un automate avec un seul état initial et reconnaissant les questions quelconques avec un seul lien de parenté (sans emboîtement). Numéroter les états : l'état initial a le numéro 1.
- Que faut-il ajouter pour emboîter les liens de parenté ?
Traduction en Prolog
Pour traduire en Prolog ce que réalise cet automate, il suffit de se rendre compte qu'en fait, chaque état (de numéro n) de l'automate peut être associé à un prédicat étatn(L) qui est vrai si la liste L permet, à partir de l'état n, d'arriver à un état final. Alors, le prédicat analyse(L) se confondra avec le prédicat etat1(L).
Il reste à donner la définition de chacun des prédicats étatn(L) :
Dernière modification : 9/9/2011
