Les deux chapitres précédents ont présenté les principes de base de la programmation impérative, à savoir les notions de :
Le but de cette seconde partie du cours est double :
Pour cela, nous allons expliquer comment décrire avec précision un langage de programmation.
Comment décrire un langage de programmation
Lorsque l'on apprend une langue (par exemple l'anglais), on doit maîtriser :
Un langage de programmation (que l'on peut considérer comme une langue artificielle par rapport aux langues naturelles comme le français et l'anglais) peut être décrit par les mêmes 3 niveaux :
La différence principale entre un langage de programmation et une langue naturelle est qu'un langage de programmation est beaucoup plus simple et beaucoup plus strict qu'une langue naturelle.
Une bonne façon de mettre en évidence les trois niveaux ci-dessus est de prendre des exemples de (morceaux de) programmes erronés (ici en Pascal) :
1 program p; 2 var 12x, y : boolean; 3 t : array [1..10] of integer; 4 begin 5 if y <> 0 6 else t[11] := 0; 7 end.
La ligne 2 contient une erreur lexicale : 12x n'est pas un identificateur légal en Pascal. La ligne 5/6 contient une erreur syntaxique : la construction if...else n'est pas légale en Pascal (il faut une partie then). La ligne 5 contient également une erreur sémantique : la variable y est déclarée booléenne, on ne peut donc la comparer à l'entier 0. Enfin la ligne 6 contient une autre erreur sémantique : 11 n'est pas un indice valide pour le tableau t. Ces deux erreurs sémantiques sont de nature différente : la première peut être détectée simplement en regardant le texte du programme, on dit qu'il s'agit d'une erreur de sémantique statique. La seconde ne peut être détectée (dans le cas général) que lorsque le programme s'exécute, on dit qu'il s'agit d'une erreur de sémantique dynamique. Nous reviendrons sur ces notions en temps utile.
Les trois niveaux lexique/syntaxe/sémantique sont également à la base de la conception des compilateurs. Un compilateur est un programme qui traduit un programme écrit dans un langage évolué (par exemple Pascal) en code machine exécutable directement sur la machine. C'est grâce à un compilateur que l'on peut écrire et exécuter des programmes dans des langages évolués. La structure générale d'un compilateur consiste à découper le programme qu'il traduit en mots (unités lexicales), a structurer ces mots en arbres syntaxiques, puis à analyser cet arbre pour vérifier qu'il est sémantiquement correct. Ensuite seulement, la traduction proprement dite peut commencer : chaque morceau de l'arbre est traduit en langage machine équivalent, puis ce langage machine est éventuellement optimisé. Inutile de dire qu'un compilateur est un programme particulièrement complexe ! Ces concepts sont approfondis dans le cours de M3 Spécialité Informatique.
Dans la suite de ce chapitre, nous nous intéressons aux éléments usuels des lexiques des langages de programmation impératifs et à la description de la syntaxe des langages.
Les unités lexicales d'un langage décrivent ses composants de base, les "mots" de son vocabulaires. La plupart des langages sont fondés sur des vocabulaires très proches. Nous allons ici décrire les principales catégories d'unités lexicales et détailler le cas du langage Pascal.
Les "mots" les plus évidents dans un programme sont les identificateurs et les mots-clés. Les identificateurs sont utilisés pour dénoter des "objets" du programme : variables, fonctions, types, etc. Les mots-clés sont utilisés pour faciliter la reconnaissance de la structure du programme. Par exemple en Pascal, les mots-clés begin et end délimitent des blocs d'instructions.
En général (en en particulier en Pascal), les identificateurs sont constitués d'au moins une lettre, suivie de lettres ou de chiffres. Certains caractères (comme le souligné "_") sont parfois également autorisés. Le nombre de caractères qui sont effectivement utilisés pour différencier deux identificateurs dépend du langage : 8 dans la version originale de Pascal. Ainsi
12x est illégal mais x12 est légal toto_tata_tutu et toto_tata_titi sont identiques
Les mots-clés sont des mots particuliers qui ne peuvent pas être utilisés comme identificateurs. En Pascal, la liste des mots-clés est la suivante :
program const var type function procedure begin end array record set of file if then else while do repeat until case for to downto and or not in div mod goto label nil packed with
Les constants sont de mots qui désignent des valeurs d'un type prédéfini du langage. Typiquement, on trouve les constantes entières, réelles, booléennes, caractères et éventuellement chaînes. Ce qui suit concerne le langage Pascal :
Les entiers et les réels s'écrivent sous la forme mathématique habituelle :
10 -50 32767 153648293764234 (illégal car trop grand) 3.14 -0.05 6.02e+23 1.0e-6 1.0 (différent de 1)
Les constants booléennes sont les deux mots
true et false
Les constantes caractères sont notées entre simple quotes. Le caractère simple quote est noté en répétant la quote :
'a' '9' ';' ''''
Les constantes chaînes de caractères sont également notées entre simple quotes, avec répétition des quotes éventuelles :
'Bonjour' 'Commet allez-vous aujourd''hui'
Dans d'autres langages, par exemple C, on utilise des doubles quotes pour les chaînes de caractères, et le caractère '\' ("backslash") pour "protéger" les doubles quotes et indiquer des caractères spéciaux :
"Il dit : \"bonjour !\"" "Un deux\ntrois quatre" "\n" indique un retour à la ligne "voici un backslash : \\"
Les langages de programmation utilisent de nombreux symboles spéciaux no alphanumériques. Par exemple, en Pascal il y en a 24 :
+ - * / := . , ; : ' = <> < <= >= > ( ) [ ] { } ^ ..
Certains de ces caractères sont des opérateurs artihmétiques et relationnels :
+ - * / = <> < <= > >=
D'autres correspondent à des opérateurs particuliers :
:= affectation [ ] accès à un tableau ^ déréférencer un pointeur
D'autres encore sont utilisés pour séparer des instructions ou grouper des expressions :
, séparer les éléments d'une liste ; séparer des instructions ( ) grouper des sous-expressions
L'espace sert de séparateur, c'est-à-dire qu'il permet de séparer des unités lexicales adjacentes. Par exemple
typet=array[1..10]ofinteger
est incorrect et doit s'écrire avec au moins deux espaces :
type t=array[1..10]of integer type t = array [1 .. 10] of integer
En Pascal, les fins de ligne et les tabulations sont également des séparateurs.
Les commentaires sont des parties du programme qui sont ignorées du compilateur et qui ne changent donc rien au sens du programme. Ils sont cependant très importants pour documenter le programme, notamment en vue de son utilisation par quelqu'un d'autre ou de sa modification ultérieure (il est très rare d'écrire un programme que l'on ne modifie plus jamais et que l'on ne réutilise pas par ailleurs).
En Pascal, les deux formes suivantes sont acceptées :
(* un commentaire *)
{ un autre commentaire }La syntaxe d'un langage décrit les façons correctes d'assembler des unités lexicales pour écrire des programmes. Un programme syntaxiquement correct peut encore être erroné s'il contient des erreurs sémantiques.
Pour décrire la grammaire d'une langue naturelle, on utilise parfois des schémas (et le plus souvent des règles). Par exemple, un phrase en français peut être composée d'un groupe sujet, d'un groupe verbal, d'un groupe complément et d'un point final. Le groupe sujet est constitué d'un article, d'un adjectif éventuel et d'un nom ou d'un nom et d'un adjectif. Le groupe verbal est composé d'un auxiliaire éventuel et d'un verbe. Le groupe complément est composé d'un préposition éventuelle et d'un groupe sujet. Par exemple, les phrases suivantes correspondent à cette description :
Le chat mange la souris. Le cadavre exquis boira le vin nouveau. Le partiel aura lieu dans le grand amphi.
La figure ci-dessous explicite la structure syntaxique de la première phrase d'après les règles de grammaire expliquées ci-dessus :
Cependant la description ci-dessus est fastidieuse à lire et peut être difficile à comprendre. Une notation un peu plus formelle peut faciliter la lecture et la compréhension. Il suffit pour cela de donner un nom à chaque noeud possible de l'arbre et de décrire quels sont les fils possibles de chaque noeud :
<phrase> -> <g_sujet> <g_verbe> <g_complément> .
<g_sujet> -> article [ adjectif ] nom
| article nom adjectif
<g_verbe> -> [ auxiliaire ] verbe
<g_complément> -> [ préposition ] <g_sujet>
Cette notation correspond à la description d'une grammaire de production. Chaque ligne correspond à une règle de production. Les noms entre chevrons (comme <phrase>) sont appelés non-terminaux. Les autres sont les terminaux, c'est-à-dire des mots du vocabulaire. Pour construire une phrase grammaticalement correcte, il faut construire un arbre dont la racine est le non-terminal à gauche de la première règles et dont les fils sont les terminaux et non-terminaux de la partie droite. Chaque feuille de l'arbre qui est un non-terminal doit être complétée en utilisant une règle dont le non-terminal est en partie gauche. Il faut noter que dans cet exemple, on peut produire des phrases "insensées". Dans les règles de production ci-dessus, les crochets permettent de mentionner des parties optionnelles et les barres verticales des alternatives.
Cette notation formelle n'est pas toujours facile à lire. On peut utiliser une autre représentation des règles de production, les diagrammes de Conway ou diagrammes syntaxiques :
Souvent, on trouve dans les grammaires des structures répétitives. Par exemple, un texte est une suite de phrases. Ces structures se traduisent par des règles récursives dans les grammaires de production, mais on peut souvent les représenter par des boucles dans les diagrammes syntaxiques :
<texte> -> <phrase>
| <phrase> <texte>
Les langages de programmation ont une structure à la fois plus simple et plus stricte que les langues naturelles. Ils se prêtent donc mieux à la représentation par règles de production et diagrammes syntaxiques. Les principales structures syntaxiques que l'on trouve dans les langages impératifs sont les suivantes :
Dans la suite, nous présentons ces principales structures syntaxiques en utilisant tantôt des règles de production, tantôt des diagrammes syntaxiques, et en étudiants particulièrement le cas de Pascal. La plupart des manuels de référence utilisent des règles de production. Les diagrammes syntaxiques sont plus rares.
Un programme impératif est généralement constitué d'un ensemble de déclarations et d'un ensemble d'instructions. Pour un programme Pascal, on a :
Les déclarations de constantes, types, variables, fonctions et procédures sont toutes optionnelles. Elles font référence aux déclarations de type décrites ci-dessous :
Un type simple correspond aux types prédéfinis (entier, réel, booléen, caractère), aux types énumérés et aux types intervalles. Les types composés sont les tableaux et les enregistrements, ainsi que d'autres types que nous n'avons pas étudié (pointeurs, ensembles, fichiers).
Le détail de la déclaration des champs d'un enregistrement (non-terminal champs) n'est pas donné et est laissé à titre d'exercice.
Pour accéder à une variable dans un programme, il suffit de mentionner son identificateur. Cependant, les types composés permettent de définir des variables complexes : ainsi, un tableau contient plusieurs éléments, et un enregistrement contient des champs. Il est possible de combiner ces types, et d'avoir ainsi un tableau d'enregistrements ou un enregistrement dont certains sont des tableaux, etc. La syntaxe de l'accès aux variables permet de décrire comment dénoter les éléments de tableaux (t [i]) et les champs d'enregistrements (c.im) et comment combiner ces notations. En Pascal, on a la syntaxe (incomplète) suivante :
Par exemple, la déclaration
var m = array [1..10, 1..10] of record re, im : real end;
définit m comme un tableau à deux dimensions dont les éléments sont des nombres complexes. Pour accéder à la partie réelle de l'élément d'indices 2, 3, il faut écrire :
m [2, 3].re
Une expression dénote une valeur. Les expressions sont construites à partir d'un ensemble d'opérateurs. On distingue les opérateurs arithmétiques, relationnels et logiques. La notation est proche de celle utilisée en mathématiques (attention cependant : le produit doit être explicitement noté *).
Ce sont les 4 opérations usuelles : +, -, *, /. En Pascal, on a également les opérateurs DIV et MOD pour les nombres entiers, qui représentent le quotient et le reste de la division entière. Ainsi, si b != 0 :
a = (a DIV b) * b + a MOD b.
Les opérateurs * et / ont une plus grande priorité que les opérateurs + et -. Ainsi
a + b * c se lit a + (b * c).
En cas d'opérateurs successifs de même priorité, l'associativité est à gauche :
a - b + c est évalué (a - b) + c.
Si nécessaire, on utilise des parenthèses pour grouper des sous-expressions :
(a + b) * c est différent de a + b * c.
Enfin, l'opérateur unaire - est de priorité supérieure à tous les autres :
- a + b se lit (- a) + b.
Les opérateurs relationnels permettent de comparer des valeurs d'un type simple. Ils ont pour signature :
entier x entier -> booléen réel x réel -> booléen
En Pascal, les opérateurs sont :
= <> < <= > >=
Ils sont tous de même priorité. En effet, on ne peut avoir une expression de la forme :
a < b < c
Celle-ci serait évaluée de la façon suivante, qui provoque une erreur car le terme entre parenthèse est de type booléen mais pas le terme de droite :
(a < b) < c
Les opérateurs logiques portent sur les booléens. Ce sont le ou logique (OR), le et logique (AND) et la négation logique (NOT). Ils ont pour priorités (par ordre croissant) : OR AND NOT.
Les opérateurs arithmétiques sont de priorité supérieure aux opérateurs relationnels, eux-même de priorité supérieur aux opérateurs logiques. Ainsi, l'expression
x + y > 10 and x - y < 0
est évaluée dans l'ordre suivant :
((x + y) > 10 ) and ((x - y) < 0)
Les priorités sont donc, par ordre croissant :
Les facteurs qui constituent les opérandes d'une expression peuvent être des constantes, des variables, ou des appels de fonction. Ainsi, si l'on ne tient pas compte des priorités, la syntaxe des expression peut se décrire comme suit :
Pour prendre en compte les priorités des opérateurs, il faut décomposer expression en plusieurs niveaux, et donner autant de diagrammes correspondants (à faire en exercice).
Les instructions constituent la partie action d'un programme impératif. Dans un langage impératif, on trouve au moins les instructions suivantes :
De plus, des instructions peuvent être groupées dans un bloc (begin-end en Pascal). Le diagramme syntaxe des instructions Pascal est le suivant :
Les instructions case, repeat et for ne sont pas complétées dans ce diagrammes. Elles sont laissées à titre d'exercice.