Recent Changes - Search:

My Projects

Courses

Writings

Source Code

Social Networks

Live Traffic !

Compilation /

Analyseur syntaxique Bison

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 :

simple.h
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <stdbool.h>
  4. #include "syntaxe_simple.tab.h"
  5. int yylex(void);
  6. void yyerror(char*);
[$[Get Code]]

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é :

syntaxe_simple.y
  1. %{
  2.  
  3. #include "simple.h"
  4. #include <string.h>
  5. bool error_syntaxical=false;
  6. extern unsigned int lineno;
  7. extern bool error_lexical;
  8.  
  9. %}
  10.  
  11. /* 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*) */
  12.  
  13. %union {
  14.         long nombre;
  15.         char* texte;
  16. }
  17.  
  18. /* 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 */
  19.  
  20. %left                   TOK_PLUS        TOK_MOINS       /* +- */
  21. %left                   TOK_MUL         TOK_DIV         /* /* */
  22. %left                   TOK_ET         
  23. %left                   TOK_OU          TOK_NON         /* et ou non */
  24. %right                  TOK_PARG        TOK_PARD        /* () */
  25.  
  26. /* 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 */
  27.  
  28. %type<texte>            code
  29. %type<texte>            instruction
  30. %type<texte>            variable
  31. %type<texte>            affectation
  32. %type<texte>            affichage
  33. %type<texte>            expression_arithmetique
  34. %type<texte>            expression_booleenne
  35. %type<texte>            addition
  36. %type<texte>            soustraction
  37. %type<texte>            multiplication
  38. %type<texte>            division
  39.  
  40. /* Nous avons la liste de nos tokens (les terminaux de notre grammaire) */
  41.  
  42. %token<texte>           TOK_NOMBRE
  43. %token                  TOK_VRAI        /* true */
  44. %token                  TOK_FAUX        /* false */
  45. %token                  TOK_AFFECT      /* = */
  46. %token                  TOK_FINSTR      /* ; */
  47. %token                  TOK_AFFICHER    /* afficher */
  48. %token<texte>           TOK_VAR         /* variable */
  49.  
  50. %%
  51.  
  52. /* 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 */
  53.  
  54. code:           %empty{}
  55.                 |
  56.                 code instruction{
  57.                         printf("Resultat : C'est une instruction valide !\n\n");
  58.                 }
  59.                 |
  60.                 code error{
  61.                         fprintf(stderr,"\tERREUR : Erreur de syntaxe a la ligne %d.\n",lineno);
  62.                         error_syntaxical=true;
  63.                 };
  64.  
  65. instruction:    affectation{
  66.                         printf("\tInstruction type Affectation\n");
  67.                 }
  68.                 |
  69.                 affichage{
  70.                          printf("\tInstruction type Affichage\n");
  71.                 };
  72.  
  73. /* L'expression variable contient uniquement le nom de la variable */
  74. variable:       TOK_VAR{
  75.                         /* $1 est la chaine de texte de l'expression retournee par l'analyseur lexical Flex. */
  76.                         printf("\t\t\tVariable %s\n",$1);
  77.                         /* 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. */
  78.                         $$=strdup($1);
  79.                 };
  80.  
  81. affectation:    variable TOK_AFFECT expression TOK_FINSTR{
  82.                         /* $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. */
  83.                         printf("\t\tAffectation sur la variable %s\n",$1);
  84.                 };
  85.  
  86. affichage:      TOK_AFFICHER expression TOK_FINSTR{
  87.                         printf("\t\tAffichage de la valeur de l'expression %s\n",$2);
  88.                 };
  89.  
  90. expression_arithmetique:        TOK_NOMBRE{
  91.                                         printf("\t\t\tNombre : %ld\n",$1);
  92.                                         /* 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. */
  93.                                         int length=snprintf(NULL,0,"%ld",$1);
  94.                                         char* str=malloc(length+1);
  95.                                         snprintf(str,length+1,"%ld",$1);
  96.                                         $$=strdup(str);
  97.                                         free(str);
  98.                                 }
  99.                                 |
  100.                                 variable{
  101.                                 }
  102.                                 |
  103.                                 addition{
  104.                                 }
  105.                                 |
  106.                                 soustraction{
  107.                                 }
  108.                                 |
  109.                                 multiplication{
  110.                                 }
  111.                                 |
  112.                                 division{
  113.                                 }
  114.                                 |
  115.                                 TOK_PARG expression_arithmetique TOK_PARD{
  116.                                         printf("\t\t\tC'est une expression artihmetique entre parentheses\n");
  117.                                         $$=strcat(strcat(strdup("("),strdup($2)),strdup(")"));
  118.                                 };
  119.  
  120. expression_booleenne:           TOK_VRAI{
  121.                                         printf("\t\t\tBooleen Vrai\n");
  122.                                         $$=strdup("vrai");
  123.                                 }
  124.                                 |
  125.                                 TOK_FAUX{
  126.                                         printf("\t\t\tBooleen Faux\n");
  127.                                         $$=strdup("faux");
  128.                                 }
  129.                                 |
  130.                                 variable{
  131.                                         $$=strdup($1);
  132.                                 }
  133.                                 |
  134.                                 TOK_NON expression_booleenne{
  135.                                         printf("\t\t\tOperation booleenne Non\n");
  136.                                         $$=strcat(strdup("non "), strndup($2,sizeof(char)*strlen($2)));
  137.                                 }
  138.                                 |
  139.                                 expression_booleenne TOK_ET expression_booleenne{
  140.                                         printf("\t\t\tOperation booleenne Et\n");
  141.                                         $$=strcat(strcat(strdup($1),strdup(" et ")),strdup($3));
  142.                                 }
  143.                                 |
  144.                                 expression_booleenne TOK_OU expression_booleenne{
  145.                                         printf("\t\t\tOperation booleenne Ou\n");
  146.                                         $$=strcat(strcat(strdup($1),strdup(" ou ")),strdup($3));
  147.                                 }
  148.                                 |
  149.                                 TOK_PARG expression_booleenne TOK_PARD{
  150.                                         printf("\t\t\tC'est une expression booleenne entre parentheses\n");
  151.                                         $$=strcat(strcat(strdup("("),strdup($2)),strdup(")"));
  152.                                 };
  153.  
  154. addition:       expression_arithmetique TOK_PLUS expression_arithmetique{printf("\t\t\tAddition\n");$$=strcat(strcat(strdup($1),strdup("+")),strdup($3));};
  155. soustraction:   expression_arithmetique TOK_MOINS expression_arithmetique{printf("\t\t\tSoustraction\n");$$=strcat(strcat(strdup($1),strdup("-")),strdup($3));};
  156. multiplication: expression_arithmetique TOK_MUL expression_arithmetique{printf("\t\t\tMultiplication\n");$$=strcat(strcat(strdup($1),strdup("*")),strdup($3));};
  157. division:       expression_arithmetique TOK_DIV expression_arithmetique{printf("\t\t\tDivision\n");$$=strcat(strcat(strdup($1),strdup("/")),strdup($3));};
  158.  
  159. %%
  160.  
  161. /* Dans la fonction main on appelle bien la routine yyparse() qui sera genere par Bison. Cette routine appellera yylex() de notre analyseur lexical. */
  162.  
  163. int main(void){
  164.         printf("Debut de l'analyse syntaxique :\n");
  165.         yyparse();
  166.         printf("Fin de l'analyse !\n");
  167.         printf("Resultat :\n");
  168.         if(error_lexical){
  169.                 printf("\t-- Echec : Certains lexemes ne font pas partie du lexique du langage ! --\n");
  170.                 printf("\t-- Echec a l'analyse lexicale --\n");
  171.         }
  172.         else{
  173.                 printf("\t-- Succes a l'analyse lexicale ! --\n");
  174.         }
  175.         if(error_syntaxical){
  176.                 printf("\t-- Echec : Certaines phrases sont syntaxiquement incorrectes ! --\n");
  177.                 printf("\t-- Echec a l'analyse syntaxique --\n");
  178.         }
  179.         else{
  180.                 printf("\t-- Succes a l'analyse syntaxique ! --\n");
  181.         }
  182.         return EXIT_SUCCESS;
  183. }
  184. void yyerror(char *s) {
  185.         fprintf(stderr, "Erreur de syntaxe a la ligne %d: %s\n", lineno, s);
  186. }
[$[Get Code]]

Nous allons légèrement modifié notre analyseur lexical afin qu'il retourne des tokens à Bison :

lexique_simple.lex
  1. %{
  2.  
  3. #include "simple.h"
  4. unsigned int lineno=1;
  5. bool error_lexical=false;
  6.  
  7. %}
  8.  
  9. %option noyywrap
  10.  
  11. nombre 0|[1-9][[:digit:]]*
  12. variable [[:alpha:]][[:alnum:]]*
  13.  
  14. %%
  15.  
  16. {nombre} {
  17.         sscanf(yytext, "%ld", &yylval.nombre);
  18.         return TOK_NOMBRE;
  19. }
  20.  
  21. "afficher"      {return TOK_AFFICHER;}
  22.  
  23. "="             {return TOK_AFFECT;}
  24.  
  25. "+"             {return TOK_PLUS;}
  26.  
  27. "-"             {return TOK_MOINS;}
  28.  
  29. "*"             {return TOK_MUL;}
  30.  
  31. "/"             {return TOK_DIV;}
  32.  
  33. "("             {return TOK_PARG;}
  34.  
  35. ")"             {return TOK_PARD;}
  36.  
  37. "et"            {return TOK_ET;}
  38.  
  39. "ou"            {return TOK_OU;}
  40.  
  41. "non"           {return TOK_NON;}
  42.  
  43. ";"             {return TOK_FINSTR;}
  44.  
  45. "vrai"          {return TOK_VRAI;}
  46.  
  47. "faux"          {return TOK_FAUX;}
  48.  
  49. "\n"            {lineno++;}
  50.  
  51. {variable} {
  52.         yylval.texte = yytext;
  53.         return TOK_VAR;
  54. }
  55.  
  56. " "|"\t" {}
  57.  
  58. . {
  59.         fprintf(stderr,"\tERREUR : Lexeme inconnu a la ligne %d. Il s'agit de %s et comporte %d lettre(s)\n",lineno,yytext,yyleng);
  60.         error_lexical=true;
  61.         return yytext[0];
  62. }
  63.  
  64. %%
[$[Get Code]]

On compile tout ça :

flex -o lexique_simple.c lexique_simple.lex
bison -d syntaxe_simple.y
gcc -o simple lexique_simple.c syntaxe_simple.tab.c
[$[Get Code]]

On teste notre analyseur syntaxique sur un fichier .simple :

programme.simple
  1. monEntier = 6 ; monBooleen = faux ;
  2.  
  3. afficher monEntier ;
  4. afficher monBooleen ;
  5. afficher 4 ;
  6. afficher non ( ( vrai et faux ) ou vrai ) ;
  7. afficher 6/3 ;
[$[Get Code]]

On passe le fichier à l'analyseur :

./simple < programme.simple
[$[Get Code]]

Le résultat est le suivant :

Debut de l'analyse syntaxique :
                        Variable monEntier
                        Nombre : 6
                Affectation sur la variable monEntier
        Instruction type Affectation
Resultat : C'est une instruction valide !

                        Variable monBooleen
                        Booleen Faux
                Affectation sur la variable monBooleen
        Instruction type Affectation
Resultat : C'est une instruction valide !

                        Variable monEntier
                Affichage de la valeur de l'expression monEntier
        Instruction type Affichage
Resultat : C'est une instruction valide !

                        Variable monBooleen
                Affichage de la valeur de l'expression monBooleen
        Instruction type Affichage
Resultat : C'est une instruction valide !

                        Nombre : 4
                Affichage de la valeur de l'expression 4
        Instruction type Affichage
Resultat : C'est une instruction valide !

                        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 !

                        Nombre : 6
                        Nombre : 3
                        Division
                Affichage de la valeur de l'expression 6/3
        Instruction type Affichage
Resultat : C'est une instruction valide !

Fin de l'analyse !
Resultat :
        -- Succes a l'analyse lexicale ! --
        -- Succes a l'analyse syntaxique ! --
[$[Get Code]]

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 :

Debut de l'analyse syntaxique :
                        Variable monEntier
                        Nombre : 6
                Affectation sur la variable monEntier
        Instruction type Affectation
Resultat : C'est une instruction valide !

                        Variable monBooleen
                        Booleen Faux
                Affectation sur la variable monBooleen
        Instruction type Affectation
Resultat : C'est une instruction valide !

                        Variable monEntier
                Affichage de la valeur de l'expression monEntier
        Instruction type Affichage
Resultat : C'est une instruction valide !

                        Variable monBooleen
                Affichage de la valeur de l'expression monBooleen
        Instruction type Affichage
Resultat : C'est une instruction valide !

                        Nombre : 4
                Affichage de la valeur de l'expression 4
        Instruction type Affichage
Resultat : C'est une instruction valide !

                        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 !

                        Nombre : 6
                        Nombre : 3
                        Division
                Affichage de la valeur de l'expression 6/3
        Instruction type Affichage
Resultat : C'est une instruction valide !

        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 --
[$[Get Code]]

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 :

programme_faux.simple
  1. 68 afficher;
  2. france japon usa = 85;
  3. japon = 118 et afficher japon;
  4. vrai+faux=19;
[$[Get Code]]

Le résultat est le suivant :

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 !

                        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 !

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 --
[$[Get Code]]

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 :

syntaxe_simple.y: avertissement: 2 conflits par réduction/réduction [-Wconflicts-rr]
[$[Get Code]]

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 :

<expression_arithmetique> ::= variable | nombre | <addition> | <soustraction> | <multiplication> | <division> | "(" <expression_arithmetique> ")"
<expression_booleenne> ::= variable | vrai | faux | <et> | <ou> | <non> | "(" <expression_booleenne> ")"
[$[Get Code]]

Pour mieux comprendre, regardons les résultats des analyses pour un autre programme :

programme.simple
  1. monEntier = 5;
  2. afficher (monEntier et vrai) ou monEntier;
[$[Get Code]]

Ce qui donne :

Debut de l'analyse syntaxique :
                        Variable monEntier
                        Nombre : 5
                Affectation sur la variable monEntier
        Instruction type Affectation
Resultat : C'est une instruction valide !

                        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 !

Fin de l'analyse !
Resultat :
        -- Succes a l'analyse lexicale ! --
        -- Succes a l'analyse syntaxique ! --
[$[Get Code]]

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 :

  1. @@ ::= <instruction> @@ | <none>
  2.  
  3. <instruction> ::= <affectation> | <affichage>
  4.  
  5. <expression> ::= <expression_booleenne> | <expression_arithmetique>
  6.  
  7. <variable> ::= variable_booleenne | variable_arithmetique
  8.  
  9. <affectation> ::= ( variable_arithmetique "=" <expression_arithmetique> | variable_booleenne "=" <expression_booleenne> ) ";"
  10.  
  11. <affichage> ::= "afficher" <expression> ";"
  12.  
  13. <expression_arithmetique> ::= variable_arithmetique | nombre | <addition> | <soustraction> | <multiplication> | <division> | "(" <expression_arithmetique> ")"
  14.  
  15. <expression_booleenne> ::= variable_booleenne | "vrai" | "faux" | <et> | <ou> | <non> | "(" <expression_booleenne> ")"
  16.  
  17. <addition> ::= <expression_arithmetique> "+" <expression_arithmetique>
  18.  
  19. <soustraction> ::= <expression_arithmetique> "-" <expression_arithmetique>
  20.  
  21. <multiplication> ::= <expression_arithmetique> "*" <expression_arithmetique>
  22.  
  23. <division> ::= <expression_arithmetique> "/" <expression_arithmetique>
  24.  
  25. <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
  26.  
  27. <ou> ::= <expression_booleenne> "ou" <expression_booleenne>
  28.  
  29. <non> ::= "non" <expression_booleenne>
[$[Get Code]]

On met à jour les codes respectifs de nos analyseurs lexical et syntaxique :

lexique_simple.lex
  1. %{
  2.  
  3. #include "simple.h"
  4. unsigned int lineno=1;
  5. bool error_lexical=false;
  6.  
  7. %}
  8.  
  9. %option noyywrap
  10.  
  11. nombre 0|[1-9][[:digit:]]*
  12. variable_booleenne b(_|[[:alnum:]])*
  13. variable_arithmetique e(_|[[:alnum:]])*
  14.  
  15. %%
  16.  
  17. {nombre} {
  18.         sscanf(yytext, "%ld", &yylval.nombre);
  19.         return TOK_NOMBRE;
  20. }
  21.  
  22. "afficher"      {return TOK_AFFICHER;}
  23.  
  24. "="             {return TOK_AFFECT;}
  25.  
  26. "+"             {return TOK_PLUS;}
  27.  
  28. "-"             {return TOK_MOINS;}
  29.  
  30. "*"             {return TOK_MUL;}
  31.  
  32. "/"             {return TOK_DIV;}
  33.  
  34. "("             {return TOK_PARG;}
  35.  
  36. ")"             {return TOK_PARD;}
  37.  
  38. "et"            {return TOK_ET;}
  39.  
  40. "ou"            {return TOK_OU;}
  41.  
  42. "non"           {return TOK_NON;}
  43.  
  44. ";"             {return TOK_FINSTR;}
  45.  
  46. "vrai"          {return TOK_VRAI;}
  47.  
  48. "faux"          {return TOK_FAUX;}
  49.  
  50. "\n"            {lineno++;}
  51.  
  52. {variable_booleenne} {
  53.         yylval.texte = yytext;
  54.         return TOK_VARB;
  55. }
  56.  
  57.  
  58. {variable_arithmetique} {
  59.         yylval.texte = yytext;
  60.         return TOK_VARE;
  61. }
  62.  
  63. " "|"\t" {}
  64.  
  65. . {
  66.         fprintf(stderr,"\tERREUR : Lexeme inconnu a la ligne %d. Il s'agit de %s et comporte %d lettre(s)\n",lineno,yytext,yyleng);
  67.         error_lexical=true;
  68.         return yytext[0];
  69. }
  70.  
  71. %%
[$[Get Code]]
syntaxe_simple.y
  1. %{
  2.  
  3. #include "simple.h"
  4. #include <string.h>
  5. bool error_syntaxical=false;
  6. extern unsigned int lineno;
  7. extern bool error_lexical;
  8.  
  9. %}
  10.  
  11. /* 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*) */
  12.  
  13. %union {
  14.         long nombre;
  15.         char* texte;
  16. }
  17.  
  18. /* 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 */
  19.  
  20. %left                   TOK_PLUS        TOK_MOINS       /* +- */
  21. %left                   TOK_MUL         TOK_DIV         /* /* */
  22. %left                   TOK_ET         
  23. %left                   TOK_OU          TOK_NON         /* et ou non */
  24. %right                  TOK_PARG        TOK_PARD        /* () */
  25.  
  26. /* Nous avons la liste de nos expressions (les non terminaux). Nous les typons tous en texte (pointeur vers une zone de char). */
  27.  
  28. %type<texte>            code
  29. %type<texte>            instruction
  30. %type<texte>            variable
  31. %type<texte>            variable_arithmetique
  32. %type<texte>            variable_booleenne
  33. %type<texte>            affectation
  34. %type<texte>            affichage
  35. %type<texte>            expression_arithmetique
  36. %type<texte>            expression_booleenne
  37. %type<texte>            addition
  38. %type<texte>            soustraction
  39. %type<texte>            multiplication
  40. %type<texte>            division
  41.  
  42. /* Nous avons la liste de nos tokens (les terminaux de notre grammaire) */
  43.  
  44. %token<texte>           TOK_NOMBRE
  45. %token                  TOK_VRAI        /* true */
  46. %token                  TOK_FAUX        /* false */
  47. %token                  TOK_AFFECT      /* = */
  48. %token                  TOK_FINSTR      /* ; */
  49. %token                  TOK_AFFICHER    /* afficher */
  50. %token                  TOK_SUPPR       /* supprimer */
  51. %token<texte>           TOK_VARE        /* variable arithmetique */
  52. %token<texte>           TOK_VARB        /* variable booleenne */
  53.  
  54. %%
  55.  
  56. /* 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 */
  57.  
  58. code:           %empty{}
  59.                 |
  60.                 code instruction{
  61.                         printf("Resultat : C'est une instruction valide !\n\n");
  62.                 }
  63.                 |
  64.                 code error{
  65.                         fprintf(stderr,"\tERREUR : Erreur de syntaxe a la ligne %d.\n",lineno);
  66.                         error_syntaxical=true;
  67.                 };
  68.  
  69. instruction:    affectation{
  70.                         printf("\tInstruction type Affectation\n");
  71.                 }
  72.                 |
  73.                 affichage{
  74.                          printf("\tInstruction type Affichage\n");
  75.                 }
  76.                 |
  77.                 suppression{
  78.                         printf("\tInstruction type Suppression\n");
  79.                 };
  80.  
  81. variable_arithmetique:  TOK_VARE{
  82.                                 printf("\t\t\tVariable %s\n",$1);
  83.                                 $$=strdup($1);
  84.                         };
  85.  
  86. variable_booleenne:     TOK_VARB{
  87.                                 printf("\t\t\tVariable %s\n",$1);
  88.                                 $$=strdup($1);
  89.                         };
  90.  
  91. variable:       variable_arithmetique{
  92.                         $$=strdup($1);
  93.                 }
  94.                 |
  95.                 variable_booleenne{
  96.                         $$=strdup($1);
  97.                 };
  98.  
  99. affectation:    variable_arithmetique TOK_AFFECT expression_arithmetique TOK_FINSTR{
  100.                         /* $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. */
  101.                         printf("\t\tAffectation sur la variable %s\n",$1);
  102.                 }
  103.                 |
  104.                 variable_booleenne TOK_AFFECT expression_booleenne TOK_FINSTR{
  105.                         printf("\t\tAffectation sur la variable %s\n",$1);
  106.                 };
  107.  
  108. affichage:      TOK_AFFICHER expression TOK_FINSTR{
  109.                         printf("\t\tAffichage de la valeur de l'expression %s\n",$2);
  110.                 };
  111.  
  112. expression_arithmetique:        TOK_NOMBRE{
  113.                                         printf("\t\t\tNombre : %ld\n",$1);
  114.                                         /* 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. */
  115.                                         int length=snprintf(NULL,0,"%ld",$1);
  116.                                         char* str=malloc(length+1);
  117.                                         snprintf(str,length+1,"%ld",$1);
  118.                                         $$=strdup(str);
  119.                                         free(str);
  120.                                 }
  121.                                 |
  122.                                 variable_arithmetique{
  123.                                         $$=strdup($1);
  124.                                 }
  125.                                 |
  126.                                 addition{
  127.                                 }
  128.                                 |
  129.                                 soustraction{
  130.                                 }
  131.                                 |
  132.                                 multiplication{
  133.                                 }
  134.                                 |
  135.                                 division{
  136.                                 }
  137.                                 |
  138.                                 TOK_PARG expression_arithmetique TOK_PARD{
  139.                                         printf("\t\t\tC'est une expression artihmetique entre parentheses\n");
  140.                                         $$=strcat(strcat(strdup("("),strdup($2)),strdup(")"));
  141.                                 };
  142.  
  143. expression_booleenne:           TOK_VRAI{
  144.                                         printf("\t\t\tBooleen Vrai\n");
  145.                                         $$=strdup("vrai");
  146.                                 }
  147.                                 |
  148.                                 TOK_FAUX{
  149.                                         printf("\t\t\tBooleen Faux\n");
  150.                                         $$=strdup("faux");
  151.                                 }
  152.                                 |
  153.                                 variable_booleenne{
  154.                                         $$=strdup($1);
  155.                                 }
  156.                                 |
  157.                                 TOK_NON expression_booleenne{
  158.                                         printf("\t\t\tOperation booleenne Non\n");
  159.                                         $$=strcat(strdup("non "), strndup($2,sizeof(char)*strlen($2)));
  160.                                 }
  161.                                 |
  162.                                 expression_booleenne TOK_ET expression_booleenne{
  163.                                         printf("\t\t\tOperation booleenne Et\n");
  164.                                         $$=strcat(strcat(strdup($1),strdup(" et ")),strdup($3));
  165.                                 }
  166.                                 |
  167.                                 expression_booleenne TOK_OU expression_booleenne{
  168.                                         printf("\t\t\tOperation booleenne Ou\n");
  169.                                         $$=strcat(strcat(strdup($1),strdup(" ou ")),strdup($3));
  170.                                 }
  171.                                 |
  172.                                 TOK_PARG expression_booleenne TOK_PARD{
  173.                                         printf("\t\t\tC'est une expression booleenne entre parentheses\n");
  174.                                         $$=strcat(strcat(strdup("("),strdup($2)),strdup(")"));
  175.                                 };
  176.  
  177. addition:       expression_arithmetique TOK_PLUS expression_arithmetique{printf("\t\t\tAddition\n");$$=strcat(strcat(strdup($1),strdup("+")),strdup($3));};
  178. soustraction:   expression_arithmetique TOK_MOINS expression_arithmetique{printf("\t\t\tSoustraction\n");$$=strcat(strcat(strdup($1),strdup("-")),strdup($3));};
  179. multiplication: expression_arithmetique TOK_MUL expression_arithmetique{printf("\t\t\tMultiplication\n");$$=strcat(strcat(strdup($1),strdup("*")),strdup($3));};
  180. division:       expression_arithmetique TOK_DIV expression_arithmetique{printf("\t\t\tDivision\n");$$=strcat(strcat(strdup($1),strdup("/")),strdup($3));};
  181.  
  182. %%
  183.  
  184. /* Dans la fonction main on appelle bien la routine yyparse() qui sera genere par Bison. Cette routine appellera yylex() de notre analyseur lexical. */
  185.  
  186. int main(void){
  187.         printf("Debut de l'analyse syntaxique :\n");
  188.         yyparse();
  189.         printf("Fin de l'analyse !\n");
  190.         printf("Resultat :\n");
  191.         if(error_lexical){
  192.                 printf("\t-- Echec : Certains lexemes ne font pas partie du lexique du langage ! --\n");
  193.                 printf("\t-- Echec a l'analyse lexicale --\n");
  194.         }
  195.         else{
  196.                 printf("\t-- Succes a l'analyse lexicale ! --\n");
  197.         }
  198.         if(error_syntaxical){
  199.                 printf("\t-- Echec : Certaines phrases sont syntaxiquement incorrectes ! --\n");
  200.                 printf("\t-- Echec a l'analyse syntaxique --\n");
  201.         }
  202.         else{
  203.                 printf("\t-- Succes a l'analyse syntaxique ! --\n");
  204.         }
  205.         return EXIT_SUCCESS;
  206. }
  207. void yyerror(char *s) {
  208.         fprintf(stderr, "Erreur de syntaxe a la ligne %d: %s\n", lineno, s);
  209. }
[$[Get Code]]

On recompile le compilateur :

flex -o lexique_simple.c lexique_simple.lex
bison -d syntaxe_simple.y
gcc -o simple lexique_simple.c syntaxe_simple.tab.c
[$[Get Code]]

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.

programme.simple
  1. booleen = vrai ou faux;
  2. entier = 5;
  3. afficher (booleen et vrai) ou booleen;
  4. afficher (entier et vrai) ou entier;
  5. afficher entier + 9;
  6. afficher booleen + 9;
  7. booleen = 87;
  8. entier = faux;
[$[Get Code]]

Résultat :

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 !

                        Variable entier
                        Nombre : 5
                Affectation sur la variable entier
        Instruction type Affectation
Resultat : C'est une instruction valide !

                        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 !

                        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 !

                        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 --
[$[Get Code]]

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 :

programme.simple
  1. afficher (3 * entier)+4;
[$[Get Code]]
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 !

Fin de l'analyse !
Resultat :
        -- Succes a l'analyse lexicale ! --
        -- Succes a l'analyse syntaxique ! --
[$[Get Code]]

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)

Page last modified on July 09, 2017, at 07:35 PM EST

This page has been requested 7661 times (Today : 3) - Total number of requests : 192632

Edit - History - Statistics - Print - Recent Changes - Search

Clin d'oeil aux victimes des attentats survenus dans la soirée du 13 novembre 2015. La nouvelle version du site a été installée quelques heures avant.