Informatique et recherche
opérationnelle
IFT2030

Concepts des langages de programmation

Automne 2002


Accueil

Professeur et
Démonstrateurs

Horaires et locaux

Notes de cours

Démonstrations
et devoirs

Examens

Liens utiles

Au sujet du
livre de cours

Consultez vos notes

Foire aux questions
(FAQ)

TP3: Mini moteur de traduction

Avant propos

Prolog a été développé à Marseille dans le but de faciliter la mise au point des applications langagières. Alain Colmarauer a fait un séjour à l'université de Montréal pendant lequel il a avec des membres de l'université développé un système de traduction pour les bulletins météorologiques. Ce système appelé METEO est un des rares succès de la traduction automatique et le système (du moins, un de ses descendants) continue d'être utilisé pour traduire automatiquement les bulletins météo canadiens (vous comprenez maintenant pourquoi les prédictions sont souvent mauvaises).

À votre tour de développer votre système de traduction...

Cadre général

Le programme que vous allez écrire doit traduire des phrases du français vers l'anglais. Le principe de base du traducteur que vous allez écrire tient en trois phases: l'analyse grammaticale (et oui encore des grammaires ...) de la phrase source (française) à traduire, le transfert de la structure syntaxique ainsi identifiée vers une structure cible (anglaise), puis la génération de la traduction (anglaise) à l'aide de la structure syntaxique cible trouvée à l'étape précédante.

En fait c'est avec ces trois étapes que sont développés la plupart des systèmes de traduction que vous pouvez utiliser sur le web. Rassurez-vous, vous avez trois semaines pour développer votre système, aussi, allons-nous travailler sur un très petit sous-ensemble des langues française et anglaise, et les contraintes d'analyse, de transfert et de génération sont simplifiées à l'extrême.

Cahier des charges

1- Analyse

Pour faire l'analyse de la phrase source, vous allez avoir besoin d'informations lexicales qui sont codées dans des faits (Prolog) qui vous sont énoncés dans ce fichier lexique.pl. Ces faits devront êtres utilisés par votre programme. Ce lexique contient les informations pertinentes de chaque entrée:

  • pour les noms communs (nc), pronom (pro), adjectifs (adj), nom propres (np) et articles (art): le genre et le nombre,

    Le genre d'un mot indique s'il est féminin (fem) ou masculin (masc). Notez que certains mots n'ont pas de genre (ex: stupide) et dans ce cas ces mots peuvent-être employés au féminin comme au masculin. Le nombre d'un mot indique si le mot est au singulier (sing) ou au pluriel (plur).

  • pour les verbes (vb): le mode du verbe.

    Le mode d'un verbe peut pendre deux valeurs: cod, dans le cas de verbes qui peuvent prendre un complément d'objet direct (ex: manger (une pomme)), et coi, pour les verbes qui doivent pendre un complément d'objet direct et optionnellement un complément d'objet indirect (ex: donner une pomme (à Adam)).

Les règles grammaticales pour l'analyse syntaxique de la phrase source sont exprimées ci-après dans un langage BNF étendu où le genre, nombre et mode (dans le cas des verbes) sont exprimés entre parenthèse. Les crochets indiquent un non-terminal optionel.

Règles grammaticales

R1  Phrase(g,n) -> Sujet(g,n) GroupeVerbal(n) [Complement]
R2  Phrase(g,n) -> Complement Sujet(g,n) GroupeVerbal(n) [Complement]

R3  Sujet(g,n) -> Pronom(g,n)
R4  Sujet(g,n) -> NomPropre(g,n)
R5  Sujet(g,n) -> GroupeNominal(g,n)

R6  GroupeNominal(g,n) -> Article(g,n) [Adverbe] [Adjectif(g,n)] NomCommun(g,n)
R7  GroupeNominal(g,n) -> Article(g,n) NomCommun(g,n) [Adverbe] [Adjectif(g,n)]

R8  GroupeVerbal(n) -> Verbe(cod,n) [ComplementDirect]
R9  GroupeVerbal(n) -> Verbe(coi,n) ComplementDirect [ComplementIndirect]

R10 ComplementDirect -> NomPropre(g,n)
R11 ComplementDirect -> GroupeNominal(g,n)

R12 ComplementIndirect -> a ComplementDirect

R13 Complement -> Adverbe
R14 Complement -> Preposition GroupeNominal(g,n)

Après le cours que nous avons eu, la sémantique de cette grammaire devrait vous être familière. À toutes fins utiles, voici une lecture possible des règles décrivant les groupes nominaux (R6 et R7): un groupe nominal de nombre n et de genre g est constitué d'un article dont le genre et nombre correspondent à ceux du groupe nominal, suivi optionnellement d'un adverbe, d'un adjectif (en genre et nombre adéquats), d'un nom commun (en genre et nombre correspondants), suivi enfin optionnellement d'un adverbe et d'un adjectif (de genre g et de nombre n).

Les non terminaux de cette grammaire font référence au lexique (à vous de faire le lien). Voici deux exemples de phrases reconnues avec cette grammaire:

le chat boit le lait
le stupide professeur raconte des histoires
et une phrase non reconnue (car le groupe sujet est au pluriel alors que le groupe verbal est au singulier).
les etudiants deteste le professeur

2- Transfert

Toutes les règles syntaxiques se transferent dans la langue cible (anglais) sans modification. Pour quelques constructions précisées ci-après, il est possible également d'observer les transformations qui sont indiquées. Prenez note que le genre, nombre et mode (pour les verbes) des groupes syntaxiques se conservent d'une langue à l'autre (un nom au pluriel en français aura une traduction au pluriel en anglais).

Règles de transfert

T1  Sujet GroupeVerbal Complement -> Sujet Complement GroupeVerbal
T2  Sujet GroupeVerbal Complement -> Complement Sujet GroupeVerbal
T3  Article NomCommun [Adverbe] [Adjectif] -> Article [Adverbe] [Adjectif] NomCommun
La règle T1 indique que la traduction d'une phrase constituée d'un sujet, d'un groupe verbal et d'un complément peut se traduire en inversant le complément et le groupe verbal; la règle T2 dit que le conplément en anglais peut être au début de la phrase. La règle T3 indique que les optionnels adverbes et adjectifs en fin de groupe nominal peuvent se déplacer devant le nom commun qu'ils qualifient.

3- Génération

Une fois une structure syntaxique cible établie, il ne vous reste plus qu'à générer la phrase cible. Cela se fait à l'aide des faits Prolog précisés dans le fichier transfert.pl. Le premier prédicat est la forme française à traduire, le second est sa traduction en anglais ou une liste de traductions si plusieurs traductions sont possibles.

Prédicats à écrire

analyse(X,Y)

Prédicat qui est effacé lorsque la structure syntaxique Y est associable à la phrase française X. La phrase est représentée par une liste d'atomes (les mots de la phrase).

Par exemple, la phrase "Paul aime les poires terriblement" représentée par la liste [paul,aime,les,poires,terriblement] est reconnaissable par la grammaire et voici son arbre syntaxique (on vous laisse le choix de représenter cette structure) que je représente ici sous forme de liste facon Scheme:

Phrase(Sujet(NomPropre(masc,sing)),GroupeVerbal(Verbe(cod,sing),ComplementDirect(GroupeNominal(Article(fem,plur),NomCommun(fem.plur)))),Complement(Adverbe(terriblement)))

Note 1: Votre représentation doit au moins faire mention des informations pertinentes ici présentes (genre, nombre, cod), vous pouvez ajouter toutes celles qui faciliterait l'étape de transfert et de génération.

Note 2: En pratique, vues les règles de transfert simplistes auxquelles on a affaire, il n'est pas nécessaire de maintenir dans la struture syntaxique source l'information du genre et du nombre. Le transfert ne modifie en effet pas les genres, nombres ou modes des groupes de la phrase source analysée. On vous demande cependant de le faire ici.

transfert(X,Y)

Prédicat qui est effacé lorsque Y, une structure syntaxique cible est la transformation valide par les règles décrites plus haut de la structure source X.

La structure de l'exemple précédant peut être transférée en anglais vers l'une des trois structures suivantes:

  • Aucune application de règle de transfert (la structure reste la même):
    Phrase(Sujet(NomPropre(masc,sing)),GroupeVerbal(Verbe(cod,sing),ComplementDirect(GroupeNominal(Article(fem,plur),NomCommun(fem.plur)))),Complement(Adverbe(terriblement)))
    
  • Application de la règle T1 - permutation du groupe verbal et du complément:
    Phrase(Sujet(NomPropre(masc,sing)),Complement(Adverbe(terriblement)),GroupeVerbal(Verbe(cod,sing),ComplementDirect(GroupeNominal(Article(fem,plur),NomCommun(fem.plur)))))
    
  • Application de la règle T2 - le complément vient en tête:
    Phrase(Complement(Adverbe(terriblement)),Sujet(NomPropre(masc,sing)),GroupeVerbal(Verbe(cod,sing),ComplementDirect(GroupeNominal(Article(fem,plur),NomCommun(fem.plur)))))
    

Note: Si le groupe nominal avait contenu un adjectif après le nom, alors il y aurait 6 structures possibles pour la phrase exemple dues à l'application possible de la règle T3.

genere(X,Y)

Prédicat qui est effacé lorsque la phrase cible Y, est une génération possible à partir de la structure cible X, selon les règles de transfert indiquées plus haut.

Note:Pour une structure donnée, il y a possiblement plusieurs phrases cibles car à un mot source peuvent être associées plusieurs traductions.

traduit(X,Y)

Prédicat qui est effacé lorsque la phrase cible Y, est une traduction valide (au sens défini par les règles décrites plus haut) de la phrase source X.

Note: Ne vous etonnez pas qu'une phrase anglaise non valide (mais cependant résultant du procédé décrit) puisse être générée par votre moteur de traduction: les règles d'analyse et de transfert sont trop rudimentaires pour assurer une qualité de traduction raisonable (nous ne parlons même pas de sémantique dans ce devoir).

BONUS

À ne faire que si vous avez déjà parfaitement fait tout le reste !
Modifiez votre programme de manière à ce qu'il devienne réversible, c'est à dire que:
  • vous pouvez aussi bien donner à votre prédicat traduit une phrase anglaise; votre programme doit alors afficher les phrases françaises associées.
  • votre prédicat traduit est capable de dresser la liste de toutes les paires (phrase source, phrase cible) où les phrases sources sont toutes les phrases sources reconnues par la grammaire et les phrases cibles associées sont toutes celles qui en sont les traductions.


Consignes

Nous testerons votre programme -- qui doit porter le nom tp3.pl à l'aide d'un fichier de test dont voici un exemple:test.pl. Cet exemple vous montre clairement que vous ne pouvez pas renommer les prédicats qu'on vous demande de coder. Il devrait également vous convaincre que vous ne devez pas modifier les fichiers lexique.pl et transfert.pl.

Nous vous encourageons de remettre ce TP par groupe de deux (ce TP se prête bien au travail "séparé"). Cependant, si vous travaillez seul(e), il est préférable de remettre seul(e). Vous devez remettre un seul fichier qui doit nécessairement porter le nom tp3.pl. Une seule remise par binôme. Votre fichier doit indiquer en entête le nom des auteurs (vous et votre binôme si vous travaillez à deux).


Procédure de remise, date limite, barême

La commande de remise est la suivante (prenez garde de remettre sous pift2030 et pas dift2030):
remise pift2030 TP3 tp3.pl
Pour ceux qui ne sont pas familiés avec la commande remise, tapez man remise dans un terminal.

Vous avez jusqu'à lundi 16 décembre 2002 midi pour remettre votre travail. Vous êtes notés sur 15 points. Plus que jamais, la notation dépendra des critères suivants:

  • conformité au cahier des charges et consignes,
  • exactitude,
  • qualité du code,
  • lisibilité, commentaires,
  • adaptabilité (votre code devrait être pensé de manière générique: une solution où vous énuméreriez sous forme de faits, toutes les paires source,cible serait un bel effort de votre part, mais en aucun cas une solution).

Prenez le temps de lire ce sujet, et n'oubliez pas que vos démonstrateurs et moi-même sommes là pour toutes vos questions. Bon courage.

[top]


Dernière mise à jour : Sun Dec 15 18:58:03 EST 2002
dift2030@iro.umontreal.ca