TP1 Équilibre de parenthèse

Sommaire

L’objectif du TP1 est de développer un programme valide.s en assembleur RISC-V qui valide un programme sous forme de S-expressions. La validation vérifie que les parenthèses du programme sont équilibrées (autant de parenthèses ouvrantes que fermantes) qui est l’erreur typique du langage.

Nombres d’ouverture

La première étape est de vérifier le nombre de pairs de parenthèses. Cette information sera affichée suivie du texte “OK”. NOTE : Les entrées se terminent par une fin de fichier et l’appel système pour la lecture de caractère va retourner la valeur -1 à ce moment.

Test 1

Entrée

(defun factorial (N)
  (if (= N 1)
      1
    (* N (factorial (- N 1)))))

Sortie

7 OK

Emplacement d’une mauvaise fermeture

Dans le cas où nous fermons une parenthèse sans avoir de parenthèses ouvrantes correspondantes, le programme se termine et affiche la ligne et la colonne ou se trouve la parenthèse sous la forme “)lLcC” ou L et C sont les numéros de ligne et colonne où se trouve la parenthèse fermante problématique.

Test 2

Entrée

(defun factorial (N)
  ((if (= N 1))))
      1)
    (* N (factorial (- N 1)))

Sortie

)l3c8

Trop d’ouvertures

Dans le cas inverse, où l’on retrouve trop de parenthèses ouvrantes et pas assez de parenthèses fermantes, le programme se termine et on affiche le nombre de parenthèses “non fermés” suivi du texte “ERR”.

Test 3

Entrée

(defun factorial (N)
  ((if (= N 1)
      (1
    ((* N (factorial (- N 1)))))

Sortie

3 ERR

Commentaire sur une ligne

Les programmes à valider supporte les commentaires de style C avec des // pour un commentaire qui s’étend jusqu’à la fin de la ligne. Les parenthèses devront donc être ignorées durant un commentaire.

Test 4

Entrée

(defun factorial (N)
  // (if (= N 1)
      1
    (* N (factorial (- N 1)))))

Sortie

)l4c31

Commentaire sur plusieurs lignes

Notre valideur doit aussi supporter les blocs de commentaires délimités par des /* et */. Tout ce qui est entre les délimiteurs n’est pas considéré.

Test 5

Entrée

(defun factorial (/*N)
  (if (= N 1)
      1
    (* N (factorial */(- N 1)))))

Sortie

)l4c32

Dans le cas où un bloc de commentaire n’est pas fermé à la fin du programme, le message d’erreur “C ERR” est affiché.

Test 6

Entrée

(defun factorial (/*N)
  (if (= N 1)
      1
    (* N (factorial (- N 1)))))

Sortie

C ERR

Traitement des crochets en plus de parenthèses

Pour augmenter la lisibilité du langage, on peut utiliser soit des parenthèses ou des crochets (braquettes carrées) [] pour créer des ouvertures et des fermetures. On compte les deux types d’ouvertures dans la sortie.

Test 7

Entrée

(defun factorial (N)
  [if [= N 1]
      1
    (* N (factorial (- N 1)))])

Sortie

7 OK

Dans le cas où une braquette fermante est de trop, on affiche la ligne et la colonne sous la forme “]lLcC”. On note que le premier caractère indique quel type fermeture est problématique.

Test 8

Entrée

(defun factorial (N)
  [if [= N 1]
      1
    (* N (factorial (- N 1)))])]

Sortie

]l4c32

Concordance des symboles les plus proches

Nous souhaitons finalement vérifier que chaque symbole de fermeture correspond au dernier symbole d’ouverture rencontré. Si le symbole de fermeture ne correspond pas au symbole d’ouverture le plus récent, nous le signalons comme une fermeture incorrecte. Note : Seul le symbole d’ouverture le plus proche est pris en considération lors de cette vérification.

Par exemple :

Considérons le code suivant :

[defun add (x y)
  (return x + y]]

Dans cet exemple, le premier symbole d’ouverture est un de la deuxième ligne est une parenthèse (, mais le symbole de fermeture correspondant est une braquette ]. Cela brise la validation, car le symbole de fermeture ne correspond pas au symbole d’ouverture le plus récent.

Test 9

Entrée

(defun factorial (N)
  [if [= N 1)
      1
    (* N (factorial (- N 1]))])

Sortie

)l2c13

EXTRA - Plusieurs niveaux de concordance entre parenthèses et crochets

Important : Cette partie est avancé et ne vaut que 2 points. Ne la faire que si tout le reste fonctionne et est d’excellente qualité.

La niveau de concordance doit marcher pour tous les niveaux.

Test EXTRA

Entrée

(defun factorial (N)
  [if [= N 1]
      1
    (* N (factorial (- N 1)))))

Sortie

)l4c30

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).
Saut avis contraire, il ne faut pas utiliser d’instructions au-delà du chapitre 3 comme l’accès à la mémoire (load ou store) ou l’utilisation de routines. De toute façon, pour ce TP elles compliqueraient votre solution plus qu’autre chose. Ce qui fait que la section .data ou la pseudo-instruction la sont interdites par exemple. Dans le doute, demandez.
Il n’est pas demandé de gérer les cas de débordement arithmétique.

Évaluation

Aptitude fonctionnelle

50%: tests publics (chaque test vaut 50*ceil(1/nombre de tests)).
Les tests publics sont ceux présentés ci-dessus.
50%: 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/tp1-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: lundi 14 octobre à 23h55.
La remise se fait via Moodle.
- Remettez un seul fichier appelé valide.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