CSC 4508 - Traduction: CF1 TP noté, 22 Mai 2015 Corrigé

0 - Consignes

Rendre sur la plate-forme Moodle, une archive Nom.tar.gz (ou .tgz) contenant uniquement les fichiers utiles. C'est-à-dire :

• les spécifications *.flex, *.bison
• le ou les fichiers Makefile
• les éventuels fichiers *.c *.h pour des codes complémentaires de l'analyseur.
• des fichiers d'exemples ou de test (*data*)
• un fichier README pour les explications et les commentaires éventuels.

Par contre :

• pas de binaire (a.out,..)
• pas de backup de l'éditeur (foo~, #bar...)
• pas de fichiers intermédiaires (lex.yy.c, gram.tab.h, yyparse.h, yylex.c ..).
• (>make clean #peut aider)

Prévoir éventuellement de rendre plusieurs versions pour le même exercice. Par exemple : une version qui marche mais fait presque rien et une version qui fait presque tout mais ne marche pas du tout !

Les 3 parties du TP sont indépendantes et de poids différents :

• I Nombres Romains : 4-5 points, 30-45 minutes
• II Addition selon Turing : 4-5 points, 30-45 minutes
• III Expressions Vectorielles : 10-12 points, 90-120 minutes

I - Nombres Romains (flex seul)

Pour une description détaillée des nombres romains, on pourra consulter les pages Wikipedia Numération Romaine ou Roman numerals

On se limitera à l'usage "classique" des nombres romains entre 1 et 4999 construits à partir des chiffres :

• Les romains ou les latins ne connaissaient pas le chiffre ou le nombre zéro, mais l'on pourra en accepter le principe dans l'analyseur et assimiler le mot vide à la valeur 0.
• Pour les tests, on fournit le code genrom.c qui écrit ligne à ligne les nombres romains de 1 à N.
• On appellera calculus d'un nombre, le nombre de chiffres utilisés dans son écriture romaine. calculus(CXXIV)=5
• Remarque sans intérêt : les déclinaisons latines de "calculus" sont "calculus, calcule, calculum, calculi, calculo, calculo" et au pluriel "calculi, calculi, calculos, calculorum, calculis, calculis".

Travail demandé

• Écrire un analyseur lexical qui reconnaît les nombres romains entre 1 et 4999. Tester avec les nombres valides (genrom.c) et Fournir un fichier de test avec des contre-exemples (nombres invalides bien choisis).
• On considère en entrée, un fichier contenant un ensemble de nombres romains.
  Compléter l'analyseur pour :
  • écrire la valeur maximum du calculus des nombres du fichier
  • écrire la fréquence de chaque valeur de calculus, c'est à dire combien d'entrées ont pour calculus 1, 2,....jusqu'a calculus_Max
  • écrire les Maxima Locaux de calculus, c'est à dire la première entrée qui a un calculus de 1, puis de 2,... jusqu'a calculus_Max
  Nota Bene: Les différents éléments peuvent être écrits en sortie dans l'ordre qui convient le mieux au développeur.

II - Addition selon Turing (bison seul)

Sur l'alphabet Σ={a,b,c}, on considère le langage L = { aⁿb^pc^n+p | p≥0,n≥0 }.
Prouvez que ce langage est algébrique déterministe. (Oups ! de la théorie !)

En pratique, construisez une spécification Bison sans conflit qui reconnaît le langage L.
Le langage est alors algébrique puisque décrit par une grammaire context-free, et déterministe puisque reconnaissable sans conflit par Bison.

Travail demandé

• Écrire sous forme d'une spécification Bison, une grammaire non ambiguë pour reconnaître le langage L.
• Vérifier que Bison compile sans conflit cette grammaire et vérifier sur des exemples que la grammaire semble correcte.
• Vérifier expérimentalement la propriété suivante :
  Le nombre de mots dans L de taille N vaut N/2+1 si N est paire, et 0 sinon.

Indications

On pourra, par étape, rechercher des grammaires context-free pour :

• L₀ = { xⁿyⁿ | n≥0 }
• L₁ = { zⁿ W tⁿ | W ∈ L₀, n≥0 } = { zⁿx^py^ptⁿ | p≥0, n≥0 }
• et obtenir L en faisant z=a, x=b, y=t=c.

On propose un squelette de spécification alan.bison qui permet de se passer de Flex. Utilisation : " bison -o alan.c alan.bison; gcc -o alan alan.c "

On donne aussi le code Astar.c qui permet de générer tout les mots de taille donnée sur un alphabet. Si on adapte la spécification pour compter et imprimer le nombre total de lignes syntaxiquement correctes, on aura la vérification expérimentale sous la forme "Astar abc N | alan" qui doit pour N = 0, 1, 2, 3, 4, ... , imprimer 1, 0, 2, 0, 3,...

III - Expressions Vectorielles (flex+bison)

Remerciements : Michel Meynard

L'objectif de cet exercice est d'écrire un interpréteur capable de reconnaître et d'évaluer des expressions arithmétiques et vectorielles. Les expressions sont construites à partir des composants suivants :

• Constantes Scalaires : des valeurs entières signées selon la notation usuelle
• Constantes Vecteurs : un vecteur contient un nombre fini de composantes scalaires, il sera noté entre crochets "[" "]", avec une virgule "," entre chaque composante scalaire. Ex: [3,-2,4,5] ou [2,1].
• L'opérateur noté '+' qui réalise l'addition usuelle de valeurs scalaires
• L'opérateur noté '+' qui réalise l'addition de 2 vecteurs. L'addition suppose que les vecteurs soient de même taille, l'addition se fait alors composante par composante. Ex : [3,5,7]+[1,-2,-5]==[4,3,2]
• L'opérateur noté '*' qui réalise la multiplication usuelle de valeurs scalaires
• L'opérateur noté '*' qui réalise la multiplication d'un vecteur et d'un scalaire. On autorise la multiplication dans les 2 sens. Ex : 4*[1,2,3]==[1,2,3]*4==[4,8,12].
• La fonction "dim(..)" qui prend en argument une expression vectorielle et retourne le nombre de composantes du vecteur. Ex : dim([])==0 ; dim([1,3])==2;
• Des parenthèses "(" et ")" pour imposer l'ordre d'évaluation des opérateurs
• On définira les règles d'associativité et de priorité selon les "usages courants"
• On accepte aussi le vecteur vide à zéro composante noté "[]"
• Les composantes d'un vecteur peuvent être des expressions Scalaires. (NB: en conséquence l'analyse d'un vecteur doit se faire au niveau syntaxique et non au niveau lexical)

• 2 * 3 * [1, -1, 1] * 2 == [12, -12, 12]
• (1 + 2) * [1, -1] + [2, 3] * 3 == [9, 6]
• 2 * [1 + 2 + 2 * -2, 1] == [-2, 2]

1- YASH (Yet another shell)

On donne un squelette d'interpréteur de commande ligne à ligne avec les fichiers yash0.flex et yash0.bison. On recommande l'utilisation des fichiers génériques du cours Makefile, proto-color.h

Travail demandé

Étudier et tester l'interpréteur Yash0.

Compléter l'interpréteur pour :

• Ajouter l'impression d'un prompt (i.e. "yash> ") en début de chaque ligne
• Ignorer au niveau lexical les caractères "espace" et "tabulation"
• Autoriser des commentaires. Un commentaire commence par le caractère "#" ou "%" et se termine à la fin de la même ligne. Les commentaires seront supprimés au niveau lexical.
• Autoriser plusieurs commandes sur la même ligne. Les commandes sont séparées par un caractère ";". On autorise aussi la commande vide qui a une action vide.
• (difficile) Ajouter une resynchronisation sur erreur de syntaxe qui porte sur chaque commande. Ne pas modifier la resynchronisation existante qui porte sur la ligne entière, mais ajouter une resynchronisation sur le caractère ";" dans le cas d'une ligne avec plusieurs commandes.

Exemple de résultat

yash> hello # fuck!
Nice to meet you
yash> thanks; ; hello @ fuck # fuck                                          
You are welcome
Nice to meet you
yash> hello; zzzzzz ; hello
Nice to meet you
<syntax error, unexpected $undefined, expecting NEWLINE or CMD_SEP>
Command invalide: 
Nice to meet you
yash> fuck # oups!
<Semantic Error : Censored !>
Ligne invalide
yash> fuck ; bye
<Semantic Error : Censored !>
Command invalide: 
See you

2- Expressions scalaires et vectorielles

Écrire l'analyseur syntaxique qui valide, évalue et imprime le résultat pour des expressions scalaires et des expressions vectorielles. Les expressions sont à intégrer comme des commandes dans l'interpréteur Yash.

On prendra soin d'assurer soit au niveau syntaxique, soit au niveau sémantique, la consistance des expressions. On n'ajoute pas un vecteur et un scalaire, on ne multiplie pas 2 vecteurs,... et l'on additionne que des vecteurs de même taille.

Indications

• Travailler étape par étape : constante scalaire, addition scalaire, multiplication scalaire (et priorité), parenthèses, constante vecteur avec 0 ou 1 composante, vecteur a N composantes, ..., addition de vecteur ... et gérer les différentes contraintes sémantiques au plus tôt.
• Le fichier vect.data contient des exemples de test avec les résultats attendus. Il peut être utilement complété.
• On propose une définition d'un type C pour les vecteurs dans vect.h. Cette définition impose une taille maximum sur les vecteurs qui devra être intégrée comme contrainte sémantique dans l'analyseur.
• IMPORTANT : Si l'on définit un type C qui est utilisé dans une directive "%union" de bison, la définition doit être partagée entre bison et Flex, même si on ne l'utilise pas dans Flex. Il convient donc de faire ces définitions de types dans un fichier ".h" à inclure dans le prologue bison et dans le prologue Flex avant "yyparse.h"
• On trouvera dans l'exemple yash0, comment on peut dans une action sémantique simuler une erreur syntaxique (cf Macro YYERROR). Ceci permet d'avoir la même resynchronisation après erreur pour des erreurs de syntaxe ou pour des erreurs sémantiques,
• NB: En terme de programmation, on ne se préoccupe pas de l'optimisation de l'espace mémoire.

3- Matrix ! ou d'autres extensions

Étendre l'analyseur dans l'une au choix des 3 directions proposées. Pour chacune des directions l'énoncé reste ouvert sur le travail à faire et la façon de le réaliser.

Prévoir de rendre une version stable de la question précédente avant de tout casser avec les extensions.

3.a) Calcul Matriciel

Intégrer des Matrices à deux dimensions.

En terme de syntaxe, on peut écrire une matrice comme un vecteur de vecteurs ([[1,2],[2,3],[3,4]]) en fixant une convention ligne par ligne ou colonne par colonne. On peut aussi différentier des vecteurs horizontaux "[]" et des vecteurs verticaux "{}" et permettre 2 écritures pour une même matrice ( {[1,2,3],[3,4,5]} == [{1,3},{2,4},{3,5}] )

Les expressions définies précédemment s'appliquent sur les matrices. Les vecteurs deviennent une cas particuliers de matrices avec une dimension égale à 1..

NB: la fonction "dim()" retourne maintenant un vecteur à deux composantes au lieu d'un scalaire.

3.b) Utilisation de variables typées

Intégrer des variables permettant d'enregistrer les valeurs des expressions scalaires ou vectorielles. Les variables devront être typées.

Il convient donc de gérer :

• Déclaration de variables sous une forme "Nom_TYPE Nom_variable" avec 2 Nom_TYPE réservés pour scalaire et vectorielle
• Affectation sous une forme "Nom_variable = Expr", avec contrôle sémantique sur la déclaration préalable de la variable, et l'adéquation des typed
• Utilisation de la variable dans une expression (à partir de son nom) et contrôle sémantique de la consistance des types.

On pourra gérer une table de symbole rudimentaire avec un nombre fini de "Nom_variable" (A-Z, V_0..V_99,..) ou utiliser l'implémentation générique de tables de symboles fournie dans le cours.

3.c) Des réels et Quelques opérations en plus

• l'opérateur produit scalaire noté "." qui donne un scalaire à partir de deux vecteurs de même taille. (X.Y = Σ x_iy_i)
• la fonction Norme notée "|| vect ||" qui donne un scalaire à partir d'un vecteur ( ||X||²=X.X)
• la fonction Projection notée "Proj( i , vect)" qui retourne la i^ème composante du vecteur (i=0..dim(vect)-1)
• la fonction Vecteur Unitaire notée "VU(i,n)" qui prend 2 entiers i<n et retourne le vecteur unitaire de dimension n avec des composantes nulles sauf pour la composante x_i=1
• l'opérateur "concaténation" de vecteurs noté " v1 @ v2 " qui produit un vecteur de taille p+q à partir des p composantes de v1 suivies des q composantes de v2
• ...