Chapitre 8 :

L’outil d’analyse syntaxique Bison

Prof. Abdelmajid Dargham

Faculté des Sciences, Oujda
Filière SMI - S4
Module Théorie des langages & Compilation

Université Mohamed Premier

Septembre, 2012
Sommaire du chapitre 8

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Sommaire du chapitre 8

Introduction

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Sommaire du chapitre 8

Introduction
Format d’un Fichier Bison

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Sommaire du chapitre 8

Introduction
Format d’un Fichier Bison
Règles

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Sommaire du chapitre 8

Introduction
Format d’un Fichier Bison
Règles
Déclarations et définitions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Sommaire du chapitre 8

Introduction
Format d’un Fichier Bison
Règles
Déclarations et définitions
Association d’une valeur aux symboles

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Sommaire du chapitre 8

Introduction
Format d’un Fichier Bison
Règles
Déclarations et définitions
Association d’une valeur aux symboles
Interaction avec l’analyseur lexical

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Sommaire du chapitre 8

Introduction
Format d’un Fichier Bison
Règles
Déclarations et définitions
Association d’une valeur aux symboles
Interaction avec l’analyseur lexical
Actions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Sommaire du chapitre 8

Introduction
Format d’un Fichier Bison
Règles
Déclarations et définitions
Association d’une valeur aux symboles
Interaction avec l’analyseur lexical
Actions
Exercices corrigés

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Une fois l’analyse lexicale effectuée, l’analyse

syntaxique (parsing) permet de vérifier qu’un texte est
conforme à une grammaire G donnée.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Une fois l’analyse lexicale effectuée, l’analyse

syntaxique (parsing) permet de vérifier qu’un texte est
conforme à une grammaire G donnée.
L’analyse syntaxique construit l’arbre syntaxique
correspondant au texte analysé.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Une fois l’analyse lexicale effectuée, l’analyse

syntaxique (parsing) permet de vérifier qu’un texte est
conforme à une grammaire G donnée.
L’analyse syntaxique construit l’arbre syntaxique
correspondant au texte analysé.
Bison est un outil qui génère d’une manière
automatique, un analyseur syntaxique basée sur une
grammaire donnée.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Une fois l’analyse lexicale effectuée, l’analyse

syntaxique (parsing) permet de vérifier qu’un texte est
conforme à une grammaire G donnée.
L’analyse syntaxique construit l’arbre syntaxique
correspondant au texte analysé.
Bison est un outil qui génère d’une manière
automatique, un analyseur syntaxique basée sur une
grammaire donnée.
Un programme Bison est enregistré avec l’extension ”.y”.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Étapes pour la conception d’un analyseur syntaxique

avec Bison

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Étapes pour la conception d’un analyseur syntaxique

avec Bison
Définir la grammaire de l’analyseur, puis l’écrire en
respectant le format de Bison.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Étapes pour la conception d’un analyseur syntaxique

avec Bison
Définir la grammaire de l’analyseur, puis l’écrire en
respectant le format de Bison.
Pour chaque règle de production de la grammaire, écrire
l’action (les instructions C) qui va être exécutée
lorsqu’une instance de cette règle est reconnue par
l’analyseur.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Étapes pour la conception d’un analyseur syntaxique

avec Bison
Définir la grammaire de l’analyseur, puis l’écrire en
respectant le format de Bison.
Pour chaque règle de production de la grammaire, écrire
l’action (les instructions C) qui va être exécutée
lorsqu’une instance de cette règle est reconnue par
l’analyseur.
Écrire un analyseur lexical qui va traiter le fichier source
et produira les lexèmes à l’analyseur syntaxique. celui-ci
peut être écrit à la main ou bien avec Flex.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Chaı̂ne de compilation

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Chaı̂ne de compilation
On compile le fichier contenant le code Bison par :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Chaı̂ne de compilation
On compile le fichier contenant le code Bison par :
bison -d parser.y

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Chaı̂ne de compilation
On compile le fichier contenant le code Bison par :
bison -d parser.y
On compile le fichier contenant le code Flex par :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Chaı̂ne de compilation
On compile le fichier contenant le code Bison par :
bison -d parser.y
On compile le fichier contenant le code Flex par :
flex [Link]

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Chaı̂ne de compilation
On compile le fichier contenant le code Bison par :
bison -d parser.y
On compile le fichier contenant le code Flex par :
flex [Link]
On compile par gcc :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Chaı̂ne de compilation
On compile le fichier contenant le code Bison par :
bison -d parser.y
On compile le fichier contenant le code Flex par :
flex [Link]
On compile par gcc :
gcc -o parser [Link].c [Link].c -ly -lfl
Pour lancer l’analyseur ainsi crée :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Introdutcion

Chaı̂ne de compilation
On compile le fichier contenant le code Bison par :
bison -d parser.y
On compile le fichier contenant le code Flex par :
flex [Link]
On compile par gcc :
gcc -o parser [Link].c [Link].c -ly -lfl
Pour lancer l’analyseur ainsi crée :
parser < [Link] > [Link]

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Format d’un fichier Bison

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Format d’un fichier Bison

Déclarations

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Format d’un fichier Bison

Déclarations
%%

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Format d’un fichier Bison

Déclarations
%%
Règles

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Format d’un fichier Bison

Déclarations
%%
Règles
%%

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Format d’un fichier Bison

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

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Règles

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Règles

Une règle est une règle de production de la grammaire,

enrichie d’actions.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Règles

Une règle est une règle de production de la grammaire,

enrichie d’actions.
Une règle s’écrit :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Règles

Une règle est une règle de production de la grammaire,

enrichie d’actions.
Une règle s’écrit :
A : Corps;

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Règles

Une règle est une règle de production de la grammaire,

enrichie d’actions.
Une règle s’écrit :
A : Corps;
où A est le nom (un identificateur) d’un non-terminal et
Corps est une suite (éventuellement vide) de noms (de
terminaux et non-terminaux) et de littéraux (caractères
entre guillemets).

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Règles

Une règle est une règle de production de la grammaire,

enrichie d’actions.
Une règle s’écrit :
A : Corps;
où A est le nom (un identificateur) d’un non-terminal et
Corps est une suite (éventuellement vide) de noms (de
terminaux et non-terminaux) et de littéraux (caractères
entre guillemets).
Lorqu’il existe plusieurs règles de production pour un
même non-terminal, l’opérateur ”|” peut être utilisé pour
séparer le corps de chaque règle.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Règles

Une règle est une règle de production de la grammaire,

enrichie d’actions.
Une règle s’écrit :
A : Corps;
où A est le nom (un identificateur) d’un non-terminal et
Corps est une suite (éventuellement vide) de noms (de
terminaux et non-terminaux) et de littéraux (caractères
entre guillemets).
Lorqu’il existe plusieurs règles de production pour un
même non-terminal, l’opérateur ”|” peut être utilisé pour
séparer le corps de chaque règle.
On peut par exemple écrire :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Règles

Une règle est une règle de production de la grammaire,

enrichie d’actions.
Une règle s’écrit :
A : Corps;
où A est le nom (un identificateur) d’un non-terminal et
Corps est une suite (éventuellement vide) de noms (de
terminaux et non-terminaux) et de littéraux (caractères
entre guillemets).
Lorqu’il existe plusieurs règles de production pour un
même non-terminal, l’opérateur ”|” peut être utilisé pour
séparer le corps de chaque règle.
On peut par exemple écrire :
exp : number | exp 0 +0 exp
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Déclarations et définitions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

La partie déclarations et définitions contient les

déclarations C (entre les symboles %{ et %}), ainsi que
la déclaration des noms de tokens (lexèmes).

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

La partie déclarations et définitions contient les

déclarations C (entre les symboles %{ et %}), ainsi que
la déclaration des noms de tokens (lexèmes).
La déclaration d’un token s’effectue via la directive
%token :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

La partie déclarations et définitions contient les

déclarations C (entre les symboles %{ et %}), ainsi que
la déclaration des noms de tokens (lexèmes).
La déclaration d’un token s’effectue via la directive
%token :
%token name1 name2 ...;

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

La partie déclarations et définitions contient les

déclarations C (entre les symboles %{ et %}), ainsi que
la déclaration des noms de tokens (lexèmes).
La déclaration d’un token s’effectue via la directive
%token :
%token name1 name2 ...;
Les noms qui n’ont pas été déclarés en tant que ”nom de
token” sont considérés comme des non-terminaux.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Lorque les tokens correspondent à des opérateurs pour
lesuqles on souhaite spécifier une propriété d’associativité,
ou utilise left et right à la place de token.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Lorque les tokens correspondent à des opérateurs pour
lesuqles on souhaite spécifier une propriété d’associativité,
ou utilise left et right à la place de token.
Par exemple, on écrira :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Lorque les tokens correspondent à des opérateurs pour
lesuqles on souhaite spécifier une propriété d’associativité,
ou utilise left et right à la place de token.
Par exemple, on écrira :
%left 0 +0 0 −0

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Lorque les tokens correspondent à des opérateurs pour
lesuqles on souhaite spécifier une propriété d’associativité,
ou utilise left et right à la place de token.
Par exemple, on écrira :
%left 0 +0 0 −0
%right 0 b 0

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Lorque les tokens correspondent à des opérateurs pour
lesuqles on souhaite spécifier une propriété d’associativité,
ou utilise left et right à la place de token.
Par exemple, on écrira :
%left 0 +0 0 −0
%right 0 b 0
Si l’on souhaite de plus spécifier la précédence entre
opérateurs, on écrit la déclaration des tokens dans l’ordre
inverse des priorités.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Lorque les tokens correspondent à des opérateurs pour
lesuqles on souhaite spécifier une propriété d’associativité,
ou utilise left et right à la place de token.
Par exemple, on écrira :
%left 0 +0 0 −0
%right 0 b 0
Si l’on souhaite de plus spécifier la précédence entre
opérateurs, on écrit la déclaration des tokens dans l’ordre
inverse des priorités.
Dans l’exemple ci-dessus, l’opérateur 0 b 0 a une priorité
plus grande que les opérateurs 0 +0 et 0 −0 (qui sont de
même priorité).
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Déclarations et définitions

Cas des opérateurs

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Il est également possible de modifier la précédence d’un
opérateur dans une règle.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Il est également possible de modifier la précédence d’un
opérateur dans une règle.
Par exemple, si l’on souhaite décrire le ”moins unaire”
aussi désigné par les symbole 0 −0 comme un opérateur
ayant même précédence qu’un token de nom NEG , on
écrira :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Il est également possible de modifier la précédence d’un
opérateur dans une règle.
Par exemple, si l’on souhaite décrire le ”moins unaire”
aussi désigné par les symbole 0 −0 comme un opérateur
ayant même précédence qu’un token de nom NEG , on
écrira :
mexp : 0 −0 %prec NEG ...

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Cas des opérateurs

Il est également possible de modifier la précédence d’un
opérateur dans une règle.
Par exemple, si l’on souhaite décrire le ”moins unaire”
aussi désigné par les symbole 0 −0 comme un opérateur
ayant même précédence qu’un token de nom NEG , on
écrira :
mexp : 0 −0 %prec NEG ...
afin de ne pas associer au ”moins unaire” la même
précédence que le ”moins binaire”.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Chaque non-terminal doit apparaı̂tre au moins une fois

comme partie gauche d’une règles.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Chaque non-terminal doit apparaı̂tre au moins une fois

comme partie gauche d’une règles.
L’axiome de la grammaire spécifiée peut être désigné
explicitement dans la partie des déclaration en utilisant la
directive %start. Par exemple :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Chaque non-terminal doit apparaı̂tre au moins une fois

comme partie gauche d’une règles.
L’axiome de la grammaire spécifiée peut être désigné
explicitement dans la partie des déclaration en utilisant la
directive %start. Par exemple : %start axiome

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Chaque non-terminal doit apparaı̂tre au moins une fois

comme partie gauche d’une règles.
L’axiome de la grammaire spécifiée peut être désigné
explicitement dans la partie des déclaration en utilisant la
directive %start. Par exemple : %start axiome
A défaut, l’axiome de la grammaire sera le premier
non-terminal apparaissant dans la partie gauche de la
première règle.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Déclarations et définitions

Chaque non-terminal doit apparaı̂tre au moins une fois

comme partie gauche d’une règles.
L’axiome de la grammaire spécifiée peut être désigné
explicitement dans la partie des déclaration en utilisant la
directive %start. Par exemple : %start axiome
A défaut, l’axiome de la grammaire sera le premier
non-terminal apparaissant dans la partie gauche de la
première règle.
Si la grammaire est ambiguë ou requière plus d’un
symbole de prévision, Bison sera confornter à des conflits
”shift/reduce” ou ”reduce/shift”.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut associer à chaque symbole (terminal ou

non-terminal) une valeur ”sémantique” (indépendante
de la correction syntaxique).

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut associer à chaque symbole (terminal ou

non-terminal) une valeur ”sémantique” (indépendante
de la correction syntaxique).
L’analyse s’effectue après l’analyse lexicale qui permet de
reconnaı̂tre les tokens via des valeurs numériques.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut associer à chaque symbole (terminal ou

non-terminal) une valeur ”sémantique” (indépendante
de la correction syntaxique).
L’analyse s’effectue après l’analyse lexicale qui permet de
reconnaı̂tre les tokens via des valeurs numériques.
Si 0 est la valeur numérique retourneé, le token
correspond à la fin du fichier.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut associer à chaque symbole (terminal ou

non-terminal) une valeur ”sémantique” (indépendante
de la correction syntaxique).
L’analyse s’effectue après l’analyse lexicale qui permet de
reconnaı̂tre les tokens via des valeurs numériques.
Si 0 est la valeur numérique retourneé, le token
correspond à la fin du fichier.
Bison fait appel à la fonction yylex() de Flex à chaque
fois qu’un token est nécessaire à la suite de l’analyse
syntaxique.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut associer à chaque symbole (terminal ou

non-terminal) une valeur ”sémantique” (indépendante
de la correction syntaxique).
L’analyse s’effectue après l’analyse lexicale qui permet de
reconnaı̂tre les tokens via des valeurs numériques.
Si 0 est la valeur numérique retourneé, le token
correspond à la fin du fichier.
Bison fait appel à la fonction yylex() de Flex à chaque
fois qu’un token est nécessaire à la suite de l’analyse
syntaxique.
L’association d’une valeur à un token se fait via la
variable globale de Bison nommée yylval et qui est de
type YYSTYPE.
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Association d’une valeur aux symboles

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Par défaut, YYSTYPE correspond au type int.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Par défaut, YYSTYPE correspond au type int.

Il est possible de redéfinir le type YYSTYPE via la
macro ”#define”. La redéfinition s’effectue dans la
section des définitions.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Par défaut, YYSTYPE correspond au type int.

Il est possible de redéfinir le type YYSTYPE via la
macro ”#define”. La redéfinition s’effectue dans la
section des définitions.
Il se peut que les valeurs des tokens aient des types
différents.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Par défaut, YYSTYPE correspond au type int.

Il est possible de redéfinir le type YYSTYPE via la
macro ”#define”. La redéfinition s’effectue dans la
section des définitions.
Il se peut que les valeurs des tokens aient des types
différents.
Pour traiter ce cas, on peut définir une union des types
via la clause %union. Par exemple, si l’on veut associer
aux tokens des valeurs de type ”entier” et ”chaı̂ne de
caractères”, on écrira :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Par défaut, YYSTYPE correspond au type int.

Il est possible de redéfinir le type YYSTYPE via la
macro ”#define”. La redéfinition s’effectue dans la
section des définitions.
Il se peut que les valeurs des tokens aient des types
différents.
Pour traiter ce cas, on peut définir une union des types
via la clause %union. Par exemple, si l’on veut associer
aux tokens des valeurs de type ”entier” et ”chaı̂ne de
caractères”, on écrira :
%union {

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Par défaut, YYSTYPE correspond au type int.

Il est possible de redéfinir le type YYSTYPE via la
macro ”#define”. La redéfinition s’effectue dans la
section des définitions.
Il se peut que les valeurs des tokens aient des types
différents.
Pour traiter ce cas, on peut définir une union des types
via la clause %union. Par exemple, si l’on veut associer
aux tokens des valeurs de type ”entier” et ”chaı̂ne de
caractères”, on écrira :
%union {
int ival;

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Par défaut, YYSTYPE correspond au type int.

Il est possible de redéfinir le type YYSTYPE via la
macro ”#define”. La redéfinition s’effectue dans la
section des définitions.
Il se peut que les valeurs des tokens aient des types
différents.
Pour traiter ce cas, on peut définir une union des types
via la clause %union. Par exemple, si l’on veut associer
aux tokens des valeurs de type ”entier” et ”chaı̂ne de
caractères”, on écrira :
%union {
int ival;
char ∗ str val }
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Association d’une valeur aux symboles

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {
int ival;

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {
int ival;
char ∗ str val;

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {
int ival;
char ∗ str val;
} YYSTYPE;

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {
int ival;
char ∗ str val;
} YYSTYPE;
Une fois le type YYSYTPE spécifié, il faut indiquer quel
membre de l’union utiliser pour les divers tokens et
non-terminaux.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {
int ival;
char ∗ str val;
} YYSTYPE;
Une fois le type YYSYTPE spécifié, il faut indiquer quel
membre de l’union utiliser pour les divers tokens et
non-terminaux. Pour cale, on utilise la clause
< nom du type > dans la partie ”déclaration”.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {
int ival;
char ∗ str val;
} YYSTYPE;
Une fois le type YYSYTPE spécifié, il faut indiquer quel
membre de l’union utiliser pour les divers tokens et
non-terminaux. Pour cale, on utilise la clause
< nom du type > dans la partie ”déclaration”.
Par exemple, on écrira :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {
int ival;
char ∗ str val;
} YYSTYPE;
Une fois le type YYSYTPE spécifié, il faut indiquer quel
membre de l’union utiliser pour les divers tokens et
non-terminaux. Pour cale, on utilise la clause
< nom du type > dans la partie ”déclaration”.
Par exemple, on écrira :
%token < ival > NUMBER

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

On peut aussi, de manière équivalente, redéfinir dans la

partie des déclarations, le type YYSTYPE comme suit :
%union {
int ival;
char ∗ str val;
} YYSTYPE;
Une fois le type YYSYTPE spécifié, il faut indiquer quel
membre de l’union utiliser pour les divers tokens et
non-terminaux. Pour cale, on utilise la clause
< nom du type > dans la partie ”déclaration”.
Par exemple, on écrira :
%token < ival > NUMBER
%token < str val > IDENT
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Association d’une valeur aux symboles

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Pour les non-terminaux, on écrira :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Association d’une valeur aux symboles

Pour les non-terminaux, on écrira :

%type < ival > exp

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Puisque l’analyse syntaxique utilise le résultat de l’analyse

lexicale, il faut que le fichier Flex utilisé dispose de
certaines informations, notamment les noms de tokens
ainsi que les types des valeurs qui seront associées aux
tokens.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Puisque l’analyse syntaxique utilise le résultat de l’analyse

lexicale, il faut que le fichier Flex utilisé dispose de
certaines informations, notamment les noms de tokens
ainsi que les types des valeurs qui seront associées aux
tokens.
Dans la partie ”déclarations” du fichier Flex, on écrira la
ligne :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Puisque l’analyse syntaxique utilise le résultat de l’analyse

lexicale, il faut que le fichier Flex utilisé dispose de
certaines informations, notamment les noms de tokens
ainsi que les types des valeurs qui seront associées aux
tokens.
Dans la partie ”déclarations” du fichier Flex, on écrira la
ligne :
#include ”parser .tab.h”

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Puisque l’analyse syntaxique utilise le résultat de l’analyse

lexicale, il faut que le fichier Flex utilisé dispose de
certaines informations, notamment les noms de tokens
ainsi que les types des valeurs qui seront associées aux
tokens.
Dans la partie ”déclarations” du fichier Flex, on écrira la
ligne :
#include ”parser .tab.h”
où ”parser ” désigne le nom du fichier Bison.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Puisque l’analyse syntaxique utilise le résultat de l’analyse

lexicale, il faut que le fichier Flex utilisé dispose de
certaines informations, notamment les noms de tokens
ainsi que les types des valeurs qui seront associées aux
tokens.
Dans la partie ”déclarations” du fichier Flex, on écrira la
ligne :
#include ”parser .tab.h”
où ”parser ” désigne le nom du fichier Bison.
Enfin, les règles d’analsye lexicale doivent être écrites de
manière à ce Bison dispose de l’information relative au
token reconnu et à sa valeur.
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Interaction avec l’analyseur lexical

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Ainsi, on écrira par exemple :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Ainsi, on écrira par exemple :

[0 − 9]+ {[Link] = atoi(yytext);
return NUMBER; }

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Interaction avec l’analyseur lexical

Ainsi, on écrira par exemple :

[0 − 9]+ {[Link] = atoi(yytext);
return NUMBER; }
[a − zA − Z ]+ {[Link] val = strdup(yytext);
return IDENT ; }

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

A chaque règle peut être associée une action qui

correspond à un bloc d’instructions C et qui sera exécuté
lorsque l’analyseur syntaxique aura reconnu la structure
spécifiée par la règle.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

A chaque règle peut être associée une action qui

correspond à un bloc d’instructions C et qui sera exécuté
lorsque l’analyseur syntaxique aura reconnu la structure
spécifiée par la règle.
Ces actions peuvent retourner une valeur et utiliser les
valeurs retournées par les actions de l’analyseur lexical.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

A chaque règle peut être associée une action qui

correspond à un bloc d’instructions C et qui sera exécuté
lorsque l’analyseur syntaxique aura reconnu la structure
spécifiée par la règle.
Ces actions peuvent retourner une valeur et utiliser les
valeurs retournées par les actions de l’analyseur lexical.
Pour retourner une valeur, on utilise le symbole ”$$”.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

A chaque règle peut être associée une action qui

correspond à un bloc d’instructions C et qui sera exécuté
lorsque l’analyseur syntaxique aura reconnu la structure
spécifiée par la règle.
Ces actions peuvent retourner une valeur et utiliser les
valeurs retournées par les actions de l’analyseur lexical.
Pour retourner une valeur, on utilise le symbole ”$$”.
Par exemple, si on veut retourner la valeur 1, on écrira :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

A chaque règle peut être associée une action qui

correspond à un bloc d’instructions C et qui sera exécuté
lorsque l’analyseur syntaxique aura reconnu la structure
spécifiée par la règle.
Ces actions peuvent retourner une valeur et utiliser les
valeurs retournées par les actions de l’analyseur lexical.
Pour retourner une valeur, on utilise le symbole ”$$”.
Par exemple, si on veut retourner la valeur 1, on écrira :
{$$ = 1; }

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

A chaque règle peut être associée une action qui

correspond à un bloc d’instructions C et qui sera exécuté
lorsque l’analyseur syntaxique aura reconnu la structure
spécifiée par la règle.
Ces actions peuvent retourner une valeur et utiliser les
valeurs retournées par les actions de l’analyseur lexical.
Pour retourner une valeur, on utilise le symbole ”$$”.
Par exemple, si on veut retourner la valeur 1, on écrira :
{$$ = 1; }
Pour utiliser les valeur retournées par les actions de
l’analyseur lexical, une action peut invoquer les
pseudo-variables $1, $2, ...etc.
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Actions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Ces variables correspondent aux valeurs retournées par les

actions correpondant aux éléments de la partie droite de
la règle.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Ces variables correspondent aux valeurs retournées par les

actions correpondant aux éléments de la partie droite de
la règle.
Par exemple, étant donné la règle :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Ces variables correspondent aux valeurs retournées par les

actions correpondant aux éléments de la partie droite de
la règle.
Par exemple, étant donné la règle :
A : B C D {f ($1, $2, $3); }

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Ces variables correspondent aux valeurs retournées par les

actions correpondant aux éléments de la partie droite de
la règle.
Par exemple, étant donné la règle :
A : B C D {f ($1, $2, $3); }
les valeurs $1, $2 et $3 correspondent aux valeurs
retournées par les actions spécifiées dans les règles
utilisées reconnaissant A, B et C .

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Ces variables correspondent aux valeurs retournées par les

actions correpondant aux éléments de la partie droite de
la règle.
Par exemple, étant donné la règle :
A : B C D {f ($1, $2, $3); }
les valeurs $1, $2 et $3 correspondent aux valeurs
retournées par les actions spécifiées dans les règles
utilisées reconnaissant A, B et C .
Voici un exemple plus concret :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Ces variables correspondent aux valeurs retournées par les

actions correpondant aux éléments de la partie droite de
la règle.
Par exemple, étant donné la règle :
A : B C D {f ($1, $2, $3); }
les valeurs $1, $2 et $3 correspondent aux valeurs
retournées par les actions spécifiées dans les règles
utilisées reconnaissant A, B et C .
Voici un exemple plus concret :
exp : 0 (0 exp 0 )0 { $$ = $2; }

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Par défaut, si aucune valeur n’est indiquée comme valeur

de retour de l’action, c’est $1 qui est retournée.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Par défaut, si aucune valeur n’est indiquée comme valeur

de retour de l’action, c’est $1 qui est retournée.
Bison permet d’exécuter des actions avant la fin de
l’application d’une règle.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Par défaut, si aucune valeur n’est indiquée comme valeur

de retour de l’action, c’est $1 qui est retournée.
Bison permet d’exécuter des actions avant la fin de
l’application d’une règle.
Il est donc possible d’indiquer une action entre deux
éléments de la partie droite d’une règle.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Par défaut, si aucune valeur n’est indiquée comme valeur

de retour de l’action, c’est $1 qui est retournée.
Bison permet d’exécuter des actions avant la fin de
l’application d’une règle.
Il est donc possible d’indiquer une action entre deux
éléments de la partie droite d’une règle.
Par exemple, la règle :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Par défaut, si aucune valeur n’est indiquée comme valeur

de retour de l’action, c’est $1 qui est retournée.
Bison permet d’exécuter des actions avant la fin de
l’application d’une règle.
Il est donc possible d’indiquer une action entre deux
éléments de la partie droite d’une règle.
Par exemple, la règle :
A : B { $$ = 1; }

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Par défaut, si aucune valeur n’est indiquée comme valeur

de retour de l’action, c’est $1 qui est retournée.
Bison permet d’exécuter des actions avant la fin de
l’application d’une règle.
Il est donc possible d’indiquer une action entre deux
éléments de la partie droite d’une règle.
Par exemple, la règle :
A : B { $$ = 1; }
C { x = $2; y = $3; };

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Par défaut, si aucune valeur n’est indiquée comme valeur

de retour de l’action, c’est $1 qui est retournée.
Bison permet d’exécuter des actions avant la fin de
l’application d’une règle.
Il est donc possible d’indiquer une action entre deux
éléments de la partie droite d’une règle.
Par exemple, la règle :
A : B { $$ = 1; }
C { x = $2; y = $3; };
aura pour effet d’affecter la valeur 1 à la variable x et la
valeur retournée par la règle utilisée pour reconnaı̂tre C à
la variable y .
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Actions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

On peut spécifier le ”type d’une valeur” dans une règle.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

On peut spécifier le ”type d’une valeur” dans une règle.

Ce qui peut être utile par exemple lorsqu’un token
”mono-lettre” n’a pas été déclaré.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

On peut spécifier le ”type d’une valeur” dans une règle.

Ce qui peut être utile par exemple lorsqu’un token
”mono-lettre” n’a pas été déclaré.
Par exemple, on peut écrire :

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

On peut spécifier le ”type d’une valeur” dans une règle.

Ce qui peut être utile par exemple lorsqu’un token
”mono-lettre” n’a pas été déclaré.
Par exemple, on peut écrire :
A : B C { f ($ < ival > 1); $ < str val > $ =
”merci”; };

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Il est possible d’appeler implicitement la fonction qui

effectue l’analyse syntaxique en invoquant son nom
”yyparse”().

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Il est possible d’appeler implicitement la fonction qui

effectue l’analyse syntaxique en invoquant son nom
”yyparse”().
Lors de l’exécution de la fonction ”yyparse”(), si une
erreur de syntaxe est détectée, la fonction ”yyerror”()
est appelée afin qu’un message d’erreur s’affiche.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Il est possible d’appeler implicitement la fonction qui

effectue l’analyse syntaxique en invoquant son nom
”yyparse”().
Lors de l’exécution de la fonction ”yyparse”(), si une
erreur de syntaxe est détectée, la fonction ”yyerror”()
est appelée afin qu’un message d’erreur s’affiche.
Par défaut, en cas d’une erreur de syntaxe, la fonction
”yyparse”() déclenche l’arrêt immédiat de l’analyse
syantique après l’exécution de la fonction ”yyperror”().

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Il est possible d’appeler implicitement la fonction qui

effectue l’analyse syntaxique en invoquant son nom
”yyparse”().
Lors de l’exécution de la fonction ”yyparse”(), si une
erreur de syntaxe est détectée, la fonction ”yyerror”()
est appelée afin qu’un message d’erreur s’affiche.
Par défaut, en cas d’une erreur de syntaxe, la fonction
”yyparse”() déclenche l’arrêt immédiat de l’analyse
syantique après l’exécution de la fonction ”yyperror”().
Celle-ci, affiche par défaut le message : ”syntax error”.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Actions

Il est possible d’appeler implicitement la fonction qui

effectue l’analyse syntaxique en invoquant son nom
”yyparse”().
Lors de l’exécution de la fonction ”yyparse”(), si une
erreur de syntaxe est détectée, la fonction ”yyerror”()
est appelée afin qu’un message d’erreur s’affiche.
Par défaut, en cas d’une erreur de syntaxe, la fonction
”yyparse”() déclenche l’arrêt immédiat de l’analyse
syantique après l’exécution de la fonction ”yyperror”().
Celle-ci, affiche par défaut le message : ”syntax error”.
En cas d’erreur de syntaxe, la fonction ”yyparse”()
retourne une valeur non nulle.
Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison
Exercices corrigés

Énoncé 1.1

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Exercices corrigés

Énoncé 1.1
Écrire un interpréteur d’expressions arithmétiques sur les
”entiers” et n’utilisant que les opérateurs + ( additions)
et ∗ (multiplications).

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Exercices corrigés

Énoncé 1.1
Écrire un interpréteur d’expressions arithmétiques sur les
”entiers” et n’utilisant que les opérateurs + ( additions)
et ∗ (multiplications).
Modifier cet interpréteur pour qu’il puisse traiter les
”doubles”.

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Exercices corrigés

Code Flex

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Exercices corrigés

Code Bison

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Exercices corrigés

Code Flex

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison

Exercices corrigés

Code Bison

Prof. Abdelmajid Dargham Chapitre 8 : L’outil d’analyse syntaxique Bison