Maîtriser l'écriture d'une grammaire pour une liste, récursivité droite et gauche, grammaire ambiguë.
Vérifier la maîtrise des grammaires de listes, exemple important en théorie des langages.
Exemple complet d'analyse syntaxique, couplage Flex/Bison avec passage de valeur, utilisation de priorités, table de symboles
Construction explicite des Arbres de Syntaxe Abstraite (AST)
Des variations de "Calculatrice Arithmétique"
Passage de valeur "char *" : yytext vs strdup
Grammaire pour langage naturel, continuation exemple du cours
Grammaire pour langage naturel, passage de valeur "char *", gestion de structures à base de "char *".
On se donne un analyseur lexical simple list.flex qui lit des entiers (Token TOK), ignore les blancs, et remonte les autres
caractères (y compris '\n').
Cette analyseur passe aussi dans la variable int yylval, la valeur associées aux tokens entier TOK. Il n'y a pas besoin de déclaration %union dans Bison pour accéder à cette valeur avec un $i dans les actions Bison.
On désire tester différentes grammaires de listes.
Vérifier le bon fonctionnement de la gestion d'erreur et en particulier que l'analyseur sait analyser une ligne correcte après avoir traité une ligne erronée
Corrigé :
token TOK '\n'
%%
Line : /*vide*/
| Line list '\n' {printf("Ligne OK\n");}
| Line error '\n' {yyerrok; printf("Ligne Fausse\n");}
;
list : TOK
%%
Écrire par exemple, l'analyseur qui lit des lignes 'a' contenant 1 entier et des lignes b contenant 2 entiers.
a 11 =OK
b 11 12 =OK
a 11 12 =FAUX
a 1 =OK
=FAUX
Corrigé :
token TOK '\n'
%%
Line : /* vide */
| Line list '\n' {printf("Ligne OK\n");}
| Line 'a' lista '\n' {printf("lista OK\n");}
| Line 'b' listb '\n' {printf("listb OK\n");}
| Line error '\n' {yyerrok; printf("Ligne Fausse\n");}
;
list : TOK
lista : TOK
listb : TOK TOK
%%
On désire reconnaître une liste d'entier. Tester et comparer les différentes grammaires :
%%
lista : TOK
| lista TOK
;
Listb : TOK
| TOK Listb
;
Listc : TOK
| Listc Listc
;
Listd :
| Listd TOK
;
%%
lista, listb et listd qui prouve que le langage correspondant
est régulier ?
listc est ambiguë et génère un conflit dans Bison ? Quel est le type de conflit ? Comment Bison résout se conflit ?
NOTA BENE :
lista est appelée "Récursive Gauche", la définition pour listb est appelée "Récursive Droite".
Corrigé
%% /* tracer ordre d'analyse des tokens */
...
lista : TOK {printf(" =%d "),$1);}
| lista TOK {printf(" %d ",$2);}
;
...
%%
lista, "Récursif gauche", les entiers sont analysés de gauche à droite,
listb, "Récursif droite", les entiers sont analysés de droite à gauche,
listd autorise la liste vide contrairement aux autres listes.
lista, listb et listd sont des grammaires linéaires droites ou gauches. Les langages sont donc
réguliers (avec pour regexp. TOK+ et TOK*)
listc est ambiguë par exemple pour analyser "TOK TOK TOK" (entrez lol!). Chaque TOK se réduit directement en un listc, par contre
une fois que l'on a réduit les 2 premiers listc issu des 2 premiers TOK se pose la question de le réduire tout de suite ou de décaler le TOK suivant. En d'autre terme, doit-on analyser (TOK TOK) TOK ou TOK (TOK TOK) ? On a un conflit "shift/reduce" que Bison traite
avec une priorité sur le "shift". Pour tracer ce fonctionnement, on peut par exemple compter la taille des listes comme suit:
listc : TOK {$$=1}
listc listc {$$=$1+$2; printf( "Tailles L1=%d + L2=%d ", $1,$2);
Écrire et Tester des grammaires pour une liste d'entiers séparés par des virgules. Cela peut par exemple servir pour l'analyse des arguments d'une fonction, ou aussi pour l'analyse d'une constante de type ensemble ({}, {2,5,6} ...)... On envisagera les cas de listes non-vides ou de listes éventuellement vides, On pourra aussi décliner l'écriture de la grammaire sous les formes récursives gauches ou droites.
Pourquoi la grammaire suivante est incorrecte (par rapport à l'usage courant) ? Écrire et tester une version correcte.
%%
listg : /* Vide */
| listg ',' TOK
;
%%
Corrigé :
%%
liste : TOK /* liste non vide RecGauche */
| liste ',' TOK
listf : TOK /* liste non vide RecDroit */
| TOK ',' listf
listg : /* mot vide */ /* liste eventuellement vide gauche FAUSSE */
| listg ',' TOK
listh : /* mot vide */ /* liste eventuellement vide droite FAUSSE */
| TOK ',' listh
listi : /* mot vide */ /* liste eventuellement vide gauche CORRECT */
| liste
%%
Écrire une grammaire récursive droite et une grammaire récursive gauche pour reconnaître une liste éventuellement vide d'entiers chacun suivi d'un ';'.
Ceci correspond par exemple à la définition d'un programme comme une séquence d'instructions terminées par un ';'.
C'est aussi le schéma de l'analyse "ligne à ligne" utilisée depuis le début de l'exercice.
Corrigé:
%%
listk : /*vide */ /* liste eventuellement vide rec. gauche */
| listk TOK ';' {printf(GREEN("%d "),$2);}
;
listj : /*vide */ /* liste eventuellement vide rec. droit */
| TOK ';' listj {printf(GREEN("%d "),$1);}
;
%%
Une spécification complète qui couvre l'ensemble des questions précédentes : list.bison
Issu du TP Noté 2013.
Le peuple shadok ne connaît que quatre syllabes : "Ga", "Bu", "Zo" et "Meu".
Tout les mots de la langue shadok sont obtenus par concaténation de ces syllabes fondamentales. Par exemple selon Wikipedia : "ZoGa" signifie pomper, "ZoBuGa" signifie pomper avec une petite pompe, et "ZoBuBuGa" signifie pomper avec une grosse pompe.
Le professeur Shadoko a défini la famille des mots "MeuMeu" comme suit :
Le lecteur vérifiera en exercice les exemples suivants : (gabu.data)
Corrigé:
Le peuple Gibi, ennemi des shadoks, semble avoir un ensemble de mots comparable, mais à la place des syllabes Ga, Bu, Zo et Meu, ils utilisent des symboles ésotériques : {, [, ], }.
En fait le langage "MeuMeu" est connu usuellement comme langage des mots bien parenthésés, ou en informatique théorique comme langage de Dyck ici sur 2 paires de parenthèses. Ce langage joue un rôle particulier en informatique théorique dans la mesure où il apparaît comme l'exemple générique ou générateur de tout les langages algébriques :
Soit Dn, le langage de Dyck sur n paires de parenthèses, on a les énoncés équivalents du théorème de Chomsky-Schützenberger :
Cet exercice illustre l'utilisation combinée de Flex et de Bison avec les notions :
Il s'agit de calculer ou d'évaluer des expressions bien parenthésées, ne comportant que des valeurs numériques et les opérateurs arithmétiques usuels.
Dans un premier temps, on suppose :
+ - / * % , mais pas le - unaire.
(1+(2*3)) ==7 ((1+2)*3) ==9 ( (3 * 4) + (4 - 3)) ==13 ( 22 + - 22 ) ==erreur de syntaxe
Définir les catégories lexicales nécessaires, définir le passage de valeurs pour ces catégories lexicales, écrire l'analyseur lexicale, définir la grammaire et écrire l'analyseur syntaxique.
Corrigé : calc0.flex et calc0.bison
On désire maintenant accepter les expressions arithmétiques avec les règles usuelles de priorité et d'associativité des opérateurs.
Modifier la grammaire pour avoir une grammaire simple et éventuellement ambiguë.
Ajouter une gestion des priorités pour résoudre les conflits avec les directives : %left %right %nonassoc
1+2*3 ==7 1*2+3 ==5 7-3-2-1 ==1 6/3/2 ==1
Corrigé : calc1.flex et calc1.bison
Modifier la calculatrice pour accepter des opérations flottantes ou entières.
N.B. : la gestion de "cast" sur les types peut être un peu lourd. On veut ici garder le type entier pour l'opération modulo "%"; Pour les autres opérations on transformera rapidement les entiers en flottant. L'expression "4 % (1+1)" sera ainsi invalide...
Corrigé : calc2.flex et calc2.bison
Les expressions peuvent maintenant contenir des noms de variables. L'affectation
d'une valeur se fera sous la forme "nom = Expr \n". L'utilisation d'une variable
à l'intérieur d'une expression s'obtient directement par son "nom".
A= 1 + 2 * 3 // A<-7 A // == 7 B= 3 * A - 1 // B<-20 B+5 // ==25 A*A-B*B-(A+B)*(A-B) // ==0 !
Les noms de variables seront uniquement les 26 lettres majuscules A,B,..Z. On pourra
alors implémenter une table des symboles simple par un tableau fixe de taille 26, servant
à stocker la valeur de chaque variable, ou le fait qu'une variable soit initialisée.
N.B. : En C, pour un caractère "char c" dans [A-Z], " c - 'A' " donne un index entier entre 0 et 25. Réciproquement, pour un entier "int i" entre 0 et 25 " 'A' + i " donne les caractères entre A et Z.
Modifier la calculette pour gérer les nom de variables.
NB: On suggère dans un premier temps de ne considérer que des affectations simples sur des lignes spécifiques. On peut ensuite généraliser en considérant une affectation comme une expression et permettre comme en C des affectations multiples "a=b=2", ou des affectations internes "a=3*(b=2+(c=3))". On notera que le "=" devient ainsi un opérateur associatif à droite.
Corrigé : calc3.flex et calc3.bison
Prévoir des cas de récupérations d'erreurs:
Ajouter aussi des contrôles d'erreurs sémantiques comme par exemple "utilisation de variable non initialisée", "Réaffectation de variable déjà initialisée" ...
Corrigé : Cf. corrigé de la question suivante ( calc4.flex et calc4.bison)
Améliorer la calculette en autorisant l'utilisation du '-' unaire.
Ajouter éventuellement la puissance '^' (en C : double pow(double x, double y) avec #include <math.h>, et gcc -lm )
La calculette est elle correcte ? :
Le problème est que la priorité définie pour le token "-" binaire, ne convient pas pour le '-' unaire.
Bison dispose d'un mécanisme pour ajouter des priorités spécifiques au niveau
d'une règle de grammaire. Pour cela, il faut définir dans le préambule de la spécification un token fictif par exemple %left UMINUS. La position
de ce token par rapport aux autres directives "%letf %right %nonassoc" fixe sa priorité. Ensuite, pour une règle où l'on veut une priorité spécifique,
ajouter à la fin de la règle (avant l'action) la directive %prec UMINUS
Tester l'analyseur en fixant une priorité spécifique pour le moins unaire. Vérifier le comportement dans les différents cas :
Corrigé : calc4.flex et
calc4.bison
NB: Le fichier Makefile générique est
modifié pour prendre en compte la fonction pow avec l'ajout d'une ligne "calc4 : EXT_SRC = -lm"
------ TestEval.c #include <stdio.h> int main() { int a=1; printf(" -(++a*++a) = %d\n", -(++a*++a)); a=1; printf(" (-++a)*++a = %d\n", (-++a)*++a); a=1; printf(" -++a*++a = %d\n", -++a*++a); return 0; }
--TestEval.resu -(++a*++a) = -9 (-++a)*++a = -6 -++a*++a = -6
Ajouter à la calculette des fonctions arithmétiques avec une syntaxe usuelle "Nom_Fonction(exp1 , exp2 , ...)".
5 + Max(3+2, 4) * 2 =>15
5 + Min(3+2, Min(3,1)*2 , 2.5 , 5 ) * 2 =>9
NB: En C, l'ordre d'évaluation des arguments d'une fonction est indéterminé, on pourra donc choisir ici ce qui convient le mieux à Bison (Récursivité gauche)
Corrigé : calc5.flex et
calc5.bison. La fonction Min() est définie avec N>0 arguments, la fonction Max() est définie avec deux arguments.
NB: Le fichier Makefile générique est
modifié pour prendre en compte la fonction pow avec l'ajout d'une ligne "calc5 : EXT_SRC = -lm"
A titre d'illustration de la notion de table de symboles, on donne ici une version étendue de la calculatrice arithmétique qui autorise comme nom de variable des identifiants quelconques.
On se donne une implémentation de base de la structure algorithmique table de symboles avec les fichiers symtab.c et symtab.h (ou Pretty Print HTML des 2 fichiers). La structure "_stab" dans "symtab.h" pourra être adaptée pour enregistrer les différentes informations utiles que l'on veut associer à chaque identificateur de notre langage.
Pour chaque identificateur rencontré au niveau lexical :
L'adaptation de la version finale "calc5" du corrigé de la calculatrice donne l'analyseur calc-symtab.flex et calc-symtab.bison.
NB: Pour tester, le fichier Makefile générique est modifié avec l'ajout d'une ligne "calc-symtab : EXT_SRC = symtab.c -lm"
Dans une analyse syntaxique de type "calculette", il n'y a pas de construction explicite de l'arbre de
syntaxe décrivant l'analyse mais une évaluation au fur et à mesure de la construction de l'arbre.
On veut illustrer ici, l'approche opposée qui consiste à construire explicitement l'arbre de syntaxe abstraite pour
un traitement ultérieure au niveau de l'analyse sémantique, ou de la génération de code.
Transformer la "calculette" arithmétique de l'exercice précèdent, de façon à construire un "compilateur" d'expression arithmétique, c'est à dire de produire explicitement et d'imprimer l'arbre de syntaxe abstraite.
Sur le principe, l'exercice est simple puisqu'il suffit juste (!) :
Dans la pratique, ce qui peut être un peu pénible, c'est la gestion des feuilles qui outre la catégorie lexicale contiennent éventuellement une valeur issue de l'analyse lexicale (valeur entière, flottante, référence dans une table de symboles...). Pour alléger l'exercice, on oublie ces valeurs et l'on considère des arbres syntaxiques ne contenant qu'une chaîne de caractère pour chaque noeud. La chaîne est le nom de la règle pour un symbole non-terminal (et donc un noeud interne) ou un nom de token pour une feuille.
On se donne une implémentation de structure d'arbres N-aires avec les fichiers arbre.c et arbre.h (ou Pretty Print HTML des 2 fichiers)
Usage :
arbre.h doit naturellement être inclus dans la spécification Bison.
arbre.h doit aussi, moins naturellement, être inclus dans la spécification Flex avant yyparse.h (yyparse.h contient un union qui utilise le type arbre)
arbre.c dans l'analyseur,
on peut "salement" faire un #include "arbre.c" dans la spécification Bison; ou plus proprement ajouter dans le Makefile générique du cours une ligne du genre :
AST-calc : EXT_SRC = arbre.c
AST-calc est l'analyseur construit à partir de AST-calc.flexet AST-calc.bison, et en plus arbre.c.
Exemple d'utilisation pour l'exercice:
%union {
...
arbre ARBRE
}
%token <ARBRE> Expr
%%
Expr : Expr '+' Expr { $$ = N("regle plus", $1, F("+"), $3); }
%%
Exemple de résultat avec l'impression print_arbre_height()
-3^4*2
- int ^ int * int
| | | | | |
| --------------- | |
| | | |
| R^ | |
| | | |
| ----------------------
| |
| R*
| |
--------------------------
|
Rumin
Corrigé : calc-AST.flex et
calc-AST.bison.
Et un fichier Makefile modifié avec l'ajout d'une ligne "calc-AST : EXT_SRC = arbre.c"
Deux variations autour de l'exercice "Calculatrice Arithmétiques" :
cf. TP Noté 2013 Exercice 1 "Analyse syntaxique d'expressions booléennes" Sujet+Corrigé
Avec deux versions de grammaire au choix :
A = union(B,C)
A = B union C
cf. TP Noté 2014 Exercice 3 "Analyse syntaxique d'expressions ensemblistes" Sujet+Corrigé
On donne ici une illustration du passage de valeurs de type chaîne de caractères entre Flex et Bison. Le choix est soit de faire une recopie systématique des chaînes (et de faire les free après usage), soit d'utiliser un pointeur en supposant que le buffer pour yytext est commun pour les différents fragments.
Le second choix semble fonctionner dans la pratique mais n'est spécifié nulle part et peut donc être dépendant de l'implémentation. Il est d'autre part sujet à des effets de bord dans le cas d'utilisation des fonctions flex comme unput(), yyless(), yymore().
Le premier choix avec par exemple l'utilisation de la fonction strdup() est donc en général préférable.
Le but est d'explorer les possibilités d'analyse syntaxique en langage naturel, sans toutefois rentrer trop dans la linguistique. On acceptera donc des solutions empiriques. L'exemple proposé est celui des sous-titres du Wall Street Journal, esquissé dans les slides du cours et dans l'exercice "Premier pas Bison". Il s'agit à chaque étape, d'améliorer la grammaire pour accepter les titres (réels) donnés en exemple.
Le but est de créer des structures mémorisant l'analyse syntaxique d'une phrase pour
des analyses sémantiques ultérieures plus poussées.
On se contente ici d'une structure de phrase très simple, pour éviter des analyses
linguistiques spécialisées :
---- langnat.data une grande entreprise rachete une petite PME . les petites PME informatique survolent un marche terne . le chat gris attrappe la souris verte les vertes souris mangent les chats gris une jolie souris attrappe le gentil chat les petits chats jolis attrappent les souris vertes les jolis chats marrants attrappent les gentilles souris le chat court vite si le joli chat attrappe la souris , alors le chat mange la souris
On se donne une version de départ (correspond au 1er exemple): langnat.flex et langnat.bison
Vous pouvez compléter la grammaire pour traiter quelques autres exemples à votre idée. Pour traiter en une seule fois plusieurs Phrases, penser à définir une notion de Texte. et traiter les erreurs.
Pour remonter les valeurs des "tokens" (chaînes de caractères) vers le niveau syntaxique et sémantique, il convient de recopier les valeurs de yytext et de remonter dans yylval un pointeur sur cette copie. (cf 6. Passage de Chaînes de caractères)
Il s'agit de créer des structures de données pour mémoriser les éléments d'une phrase. Les structures et fonctions associées seront programmées dans un fichier séparé à inclure au niveau du prologue (mettre au point ce code d'abord isolement).
Un exemple de code de départ est donné dans langnat.c pour une structure "GroupNom".
NB: Pour une intégration rapide du code externe "langnat.c" dans la spécification, on se permettra de faire directement un #include "langnat.c" dans la spécification Bison (horreur!!).
La bonne pratique serait de structurer le code externe avec un
"langnat.c" et un "langnat.h", de faire le #include "langnat.h"
dans la spécification et d'ajouter à la compilation le "langnat.c".
Avec le Makefile générique du cours, il suffirait d'ajouter dans le fichier Makefile une ligne "langnat : EXT_SRC = langnat.c"
Corrigé : langnat1.flex,
langnat1.bison et
langnat1.c
Avec par exemple en entrée :
le chat gris attrappe la souris verte les vertes souris mangent les chats gris