Créer son propre langage de programmation de A à Z
<< Analyseur lexical | Analyseur syntaxique | Analyse sémantique >>
Nous avons créé un analyseur lexical. Maintenant il s'agira de faire l'analyseur syntaxique. C'est la partie la plus complexe du cours. Bison permet de générer un analyseur syntaxique et il est très bien utilisé avec Flex. Notre analyseur syntaxique recevra les tokens qu'enverra l'analyseur lexical. Les tokens sont en fait les entités lexicales lues par Flex. Ils correspondraient aux terminaux du langage. Au fur et à mesure que notre futur analyseur syntaxique recevra les tokens, il regardera si leur ordre est correct ou non. Un fichier Bison génère un fichier en C (tout comme fait Flex aussi quand il génère son analyseur lexical) où il va construire la fonction yyparse(). Cette fonction parse du contenu textuel et fait une analyse syntaxique. Elle appelle automatiquement la fonction yylex() de notre analyseur lexical pour récupérer les tokens. On a donc plus besoin de la fonction main() dans notre fichier Flex.
J'ai construit un petit fichier d'entête commun aux deux fichiers :
⚠ (:source lang=c header="simple.h" linenum:)
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "syntaxe_simple.tab.h"
int yylex(void);
void yyerror(char*);
(:sourcend:)
A la ligne 3, j'ai inclus le futur fichier d'entête qui sera généré par Bison. Il sera surtout utile pour Flex car on a à l'intérieur toutes les déclarations des tokens. Les noms de fichiers que génèrent Bison sont toujours par défaut sous la forme de <nom_fichier>.tab.h et <nom_fichier>.tab.c.
Je donne le code de l'analyseur syntaxique Bison commenté :
⚠ (:source lang=c header="syntaxe_simple.y" linenum:)
%{
<:vspace>
#include "simple.h"
#include <string.h>
bool error_syntaxical=false;
extern unsigned int lineno;
extern bool error_lexical;
<:vspace>
%}
<:vspace>
/* L'union dans Bison est utilisee pour typer nos tokens ainsi que nos non terminaux. Ici nous avons declare une union avec deux types : nombre de type int et texte de type pointeur de char (char*) */
<:vspace>
%union {
long nombre;
char* texte;
}
<:vspace>
/* Nous avons ici les operateurs, ils sont definis par leur ordre de priorite. Si je definis par exemple la multiplication en premier et l'addition apres, le + l'emportera alors sur le * dans le langage. Les parenthese sont prioritaires avec %right */
<:vspace>
%left TOK_PLUS TOK_MOINS /* +- */
%left TOK_MUL TOK_DIV /* /* */
%left TOK_ET
%left TOK_OU TOK_NON /* et ou non */
%right TOK_PARG TOK_PARD /* () */
<:vspace>
/* Nous avons la liste de nos expressions (les non terminaux). Nous les typons tous en texte (pointeur vers une zone de char). On a legitimement cree un non terminal variable afin d'isoler le token TOK_VAR et avoir une expression qui contiendra uniquement le nom de la variable */
<:vspace>
%type<texte> code
%type<texte> instruction
%type<texte> variable
%type<texte> affectation
%type<texte> affichage
%type<texte> expression_arithmetique
%type<texte> expression_booleenne
%type<texte> addition
%type<texte> soustraction
%type<texte> multiplication
%type<texte> division
<:vspace>
/* Nous avons la liste de nos tokens (les terminaux de notre grammaire) */
<:vspace>
%token<texte> TOK_NOMBRE
%token TOK_VRAI /* true */
%token TOK_FAUX /* false */
%token TOK_AFFECT /* = */
%token TOK_FINSTR /* ; */
%token TOK_AFFICHER /* afficher */
%token<texte> TOK_VAR /* variable */
<:vspace>
%%
<:vspace>
/* Nous definissons toutes les regles grammaticales de chaque non terminal de notre langage. Par defaut on commence a definir l'axiome, c'est a dire ici le non terminal code. Si nous le definissons pas en premier nous devons le specifier en option dans Bison avec %start */
<:vspace>
code: %empty{}
|
code instruction{
printf("Resultat : C'est une instruction valide !\n\n");
}
|
code error{
fprintf(stderr,"\tERREUR : Erreur de syntaxe a la ligne %d.\n",lineno);
error_syntaxical=true;
};
<:vspace>
instruction: affectation{
printf("\tInstruction type Affectation\n");
}
|
affichage{
printf("\tInstruction type Affichage\n");
};
<:vspace>
/* L'expression variable contient uniquement le nom de la variable */
variable: TOK_VAR{
/* $1 est la chaine de texte de l'expression retournee par l'analyseur lexical Flex. */
printf("\t\t\tVariable %s\n",$1);
/* On affecte comme valeur a l'expression (variable Bison $$) une copie de $1. Copie car $1 sera automatiquement efface apres sortie de la "routine". Toutes ces variables Bison nous permettent en realite de construire un arbre syntaxique. */
$$=strdup($1);
};
<:vspace>
affectation: variable TOK_AFFECT expression TOK_FINSTR{
/* $1 est la valeur du premier non terminal. Ici c'est la valeur du non terminal variable. $3 est la valeur du 2nd non terminal. */
printf("\t\tAffectation sur la variable %s\n",$1);
};
<:vspace>
affichage: TOK_AFFICHER expression TOK_FINSTR{
printf("\t\tAffichage de la valeur de l'expression %s\n",$2);
};
<:vspace>
expression_arithmetique: TOK_NOMBRE{
printf("\t\t\tNombre : %ld\n",$1);
/* Comme le token TOK_NOMBRE est de type entier et que on a type expression_arithmetique comme du texte, il nous faut convertir la valeur en texte. */
int length=snprintf(NULL,0,"%ld",$1);
char* str=malloc(length+1);
snprintf(str,length+1,"%ld",$1);
$$=strdup(str);
free(str);
}
|
variable{
}
|
addition{
}
|
soustraction{
}
|
multiplication{
}
|
division{
}
|
TOK_PARG expression_arithmetique TOK_PARD{
printf("\t\t\tC'est une expression artihmetique entre parentheses\n");
$$=strcat(strcat(strdup("("),strdup($2)),strdup(")"));
};
<:vspace>
expression_booleenne: TOK_VRAI{
printf("\t\t\tBooleen Vrai\n");
$$=strdup("vrai");
}
|
TOK_FAUX{
printf("\t\t\tBooleen Faux\n");
$$=strdup("faux");
}
|
variable{
$$=strdup($1);
}
|
TOK_NON expression_booleenne{
printf("\t\t\tOperation booleenne Non\n");
$$=strcat(strdup("non "), strndup($2,sizeof(char)*strlen($2)));
}
|
expression_booleenne TOK_ET expression_booleenne{
printf("\t\t\tOperation booleenne Et\n");
$$=strcat(strcat(strdup($1),strdup(" et ")),strdup($3));
}
|
expression_booleenne TOK_OU expression_booleenne{
printf("\t\t\tOperation booleenne Ou\n");
$$=strcat(strcat(strdup($1),strdup(" ou ")),strdup($3));
}
|
TOK_PARG expression_booleenne TOK_PARD{
printf("\t\t\tC'est une expression booleenne entre parentheses\n");
$$=strcat(strcat(strdup("("),strdup($2)),strdup(")"));
};
<:vspace>
addition: expression_arithmetique TOK_PLUS expression_arithmetique{printf("\t\t\tAddition\n");$$=strcat(strcat(strdup($1),strdup("+")),strdup($3));};
soustraction: expression_arithmetique TOK_MOINS expression_arithmetique{printf("\t\t\tSoustraction\n");$$=strcat(strcat(strdup($1),strdup("-")),strdup($3));};
multiplication: expression_arithmetique TOK_MUL expression_arithmetique{printf("\t\t\tMultiplication\n");$$=strcat(strcat(strdup($1),strdup("*")),strdup($3));};
division: expression_arithmetique TOK_DIV expression_arithmetique{printf("\t\t\tDivision\n");$$=strcat(strcat(strdup($1),strdup("/")),strdup($3));};
<:vspace>
%%
<:vspace>
/* Dans la fonction main on appelle bien la routine yyparse() qui sera genere par Bison. Cette routine appellera yylex() de notre analyseur lexical. */
<:vspace>
int main(void){
printf("Debut de l'analyse syntaxique :\n");
yyparse();
printf("Fin de l'analyse !\n");
printf("Resultat :\n");
if(error_lexical){
printf("\t-- Echec : Certains lexemes ne font pas partie du lexique du langage ! --\n");
printf("\t-- Echec a l'analyse lexicale --\n");
}
else{
printf("\t-- Succes a l'analyse lexicale ! --\n");
}
if(error_syntaxical){
printf("\t-- Echec : Certaines phrases sont syntaxiquement incorrectes ! --\n");
printf("\t-- Echec a l'analyse syntaxique --\n");
}
else{
printf("\t-- Succes a l'analyse syntaxique ! --\n");
}
return EXIT_SUCCESS;
}
void yyerror(char *s) {
fprintf(stderr, "Erreur de syntaxe a la ligne %d: %s\n", lineno, s);
}
(:sourcend:)
Nous allons légèrement modifié notre analyseur lexical afin qu'il retourne des tokens à Bison :
⚠ (:source lang=c header="lexique_simple.lex" linenum:)
%{
<:vspace>
#include "simple.h"
unsigned int lineno=1;
bool error_lexical=false;
<:vspace>
%}
<:vspace>
%option noyywrap
<:vspace>
nombre 0|[1-9][[:digit:]]*
variable [[:alpha:]][[:alnum:]]*
<:vspace>
%%
<:vspace>
{nombre} {
sscanf(yytext, "%ld", &yylval.nombre);
return TOK_NOMBRE;
}
<:vspace>
"afficher" {return TOK_AFFICHER;}
<:vspace>
"=" {return TOK_AFFECT;}
<:vspace>
"+" {return TOK_PLUS;}
<:vspace>
"-" {return TOK_MOINS;}
<:vspace>
"*" {return TOK_MUL;}
<:vspace>
"/" {return TOK_DIV;}
<:vspace>
"(" {return TOK_PARG;}
<:vspace>
")" {return TOK_PARD;}
<:vspace>
"et" {return TOK_ET;}
<:vspace>
"ou" {return TOK_OU;}
<:vspace>
"non" {return TOK_NON;}
<:vspace>
";" {return TOK_FINSTR;}
<:vspace>
"vrai" {return TOK_VRAI;}
<:vspace>
"faux" {return TOK_FAUX;}
<:vspace>
"\n" {lineno++;}
<:vspace>
{variable} {
yylval.texte = yytext;
return TOK_VAR;
}
<:vspace>
" "|"\t" {}
<:vspace>
. {
fprintf(stderr,"\tERREUR : Lexeme inconnu a la ligne %d. Il s'agit de %s et comporte %d lettre(s)\n",lineno,yytext,yyleng);
error_lexical=true;
return yytext[0];
}
<:vspace>
%%
(:sourcend:)
On compile tout ça :
⚠ (:source lang=bash:)
flex -o lexique_simple.c lexique_simple.lex
bison -d syntaxe_simple.y
gcc -o simple lexique_simple.c syntaxe_simple.tab.c
(:sourcend:)
On teste notre analyseur syntaxique sur un fichier .simple :
⚠ (:source lang=text header="programme.simple" linenum:)
monEntier = 6 ; monBooleen = faux ;
<:vspace>
afficher monEntier ;
afficher monBooleen ;
afficher 4 ;
afficher non ( ( vrai et faux ) ou vrai ) ;
afficher 6/3 ;
(:sourcend:)
On passe le fichier à l'analyseur :
⚠ (:source lang=bash:)
./simple < programme.simple
(:sourcend:)
Le résultat est le suivant :
⚠ (:source lang=text:)
Debut de l'analyse syntaxique :
Variable monEntier
Nombre : 6
Affectation sur la variable monEntier
Instruction type Affectation
Resultat : C'est une instruction valide !
<:vspace>
Variable monBooleen
Booleen Faux
Affectation sur la variable monBooleen
Instruction type Affectation
Resultat : C'est une instruction valide !
<:vspace>
Variable monEntier
Affichage de la valeur de l'expression monEntier
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Variable monBooleen
Affichage de la valeur de l'expression monBooleen
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Nombre : 4
Affichage de la valeur de l'expression 4
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Booleen Vrai
Booleen Faux
Operation booleenne Et
C'est une expression booleenne entre parentheses
Booleen Vrai
Operation booleenne Ou
C'est une expression booleenne entre parentheses
Operation booleenne Non
Affichage de la valeur de l'expression non ((vrai et faux) ou vrai)
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Nombre : 6
Nombre : 3
Division
Affichage de la valeur de l'expression 6/3
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Fin de l'analyse !
Resultat :
-- Succes a l'analyse lexicale ! --
-- Succes a l'analyse syntaxique ! --
(:sourcend:)
Maintenant testons-le avec un programme faux lexicalement. Nous allons simplement rajouter les caractères spéciaux @$# à la fin du fichier. Le résultat est le suivant :
⚠ (:source lang=text:)
Debut de l'analyse syntaxique :
Variable monEntier
Nombre : 6
Affectation sur la variable monEntier
Instruction type Affectation
Resultat : C'est une instruction valide !
<:vspace>
Variable monBooleen
Booleen Faux
Affectation sur la variable monBooleen
Instruction type Affectation
Resultat : C'est une instruction valide !
<:vspace>
Variable monEntier
Affichage de la valeur de l'expression monEntier
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Variable monBooleen
Affichage de la valeur de l'expression monBooleen
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Nombre : 4
Affichage de la valeur de l'expression 4
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Booleen Vrai
Booleen Faux
Operation booleenne Et
C'est une expression booleenne entre parentheses
Booleen Vrai
Operation booleenne Ou
C'est une expression booleenne entre parentheses
Operation booleenne Non
Affichage de la valeur de l'expression non ((vrai et faux) ou vrai)
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Nombre : 6
Nombre : 3
Division
Affichage de la valeur de l'expression 6/3
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
ERREUR : Lexeme inconnu a la ligne 8. Il s'agit de @ et comporte 1 lettre(s)
Erreur de syntaxe a la ligne 8: syntax error
ERREUR : Erreur de syntaxe a la ligne 8.
ERREUR : Erreur de syntaxe a la ligne 8.
ERREUR : Lexeme inconnu a la ligne 8. Il s'agit de $ et comporte 1 lettre(s)
ERREUR : Erreur de syntaxe a la ligne 8.
ERREUR : Lexeme inconnu a la ligne 8. Il s'agit de # et comporte 1 lettre(s)
ERREUR : Erreur de syntaxe a la ligne 8.
Fin de l'analyse !
Resultat :
-- Echec : Certains lexemes ne font pas partie du lexique du langage ! --
-- Echec a l'analyse lexicale --
-- Echec : Certaines phrases sont syntaxiquement incorrectes ! --
-- Echec a l'analyse syntaxique --
(:sourcend:)
Nous pouvons voir en toute logique des lexèmes non reconnus par l'analyseur lexical. Comme le programme ne passe pas à l'analyse lexicale, il ne passe évidemment pas par l'analyse syntaxique. Il n'existe pas de tokens correspondant à ces lexèmes et par conséquent l'analyseur lexical envoie à l'analyseur syntaxique des choses qui ne connait pas. L'analyseur syntaxique voit ensuite qu'aucune règle ne correspond. Il met alors échec à l'analyse syntaxique.
Maintenant testons-le sur un programme faux syntaxiquement mais lexicalement correct. Reprenons le fichier programme_faux.simple :
⚠ (:source lang=text header="programme_faux.simple" linenum:)
68 afficher;
france japon usa = 85;
japon = 118 et afficher japon;
vrai+faux=19;
(:sourcend:)
Le résultat est le suivant :
⚠ (:source lang=text:)
Erreur de syntaxe a la ligne 1: syntax error
ERREUR : Erreur de syntaxe a la ligne 1.
ERREUR : Erreur de syntaxe a la ligne 1.
ERREUR : Erreur de syntaxe a la ligne 1.
ERREUR : Erreur de syntaxe a la ligne 1.
Variable france
ERREUR : Erreur de syntaxe a la ligne 2.
Variable japon
ERREUR : Erreur de syntaxe a la ligne 2.
Variable usa
Nombre : 85
Affectation sur la variable usa
Instruction type Affectation
Resultat : C'est une instruction valide !
<:vspace>
Variable japon
Nombre : 118
Erreur de syntaxe a la ligne 3: syntax error
ERREUR : Erreur de syntaxe a la ligne 3.
ERREUR : Erreur de syntaxe a la ligne 3.
Variable japon
Affichage de la valeur de l'expression japon
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Erreur de syntaxe a la ligne 4: syntax error
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
Fin de l'analyse !
Resultat :
-- Succes a l'analyse lexicale ! --
-- Echec : Certaines phrases sont syntaxiquement incorrectes ! --
-- Echec a l'analyse syntaxique --
(:sourcend:)
Sans surprise, il met succès à l'analyse lexicale et échec à l'analyse syntaxique. Notez toute fois qu'apparaît 2 fois "Resultat : C'est une instruction valide !". En réalité parmi ces instructions fausses, il y a à l'intérieur des morceaux d'instructions valides. A la ligne 2, il reconnaît une instruction valide usa = 85; à l'intérieur de la fausse instruction france japon usa = 85;. De même à la ligne 5, il reconnaît afficher japon; dans l'instruction syntaxiquement incorrecte japon = 118 et afficher japon;.
A la compilation de notre fichier Bison, vous avez certainement vu ces avertissements :
⚠ (:source lang=text:)
syntaxe_simple.y: avertissement: 2 conflits par réduction/réduction [-Wconflicts-rr]
(:sourcend:)
Bison nous prévient en réalité d'une ambiguïté dans notre grammaire. Si on revient quelques secondes sur notre grammaire, nous pouvons voir qu'effectivement il y a quelque chose qui cloche sur ces deux lignes :
⚠ (:source lang=bnf:)
<expression_arithmetique> ::= variable | nombre | <addition> | <soustraction> | <multiplication> | <division> | "(" <expression_arithmetique> ")"
<expression_booleenne> ::= variable | vrai | faux | <et> | <ou> | <non> | "(" <expression_booleenne> ")"
(:sourcend:)
Pour mieux comprendre, regardons les résultats des analyses pour un autre programme :
⚠ (:source lang=text header="programme.simple" linenum:)
monEntier = 5;
afficher (monEntier et vrai) ou monEntier;
(:sourcend:)
Ce qui donne :
⚠ (:source lang=text:)
Debut de l'analyse syntaxique :
Variable monEntier
Nombre : 5
Affectation sur la variable monEntier
Instruction type Affectation
Resultat : C'est une instruction valide !
<:vspace>
Variable monEntier
Booleen Vrai
Operation booleenne Et
C'est une expression booleenne entre parentheses
Variable monEntier
Operation booleenne Ou
Affichage de la valeur de l'expression (monEntier et vrai) ou monEntier
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Fin de l'analyse !
Resultat :
-- Succes a l'analyse lexicale ! --
-- Succes a l'analyse syntaxique ! --
(:sourcend:)
Notre grammaire dit qu'une expression arithmétique peut être une variable. Et qu'une expression booléenne peut être aussi une variable. Or si Bison lit une variable, comment pourra-t-il savoir s'il s'agit d'une expression arithmétique ou d'une expression booléenne ? Il ne s'agit que d'avertissements. Mais cela pose problème quand même car il supposerait que l'on puisse avoir des expressions booléennes dans des expressions arithmétiques. Si on assigne à monEntier la valeur numérique 5, on peut écrire des expressions comme "(monEntier et vrai) ou monEntier" car elles respecteraient la syntaxe de notre langage. Et pourtant cela n'a pas de sens. On peut mettre en place une analyse sémantique et vérifier le type des variables. Il s'agirait alors de mettre en place une structure de donnée telle qu'une table de hachage. Ou on peut laisser comme tel, prendre le risque de générer du code faux et laisser le compilateur C faire cette analyse pour nous. Nous allons plutôt changer la syntaxe du langage Simple pour lever cette malheureuse ambiguïté. Vérifier le typage des variables à l'analyse syntaxique et non pas à l'analyse sémantique imposera en revanche au programmeur une certaine rigueur dans le nommage de ces variables. Car ce sera forcément par le nom des variables que l'analyseur pourra déterminer leur types. L'avantage je trouve, c'est que le programmeur aura toujours connaissance du type quand il utilise les variables. Nous allons devoir enrichir le lexique de notre langage Simple. On va dire que les variables booléennes devront commencer par un 'b' minuscule et les variables entières par un 'e' minuscule. Le caractère '_' sera permis dans le nom des variables.
Révision de la syntaxe de Simple :
⚠ (:source lang=bnf linenum:)
@@ ::= <instruction> @@ | <none>
<:vspace>
<instruction> ::= <affectation> | <affichage>
<:vspace>
<expression> ::= <expression_booleenne> | <expression_arithmetique>
<:vspace>
<variable> ::= variable_booleenne | variable_arithmetique
<:vspace>
<affectation> ::= ( variable_arithmetique "=" <expression_arithmetique> | variable_booleenne "=" <expression_booleenne> ) ";"
<:vspace>
<affichage> ::= "afficher" <expression> ";"
<:vspace>
<expression_arithmetique> ::= variable_arithmetique | nombre | <addition> | <soustraction> | <multiplication> | <division> | "(" <expression_arithmetique> ")"
<:vspace>
<expression_booleenne> ::= variable_booleenne | "vrai" | "faux" | <et> | <ou> | <non> | "(" <expression_booleenne> ")"
<:vspace>
<addition> ::= <expression_arithmetique> "+" <expression_arithmetique>
<:vspace>
<soustraction> ::= <expression_arithmetique> "-" <expression_arithmetique>
<:vspace>
<multiplication> ::= <expression_arithmetique> "*" <expression_arithmetique>
<:vspace>
<division> ::= <expression_arithmetique> "/" <expression_arithmetique>
<:vspace>
<et> ::= <expression_booleenne> "et" <expression_booleenne> ;Ne pas confondre <et> qui est le non terminal lie a l'operation du ET logique et "et" qui est le terminal correspondant a l'operateur ET
<:vspace>
<ou> ::= <expression_booleenne> "ou" <expression_booleenne>
<:vspace>
<non> ::= "non" <expression_booleenne>
(:sourcend:)
On met à jour les codes respectifs de nos analyseurs lexical et syntaxique :
⚠ (:source lang=c header="lexique_simple.lex" linenum:)
%{
<:vspace>
#include "simple.h"
unsigned int lineno=1;
bool error_lexical=false;
<:vspace>
%}
<:vspace>
%option noyywrap
<:vspace>
nombre 0|[1-9][[:digit:]]*
variable_booleenne b(_|[[:alnum:]])*
variable_arithmetique e(_|[[:alnum:]])*
<:vspace>
%%
<:vspace>
{nombre} {
sscanf(yytext, "%ld", &yylval.nombre);
return TOK_NOMBRE;
}
<:vspace>
"afficher" {return TOK_AFFICHER;}
<:vspace>
"=" {return TOK_AFFECT;}
<:vspace>
"+" {return TOK_PLUS;}
<:vspace>
"-" {return TOK_MOINS;}
<:vspace>
"*" {return TOK_MUL;}
<:vspace>
"/" {return TOK_DIV;}
<:vspace>
"(" {return TOK_PARG;}
<:vspace>
")" {return TOK_PARD;}
<:vspace>
"et" {return TOK_ET;}
<:vspace>
"ou" {return TOK_OU;}
<:vspace>
"non" {return TOK_NON;}
<:vspace>
";" {return TOK_FINSTR;}
<:vspace>
"vrai" {return TOK_VRAI;}
<:vspace>
"faux" {return TOK_FAUX;}
<:vspace>
"\n" {lineno++;}
<:vspace>
{variable_booleenne} {
yylval.texte = yytext;
return TOK_VARB;
}
<:vspace>
<:vspace>
{variable_arithmetique} {
yylval.texte = yytext;
return TOK_VARE;
}
<:vspace>
" "|"\t" {}
<:vspace>
. {
fprintf(stderr,"\tERREUR : Lexeme inconnu a la ligne %d. Il s'agit de %s et comporte %d lettre(s)\n",lineno,yytext,yyleng);
error_lexical=true;
return yytext[0];
}
<:vspace>
%%
(:sourcend:)
⚠ (:source lang=c header="syntaxe_simple.y" linenum:)
%{
<:vspace>
#include "simple.h"
#include <string.h>
bool error_syntaxical=false;
extern unsigned int lineno;
extern bool error_lexical;
<:vspace>
%}
<:vspace>
/* L'union dans Bison est utilisee pour typer nos tokens ainsi que nos non terminaux. Ici nous avons declare une union avec deux types : nombre de type int et texte de type pointeur de char (char*) */
<:vspace>
%union {
long nombre;
char* texte;
}
<:vspace>
/* Nous avons ici les operateurs, ils sont definis par leur ordre de priorite. Si je definis par exemple la multiplication en premier et l'addition apres, le + l'emportera alors sur le * dans le langage. Les parenthese sont prioritaires avec %right */
<:vspace>
%left TOK_PLUS TOK_MOINS /* +- */
%left TOK_MUL TOK_DIV /* /* */
%left TOK_ET
%left TOK_OU TOK_NON /* et ou non */
%right TOK_PARG TOK_PARD /* () */
<:vspace>
/* Nous avons la liste de nos expressions (les non terminaux). Nous les typons tous en texte (pointeur vers une zone de char). */
<:vspace>
%type<texte> code
%type<texte> instruction
%type<texte> variable
%type<texte> variable_arithmetique
%type<texte> variable_booleenne
%type<texte> affectation
%type<texte> affichage
%type<texte> expression_arithmetique
%type<texte> expression_booleenne
%type<texte> addition
%type<texte> soustraction
%type<texte> multiplication
%type<texte> division
<:vspace>
/* Nous avons la liste de nos tokens (les terminaux de notre grammaire) */
<:vspace>
%token<texte> TOK_NOMBRE
%token TOK_VRAI /* true */
%token TOK_FAUX /* false */
%token TOK_AFFECT /* = */
%token TOK_FINSTR /* ; */
%token TOK_AFFICHER /* afficher */
%token TOK_SUPPR /* supprimer */
%token<texte> TOK_VARE /* variable arithmetique */
%token<texte> TOK_VARB /* variable booleenne */
<:vspace>
%%
<:vspace>
/* Nous definissons toutes les regles grammaticales de chaque non terminal de notre langage. Par defaut on commence a definir l'axiome, c'est a dire ici le non terminal code. Si nous le definissons pas en premier nous devons le specifier en option dans Bison avec %start */
<:vspace>
code: %empty{}
|
code instruction{
printf("Resultat : C'est une instruction valide !\n\n");
}
|
code error{
fprintf(stderr,"\tERREUR : Erreur de syntaxe a la ligne %d.\n",lineno);
error_syntaxical=true;
};
<:vspace>
instruction: affectation{
printf("\tInstruction type Affectation\n");
}
|
affichage{
printf("\tInstruction type Affichage\n");
}
|
suppression{
printf("\tInstruction type Suppression\n");
};
<:vspace>
variable_arithmetique: TOK_VARE{
printf("\t\t\tVariable %s\n",$1);
$$=strdup($1);
};
<:vspace>
variable_booleenne: TOK_VARB{
printf("\t\t\tVariable %s\n",$1);
$$=strdup($1);
};
<:vspace>
variable: variable_arithmetique{
$$=strdup($1);
}
|
variable_booleenne{
$$=strdup($1);
};
<:vspace>
affectation: variable_arithmetique TOK_AFFECT expression_arithmetique TOK_FINSTR{
/* $1 est la valeur du premier non terminal. Ici c'est la valeur du non terminal variable. $3 est la valeur du 2nd non terminal. */
printf("\t\tAffectation sur la variable %s\n",$1);
}
|
variable_booleenne TOK_AFFECT expression_booleenne TOK_FINSTR{
printf("\t\tAffectation sur la variable %s\n",$1);
};
<:vspace>
affichage: TOK_AFFICHER expression TOK_FINSTR{
printf("\t\tAffichage de la valeur de l'expression %s\n",$2);
};
<:vspace>
expression_arithmetique: TOK_NOMBRE{
printf("\t\t\tNombre : %ld\n",$1);
/* Comme le token TOK_NOMBRE est de type entier et que on a type expression_arithmetique comme du texte, il nous faut convertir la valeur en texte. */
int length=snprintf(NULL,0,"%ld",$1);
char* str=malloc(length+1);
snprintf(str,length+1,"%ld",$1);
$$=strdup(str);
free(str);
}
|
variable_arithmetique{
$$=strdup($1);
}
|
addition{
}
|
soustraction{
}
|
multiplication{
}
|
division{
}
|
TOK_PARG expression_arithmetique TOK_PARD{
printf("\t\t\tC'est une expression artihmetique entre parentheses\n");
$$=strcat(strcat(strdup("("),strdup($2)),strdup(")"));
};
<:vspace>
expression_booleenne: TOK_VRAI{
printf("\t\t\tBooleen Vrai\n");
$$=strdup("vrai");
}
|
TOK_FAUX{
printf("\t\t\tBooleen Faux\n");
$$=strdup("faux");
}
|
variable_booleenne{
$$=strdup($1);
}
|
TOK_NON expression_booleenne{
printf("\t\t\tOperation booleenne Non\n");
$$=strcat(strdup("non "), strndup($2,sizeof(char)*strlen($2)));
}
|
expression_booleenne TOK_ET expression_booleenne{
printf("\t\t\tOperation booleenne Et\n");
$$=strcat(strcat(strdup($1),strdup(" et ")),strdup($3));
}
|
expression_booleenne TOK_OU expression_booleenne{
printf("\t\t\tOperation booleenne Ou\n");
$$=strcat(strcat(strdup($1),strdup(" ou ")),strdup($3));
}
|
TOK_PARG expression_booleenne TOK_PARD{
printf("\t\t\tC'est une expression booleenne entre parentheses\n");
$$=strcat(strcat(strdup("("),strdup($2)),strdup(")"));
};
<:vspace>
addition: expression_arithmetique TOK_PLUS expression_arithmetique{printf("\t\t\tAddition\n");$$=strcat(strcat(strdup($1),strdup("+")),strdup($3));};
soustraction: expression_arithmetique TOK_MOINS expression_arithmetique{printf("\t\t\tSoustraction\n");$$=strcat(strcat(strdup($1),strdup("-")),strdup($3));};
multiplication: expression_arithmetique TOK_MUL expression_arithmetique{printf("\t\t\tMultiplication\n");$$=strcat(strcat(strdup($1),strdup("*")),strdup($3));};
division: expression_arithmetique TOK_DIV expression_arithmetique{printf("\t\t\tDivision\n");$$=strcat(strcat(strdup($1),strdup("/")),strdup($3));};
<:vspace>
%%
<:vspace>
/* Dans la fonction main on appelle bien la routine yyparse() qui sera genere par Bison. Cette routine appellera yylex() de notre analyseur lexical. */
<:vspace>
int main(void){
printf("Debut de l'analyse syntaxique :\n");
yyparse();
printf("Fin de l'analyse !\n");
printf("Resultat :\n");
if(error_lexical){
printf("\t-- Echec : Certains lexemes ne font pas partie du lexique du langage ! --\n");
printf("\t-- Echec a l'analyse lexicale --\n");
}
else{
printf("\t-- Succes a l'analyse lexicale ! --\n");
}
if(error_syntaxical){
printf("\t-- Echec : Certaines phrases sont syntaxiquement incorrectes ! --\n");
printf("\t-- Echec a l'analyse syntaxique --\n");
}
else{
printf("\t-- Succes a l'analyse syntaxique ! --\n");
}
return EXIT_SUCCESS;
}
void yyerror(char *s) {
fprintf(stderr, "Erreur de syntaxe a la ligne %d: %s\n", lineno, s);
}
(:sourcend:)
On recompile le compilateur :
⚠ (:source lang=bash:)
flex -o lexique_simple.c lexique_simple.lex
bison -d syntaxe_simple.y
gcc -o simple lexique_simple.c syntaxe_simple.tab.c
(:sourcend:)
Vous ne devez plus voir d'avertissements maintenant. Et on teste avec un nouveau programme.simple, ou les variables entières doivent commencer par un 'e' et booléennes par un 'b' afin de respecter la nouvelle syntaxe.
⚠ (:source lang=text header="programme.simple" linenum:)
booleen = vrai ou faux;
entier = 5;
afficher (booleen et vrai) ou booleen;
afficher (entier et vrai) ou entier;
afficher entier + 9;
afficher booleen + 9;
booleen = 87;
entier = faux;
(:sourcend:)
Résultat :
⚠ (:source lang=text:)
Debut de l'analyse syntaxique :
Variable booleen
Booleen Vrai
Booleen Faux
Operation booleenne Ou
Affectation sur la variable booleen
Instruction type Affectation
Resultat : C'est une instruction valide !
<:vspace>
Variable entier
Nombre : 5
Affectation sur la variable entier
Instruction type Affectation
Resultat : C'est une instruction valide !
<:vspace>
Variable booleen
Booleen Vrai
Operation booleenne Et
C'est une expression booleenne entre parentheses
Variable booleen
Operation booleenne Ou
Affichage de la valeur de l'expression (booleen et vrai) ou booleen
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Variable entier
Erreur de syntaxe a la ligne 4: syntax error
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
Variable entier
ERREUR : Erreur de syntaxe a la ligne 4.
ERREUR : Erreur de syntaxe a la ligne 4.
Variable entier
Nombre : 9
Addition
Affichage de la valeur de l'expression entier+9
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Variable booleen
Erreur de syntaxe a la ligne 6: syntax error
ERREUR : Erreur de syntaxe a la ligne 6.
ERREUR : Erreur de syntaxe a la ligne 6.
ERREUR : Erreur de syntaxe a la ligne 6.
ERREUR : Erreur de syntaxe a la ligne 6.
Variable booleen
ERREUR : Erreur de syntaxe a la ligne 7.
ERREUR : Erreur de syntaxe a la ligne 7.
ERREUR : Erreur de syntaxe a la ligne 7.
Variable entier
ERREUR : Erreur de syntaxe a la ligne 8.
ERREUR : Erreur de syntaxe a la ligne 8.
ERREUR : Erreur de syntaxe a la ligne 8.
Fin de l'analyse !
Resultat :
-- Succes a l'analyse lexicale ! --
-- Echec : Certaines phrases sont syntaxiquement incorrectes ! --
-- Echec a l'analyse syntaxique --
(:sourcend:)
On voit que le résultat de l'analyse syntaxique est mis en échec si on a le malheur de mal utiliser les variables. On les a en quelque sorte typées (par l'analyse syntaxique) et on ne peut plus affecter de valeur numérique à un type booléen et de valeur booléenne à un type entier.
Je suis un poil curieux de connaître le résultat d'analyse de cette simple ligne de code :
⚠ (:source lang=text header="programme.simple" linenum:)
afficher (3 * entier)+4;
(:sourcend:)
⚠ (:source lang=text:)
Debut de l'analyse syntaxique :
Nombre : 3
Variable entier
Multiplication
C'est une expression artihmetique entre parentheses
Nombre : 4
Addition
Affichage de la valeur de l'expression (3*entier)+4
Instruction type Affichage
Resultat : C'est une instruction valide !
<:vspace>
Fin de l'analyse !
Resultat :
-- Succes a l'analyse lexicale ! --
-- Succes a l'analyse syntaxique ! --
(:sourcend:)
Malgré le succès de ces analyses, on voit encore un problème : on peut utiliser des variables qui n'ont pas été affectées dans les expressions. Si une variable ne contient aucune valeur, il est alors impossible de l'évaluer dans une expression et donc d'évaluer l'expression tout court. Encore une fois on peut passer dessus, et laisser le compilateur C faire cette analyse pour nous. Seulement, à quoi servirait de développer un compilateur si c'est pour générer du faux code ? Nous allons donc tout de même faire une petite analyse sémantique dans le chapitre suivant, histoire de vérifier si les variables ont bien été affectées avant de les utiliser. L'analyse sémantique est la troisième et dernière analyse du processus de compilation ! Courage !
<< Analyseur lexical | Analyseur syntaxique | Analyse sémantique >>
Thomas - (CC BY-NC-SA 3.0 FR)
