L’outil d’analyse syntaxique
Bison
Introduction
Une fois l’analyse lexicale est 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é sur une grammaire donnée.
Un programme Bison est enregistré avec l’extension ”.y”.
Introduction
Etapes 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.
Introduction
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]
Format d’un fichier Bison
%{
déclaration (en C) de variables, constantes, inclusions de fichiers,…
}%
déclarations des unités lexicales utilisées
déclarations de priorités et de types
%%
règles de production et actions sémantiques
%%
routines C et bloc principal
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).
Les symboles terminaux utilisables dans la description du langage sont
des unités lexicales que l’on doit impérativement déclarer par %token
nom. Par exemple :
des caractères entre quotes. Par exemple: ‘+’ ‘a’
Les symboles non-terminaux sont les caractères ou les chaînes de
caractères non déclarées comme unités lexicales
Yacc/bison fait la différence entre majuscules et minuscules SI et si ne
désignent pas le même objet.
Déclarations et définitions
Cas des opérateurs
Lorsque les tokens correspondent à des opérateurs pour lesquels on
souhaite spécifier une propriété d’associativité, ou utilise left et right
au lieu de token.
Par exemple, on écrira :
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 ‘^' a une priorité plus grande que
les opérateurs '+' et '−' (qui sont de même priorité).
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 '−' comme un opérateur ayant même précédence qu’un
token de nom NEG, on écrira :
' −' %prec NEG
afin de ne pas associer au ”moins unaire” la même précédence que le
”moins binaire”.
Déclarations et définitions
Il ne faut pas oublier de retourner les unités lexicales (les tokens) au
niveau de la partie « règles » du programme flex associé
Déclarations et définitions
Chaque non-terminal doit apparaître au moins une fois comme partie
gauche d’une règle.
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
Par 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 ambigüe, Bison sera confronté à des conflits
”shift/reduce” ou ”reduce/shift”.
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).
Lorsqu’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 :
Règles
Les règles de production sont des suites d’instructions de la forme
non-terminal : prod1
|prod2
…
| prodn
;
Les actions sémantiques sont des instructions en C insérées dans les
règles de production. Elles sont exécutées chaque fois que la production
est vérifiée.
Exemple:
Association d’une valeur aux
symboles
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.
L’analyseur syntaxique et l’analyseur lexical peuvent communiquer
entre eux par l’intermédiaire de la variable int yylval
Association d’une valeur aux
symboles
Dans une action lexicale (dans le fichier flex par exemple), l’instruction
return(unité) permet de renvoyer à l’analyseur syntaxique l’unité
lexicale unité.
La valeur de cette unité lexicale peut être rangée dans yylval.
L’analyseur syntaxique prendra automatiquement le contenu de yylval
comme valeur de l’attribut associé à cette unité lexicale.
Association d’une valeur aux
symboles
yylval est de type YYSTYPE.
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 :
permet de stocker dans yylval à la fois des int des double et des char*.
Association d’une valeur aux
symboles
L’analyseur lexical pourra par exemple contenir
Le type des lexèmes doit alors être précisé en utilisant les noms des
champs de l’union
Association d’une valeur aux
symboles
On peut également typer des non-terminaux pour pouvoir associer une
valeur de type autre que int à un non-terminal par
Attributs
A chaque symbole (terminal ou non) est associé une valeur (de type entier
par défaut) Cette valeur peut être utilisée dans les actions sémantiques
comme un attribut synthétisé).
Le symbole $$ référence la valeur de l’attribut associé au non-terminal de la
partie gauche, tandis que $i référence la valeur associée au i-ème symbole
(terminal ou non-terminal) ou action sémantique de la partie droite.
Ces variables correspondent aux valeurs retournées par les actions
correspondant aux éléments de la partie droite de la règle.
Par exemple, étant donné la règle :
A : B C D { ($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 B, C et D
Actions
Exemple:
Par défaut lorsqu’aucune action n’est indiquée, c’est $1 qui est
retournée et yacc/bison génère l’action {$$=$1;}
Actions
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 :
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.
Actions
Il est possible d’appeler 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.
la fonction ”yyparse”() déclenche l’arrêt immédiat de l’analyse syntaxique
après l’exécution de la fonction ”yyerror”().
Celle-ci, affiche par défaut le message : ”syntax error”.
la fonction ”yyparse”() retourne une valeur non nulle.
Variables fonctions et actions prédéfinies
yyparse(): appel de l’analyseur syntaxique
YYACCEPT: instruction qui permet de stopper l’analyseur syntaxique
YYABORT : instruction qui permet également de stopper l’analyseur mais
yyparse() retourne alors ce qui peut être utilisé pour signifier l’echec de l
analyseur
main(): le main par défaut se contente d’appeler yyparse(). L’utilisateur
peut écrire son propre main dans la partie du bloc principal.
Exemple
Cet exemple lit des listes d’entiers précédées soit du mot somme, soit
du mot produit.
Une liste d’entiers est composée d’entiers séparés par des virgules et se
termine par un point.
Lorsque la liste débute par somme, l’exécutable doit afficher la somme des
entiers,
lorsqu’elle débute par produit il doit en afficher le produit,
Le fichier doit se terminer par $.
Cet exemple utilise la fonction yylex générée par le compilateur flex à
partir du fichier de spécification suivant:
Le fichier de spécifications bison est alors le suivant
Exécution
utiliser le compilateur bison du nom.y avec l’option -d qui produit un fichier
[Link].h contenant les définitions (sous forme de #define) des unités lexicales (les
tokens) rencontrées et du type YYSTYPE s’il est redéfini
Bison –d
nom.y nom.y [Link].h
Dans la partie ”déclarations” du fichier Flex, on écrira la ligne :
#include ”nom .tab.h”
Compiler le fichier flex par
[Link] Flex [Link]
[Link].c
x
lors de la compilation C du fichier [Link].c, il faut faire le lien avec [Link].c et
rajouter la bibliothèque flex lors de la compilation C du fichier [Link].c avec :
gcc [Link].c [Link].c -ly -lfl
attention à l’ordre de ces bibliothèques
Exercice
Enoncé
é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”.
