DM 2 - Conduite de voiture

Dominique Rossin

Ce devoir consiste à mettre en place un mini-langage dédié à la commande d'une voiture. Le langage contient des expressions arithmétiques et des commandes de conduite pour contrôler l'accélérateur et le volant de la voiture. La voiture est donc un robot et le mini-langage sert à la programmation de la commande de ce robot. La voiture se déplace sur un circuit qu'elle ne connait pas à priori. Elle ne possède que des commandes de conduite pour avancer ou tourner et des commandes pour regarder devant elle. La position initiale de la voiture est un paramètre de chaque circuit.

La partie 1 avec la question 2.1 sur les expressions suffira pour obtenir la note A. Vous devez rendre ce devoir à la maison pour le mercredi 20 avril au plus tard. La remise des travaux se fera par la commande:

/users/profs/info/Depot/INF_431/deposer [pgm] DM_2 [gpe]

où [pgm] doit être remplacé par la liste des noms des fichiers contenant vos programmes et [gpe] doit être remplacé par votre numéro de groupe.

Voici un exemple d'exécution du programme.

Voici le texte du source du programme de la voiture pour tourner dans ce circuit.

# Programme de test 1
        # Boucle infinie
        WHILE (0 < 1) {
	    AC(60); # on passe la vitesse a 60
            # On regarde la distance au prochain obstacle
            SET DIST = SCAN();
	    # Tant qu on est assez loin de l'obstacle
            WHILE (DIST < 56) {
                # ici on a un obstacle assez proche
		AC(40); # on roule un peu moins vite
		# On regarde le type de mur devant soi
                SET MUR = SCANT(); 
		# 0=gauche, 1=droit
                IF (MUR < 1) 
                    TD(5); # on tourne a droite
                IF (0 < MUR) 
                    TG(5); # on tourne a gauche
                SET DIST = SCAN();
            }
	    TG(0); # on remet les roues droite
        }

1. Mise en oeuvre (Avancer et Tourner)

1.1 Premier exemple de fonctionnement

Dans un premier temps, vous devez télécharger le programme au format zip ou au format tar. Vous désarchivez les fichiers sources soit à l'aide de la commande unzip, soit sous Linux par la commande tar -xvf DM2.tar. Cela créera un répertoire Voiture et à l'intérieur de celui-ci, vous trouverez tous les fichiers sources en Java ainsi qu'un sous-répertoire Images contenant les images nécessaires au fonctionnement du programme.

Vous n'avez pas à lire ces programmes, ni à les modifier pour réaliser le devoir à la maison. Vous avez aussi deux sous-répertoires:

Programmes qui contient des exemples de programmes de voiture et
Circuits qui contient des exemples de circuits.

Votre partie consiste à écrire la classe DM2 dont le squelette est donné ci-dessous.

/* DM2.java */

import java.io.*;
public class DM2 {
    
    Voiture voiture;
    BufferedReader in;

    /** Creates a new instance of DM2 */
    public DM2(Voiture v, BufferedReader fichierProgramme) {
        voiture = v;
        in = fichierProgramme;
    }

    public void run() {
        // Analyse Lexicale
	...
	// Analyse syntaxique  et Construction de l'ASA
	...
	// Interpretation de l'ASA
	...

    }   
}

Afin de réaliser un premier test de fonctionnement, vous pouvez télécharger le fichier suivant dans votre répertoire. Ce fichier contient deux instructions dans la méthode run() permettant de donner des ordres à la voiture.

Mettez cette classe dans votre répertoire Voiture, puis compilez l'ensemble des programmes et lancez le à l'aide de la commande java Main. Vous avez alors une interface graphique devant vous.

Allez dans le menu Fichier et sélectionnez Ouvrir Circuit. Allez dans le sous-répertoire Circuits et choisissez le fichier circuit1.txt. Vous venez de charger un fichier de définition de circuit. Notez que dans ce circuit, il n'y a pas d'herbe; cela va nous permettre de faire des essais de déplacement.
Retournez dans le menu Fichier et sélectionnez cette fois Ouvrir Fichier Programme. Allez dans le sous-répertoire Programmes et choisissez le fichier progTest1.txt. C'est le fichier donné au début de l'énoncé.
Allez dans le menu Execution et sélectionnez Run. Votre voiture décrit un cercle car pour l'instant, elle ne lit pas progTest1.txt et exécute les deux instructions.

Afin d'éviter toutes ces manipulations, vous pouvez aussi lancer le programme depuis le shell sous la forme java Main Circuits/circuit1.txt Programmes/progTest1.txt.

1.2 Fonctionnement général du programme

Le projet est constitué de deux parties, l'une fournie (Main.java) et l'autre que vous devez écrire (DM2.java).

Les classes dans le fichier Main.java sont fournies et permettent de gérer le fonctionnement de la voiture ainsi que l'interface graphique du programme. La méthode main qui se trouve dans la classe fournie Main fait les opérations suivantes:

Création de l'interface graphique.
Création d'un objet de type voiture.
Déplacement de la voiture toutes les 30 millisecondes en fonction de ses paramètres internes de vitesse et d'angle des roues. Ces paramètes de vitesse et d'angle peuvent être modifiés de l'extérieur. Ceci sera fait dans la classe DM2.

La classe DM2 est un programme qui s'effectue en parallèle, et qui est lancée depuis Main.java. Son point de départ est la méthode run().

Dans ce programme, on peut appeler les 2 méthodes setVitesse(int v) et addAngle(int a) qui modifient ces deux paramètres internes à la prochaine tranche de 30 millisecondes. Par ailleurs, deux autres méthodes int scan() et int scant() renvoient la distance et le type (mur gauche ou droit) d'obstacle devant la voiture.

1.3 Description détaillée du programme

Lors de la sélection de Run dans le menu. les actions suivantes sont réalisées:

Appel au constructeur new DM2(voiture, fichierProgramme). L'objet voiture est l'objet à travers lequel on peut interagir avec le fonctionnement du programme grâce aux méthodes permettant de changer la vitesse voiture.setVitesse(vitesse); ou de tourner (voiture.addAngle(5);). L'objet fichierProgramme est positionné par le système sur le début du fichier de programme que vous avez choisi.
Lancement d'un programme se déclenchant toutes les 30 millisecondes et provoquant le déplacement de la voiture selon ses paramètres de vitesse et d'angle.
Lancement en parallèle d'un second programme qui appelle la méthode void run() de la classe DM2. C'est cette méthode que vous avez à modifier.

Ainsi, dans la méthode run de la classe DM2, des ordres peuvent être donnés à la voiture permettant de modifier sa vitesse ou son angle. Pour rendre effectif le changement de ces paramètres, les méthodes setVitesse et addAngle attendent la prochaine tranche de 30 millisecondes pour les modifier.

Votre travail consiste donc à écrire la méthode run dans la classe DM2, qui :

Réalisera l'analyse lexicale du programme de conduite de la voiture.
Réalisera l'analyse syntaxique et construira l'arbre de syntaxe abstraite (ASA). Cet arbre sera décrit plus précisement lors de l'introduction de la grammaire.
Interprétera cet arbre pour donner les commandes à la voiture grâce aux méthodes de la classe Voiture décrites ci-dessous.

L'accès à l'objet voiture se fait de la manière suivante:

void voiture.setVitesse(int v) met la vitesse de la voiture à v. (cette valeur est ramenée entre -80 et 80).
void voiture.addAngle(int angle) met le volant de manière à tourner de angle degrés à chaque pas de temps. Un angle positif permet de tourner à droite tandis qu'un angle négatif tourne à gauche (cet angle est ramené dans l'intervalle [-5,5]).
int voiture.scan() renvoie la distance de la voiture au premier obstacle devant elle en ligne droite.
int voiture.scant() renvoie le type du premier obstacle devant la voiture en ligne droite. (0= mur gauche de la route, 1 = mur droit de la route, ...)

1.4 Les premières instructions du mini-langage

La première partie de votre travail consiste à programmer l'analyse lexicale et syntaxique de quelques commandes du langage de déplacement de la voiture. On prendra la grammaire suivante:

ListeInstructions ::= Instruction [Instruction ]*

Instruction ::= AC(Expression);
              | TG(Expression);
	      | TD(Expression);
	      | { ListeInstructions }


Expression ::= Entier

[Instruction]* représente une liste d'instructions.

Pour lire un caractère dans l'objet in de la classe BufferedReader, on peut utiliser la commande in.read() qui renvoie un entier représentant le prochain caractère. Cet entier vaut -1 dans le cas où la fin de fichier est atteinte.
Cette lecture correspond exactement à la lecture dans un InputStream dans le TD 5 et le TD 7. Cette méthode run devrait ressembler à:

public void run() {
  AnalyseLex analyse = new AnalyseLex(in);
  AnalyseSynt analyseur = new AnalyseSynt(analyse);
  ASA programme = analyseur.construitASA();
  ASA.executerInstructions(programme,voiture);
}

Un arbre de syntaxe abstrait comprend des noeuds de différents types. Pour les expressions, il suffit de reprendre le format des ASA considérés dans le cours. Pour les instructions, ce seront :

Des noeuds de type Instruction unaire. C'est le cas pour AC(Expr), TG(Expr) ou TD(Expr) . Leur unique fils est un ASA d'expression.
Des noeuds de type Liste d'instructions qui correspondent à des listes d'ASA d'instructions.

À partir de ce petit programme, on peut maintenant interpréter la commande suivante qui donnera graphiquement sur le circuit linéaire circuit2.txt :

AC(30);

De même, sur le circuit sans obstacles circuit1.txt, le programme suivant

AC(30);
TD(2);

donnera le beau cercle ci-dessous:

2. Du cercle à la spirale

2.1 Ajout des expressions

Afin de pouvoir réaliser des boucles, nous avons besoin de variables. De la même manière que dans le TD 7, nous ajoutons les expressions arithmétiques de la manière suivante:

Instruction ::= ...
              | ...
	      | SET Identificateur = Expression;
	      | PRINT expr;

Expression ::= Produit + Expression
            |  Produit - Expression
	    |  Produit

Produit ::= Facteur * Produit
         |  Facteur / Produit
	 |  Facteur

Facteur ::= Nombre
         |  ( Expression )
	 |  Identificateur

L'instruction SET x=3 stocke la valeur 3 dans la variable x. L'instruction PRINT x+4 affiche l'expression ainsi que sa valeur soit "x+4 = 7".
Le choix du mode de stockage des variables est libre.

Vous pouvez tester l'instruction SET à l'aide du programme neuf.txt qui doit vous dessiner un 9 à l'écran en utilisant le circuit circuit1.txt.

2.2 Ajout des boucles

Nous allons maintenant modifier la grammaire et y ajouter les instructions suivantes:

Instruction ::= ...
	      | ...
	      | IF (Expression1 < Expression2) Instruction
	      | WHILE (Expression1 < Expression2) Instruction

L'instruction WHILE répète l'instruction qu'elle contient tant que la comparaison des deux expressions est vraie. L'instruction IF réalise la meme opération mais une seule fois. Voici deux exemples de programmes itératifs:

# Programme de test 1
    WHILE (0 < 1) {
        SET x = 30;
        WHILE (0 < x) {
            AC(60);
            SET x = x - 1;
        }
        SET y = 18;
        WHILE (0 < y) {
            TG(5);
            SET y = y-1;
        }
        TG(0);
        TG(5);
        TG(0);
    }

AC(30);
SET x = 1;
SET y = 30;
WHILE (0 < 1) {
        SET r = 30;
        WHILE (0 < r) {
        SET z = y;
        WHILE (0 < z) {
                TG(x);
                SET z = z - 1;
                SET r = r - 1;
        }
        TG(x+2);
        TG(x);
        SET r = r - 2;
        }

        SET y = y - 1;

}

3. Un peu d'interactivité

Nous étendons le langage en rajoutant deux fonctions testant la présence d'obstacles. Pour cela nous avons deux fonctions SCAN et SCANT qui renvoient pour la première la distance au premier obstacle et pour la deuxième le type de l'obstacle. Rajoutez ces fonctions (attention ce ne sont pas des instructions) à votre grammaire. Maintenant, vous devriez pouvoir interpréter le code suivant en prenant comme circuit circuit3.txt.

# Programme de test 1
        AC(60);
        
        WHILE (0 < 1) {
	    AC(60);
            SET DIST = SCAN();
            WHILE (DIST < 56) {
	            AC(40);
                    SET MUR = SCANT();
                IF (MUR < 1) {
                    TD(8);
                }
                IF (0 < MUR) {
                    TG(8);
                }
                SET DIST = SCAN();
            }
	        TG(0);
        }

Vous obtiendrez alors la première figure de cet énoncé.

4. Extensions

Les commentaires

Votre programme devra être capable de lire des programmes avec des commentaires débutant par le caractère

et terminant à la fin de la ligne.

Le moins unaire

Rajoutez dans la lecture des expressions le - unaire à savoir SET X = -3.

Les procédures

On va changer légèrement la grammaire en rajoutant la notion de programme.

Programme ::= [Procedure]* [Instruction]*
Procedure ::= PROC Identificateur { ListeInstruction }

Pour appeler une procédure, on rajoutera l'instruction CALL nomProcedure qui appelle la procédure nomProcedure L'execution du programme débutera à la première des instructions suivant la déclaration des procédures.