TP2 - Découpage et tri de mots dans un texte

Sommaire

Objectif

Dans ce deuxième devoir, vous aurez l’occasion de pratiquer les concepts suivants :

  • Les boucles ;
  • Les tableaux ;
  • Les routines et la décomposition fonctionnelle.

Problématique

Étant donné un texte composé de phrases, l’objectif est de découper ce texte en mots afin de former un tableau de mots, puis de trier les éléments de ce tableau. Votre programme doit gérer des textes d’un maximum de 300 caractères écrits en anglais (caractères dans la table ASCCI standard sur 7-bit). Les données doivent être saisies dans la section data de la mémoire.

texte:      .space   300
            .eqv     txtLen, 300   # Taille du tampon

Débordement de tampon

Si la capacité du tampon est dépassée, il faudra terminer le programme avec un message d’erreur Erreur : Tampon plein.

Test 1

Entrée

The Moon is Earth's only natural satellite. It orbits at an average distance of 384,400 km (238,900 mi),
about 30 times the diameter of Earth. Tidal forces between Earth and the Moon have synchronized the
Moon's orbital period (lunar month) with its rotation period (lunar day) at 29.5 Earth days, causing the
same side of the Moon to always face Earth. The Moon's gravitational pull-and, to a lesser extent, the
Sun's-are the main drivers of Earth's tides.

Sortie

Erreur : Tampon plein

Découpage en mots

Le texte saisi devra être découpé en mots pour créer un second tableau, appelé tableau de mots placé dans la section data de la mémoire.

tabMots:    .space  1800
            .eqv    tabLen, 1800   # Taille du tableau de mots

La taille maximale du tableau de mots est définie comme suit : en supposant que le tampon peut contenir 300 octets, le nombre maximum de mots est de 150, car il doit y avoir au moins un espace entre chaque mot. En supposant que chaque mot est composé d’une seule lettre, on arrive à ce nombre.

Un mot est défini comme une entité composée des lettres de l’alphabet latin (a-z, A-Z), qu’elles soient en minuscules, en majuscules, ou un mélange des deux.

Le tableau de mots peut être modélisé par une structure contenant deux champs : des pointeurs vers les mots respectifs et la longueur de ces mots.

Pour 150 mots au maximum, notre tableau de mots doit être composé de 150 * (8 octets pour l’adresse du mot + 4 octets pour la longueur du mot) = 150 * 12 = 1800 octets.

Tri de mots

Les mots devront être triés en réorganisant la table des mots.

On affiche en premier le tableau de mots non trié avec 4 mots par ligne séparé par un espace en chaque mot. Ensuite, on affiche le tableau de mots trié avec la même configuration de 4 mots par ligne.

Test 2

Entrée

a b c d e f g h 
j k l m n o

Sortie

a b c d
e f g h
j k l m
n o

a b c d
e f g h
j k l m
n o

Routines à créer

Contraintes des routines

Les routines doivent suivre les règles d’ABI vu en classe (utilisation du stack pour modifier les registres sauvegardés, registres pour les paramètres d’entrées et sorties, etc.). Les routines doivent aussi éviter d’utiliser des adresses de tableaux écrites directement avec des étiquettes. Si vous travaillez avec les espaces mémoire, il faut ajouter les paramètres qui enverront les adresses à utiliser.

Pour accomplir la tâche du TP, il sera nécessaire de créer au minimum les routines suivantes :

saisir

La routine saisir permet d’entrer et de sauvegarder le texte à traiter dans le tampon texte. La routine retourne le nombre de caractères saisis ou -1 en cas de débordement.

decMots

La routine decMots prend comme paramètre la taille (en octets) du texte saisi dans le tampon texte et forme le tableau des mots (tabMots) en découpant le texte initial. La dernière valeur dans le tableau de mots doit être -1 pour indiquer la fin. La routine decMots doit utiliser la routine isalpha comme routine auxiliaire.

isalpha

La routine isalpha prend comme paramètre un caractère et retourne 0 (faux) si ce caractère n’est pas une lettre, et 1 (vrai) dans le cas contraire.

afficher

La routine afficher affiche le contenu d’un tableau de mots ; 4 mots par ligne doivent être affichés, séparés par un espace. La routine afficher doit être appelée deux fois. La première fois après avoir découpé le texte en mots, et la deuxième fois après avoir réorganisé le tableau de mots à la suite du tri.

Test 3

Entrée

The Moon is Earth's only natural satellite.
It orbits at an average distance of 384,400 km,
about 30 times the diameter of Earth.

Sortie

The Moon is Earth
s only natural satellite
It orbits at an
average distance of km
about times the diameter
of Earth

Earth Earth It Moon
The about an at
average diameter distance is
km natural of of
only orbits s satellite
the times

trier

La routine trier réorganise les structures associées à chaque mot afin que ceux-ci soient triés par ordre alphabétique croissant, en utilisant la routine auxiliaire strCmp pour comparer les mots.

strCmp

Une routine permettant de comparer deux chaînes de caractères.

Les deux paramètres sont les adresses des deux structures contenant à leur tour les adresses des chaînes et leurs longueurs. La routine retourne -1 si la première chaîne est inférieure à la deuxième, 0 si les deux chaînes sont identiques, et 1 si la première chaîne est supérieure à la deuxième.

Test 4

Entrée

lll hhh aaa ttt Y
jjj jjjj aja
klm

Sortie

lll hhh aaa ttt
Y jjj jjjj aja
klm

Y aaa aja hhh
jjj jjjj klm lll
ttt

Test 5

Entrée

1234 5678 9000
5555a

Sortie

a

a

EXTRA

Important : Cette partie est avancée et vaut 2 points pour chaque EXTRA (donc 3 extras pour 6 points). Ne la faire que si tout le reste fonctionne et est d’excellente qualité. Les extras sont mutuellement exclusifs, il n’est pas attendu que les différents modes extra fonctionnent ensemble.

EXTRA1 - Alignement des mots

Si le premier mot du texte est extra1, ce premier mot ne sera pas écrit dans la liste de mot. La routine afficher sera modifiée pour trouver le nombre de lettres du plus grand mot du texte. Cela dans le but que les premières lettres des mots s’alignent avec la longueur du plus grand mot.

Test Extra 1

Entrée

extra1 one two three
four five six
seven

Sortie

one   two   three four
five  six   seven

five  four  one   seven
six   three two

Note : On remarque que le plus long mot est de 5 lettres et nous avons donc 5 caractères pour chaque mot (comblé avec des espaces).

EXTRA2 - Alignement par colonne

Si le premier mot du texte est extra2, ce premier mot ne sera pas écrit dans la liste de mot. La fonction afficher sera modifiée pour trouver le nombre de lettres du plus grand mot de chaque colonne d’affichage du texte. Cela dans le but que les premières lettres des mots s’alignent avec les mots qui seront dans leur colonne respective.

Test Extra 2

Entrée

extra2 one two three
four five six
seven

Sortie

one  two three four
five six seven

five four  one seven
six  three two

Note : On remarque que toutes les colonnes sont alignées avec le nombre minimum d’espaces.

EXTRA3 - Remplacement des contractions anglophone

Si le premier mot du texte est extra3, ce premier mot ne sera pas écrit dans la liste de mot. La fonction saisir va faire un travail spécial pour les contractions. Elles seront transformées en mots. Les contractions sont les mots incomplets qui sont collés à un premier mot suivi d’un guillemet. Faire attention à la contraction avec 't' comme don't qui change le premier mot aussi en se remplaçant par do not.

NOTE de conception: Les appartenances qui utilise 's seront considérés comme étant le mot is pour facilité l’implémentation. Nous ne tiendrons pas non plus compte des contractions qui donne un mot comme can't qui sera converti en can not.

Voici une liste des contractions à implémenter:

Contraction Mot complet
I’m I am
you’re you are
he’s he is
she’s she is
it’s it is
we’re we are
they’re they are
I’ve I have
you’d you would
I’ll I will
don’t do not
isn’t is not

Test Extra 3

Entrée

extra3 Please
don't cut me off

Sortie

Please do not cut
me off

Please cut do me
not off

Note : On remarque que les deux affichages ont les versions remplacées.

Réalisation

La réalisation de ce programme se fera par groupes, d’au plus, deux personnes. Chaque membre de l’équipe devra maîtriser tous les aspects du programme.

Contraintes d’implémentation:

  • Votre programme doit fonctionner avec RARS 1.7 en mode 64 bits (voir site du cours).
  • Il faudra respecter les conventions d’appel.

Évaluation

Aptitude fonctionnelle

  • 40%: tests publics (chaque test vaut 50*ceil(1/nombre de tests)).
    Les tests publics sont ceux présentés ci-dessus.

  • 60%: plusieurs tests privés évalués par le correcteur après la remise.
    Il est donc de votre responsabilité de vous assurer que votre programme fonctionne correctement au-delà des tests publics fournis.

Pour vous aider, le script de correction qui sera utilisé qui inclus tous les tests est disponible à https://gitlab.info.uqam.ca/inf2171/20243/tp2-corrige.

Important: si le programme remis ne s’assemble pas (erreur de syntaxe, fichier corrompu, etc.) ou si aucun test ne passe avec l’outil (échec systématique), la note zéro sera automatiquement attribuée au TP, et ce, indépendamment de la qualité du code, du temps de développement passé ou des affichages de RARS sur l’ordinateur de l’étudiant.

Qualité et lisibilité du code source

Des points bonus et malus seront attribués en fonction de la qualité du code.

  • Indentation et aération.
  • Nommage adéquat des symboles.
  • Présence et pertinence des commentaires.
  • Organisation du code, simplicité, modularité.

Les critères sont plus détaillés dans le guide de style.

Modalités de remise et dates

  • Date de remise: vendredi 15 novembre à 23h59.
  • La remise se fait via Moodle.
    • Remettez un seul fichier appelé mots.s (pas d’archive, juste ce fichier)
    • Mettez les noms, prénoms et codes permanents des étudiants du groupe en commentaire au début du fichier.
    • Dans un groupe de deux étudiants, un seul étudiant doit remettre.
    • Seule la remise la plus récente est considérée. Vous pouvez remettre autant de fois que vous le voulez avant l’échéance.
  • Si vous ne voulez pas perdre de points, assurez-vous de respecter le guide de style