"ExoLexParse" : Exercices sur le couplage Analyseur Lexical et Analyseur Syntaxique (Corrigé)

0. Sommaire et Objectifs

1. Analyse lexicale manuelle

   Structure basique de yylex(), préparation au couplage avec bison.

2. Premiers pas Bison sans Flex (== avec Analyse lexicale manuelle)

   Format spécification Bison, couplage yyparse() et yylex(), tokens.

3. Utilisation combinée de Flex et Bison

   Makefile et prototypes de spécification du cours, gestion d'erreurs.

4. Flexification de "Bison sans Flex"

   Exemple corrigé d'une version combinée Flex et Bison des 2 premiers exercices

1. Analyse lexicale manuelle

L'objectif de cet exercice est de démystifier ce qu'est un analyseur lexical et de pouvoir en cas de besoin écrire le sien sans utiliser lex/flex.

1.1) Prise en main

Les éléments suivants sont fournis:

• un fichier exemple élémentaire test.data
• un analyseur lexical rudimentaire yylex0.c

Lire et comprendre le code de l'analyseur.

Compiler, exécuter et expliquer ...

• N.B.: imprimer sur stderr garantit une impression immédiate, même sans \n ou flush
• l'automate reconnaisseur est à programmer entièrement
• quelles sont les catégories lexicales ?

1.2) Améliorations simples

Implanter un analyseur lexical yylex1.c contenant les affichages suivants:

• ART: pour "a" "an" "the"
• TRANS_VRB: pour "cut" "cuts"
• COMM_NOUN: pour "bill" "bills"
• PROP_NOUN: pour "Bell" "Verizon"
• et les catégories '.' et '\n'

L'exercice devient vite fastidieux ! C'est pourquoi on peut aimer l'outil flex même avec une utilisation simpliste des expressions régulières.

2. Premiers pas Bison Sans Flex (== avec Analyseur lexicale manuelle)

En reprenant l'analyseur lexical simple de l'exercice précédent, on se concentre ici sur l'utilisation de bison pour développer une analyse syntaxique au dessus de l'analyse lexicale.

2.1) Prise en mains

On reprend les éléments fournis dans l'exercice précédent

• un fichier exemple test.data
• un analyseur lexical yylex0.c

On donne de plus une spécification simple Bison d'analyseur syntaxique gram0.bison

a) Lire et comprendre :

• L'outil bison générera le code d'une fonction yyparse() et utilisera la fonction externe yylex() (celle de yylex0.c) pour lire les unités lexicales successives en entrée.
  De plus, il convient de fournir le code d'une fonction yyerror(char *) appelée pour l'impression de messages en cas d'erreur de syntaxe
• La spécification gram0.bison définit un axiome Text comme une liste sans structuration d'unités lexicales. Il y a 3 unités lexicales : "WORD", '\n' et '.'
• Les unités lexicales sont gérées comme des valeurs entières. Ce sera la valeur de retour de la fonction int yylex() au niveau lexical, et la valeur des tokens au niveau syntaxique. Il faut donc partager cette valeur de retour entre le code de l'analyseur syntaxique et le code d'analyseur lexical.
• En pratique, Bison générera les valeurs des unités lexicales à partir de la directive %token, ces valeurs sont ensuite intégrées dans l'analyseur lexical par un #include ""
• On notera qu'un caractère peut former une catégorie lexicale à lui seul. Pour Bison, les caractères ASCII (sauf NUL=\0) sont implicitement des catégories lexicales (valeur==code ASCII) et il n'est pas nécessaire de les déclarer dans la directive %token. Pour la lisibilité de la spécification, il est toutefois mieux de les déclarer systématiquement.

b) Compiler, adapter et exécuter :

• Compiler la spécification bison :
  

  > bison -d -o gram.tab.c  gram0.bison 
  

  • Ceci produit le code de la fonction yyparse() dans le fichier "gram.tab.c" (option -o).
  • Cela génère de plus un fichier "gram.tab.h" (option -d).
    Quel est le rôle de ce fichier ?
• Compiler et tester :
  

  > gcc gram.tab.c yylex0.c
  > a.out < test.data
  

• Adapter le fichier yylex0.c pour que cela marche :
  • Déactiver le main() obsolète de yylex0.c (=> compile OK)
  • Inclure le fichier "gram.tab.h" au lieu du "#define WORD" existant (=> même valeur de WORD entre yylex et yyparse)
  • ...
  • Suggestion : Introduire une macro cpp ("#define FLEXALONE") pour avoir, avec le même code, la version couplée avec bison ou la version analyseur lexical autonome.

2.2) Améliorations simples

Ajouter les catégories lexicales ART, TRANS_VRB, COMM_NOUN, PROP_NOUN comme dans l'exercice précédent.

On peut reprendre le corrigé de l'exercice précédent yylex1.c ou sa forme adaptée yylex1-bis.c.

Enrichissez par étape la grammaire "gram0.bison" pour :

• Définir et accepter les nouvelles catégories lexicales

  Corrigé : gram1.bison.

• Reconnaître un GroupeNom (nom propre ou article et nom commun)

  Corrigé : gram2.bison.

• Reconnaître une Phrase (sujet verbe complément et '.')

  Corrigé : gram3.bison.

• Reconnaître une Liste de phrases ligne à ligne et accepter les lignes vides

  Corrigé : gram4.bison.

• Gérer les erreurs de syntaxe et resynchronisation par ligne (cf . exercice suivant)

  Corrigé : gram5.bison.

2.3) Flexification

Refaire l'exercice en remplaçant l'analyseur lexical manuel par un analyseur lexical Flex.
Ceci constitue l'exercice 4. Flexification de "Bison sans Flex" à traiter après l'exercice 3.

3. Utilisation combinée de Flex et Bison

L'écriture manuelle d'un analyseur lexical est peu optimisée, et rapidement fastidieuse. Il est plus commode de le préparer avec Flex; puis de le combiner avec un analyseur syntaxique préparé par Bison.

3.1) Makefile et prototypes de spécification

On recommande le schéma générique suivant pour la construction d'analyseurs syntaxiques/lexicaux Flex+Bison :

Fichiers Prototypes :

• Makefile Fichier Makefile Générique
• proto-color.h Impression Couleur utilisée dans les specif.
• proto.flex Prototype de spécification flex (avec couplage bison)
• proto.bison Prototype de spécification Bison

On suppose alors que :

• Les fichiers de spécifications sont nommés "NOM.flex" et "NOM.bison"
• L'analyseur exécutable est nommé "NOM" et s'obtient par "> make NOM"
• Bison génère les fichiers intermédiaire "yyparse.c" et "yyparse.h"
• Flex génère le fichier intermédiaire "yylex.c", et inclus potentiellement le fichier "yyparse.h"
• Pas de librairies -ll ou -ly, les fonctions "yywrap()", "yyerror()" et "main()" doivent être écrites dans les fichiers .flex ou .bison
• Pour éviter certains warnings avec gcc -Wall, on ajoute les options "%option nounput noinput" dans les spécifications Flex.
• La spécification flex "proto.flex" utilise un define "FLEXALONE" qui permet d'avoir le même code pour une version analyseur Flex seul ou analyseur combiné Flex et Bison
• "> make lex-NOM" génère l'analyseur lexical seul. "> make NOM" aura le même effet si le fichier "NOM.bison" n'existe pas,
• "> make parse-NOM" génère l'analyseur syntaxique ou une erreur si le fichier "NOM.bison" n'existe pas.

Analyser les fichiers fournis.

3.2) Prise en main sur un exemple simple

On se donne les spécifications et fichiers de test suivants :

• flexbison0.flex dérivé de proto.flex
• flexbison0.bison dérivé de proto.bison
• flexbison.data et flexbison.data1

Analyser les fichiers fournis.
Créer l'analyseur lexical seul : > make lex-flexbison0
Créer l'analyseur syntaxique > make flexbison0 , ou > make parse-flexbison0
Exécuter et comprendre les résultats.

3.3) Grammaire plus étendue

Améliorer la grammaire précédente en définissant un Text comme une succession de Sentence.
Chaque Sentence a une forme simple :

• une chaîne entre doubles quotes "" est considérée comme un mot
• une Sentence commence par une majuscule, ou par une chaîne entre quotes
• une Sentence se termine par un point.

3.4) Traitement d'erreurs au niveau syntaxique : Explications

Il ne s'agit pas ici des techniques de traces (echo(),print(),...) utilisées lors de la mise au point d'une grammaire, mais de la gestion des erreurs lexicales ou syntaxiques dans les données analysées par un analyseur déjà au point. Comment localiser l'erreur ? Comment la remonter vers l'utilisateur ? Peut-on continuer l'analyse après une première erreur ? ...

Le problème devient vite assez complexe à gérer (et la documentation pas très accessible). On se contentera ici de donner un schéma relativement simple de traitement des erreurs syntaxiques qui permet de couvrir une base déjà assez large de problèmes.

a) Erreurs lexicales

La détection d'erreurs lexicales peut être facilement gérée par l'utilisation d'une règle-balai dans Flex. On a alors deux stratégies :

• Cacher ou manger l'erreur et continuer l'analyse de façon transparente.
  

  .     printf("Caractère Invalide");
  

• Remonter l'erreur vers le niveau syntaxique et provoquer sans doute une erreur au niveau syntaxique avec ce token "non prévu".
  

  .     /*printf("Caractère Invalide");*/ return(yytext[0]);
  

En pratique, le meilleur choix est généralement de ne pas cacher l'erreur lexicale et de reporter au niveau syntaxique. Dans un cas, comme dans l'autre on tente de poursuivre l'analyse lexicale pour détecter plusieurs erreurs dans une même passe.

b) Traitement d'erreurs syntaxiques avec Bison

Quand l'analyseur syntaxique Bison détecte une portion de texte erronée, c'est-à-dire qu'aucune règle de grammaire ne permet de traiter le token lu pour espérer reconstruire un arbre syntaxique complet, on a alors :

• l'analyseur passe dans l'état "Erreur"
• la fonction yyerror(), définie par l'utilisateur, est appelée pour l'impression d'un message d'erreur.
  N.B. : l'option %error-verbose donne des messages plus explicites ou en tout cas plus complets
• Bison utilise un symbole prédéfini "error", qui peut être utilisé dans les règles de la grammaire.
  Dans l'état "Erreur", l'analyseur acceptera les tokens successifs comme reconnaissables par le symbole "error" et ceci jusqu'à retrouver un token qui peut avoir une interprétation correcte selon les règles de grammaire.
  Ceci permet un mécanisme de resynchronisation après erreur pour tenter de relancer l'analyse syntaxique sur la suite des données.
• Dans une règle utilisant le symbole "error", les actions suivantes peuvent être utiles :
  • yyerrok macro pour sortir de l'état "Erreur" et revenir à l'état normal.
  • yyerror() pour ajouter un message spécifique au yyerror() appelé par défaut
  • yyclearin macro pour purger le lookahead (pas d'autres explications pour le moment!!!)

c) Exemples de resynchronisation après erreur

Texte :   /* mot vide */
        | Texte  Ligne  '\n'  { printf("Ligne Correcte"); }
        | Texte  error  '\n'  { yyerrok; printf("Ligne Incorrecte ignorée");}
;

Ici les fins de lignes servent de resynchronisation après erreur.

Quelques variations :

Instr : ...
   | error ';' /* on error, skip until ';' is read */
;

Parent_expr : '(' expr ')'
            | '(' error ')'  /* resync with the next ')',   */
                             /* may be not the matching one */
;

3.5) Traitement d'erreurs au niveau syntaxique : Pratique

Améliorer la grammaire traitant un Text en ajoutant un traitement d'erreur au niveau syntaxique. Faire en sorte que l'analyseur ne s'arrête pas à la première erreur mais analyse l'ensemble du texte en signalant des erreurs successives.
Mettre en particulier en oeuvre la remontée d'erreur avec la règle-balai au niveau lexical.
Expérimenter éventuellement l'option Flex %option yylineno pour remonter et imprimer un numéro de ligne en cas d'erreur.

Étendre pas à pas la grammaire pour faire disparaître des cas d'erreur. Par exemple gérer les ponctuations (, ' ...),

4. Flexification de "Bison sans Flex"

A titre d'exemple, on donne ici le corrigé d'une version Flex+bison de l'exercice 2. Premiers pas : Bison sans Flex.
Ceci illustre l'utilisation du Makefile générique et des fichiers prototypes proposés comme modèles pour le cours.

4.1) Spécification Flex

Écrire une spécification Flex équivalente à l'analyseur lexical manuel yylex0.c de l'exercice 1.
Utiliser le nom gram0.flex.

Corrigé : gram0.flex.

4.2) Analyseur lexical seul

Construire et tester l'analyseur lexical seul avec "gram0.flex".

> make lex-gram0
> lex-gram0 < test.data

4.3) Analyseur syntaxique

Construire et tester l'analyseur syntaxique avec "gram0.flex" et la spécification "gram0.bison" de l'exercice 2.

> make gram0
> gram0 < test.data

4.4) Améliorations

Étendre la spécification Flex en ajoutant les autres catégories lexicales comme dans l'exercice 1 avec yylex1.c.

Corrigé : gram1.flex.

Construire et tester les versions successives des grammaires de l'exercice 2.

Corrigés des grammaires de l'exercice 2 : gram1.bison, gram2.bison, gram3.bison, gram4.bison, gram5.bison

--- pour X = 1..5
> ln -s gram1.flex gramX.flex
> make gramX
> gramX < test.data