Programmation II (IFT1025), TP 1, Partie 1, 22 Janvier 2008 Date de remise : 5 Février 2008, à 23h59m59s La seconde partie sera mise en ligne au plus tard le 29 Janvier, elle sera due pour le 19 Février. Une correction intégrale de la première partie sera donnée durant le lab du 6 Février. Manipulateur d'expressions algébriques. Objectifs: * Programmation procédurale (révision) * Utilisation de classes & objets prédéfinis * Introduction et utilisation du `Pattern' visiteur Description de tâche: À partir des classes `ExprTokenizer' et `Expr', écrire un analyseur syntaxique pour une grammaire simple afin de produire un arbre syntaxique et le manipuler. Il est bien sûr interdit de modifier les classes fournies dans le sujet (contacter un démo si vous pensez avoir une bonne raison). Afin de faciliter le test des programmes, une classe `REPL' (`REPL.java') est fournie. On y appelle en boucle l'analyseur syntaxique, imprime l'Expr obtenue à l'écran (à l'aide de PrintInfix), évalue cette Expr avec Reduce, et en affiche le résultat. Première partie: a) Développer un analyseur syntaxique pour la grammaire suivante: Expr ::= Number | (UnaryOp Expr) | (Expr BinaryOp Expr) Number ::= [0-9]+ | [0-9]+.[0-9]+ UnaryOp ::= + | - | & BinaryOp ::= + | - | * | / Où Number est representé par la classe Number; les opérateurs unaires +, - et & (exp) par, respectivement, Plus, Minus et Exp; les opérateurs binaires +, -, * et / par, respectivement, Add, Subtract, Multiply, Divide (Grammaire Expr) Il n'est pas nécessaire de traiter les entrées ne correspondant pas à cette grammaire. Il est recommandé d'utiliser la méthode `readToken' de la classe `ExprTokenizer' afin de séparer l'entrée en lexemes. Remarquons de plus qu'il est toujours possible de désambiguer les cas à l'aide de la méthode `peek' de `ExprTokenizer'. Cette fonctionnalitée doit être implantée dans la classe `Parser' (`Parser.java') via la méthode `public static Expr parse (ExprTokenizer stream)'. Exemples, avec un Parser fonctionel et Reduce tel que donné dans le sujet : $ java REPL > 42 Expression : 42.0 Valeur/Forme Reduite : 42.0 > (+ 42) Expression : (+ 42.0) Valeur/Forme Reduite : (+ 42.0) > (6 * 7) Expression : (6.0 * 7.0) Valeur/Forme Reduite : (6.0 * 7.0) > ((+ 7) * (3 * 2)) Expression : ((+ 7.0) * (3.0 * 2.0)) Valeur/Forme Reduite : ((+ 7.0) * (3.0 * 2.0)) b) Développper un évaluateur d'arbres d'expressions arithmétiques tels que produits en a). Il est nécessaire de traiter tous les types d'opérations décrits dans la grammaire `Expr'. S'inspirer de la classe `PrintInfix' pour l'implantation d'un visiteur. Cette fonctionnalitée doit être implantée dans la classe `Reduce' (`Reduce.java'), qui sera utilisée comme visiteur d'Expr, qui retourne l'Expr contenant le résultat de l'évaluation (un Number). Défi: Développer immédiatement un analyseur syntaxique pour la grammaire Expr' décrite ci-bas), et un simplificateur d'expressions algébriques (le cas où il n'y a aucune variable devra évidemment être simplifiée à un Number, sinon une Expr équivalent à l'Expr visitée). Expr ::= Operand | (UnaryOp Expr) | (Expr BinaryOp Expr) Operand ::= Number | Variable Number ::= [0-9]+ | [0-9]+.[0-9]+ Variable ::= [a-zA-Z]+ UnaryOp ::= + | - | & BinaryOp ::= + | - | * | / (Grammaire Expr') Exemples avec Parser fonctionel et Reduce fonctionel (sans le bonus) > 42 Expression : 42.0 Valeur/Forme Reduite : 42.0 > (+ 42) Expression : (+ 42.0) Valeur/Forme Reduite : 42.0 > (6 * 7) Expression : (6.0 * 7.0) Valeur/Forme Reduite : 42.0 > ((+ 7) * (3 * 2)) Expression : ((+ 7.0) * (3.0 * 2.0)) Valeur/Forme Reduite : 42.0 > ((& 5) + (6 / 9)) Expression : ((& 5.0) + (6.0 / 9.0)) Valeur/Forme Reduite : 149.07982576924326 > ((6 + 7) - (5 + 3)) Expression : ((6.0 + 7.0) - (5.0 + 3.0)) Valeur/Forme Reduite : 5.0 Modalités de remise : Utiliser le système de remise. à partir d'une des machines du DIRO : $ ssh remise $ cd /dir/ou/est/votre/code $ remise ift1025 tp1-partie1 Parser.java Reduce.java Modalités d'évaluation Première partie 6/10 Analyseur syntaxique 4/10 Évaluateur 2/10 Le fonctionnement correct du code comptera pour la moitié des points, et la qualité du code (clarté, longueur, modularité, étendabilité, etc) pour l'autre moitié.