TD 4 - Interprète mini-Turtle

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.

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

turtle.ml(i)	la tortue graphique (complet)
ast.ml	la syntaxe abstraite de mini-Turtle (complet)
lexer.mll	l'analyseur lexical (à compléter)
parser.mly	l'analyseur syntaxique (à compléter)
interp.ml	l'interprète (complet)
miniturtle.ml	le programme principal (complet)
Makefile/dune	pour automatiser la compilation (complet)

Le code fourni compile (taper make, qui va lancer dune build) mais est incomplet.

L'exécutable s'applique à un fichier mini-Turtle portant le suffixe .logo. Quand on fait make, le programme est lancé sur le fichier test.logo.

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).

  prog ::= 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.mll (ocamllex) et parser.mly (menhir). 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 construit l'exécutable et le lance sur le fichier test.logo. Une fenêtre graphique s'ouvre et montre l'interprétation du programme. On ferme la fenêtre en appuyant sur une touche.

Documentation :

Question 1. Commentaires

Compléter le fichier lexer.mll pour ignorer les blancs et les commentaires et renvoyer le lexème EOF lorsque la fin du fichier est atteinte. 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. Vous pouvez utiliser make explain pour voir les détails d'un conflit de Menhir, ou regarder le fichier _build/default/parser.conflicts généré par dune.

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 l'exécutable sur chacun de ces fichiers. On doit obtenir les images suivantes (en appuyant sur une touche après chaque image) :

solution : lexer.mll / parser.mly

retour à la page du cours