- monEntier = 6 ; monBooleen = faux ;
- afficher monEntier ;
- afficher monBooleen ;
- afficher 4 ;
- afficher non ( ( vrai et faux ) ou vrai ) ;
- afficher 6/3 ;
My Projects Courses Writings
Source Code Social Networks |
Analyseur syntaxique BisonCré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
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
Nous allons légèrement modifié notre analyseur lexical afin qu'il retourne des tokens à Bison : lexique_simple.lex
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 On teste notre analyseur syntaxique sur un fichier .simple : programme.simple
On passe le fichier à l'analyseur : ./simple < programme.simple 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 ! -- 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 -- 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
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 -- 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] 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> ")" Pour mieux comprendre, regardons les résultats des analyses pour un autre programme : programme.simple
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 ! -- 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 :
On met à jour les codes respectifs de nos analyseurs lexical et syntaxique : lexique_simple.lex
syntaxe_simple.y
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 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
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 -- 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
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 ! -- 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 >> |
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.