Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

TP1

Dans de TP, vous ne devez pas utiliser de tableau, mais uniquement des variables de types primitifs (entiers, caractères…).

Partie 1 : un petit jeu

1. Compiler votre premier programme

Vous devez saisir, à l’aide d’un éditeur de texte, le programme suivant dans un fichier nommé bonjour.c.

#include <stdio.h>

int main()
{
    printf("Bonjour\n");
    return 0;
}

Le fichier doit être placé dans un dossier que nous appellerons répertoire de travail (current directory). Vous devez ouvrir une console Linux dans ce répertoire de travail. La ligne de commande pour compiler votre fichier est :

gcc bonjour.c -Wall -Wfatal-errors -Werror -o bonjour

Si tout se passe bien, aucun message n’apparait à l’écran et un fichier exécutable nommé bonjour a été créé dans le répertoire de travail. Vous pouvez exécuter ce programme en tapant :

./bonjour

Si un problème est survenu, vous devez essayer de le résoudre avant de continuer le TP. Les principaux problèmes peuvent êtres les suivant :

  • Le compilateur gcc n’est pas installé ou est mal installé. Vous devez l’installer sur la machine que vous utilisez. Dans une salle TP, ce problème ne devrait pas se produire. Sur une machine personnelle sous Linux, vous trouverez facilement de l’aide sur le WEB. Si vous utilisez un MAC, il vous sera facile d’installer les outils de développement en ligne de commande, qui incluent le compilateur gcc. Sous Windows, il est possible d’ouvrir une session Linux et d’installer gcc. Là encore, vous trouverez les informations nécessaires en faisant des recherches sur le WEB ou en demandant conseil à des condisciples plus expérimentés que vous.
  • Le compilateur ne trouve pas fichier bonjour.c. Vérifiez que ce fichier est bien dans le répertoire de travail utilisé par la console dans laquelle vous travaillez. Quelques bases de système Unix peuvent être nécessaire. Votre enseignante ou votre enseignant vous aidera volontiers.
  • Il y a des erreurs de compilation. Lisez attentivement les messages d’erreur et corrigez votre programme.

2. Lire des caractères au clavier

Pour toute la suite du TP, vous allez utiliser un fichier – vous pouvez par exemple le nomme tp1.c, situé dans votre répertoire de travail et commençant par les lignes de code suivantes :

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#include <termios.h>

struct termios tty_attr;

void tty_raw_mode(void)
{
	tcgetattr(0,&tty_attr);
	tty_attr.c_lflag &= (~(ICANON|ECHO));
	tty_attr.c_cc[VTIME] = 0;
	tty_attr.c_cc[VMIN] = 1;
	tcsetattr(0,TCSANOW,&tty_attr);
}

void tty_disable_raw() 
{
  tty_attr.c_lflag |= ((ICANON|ECHO));
  tcsetattr(0, TCSAFLUSH, &tty_attr);
}
// --------------- Fin de l'entete -----------------------

Ne cherchez pas à comprendre ces lignes de code. Elles relèvent de la programmation système Unix et permettent la saisie de caractères au clavier sans avoir à taper sur la touche Entrée.

Complétez votre programme sous la mention "Fin de l’entête" avec la fonction main suivante :

int main()
{
    tty_raw_mode(); // Passage du terminal en mode brut
    for(int i=0; i<10; i++)
    {
        char c = getchar();
        printf("%02X ",c);
    }
    tty_disable_raw();
    return 0;
}

L’appel à tty_raw_mode() permet de configurer le terminal (la console) pour permettre une saisie directe de caractères au clavier. Dans le mode par défaut, on ne peut récupérer les caractères saisis qu’après avoir tapé sur la touche entrée. L’appel à tty_disable_raw() permet de faire repasser le terminal en mode par défaut.

Compilez, exécutez, et tapez au clavier sur les touches espace, a, z, e, r et quelques autres. Observez ce qui est affiché et déduisez ce que fait la fonction getchar().

3. Petite simulation du déplacement d’un robot

Effacez la fonction main précédente et remplacez-là par le code suivant :

#define MAX_X 40     // Ligne A
#define MAX_Y 20     // Ligne B

int x=20;            // Ligne C
int y=5;             // Ligne D

void afficheBord()
{
	for(int i=0; i<=MAX_X+1; i++)
	{
		printf("+");
	}
	printf("\n");
}

void afficheLigne(int pos, char c)
{
	printf("+");
	for(int i=0; i<MAX_X; i++)
	{
		if(i==pos) printf("%c",c);
		else printf(" ");
	}
	printf("+\n");
}

void affiche()
{
	afficheBord();
	for(int i=0; i<MAX_Y; i++)
	{
		if(i==y)
		{
			afficheLigne(x, 'X');
		}
		else
		{
			afficheLigne(-1, 'X');
		}
	}
	afficheBord();
}

int main()
{
    tty_raw_mode();
    system("clear");  // Ligne E
    affiche();        // Ligne F
    tty_disable_raw();
    return 0;
}

Les lignes A et B définissent des constantes. Par exemple, chaque occurrence de MAX_X dans le code sera remplacée par 40. Attention, il n’y a pas et ne doit pas y avoir de point virgule à la fin de ces lignes. Elles sont traitées préalablement à la compilation par un programme appelé préprocesseur.

Les lignes C et D déclarent et initialisent deux variables globales x et y.

La ligne E fait un appel à une commande système qui efface le contenu de la console. Ce type de code n’est pas portable sur d’autres systèmes tel que Windows par exemple. Pas plus que ce qui se trouve dans l’entête du programme.

La ligne F appelle la fonction affiche qui réalise un affichage que vous pourrez découvrir en exécutant (après compilation) le programme.

Faites plusieurs essais avec différentes valeurs de x et y pour comprendre leurs rôles.

Vous pouvez étudier le code des fonctions d’affichage pour comprendre leur principe.


Maintenant, vous devez compléter ce programme de manière à ce qu’il permette de déplacer le petit robot symbolisé par le caractère X dans les limites du cadre. Par exemple, les touches a, z, e, r peuvent être utilisées pour déplacer le robot d’une position à gauche, à droite, en bas et en haut. Le programme doit s’arrêter lorsque la touche espace est pressée.

4. Un petit jeu de poursuite

En prenant pour base le programme précédent, vous devez réaliser un petit jeu avec deux robots. L’un, appelé X, est contrôlé au clavier et l’autre, appelé O, est contrôlé par l’ordinateur. Le but du jeu est que X rattrape O, qui essaye de le fuir. Le robot O fait un déplacement d’une case après chaque déplacement de X. Structurez votre code en plusieurs fonctions ayant des rôles bien identifiés et documentés afin d’éviter de produire un gros "pâté" de code peu lisible.

Partie 2 : Reconnaissance de mots

1. Expressions bien parenthésées

On dit qu’un expression est bien parenthésée si elle vérifie les deux conditions suivantes.

  1. À toute position dans l’expression, il y a au moins autant de parenthèses ouvrantes que de parenthèses fermantes.
  2. Dans l’expression complète, il y a autant de parenthèses ouvrantes que de parenthèses fermantes.

Voici quelques exemple d’expression bien parenthésées. On ne s’intéresse pas aux caractères autres que les parenthèses.

()(()())
((()))
(()()())(())

Voici quelques exemple d’expression mal parenthésées.

()())(())
(((()()))

Vous devez réaliser un programme qui permet la saisie et l’affichage d’une expression. Cette expression n’est pas stockée en mémoire, elle est juste affichée au fur et à mesure de sa saisie au clavier. La saisie se termine par la pression sur la touche entrée. Si, au cours de la saisie, l’expression devient mal parenthésée, le programme s’arrête et un message d’erreur est affiché (ceci n’est possible que si le terminal a été placé en mode brut comme présenté dans la partie précédente. Après la saisie, un message indique si l’expression est bien ou mal parenthésée.

2. Reconnaissance d’une expression par automate fini

Ceci est un approfondissement. Il n’est pas nécessaire de réaliser cette partie pour considérer que ce TP est réalisé. Mais si vous êtes un peu en avance et avez réalisés avec un certaine aisance les parties précédente, vous pourrez découvrir ici une technique de programmation qui peut s’avérer très utile pour traiter de nombreux problèmes.

On souhaite vérifier si une ligne saisie au clavier est une liste de nombres entiers positifs au format CSV (Comma Separated Values). Une telle ligne est constituée d’une suite de nombres séparés par des virgules obligatoires et espaces facultatifs. Voici un exemple de ligne valide :

12, 456 , 47,78

On ne doit pas stocker la ligne en mémoire (puisque dans ce TP on utilise pas de chaînes ni de tableaux), mais seulement l’afficher et vérifier son format au moment de la saisie.

Pour réaliser cette vérification, on utilise un automate fini.

image-20211224114556999

L’automate a 4 état possibles. L’état initial est 1. À partir de cet état, si des espaces sont lus, on reste dans l’état 1. Si un chiffre est lu au clavier, on passe dans l’état 2. Si autre chose est lu, le programme s’arrête et affiche un message d’erreur.

Dans l’état 2, la lecture d’un chiffre ne provoque pas de changement d’état. La lecture d’un espace entraîne le passage dans l’état 3, la lecture d’une virgule entraîne le passage à l’état 4, la lecture de tout autre caractère entraîne une erreur.

Lorsque vous avez compris le principe, le schéma de l’automate parle de lui même. À la fin de la lecture, si l’automate est dans l’état 3 alors la ligne saisie est correcte, sinon elle comporte une erreur.

L’état de l’automate peut être représenté par une simple variable. Une boucle while peut contenir la lecture des caractères et tout le mécanisme de gestion des changement d’état.