(English version)

INF564 - TD 3 - Mini-Turtle (en Java)

Le but de ce TD est de réaliser l'analyse syntaxique d'un petit langage Logo (tortue graphique) dont l'interprète est fourni ; il n'est pas nécessaire de connaître le langage Logo.

L'analyse syntaxique sera effectuée avec les outils JFlex et Cup. L'outil JFlex est déjà installé en salles info. L'outil Cup est contenu dans le code fourni.

Nous vous fournissons la structure de base (sous la forme d'un ensemble de fichiers Java et d'un Makefile) que vous pouvez récupérer ici : mini-turtle-java.tar.gz. Une fois cette archive décompressée (par exemple avec tar zxvf mini-turtle-java.tar.gz), vous obtenez un répertoire mini-turtle-java/. Ce projet contient un package mini_turtle avec les fichiers suivants :

Turtle.java(i) la tortue graphique (complet)
Syntax.java la syntaxe abstraite de mini-Turtle (complet)
Lexer.flex l'analyseur lexical (à compléter)
Parser.cup l'analyseur syntaxique (à compléter)
Interp.java l'interprète (complet)
Main.java le programme principal (complet)
Makefile pour automatiser la compilation (complet)

Le code fourni compile mais est incomplet. Les endroits à compléter contiennent * À COMPLÉTER */. Le programme accepte un nom de fichier à interpréter. En cas d'absence, il utilise le fichier test.logo.

Note : La bibliothèque java-cup-11a-runtime.jar qui est contenue dans le sous-répertoire lib/ est requise pour l'exécution du code produit par CUP. VSCode et Eclipse devraient ajouter automatiquement lib/ au class path, mais de vieilles versions d'Eclipse nécessitent de le faire manuellement (avec Java Build Path -> Libraries -> Add JARs).

Syntaxe de mini-Turtle

Conventions lexicales

Les espaces, tabulations et retours chariot sont des blancs. Les commentaires sont de deux formes différentes : débutant par // et s'étendant jusqu'à la fin de la ligne, ou encadrés par (* et *) (et non imbriqués). Les identificateurs suivants sont des mot clés : 
     if else def repeat penup pendown forward turnleft
     turnright color black white red green blue
Un identificateur ident contient des lettres, des chiffres et des caractères _ et débute par une lettre. Une constante entière integer est une suite de chiffres.

Syntaxe

Les noms en italique, comme expr, désignent des non terminaux. La notation stmt* désigne une répétition zéro, une ou plusieurs fois du non terminal stmt. La notation expr*, désigne une répétition du non terminal expr, les occurrences étant séparées par le lexème , (une virgule). 
  file ::= def* stmt*
  def  ::= def ident ( ident*, ) stmt
  stmt ::= penup
         | pendown
         | forward expr
         | turnleft expr
         | turnright expr
         | color color
         | ident ( expr*, )
         | if expr stmt
         | if expr stmt else stmt
         | repeat expr stmt
         | { stmt* }
  expr ::= integer
         | ident
         | expr + expr
         | expr - expr
         | expr * expr
         | expr / expr
         | - expr
         | ( expr )
 color ::= black | white | red | green | blue
Les priorités des opérations arithmétiques binaires sont usuelles et la négation unaire a une priorité encore plus forte.

Travail à faire

Votre travail consiste à compléter les fichiers Lexer.flex (JFlex) et Parser.cup (Cup). Les questions suivantes vous suggèrent une façon de procéder. Il est possible de tester à chaque fois en modifiant le fichier test.logo. La commande make à la racine du projet lance les outils jflex et cup (pour faire/refaire les fichiers Java Lexer.java, sym.java et parser.java dans src/mini_turtle/), puis compile le code Java et enfin lance le programme sur le fichier test.logo. Si l'analyse syntaxique s'effectue avec succès, une fenêtre graphique s'ouvre et montre l'interprétation du programme. On ferme la fenêtre en appuyant sur une touche.

Note : on peut visualiser/compiler/lancer le code Java depuis Eclipse et même se servir d'Eclipse pour éditer les fichiers Lexer.flex et Parser.cup. Mais il faut tout de même lancer les commandes jflex et cup (avec make dans un terminal) puis rafraîchir alors Eclipse avec F5.

Question 1. Commentaires

Compléter le fichier Lexer.flex pour ignorer les blancs et les commentaires. La commande make doit alors ouvrir une fenêtre vide, car le fichier test.logo fourni ne contient que des commentaires.

Question 2. Expressions arithmétiques

Ajouter les règles de grammaire nécessaires à la reconnaissance des expressions arithmétiques et de l'unique instruction forward. Le fichier test.logo contenant 
  forward 100
doit alors être accepté et la fenêtre doit s'ouvrir avec le dessin d'un trait horizontal (de 100 pixels de long). Vérifier que les priorités des opérateurs arithmétiques sont les bonnes, par exemple avec la commande suivante : 
  forward 100 + 1 * 0
Si la priorité n'est pas la bonne, un point s'affichera plutôt qu'un trait.

Question 3. Autres instructions atomiques

Ajouter la syntaxe des autres instructions atomiques, à savoir penup, pendown, turnleft, turnright et color.

Tester avec des programmes comme 

forward 100
turnleft 90
color red
forward 100

Question 4. Blocs et structures de contrôle

Ajouter la syntaxe des blocs et des structures de contrôles if et repeat. Les deux règles de grammaire pour l'instruction if doivent provoquer un conflit shift/reduce. L'identifier, le comprendre et le résoudre de la manière qui vous semble la plus appropriée.

Tester avec des programmes comme 

repeat 4 {
  forward 100
  turnleft 90
}

Question 5. Fonctions

Ajouter enfin la syntaxe des déclarations de fonctions et de l'appel d'une fonction dans les instructions.

On pourra tester avec les fichiers fournis dans le sous-répertoire tests, à savoir :

La commande make tests lance le programme sur chacun de ces fichiers. On doit obtenir les images suivantes (en appuyant sur une touche après chaque image) :
solution : Lexer.flex / Parser.cup
retour à la page du cours