Table des matières

Introduction​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 2
I Rappels sur l’analyse syntaxique​ ​ ​ ​ ​ ​ ​ ​ 3
​ I-1 Objectifs et principes fondamentaux de l’analyse syntaxique​ ​ ​ 3
II Notions de base sur l’outil Yacc/Bison​ ​ ​ ​ ​ ​ ​ 4
​ II-1 Origine et historique de Yacc/Bison​ ​ ​ ​ ​ ​ 4
​ II-3 Installation de Yacc/Bison​ ​ ​ ​ ​ ​ ​ 4
​ II-2 Rôle de Yacc/Bison​ ​ ​ ​ ​ ​ ​ ​ 5
​ II-4 Processus de développement avec Yacc/Bison​ ​ ​ ​ ​ 7
​ II-5 Format du fichier de spécification​ ​ ​ ​ ​ ​ 8
​ II-6 Exercice corrigé : un calculateur simple​​ ​ ​ ​ ​ 12
Conclusion​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 15

1
Introduction

​ Dans le domaine de la compilation et de l’analyse des langages informatiques,

l’analyse syntaxique joue un rôle fondamental. Elle intervient après l’analyse lexicale et
consiste à vérifier si une suite de symboles (tokens) forme une structure correcte selon la
grammaire du langage. Parmi les outils utilisés pour automatiser cette étape, Yacc (Yet
Another Compiler Compiler) est l’un des plus anciens et des plus populaires. Cependant, au
fil du temps, des besoins d'évolution, de compatibilité avec les normes modernes et
d'ouverture du code source ont conduit à la création de Bison, développé par le projet GNU.
Bison est une alternative libre à Yacc, offrant plus de fonctionnalités tout en restant
compatible avec lui. Il permet ainsi de conserver la simplicité d’utilisation de Yacc, tout en
bénéficiant d'améliorations significatives telles que la prise en charge de langages
supplémentaires, une meilleure gestion des erreurs syntaxiques, et la possibilité de produire
du code plus portable. Dans le cadre de notre travail, nous utiliserons donc Bison pour
illustrer concrètement l'utilisation d'un générateur d’analyseurs syntaxiques, tout en
respectant l'esprit et les principes fondamentaux introduits par Yacc.

2
I Rappels sur l’analyse syntaxique

​ L'analyse syntaxique, également connue sous le nom de parsing, constitue la

deuxième phase clé du processus de compilation. Faisant suite à l'analyse lexicale, elle joue
un rôle fondamental dans la vérification de la structure du programme source en s'assurant
que la séquence de tokens générée respecte les règles grammaticales du langage de
programmation.

​ En d'autres termes, l'analyse syntaxique consiste à organiser les tokens en structures

hiérarchiques appelées arbres syntaxiques ou arbres d'analyse. Ces structures reflètent la
façon dont les éléments du langage doivent être combinés pour former des instructions
valides.

​ Par exemple, dans un langage comme C, une déclaration telle que int x = 5; sera
interprétée non seulement comme une suite de tokens mais également comme une
construction syntaxique valide respectant une règle grammaticale spécifique. Ainsi, l'analyse
syntaxique détecte précocement les erreurs de syntaxe, telles que des parenthèses manquantes
ou un ordre incorrect des mots-clés, et prépare la transition vers l'étape suivante du processus
de compilation, en fournissant une représentation arborescente structurée du programme.

I-1 Objectifs et principes fondamentaux de l’analyse syntaxique

​ Les principaux objectifs de l'analyse syntaxique sont :

• Valider la conformité du code source aux règles de la grammaire du langage.
• Construire une représentation arborescente formelle (souvent appelée arbre de syntaxe
abstraite ou AST - Abstract Syntax Tree) du programme.
• Signaler de manière claire et précise les erreurs de syntaxe détectées pour permettre leur
correction.
Les principes fondamentaux qui sous-tendent cette étape reposent sur la définition de
grammaires formelles, telles que les grammaires hors-contexte (CFG - Context-Free
Grammars) et sur l'implémentation de parseurs efficaces, notamment les parseurs descendants
(top-down) et ascendants (bottom-up). Ainsi, l'analyse syntaxique a pour but de transformer

3
la suite linéaire de tokens produits par l'analyse lexicale en une structure logique et
hiérarchisée, posant ainsi les bases solides pour l'analyse sémantique et la génération de code.

II Notions de base sur l’outil Bison/Yacc

II-1 Origine et historique de Bison/Yacc

Yacc, abréviation de "Yet Another Compiler Compiler", est un générateur

d'analyseurs syntaxiques largement reconnu dans le domaine de la compilation. Développé
dans les années 1970 par Stephen C. Johnson aux laboratoires Bell Labs, Yacc visait à
faciliter la création de compilateurs en automatisant la production d'analyseurs syntaxiques à
partir de grammaires formelles. Grâce à son approche méthodique et puissante, Yacc est
devenu un outil central dans le développement de langages de programmation.
Face aux besoins croissants de compatibilité et d'amélioration, GNU a proposé Bison,
une version libre et améliorée de Yacc. Bison conserve la compatibilité avec Yacc tout en
offrant des fonctionnalités supplémentaires telles que la prise en charge de langages de sortie
variés et la détection d'ambiguïtés dans les grammaires. Depuis leur apparition, Yacc et Bison
sont devenus des piliers du génie logiciel, utilisés aussi bien dans les projets académiques que
dans les développements industriels, pour concevoir des compilateurs robustes, des
interprètes de commandes et des outils d'analyse syntaxique avancés.

II-2 Installation de Yacc/Bison

​
​ L’installation de Bison et Yacc est simple et accessible sur la plupart des systèmes
d’exploitation en particulier sous les environnements Unix/Linux. Sur les distributions basées
sur Debian ou Ubuntu, il suffit d’utiliser les commandes suivantes dans le terminal :
sudo apt-get install bison flex

Cette commande installe Bison ainsi que Flex, souvent utilisé en complément pour l’analyse
lexicale.

Sous Fedora ou CentOS, la commande a employé est :

4
sudo dnf install bison flex

Pour les utilisateurs de systèmes Windows, il est possible de télécharger des versions
compatibles via des environnements comme Cygwin ou MSYS2, ou encore d’utiliser WSL
(Windows Subsystem for Linux) pour installer les outils comme sous Linux.
Après installation, la commande bison –version nous permet de vérifier que
l’installation a bien été effectuée et d’afficher la version de Bison installée.

II- 3 Rôle de Bison

​ Bison est un compilateur qui permet de générer automatiquement un analyseur
syntaxique à partir d’un schéma de traduction dirigée par la syntaxe. Ce schéma est défini à
l’aide d’une grammaire enrichie d’actions sémantiques.
​ Une fois l’analyseur syntaxique produit par Bison, il est capable de reconnaître les
mots du langage définis par la grammaire spécifiée. Cet analyseur est implémenté sous forme
de fonction en langage C, nommée yyparse(), générée automatiquement par Bison.

5
 La fonction yyparse() appelle à chaque étape la fonction yylex() pour obtenir le
prochain lexème (ou jeton) de l’entrée. Cette fonction yylex() peut être soit codée
manuellement en langage C, soit générée automatiquement par le compilateur Flex. La
fonction yyparse() retourne un entier indiquant le résultat de l’analyse syntaxique :
• Elle retourne 0 si l’analyse a été effectuée avec succès,
• et 1 si une erreur de syntaxe a été rencontrée au moins une fois pendant l’analyse.

6
II-4 Processus de développement avec Yacc/Bison
​
Le développement avec Bison suit plusieurs étapes essentielles, allant de la définition
de la grammaire jusqu'à la gestion des erreurs syntaxiques :

​ a) Spécification formelle de la grammaire du langage source

​ Il s'agit de mettre la grammaire du langage sous une forme reconnue par Bison.
Chaque règle grammaticale est enrichie avec des actions sémantiques, c’est-à-dire du code en
langage C qui sera exécuté lors de l’analyse syntaxique. Le fichier contenant cette grammaire
formelle porte généralement l’extension .y.

​ b) Écriture de l’analyseur lexical

Cette étape consiste à définir comment les lexèmes (mots ou symboles du langage) sont
extraits manuellement en écrivant directement le code de l’analyseur lexical en C ou
automatiquement en utilisant un outil tel que Flex qui génère l’analyseur à partir de règles
lexicales.

​ c) Écriture d’une fonction de contrôle

Cette fonction en langage C sert à appeler et coordonner l’exécution de l’analyseur

syntaxique généré par Bison.

​ d) Routines de traitement des erreurs syntaxiques

​ Si besoin, on écrit en C des routines spécifiques pour gérer les erreurs de syntaxe
détectées pendant l’analyse. Ces routines permettent de rendre le programme plus robuste et
de fournir des messages d’erreurs clairs à l’utilisateur.

​ e) Étape de compilation avec Bison

7
​ Pour réaliser un analyseur syntaxique à l’aide de Bison, certaines étapes de
compilation doivent être suivies afin de générer un programme capable de reconnaître et
analyser un langage donné.
- Compilation du fichier de grammaire syntaxique (.y) : utiliser la commande bison pour
générer l’analyseur syntaxique à partir du fichier .y.

Exemple : bison -d parser.y

- Compilation du fichier lexical (. lex) : utiliser la commande flex pour générer l’analyseur
lexical à partir du fichier .lex.

Exemple : flex [Link]

- Compilation des fichiers générés : utiliser un compilateur C (comme gcc) pour compiler les
fichiers produits par Bison et Flex ensemble.

Exemple : gcc -o compiler [Link].c [Link].c -ly -lfl

Une fois les fichiers compilés, on peut exécuter le compilateur avec une commande de type
./compiler . Cela signifie qu’on utilise le binaire généré pour analyser un fichier source et
produire un résultat dans le fichier cible.

II-5 Format du fichier de spécification

Un fichier de spécification de Bison possède 03 sections :

Déclarations
%%
Règles
%%
Code complémentaire

8
​ a) Les déclarations

​ C’est un bloc délimité par les symboles %{ et %} qui contient les déclarations C des
variables et des fonctions globales ainsi que les directives du préprocesseur. Ces déclarations
peuvent être utilisées dans les sections 2 et 3. Les tokens doivent être également déclarés dans
cette section. Ces tokens peuvent être soit nommés, soit donnés sous formes de chaînes
terminables entre des quotes (" "). Les tokens nommés doivent être déclarés pour les
distinguer des symboles non-terminaux.
​ La forme d’une déclaration de tokens est :
%token token1 value1 token2 value2 . . .
Les valeurs entières définissent les codes des tokens utilisés par l’analyseur lexical. Tous les
tokens déclarés doivent avoir des valeurs positives comme code. L’affectation des valeurs de
code pour les tokens est optionnelle : les tokens n’ayant pas un code explicite reçoivent des
codes implicites.
La déclaration de l’axiome de la grammaire est définie par la commande : %start
nom_axiome.
Par défaut, le nom de la tête de la première production est l’axiome. La « %start » est donc
obligatoire lorsque la première production écrite n’est pas celle issue de l’axiome de la
grammaire.

​ b) Les règles

Une règle correspond à une production étendue de la grammaire. La forme d’une

règle dans Bison est : Tête : Queue Actions;
​ - Tête : est le nom du symbole variable se trouvant à gauche d’une production de la
grammaire.
​ - Queue : est la forme se trouvant à droite dans une production.
​ - Actions : sont des fragments de programmes C qui seront exécutées par la fonction «
yyparse() » lorsque la règle aura été reconnue.
On peut faire référence aux variables globales déclarées dans la 1ère section, appeler
des sous-programmes déclarés dans la 3ème section, etc.

Écriture des productions en Bison

9
Soient « X → A | B | C | ε » les règles de production dont la tête est le symbole « X ».
En Bison, ces règles s’écrivent :
X:A;
X:B;
X:C;
X:;
Il faut noter que l’ordre des productions n’est pas obligatoire. On peut également les écrire
d’une manière simplifiée en utilisant le symbole d’union « | »:
X:A;
|B;
|C;
|;

La notation « $ »

Soit « X → A1 A2...Ak » une règle de production issue de « X ».

En Bison, on écrit :
X : A1 A2...Ak ;
À chaque symbole d’une production, on peut affecter un « attribut » ayant une
certaine « valeur » d’un certain « type ». Par défaut, le type de la valeur d’un attribut d’un
symbole est « int ».
L’attribut par défaut du symbole « x » est désigné par la variable « $$ ». L’attribut par
défaut d’un symbole « Ai » est désigné par la variable « $i » où « i » est le numéro qui
désigne l’ordre de « Ai » dans la queue de la production « X → A1 A2...Ak ».
Exemple :
Soit la production « E → T "+" F ». La valeur de l’expression « E » est celle de « T »
plus celle de « F ». On peut alors écrire en Bison l’action sémantique suivante :
E : T "+" F { $$ = $1 + $3; }
;
c) Code complémentaire

​ La 3ème section comprend une séquence de déclarations de fonctions « C » utilisées

par ailleurs dans les actions ou par l’analyseur généré. L’une d’entre elles doit être l’analyseur
lexical, la fonction « yylex() ». Cette fonction délivre à chaque appel un entier qui est le code

10
de l’unité lexicale suivante lue, et transmet dans la variable yylval la valeur associée à cette
unité lexicale. Par défaut, le type de la variable yylval est « int ». Il est possible de le modifier
via la macro-constante #define YYSTYPE 3.
Informations sur les opérateurs
- %left : permet de spécifier des opérateurs associatifs à gauche.
– %right : permet de spécifier des opérateurs associatifs à droite.
– %noassoc : permet de spécifier des opérateurs non associatifs.
– %prec : permet de forcer la précédence des opérateurs.

Définir les attributs et leurs types

La structure contenant les attributs d’un symbole (terminal ou variable) est décrite à
l’aide de la clause « %union ». Deux variables globales sont fournies (de type « int » par
défaut) :
- yylval : l’analyseur lexical stocke dans cette variable les attributs de l’unité lexicale
reconnue. L’analyseur syntaxique récupère ces attributs en lisant cette variable.
- yyval : l’analyseur syntaxique stocke dans cette variable les attributs du symbole variable
courant. L’analyseur syntaxique travaille avec une pile : il empile et dépile les symboles
(terminaux et variables) avec leurs attributs. Une clause « %union » permet de changer les
types de ces deux variables. Lorsqu’un lexème n’a pas d’attribut ou à un attribut entier, il
n’est pas nécessaire de spécifier le type (car le type entier est pris par défaut). La clause
%type permet de déclarer les noms et les types des symboles non terminaux. De même,
lorsqu’un symbole variable n’a pas d’attribut ou à un attribut entier, il n’est pas nécessaire de
spécifier le type. Les types spécifiés par %token et %type doivent avoir été définis par une
clause %union.

Procédure de récupération sur erreur

On peut spécifier une fonction de traitement d’erreurs dans un analyseur syntaxique
écrit à l’aide de Bison. Cette fonction doit porter le nom « yyerror() » pour être invoquée
automatiquement lorsqu’une erreur syntaxique est rencontrée.

Exemple :

void yyerror(char *s){

11
fprintf(stderr, "%s\n", s);
return 0;
}

II-6 Exercice corrigé : un calculateur simple

L’analyseur lexical :

/* fichier calc.l */
%{
#include "[Link].h"
#include <stdlib.h>
%}

%%
[0-9]+ { yylval = atoi(yytext); return NOMBRE; }
[ \t] ; /* ignore espaces et tabulations */
\n { return 0; }
. { return yytext[0]; }
%%

int yywrap() {
return 1;
}

L’analyseur syntaxique :

/* fichier calc.y */
%{
#include <stdio.h>
#include <stdlib.h>

12
int yylex();
void yyerror(const char *s);
%}

%token NOMBRE
%start calcul

%%
calcul:
expr { printf("Résultat = %d\n", $1); }
;

expr:
expr '+' terme { $$ = $1 + $3; }
| expr '-' terme { $$ = $1 - $3; }
| terme { $$ = $1; }
;

terme:
terme '*' facteur { $$ = $1 * $3; }
| terme '/' facteur { $$ = $1 / $3; }
| facteur { $$ = $1; }
;

facteur:
'(' expr ')' { $$ = $2; }
| '-' facteur { $$ = -$2; }
| NOMBRE { $$ = $1; }
;

%%

void yyerror(const char *s)

{

13
 fprintf(stderr, "Erreur : %s\n", s);
}

int main()
{
printf("Entrez une expression :\n");
yyparse();
return 0;
}

Pour compiler :
bison -d calc.y
flex calc.l
gcc [Link].c [Link].c -o calc -lfl
./calc

14
Conclusion

​ Au terme de cet exposé, nous avons pu comprendre le rôle fondamental de l’analyse

syntaxique dans le processus de compilation, en tant qu' étape intermédiaire entre l’analyse
lexicale et l’analyse sémantique. Nous avons vu qu’elle permet de structurer et de valider la
syntaxe des programmes selon des règles grammaticales précises, tout en préparant la
construction d’arbres syntaxiques nécessaires à la suite du traitement. Nous avons également
découvert l’outil Bison, successeur libre et amélioré de Yacc, qui facilite la génération
automatique d’analyseurs syntaxiques à partir de grammaires formelles enrichies d’actions
sémantiques. À travers l’étude de son origine, de son fonctionnement et du format de ses
fichiers de spécification, nous avons mis en évidence l’intérêt de cet outil pour concevoir des
compilateurs et interprètes robustes et [Link], la mise en pratique à travers
l’exercice du calculateur simple a permis d’illustrer concrètement le processus de
développement avec Bison, depuis la définition des lexèmes avec Flex, jusqu’à la
compilation et l’exécution de l’analyseur syntaxique.

15