INFO916 : Cours de C

Introduction

Qu'est ce qu'un langage de programmation :

Ce sont des intructions indiquant à un ordinateur ce qu'il doit faire.

Un langage est caractérisé par trois éléments :

• syntaxe/grammaire : définit l'ensemble des programmes valides.
• sémantique : que font faire ces programmes à la machine lors de l'exécution ?
• des usages et conventions : des pratiques usuelles pour mieux programmer.

Ce cours portera sur les trois aspects, notemment, on devra être capable d'évaluer un programme C à la main.

Avertissement : on ne va pas tenter de décrire le langage C dans tous ses détails, on en décrira un sous-ensemble plus simple et donc pédagogiquement plus pertinent. De plus, la description de la syntaxe de C sous forme de BNF (voir plus loin) ne sera pas tout à fait exacte, mais sera complété par des remarques (donner la syntaxe exacte du C est difficile et nuirait à la clarté).

Historique et classification des languages

Le langage C est un

• langage impératif : possibilité de changer la valeur d'une variable.
• langage procédural : existence de sous-programme.
• langage de bas niveau, "assembleur" portable (l'assembleur est un langage compris presque directement par la machine). L'aspect bas niveau du C se traduit surtout par la possibilité de manipuler directement, en tant qu'entier, les positions des octets dans la mémoire (voir plus loin).

Modèle mémoire et type de données

Modèle mémoire

Afin de pouvoir donner la sémantique du langage, il nous faut un "modèle" simplifié de machine. Essentiellement, un programme C agit sur deux choses:

• La mémoire de l'ordinateur,
• Les entrées/sorties (fichier).

On s'intéressera aux entrées/sorties en fin de cours.

La mémoire est en fait un tableau (= vecteur) d'octets (byte en anglais). Un octet est un entier sur 8 bits (bits aussi en anglais) donc compris entre 0 et 255 = 2⁸ - 1. Donc mathématiquement un élément de {0;1;2;...;255}^N où N dépend de l'architecture de la machine (N = 2³⁰, N = 2³¹ ou N = 2³² sur une machine 32 bits et N = 2⁴⁸ ou plus sur une machine 64 bits).

Attention: N ne dépend pas de la quantité de mémoire installée dans la machine !

Puisque la pile est un tableau, on peut parler de son i-ème élément $x$. L'index d'un élément dans la mémoire s'appelle l'adresse de cet élément.

Seul une partie de la mémoire est accessible en lecture écriture pour le programme C (on peut aussi avoir des zones mémoire accessibles en lecture seule). Lorsque l'on essaye d'accéder au contenu d'une adresse qui n'est pas accessible le programme s'arrête brusquement sur une erreur de type bus error ou segmentation fault.

De plus, la mémoire accessible est divisée en deux zones:

• La pile (stack)
• Le tas (heap)

La différence principale en ces zones mémoire est que la pile est une zone continue (connexe) de la mémoire tandis que le tas est en général fragmenté. L'utilisation de ces deux zones en C est aussi très différente. La pile sera examinée dans ce chapitre tandis que le tas fait l'objet d'un chapitre à lui seul.

Puisque la pile est une zone mémoire connexe, on ne peut l'agrandir ou la diminuer qu'en changeant la position (l'adresse) de ces extrémitées. En fait les extrémitées de la pile s'appelle le fond de pile (bottom of the stack) et le sommet de la pile (top of the stack) et seul le sommet de la pile change. Donc pour allouer ou libérer de la mémoire dans la pile, ce qui est ultra rapide, on se contente de déplacer le sommet de la pile.

Remarques:

• On n'a pas acces directement en C au sommet de la pile (on ne connait pas son adresse). Néanmoins on ne peut pas donner la sémantique du langage C sans en parler.
• Attention, le fait que l'adresse du sommet de la pile suit supérieure ou inférieure à celle du fond de la pile dépend de l'architecture de la machine.

Types de base

On n'utilise pas la mémoire octet par octet. Les données que l'on place dans la mémoire ont un type (on parle de type de donnée). Un type possède trois caractéristiques essentielles:

1. Son nom que l'on utilisera dans les programmes C.
2. Sa taille, c'est à dire le nombre d'octets nécessaire pour stocker un objet de ce type dans la mémoire. Une caractéristique étonnante du C est que tous les types ont une taille fixe ... et pourtant ceci ne nous empêchera pas de manipuler des objets de taille variable tels que les tableaux ou les chaînes de caractères. Si type est un type C, alors on peux utiliser sizeof(type) pour obtenir la taille du type.
3. Son sens : cet aspect est totalement ignoré par le compilateur C, mais il facilite la lecture des programmes. Si on ne mettait pas un sens derrière les noms des types, on utiliserait directement leur taille comme nom, car c'est la seule chose qui compte pour le compilateur C.

Remarque: on vient pour la première fois d'utiliser une convention d'écriture pour le code C qui prévaudra dans tout le cours. On écrira le code C en utilisant une police style machine à écrire (coome pour le mot sizeof si dessus et les parenthèses). Toutefois, type n'est pas du C, mais une meta-variable qui devra être remplacée par du C valide (ici le nom d'un type). Par exemple: sizeof(int) est du C valide.

Voici les types de base du C:

void

(taille 0/1) : par exemple type de retour des procédures. Nous reviendrons plus tard sur les usages très particulier de ce type;

char

(taille 1): un caractère ASCII ou parfois un très petit entier relatif;

short int

(taille 2) : un entier relatif de petite taille;

int

(taille 4) : un entier relatif de taille moyenne;

long int

(taille 4) : un entier relatif de grande taille;

long long int

(taille 8) : un entier relatif de très grande taille;

unsigned char

(taille 1): un caractère ASCII ou parfois un très petit entier naturel;

short unsigned int

(taille ?) : un entier naturel de petite taille;

unsigned int

(taille ?) : un entier naturel de taille moyenne;

long unsigned int

(taille ?) : un entier naturel de grande taille;

long long unsigned int

(taille ?) : un entier naturel de très grande taille;

float

(taille 4) : un nombre en virgule flottante 32 bits;

double

(taille 8) : un nombre en virgule flottante 64 bits;

long double

(taille ?) : un nombre en virgule flottante 64 bits ou plus (taille 16, mais seulement 86 bits de précision en réalité sur intel).

Remarque:

char

{-128,...,127} ou {-127,...,128}

Le codage des entiers négatifs dépend de la machine: - complément à 1 - complément à 2 L'ordre des octets d'un entier relatif, ou non, dépend de la machine. On appel: -little endian: lorsque l'octet de poid faible est à la fin -big endian: lorsque l'octet de poid fort est à la fin

Voici donc notre premier programme C qui affiche la taille des types ci-dessus (il faudra aller un peu plus loin dans le cours pour comprendre réellement ce programme) : <source lang="c">

1. include<stdio.h>

main(int argc, char **argv) {

 printf("void: %d\n", sizeof(void));
 printf("void*: %d\n", sizeof(void*));
 printf("char: %d\n", sizeof(char));
 printf("short int: %d\n", sizeof(short int));
 printf("int: %d\n", sizeof(int));
 printf("long int: %d\n", sizeof(long int));
 printf("long long int: %d\n", sizeof(long long int));
 printf("unsigned char: %d\n", sizeof(unsigned char));
 printf("short unsigned int: %d\n", sizeof(short unsigned int));
 printf("unsigned int: %d\n", sizeof(unsigned int));
 printf("long unsigned int: %d\n", sizeof(long unsigned int));
 printf("long long unsigned int: %d\n", sizeof(long long  unsigned int));
 printf("float: %d\n", sizeof(float));
 printf("double: %d\n", sizeof(double));
 printf("long double: %d\n", sizeof(long double));

} </source>

Exercice: compilez le programme précédent, exécutez-le et analysez le résultat.

Allocation dans la pile

On utilise la pile en déclarant des variables avec la syntaxe suivante:

instruction := type ident[,ident]*;

Ici on utilise la convention précédente: type doit être remplacé par un type et ident par un nom de variable. Les crochets indiquent qu'il est possible de mettre un second identificateur et l'asterisque indique que l'on peut en fait en mettre autant que l'on veut. On a écrit instruction := en début de ligne pour indiquer qu'une déclaration de variable est une instruction. On vien en fait de commencer à donner la syntaxe du C.

L'effet d'une déclaration de variables est de déplacer le sommet de la pile du nombre d'octets nécessaire pour stocker les objets dont les types sont donnés. Le sommet de la pile est donc déplacé d'un nombre d'octets égal à $n$ sizeof(type) si on alloue $n$ variables de type type.

Cette affectation de la variable établi un lien strict entre la variable et une zone de la pile. La valeur de la variable à un instant donné sera le contenu de cette portion de la pile à cet instant.

Exercice : décrire l'état de la pile lorsque l'on execute les instructions suivantes: <source lang="c"> int x,y; char c; x = 5; int z; y=2; z=x+y; </source>

Important : on peut donner la valeur d'une variable en même temps que la déclare en utilisant la syntaxe suivante (qui étend la précédente):

instruction := type ident[=expression][,ident[=expression]]*;

expression := ident

Dans la ligne précédente: [=expression] indique que le nom du type peut être suivi d'une expression donnant la valeur initiale de la variable. La seconde ligne indique que les noms de variable font parti des expressions.

Important : il faut initialiser les variables lors de la déclaration ou tout de suite après. Il est dommage que C n'impose pas cette contrainte, car les variables non initialisées sont la source de nombreux bugs.

On vient de voir que l'on alloue de la mémoire dans la pile en déclarant des variables. Mais comment libère-t-on cette mémoire.

La réponse est simple: les variables sont déclarées à l'intérieur d'un bloc éncadré par des accolades. Lorsque l'on rencontre une accolate fermante, toutes les variables alloués depuis l'accolade ouvrante correspondante sont libérées. En fait, l'accolade ouvrante mémorise l'adresse du sommet de la pile et l'accolade fermante correspondant restaure la valeur su sommet de la pile.

Exercice : décrire l'état de la pile lorsque l'on execute les instructions suivantes: <source lang="c"> {

 int x,y;
 char c;
 {
   x = 5;
   int z;
   z=2;
   x=z+y;
 }
 { 
   int a;
   a=y;
   x=a+a*x;
 }

} </source>

Comment va-t-on décrire la syntaxe et la sémantique du langage C

Au cours de la syntaxe précédente, on a commencé à donner la syntaxe du langage C (un peu simplifié). On va continuer tout au long de ce document, sous forme de BNF aggrémentée de crochets et astérisques qui sont des conventions courantes.

Afin d'expliquer nos conventions, reprenons ce que nous avons déjà donné en l'augmentant un peu:

instruction :=
  expression;
| type ident[=expression][,ident[=expression]]*;
| {[instruction]*}

expression := a-expression

a-expression := ident

On vient de définir trois sortes d'objets syntaxiques :

• Les instructions;
• Les expressions qui sont des instructions qui ont en plus une valeur;
• Les a-expressions (lvalue en anglais) qui sont des intructions qui ont une adresse, c'est à dire que la valeur de l'expression est stockée dans la mémoire.

Ainsi pour donner la sémantique d'une instruction, il suffit de préciser l'état de la mémoire et des entrées/sorties après execution de l'instruction en fonction de l'état avant. Si ${\mathcal {S}}$ désigne l'ensembles des états possible de la mémoire et des entrées/sorties, la sémantique d'une instruction est une fonction (partielle car l'instruction peut échouer) de ${\mathcal {S}}$ dans ${\mathcal {S}}$.

Pour donner la sémantique d'une expression, il faut connaitre son type type (toutes les expressions doivent avoir un type) et la sémantique est alors une fonction de ${\mathcal {S}}$ dans $\{0;1;\dots ;255\}^{n}\times {\mathcal {S}}$ où $n=$ sizeof(type). En effet, on donne en fonction de l'état initial, l'état final et la valeur de l'expression représenté par le bon nombre d'octet.

Pour donner la sémantique d'une a-expression de type type , on doit aussi indiquer son adresse, donc cette sémantique est une fonction de ${\mathcal {S}}$ dans $\{0;1;\dots ;255\}^{n}\times \mathbb {N} \times {\mathcal {S}}$ où $n=$ sizeof(type). De plus, une telle fonction $f$ doit vérifier que si $f(s)=(v,a,s')$ alors la mémoire de l'état $s'$ contient $v$ à l'adresse $a$.

Pointeurs et adresses

Un pointeur est une zone mémoire contenant une addresse. On peut déclarer une variable de type pointeur. Voici les constructions permettants de manipuler les pointeurs :

type := ... | type*

expression := ... | &a-expression

a-expression := ... | *expression

On vient d'étendre la grammaire du C :

• Lorsque l'on place une astérisque après un type, le nouveau type désigne un pointeur sur le premier. Par exemple int* désigne le type d'un pointeur sur un entier. C'est à dire qu'une zone mémoire ou une variable de type int* à pour valeur un entier naturel qui représente la position dans la mémoire d'un autre entier (attention le pointeur peut représenter une adresse valide ou non dans la mémoire).
• Lorsque l'on place le signe & devant une a-expression, la valeur retourné est l'adresse de cette a-expression (cela est raisonnable puisque les a-expression sont des expression dont la valeur est réellement stocké dans la mémoire). Par exemple &x retourne la position de la variable x dans la mémoire. Attention, &x est seulement une expression dont la valeur n'est pas nécessairement stocké dans la mémoire.
• Lorsque l'on place le signe * devant une expression dont la valeur est n, on obtient comme résultat la valeur stocké à l'adresse n dans la mémoire. Par exemple *12

donne le contenu de la case 12 en mémoire. Attention cette case mémoire est sans doute innacessible. Remarque : si e est une expression, puisque *e désigne le contenu d'une case mémoire c'est une a-expression.

D'après ce que l'on vient de dire, on peut dire que pour toute expression e, &*e à la même valeur que e. De même, pour toute a-expression e, *&e à la même valeur que e. Il y a tout de même une différence : *&e est bien défini pour toute a-expression alors que &*e n'est défini que si la valeur de l'expression e est une adresse valide dans la mémoire.

Exercice : décrire l'état de la pile lorsque l'on execute les instructions suivantes: <source lang="c"> {

 int x,*y;
 {
   int z;
   y = &z;
 }
 int a;
 *y = 2;
 x=a;

} </source>

Fonctions et prototypes

Pour parler des fonctions, il nous faut introduire une nouvelle catégorie syntaxique du C : le fichier. En effet, on a pas encode donné le point d'entrée de la grammaire du C, c'est-à-dire que l'on a pas encode décrit ce que doit contenir vraiment un fichier C. On doit aussi indiquer de nouveaux type d'instruction et d'expression.

fichier :=
  type ident([type ident[,type ident]*];
| type ident([type ident[,type ident]*]{[instruction]*}

instruction := ...
| return [expression];

expression := ...
| ident( [expression[,expression]*])

Exercice : décrire l'état de la pile lorsque l'on évalue l'expression fib(3) avec les deux définitions suivantes: <source lang="c"> unsigned int fib(unsigned int n) {

 if (n < 2 ) return(1);
 return fib(n-1) + fib(n-2);

} </source> <source lang="c"> unsigned int fib_aux(unsigned int n,unsigned int a,unsigned int b) {

 if (n==0) return a;
 return fix_aux(n-1,b,a+b);

} unsigned int fib(unsigned int n) {

 return fib_aux(n,1,1);

} </source>

Exercice : Démontrer que les deux définitions ci-dessus sont équivalentes.

Malloc et le tas

L'allocation dans la pile est très rapide. Toutefois, ce mécanisme n'est pas suffisant. On peut vouloir allouer une zone mémoire dans un bloc de sorte que cette zone mémoire ne soit pas désallouée à la sortie du bloc (l'accolade fermante).

Pour cela on dispose de la fonction malloc dont voici le prototype :

<source lang="c">

1. include <stdlib.h>

void *malloc(size_t size); </source>

La syntaxe simplifiée du langage C

fichier :=
  type ident([type ident[,type ident]*];
| type ident([type ident[,type ident]*]{[instruction]*}

instruction :=
  expression;
| type ident[=expression][,ident[=expression]]*;
| {[instruction]*}
| return [expression];

expression :=
  a-expression
| &a-expression | ident( [expression[,expression]*])

a-expression :=
  ident
| *expression

type :=
  void
| char
| ... autres types de base ...
| type*

ATTENTION: cette grammaire est approximative (pour être plus simple). Voici donc quelques corrections:

• Dans le code suivant : int* x,y; on n'indique pas que x et y sont des pointeurs, mais que *x est un entier et y est un entier. En fait il faut mieux écrire int *x,y; ou int x,*y;

Annexes

Un makefile de base (attention les lignes identées commencent avec une tabulation, c'est indispensable pour make):

<source lang="bash"> CSOURCES=name_of_the_C_files FSOURCES=name_of_the_Fortran_files TARGET=name_of_the_program OBJECTS=$(CSOURCES:.c=.o) $(FSOURCES:.f=.o)

CC=gcc F77=g77 LINKFLAGS=-g -lm CFLAGS=-g -Wall FFLAGS=-g

$(TARGET): $(OBJECTS)

       gcc $(LINKFLAGS) -o $(TARGET) $(OBJECTS)

clean:

       rm $(OBJECTS) $(TARGET)

depend:

       makedepend $(CSOURCES)

veryclean: clean

       rm *~ \#~\# core *.bak

</source>