CSC4536– Compilation : De l'algorithme à la porte logique

Portail informatique
Ce mémento résume les fonctionnalités de JFlex et les illustre avec des exemples. On se limite aux fonctionnalités utilisées dans le cours et on suppose l'utilisation des options fournies par les fichiers Jflex.include et JflexCup.include.
Pour des informations plus complètes ou détaillées, on se reportera au manuel JFlex.
L'outil JFlex est fourni sous la forme d'une archive Java exécutable. Il prend en entrée une spécification JFlex et produit en sortie une classe Yylex.java contenant la méthode d'analyse lexicale yylex() ou next_token().
Si l'on définit une méthode main() dans la spécification, on a l'exécution : java -jar jflex.jar <options> foo.jflex javac Yylex.java java Yylex <args> Options utiles :
-h --help affiche toutes les options
-v --verbose plus verbeux (défaut)
-q --quiet moins verbeux
-d <directory> génère la classe dans directory (package Java non géré!)
--nobak pas de fichier backup pour la classe générée
--dump affichage textuel des automates générés
--dot écriture des automates générés dans des fichiers .dot (graphviz)
Trois sections séparées par "%%" Par exemple : Les commentaires sont dans le style C/C++. Ne pas mettre de commentaires sur la même ligne qu'une directive "%xxx"
Pour un fragment reconnu par une expression régulière :
  • l'action associée à l'expression est exécutée
  • la valeur du fragment est accessible par la méthode String yytext();
  • la méthode void ECHO() imprime la valeur de yytext();
  • si l'action est vide, l'unité lexicale est "absorbée"
Pour un fragment non reconnu, une exception Java est lancée Le fonctionnement traditionnel de lex ou flex, ou le mode %standalone de JFlex imprime par défaut les fragments non reconnus. Pour le cours, on préfère spécifier explicitement la reconnaissance et les actions pour tout les fragments possibles (cf. règle balai).
  • Un fragment débute avec la reconnaissance d'une expression régulière et se prolonge le plus loin possible jusqu'à la reconnaissance d'un autre fragment ou jusqu'à la fin de l'entrée
  • La reconnaissance est dite "glouton" (greedy) par opposition à d'autres outils permettant une reconnaissance dites "récalcitrantes" (reluctant)
  • Une action n'est réalisée que sur un fragment qui ne peut être prolongé

Si plusieurs règles peuvent s'appliquer :
  • l'expression reconnaissant le plus long fragment est choisie,
  • en cas d'égalité de longueur, on choisit la règle en premier dans la spécification
En permutant les deux premières règles dans la spécification. La règle R1 ne s'appliquera jamais car toujours devancée par R2. L'outil JFlex le signale à la compilation par un message Rule can never be matched

L'entrée peut contenir des données erronées, ou sans utilité applicative, ou incorrectement traitée par la spécification. Il est donc utile d'ajouter des règles pour traiter ce qui n'est pas reconnu par le reste de la spécification.

Une réalisation simple consiste à ajouter en fin de spécification une "regle-balai" ou "ramasse-miettes", reconnaissant tous les caractères. Elle s'appliquera sur les fragments non reconnus par les règles précédentes. L'action associée permettra de faire du traitement d'erreur, ou de debugging, ou un traitement par défaut des caractères inutiles

Traditionnellement la règle balai s'écrit sous la forme . | \n. Avec Jflex, on a une écriture plus systématique avec [^] ou . | \R (cf. plus loin).

L'action notée | indique qu'il faut faire l'action de la règle suivante. On peut aussi le voir comme l'écriture d'une expression régulière sur plusieurs lignes séparées par l'opérateur "OU".

Les caratères suivant peuvent avoir une interprétation réservée dans une spécification JFlex : <>{}()[]|!~*+?"^$/.\,
Pour supprimer l'interprétation par JFlex des méta-caractères, on dispose de :
" " Chaîne de caractères monoligne
Dans une chaîne, seul " et \ sont des caractères réservés
\ Echappement du caractère suivant

Les expressions régulières sont définies à partir des opérateurs (ordre croissant de priorité) :
r1 | r2 Alternative
r1 r2 Concaténation
r * Fermeture de Kleene
( r ) Groupement pour application des opérateurs

Un caractère C dans une expression régulière peut être obtenu par :
C si C est imprimable et n'est pas un metacaractère JFlex
\C si C est imprimable et n'est pas en conflit avec la suite
\xnm ASCII avec nm 2 chiffres hexadécimaux ([0-9a-fA-F])
\ijk ASCII avec ijk 3 chiffres octaux ([0-7])
\unmop Unicode avec 4 chiffres hexadécimaux
\Unmopqr Unicode avec 6 chiffres hexadécimaux
\b ANSI-C Backspace
\f ANSI-C Form Feed
\n ANSI-C Newline
\r ANSI-C Carriage Return
\t ANSI-C Horizontal Tabulation
Halloween c'est Noël: 31 oct. = 25 dec.

Une classe de caractère reconnaît un seul caractère choisi parmi un ensemble. on a ainsi :
[ab...] un caractère parmi a, b, ... (== a|b|....)
[i-p...] un caractère dans l'intervalle ASCII de i à p ou ...
[^ab...] un caractère quelconque sauf a,b, ... (Complémentaire)
. un caractère quelconque sauf fin de ligne
(== [^\r\n\u2028\u2029\u000B\u000C\u0085] )

De manière spécifique à JFlex, on a aussi :
[^] un caractère quelconque (== . | \R)
\R "caractère" de fin de ligne
== \r\n | [\r\n\u2028\u2029\u000B\u000C\u0085]
n'est ni un caractère ni une classe,
n'est pas utilisable à l'interieur d'une classe

Pour une expression r, on a les "Répétitions" de r :
r * répétition n fois avec n≥0
r + répétition n fois avec n>0
r ? répétition n fois avec n=0 ou n=1
r {N} répétition exactement N fois
r {N,M} répétition n fois avec N≤n≤M

Pour une expression r, on a les reconnaissances :
^ rreconnaît r uniquement en début de ligne
r $reconnaît r uniquement en fin de ligne
r / suitereconnaît r uniquement avant "suite"
  • Dans les différents cas, le contexte "\n" ou "suite" n'est pas consommé.
  • Si quelque chose précède ^, ou suit $, les caractères ^ et $ reprennent leur sens littéral.
  • ^r$ est interdit si r peut être vide
  • L'usage simultané de / et $ est interdit

Les éléments suivants sont plus spécifiques à l'outil JFlex et l'on evitera de les utiliser :
[:jletter:] [:jletterdigit:]
[:letter:] [:digit:]
[:uppercase:] [:lowercase:]
Classes prédéfinies à la POSIX
\p{...} \P{...}Classes prédéfinies selon les catégories Unicode
\d \D \s \S \w \W Classes "digit", "space", "word" et complèmentaires
! r
~ r
Opérateurs Négation et UpTo
(Danger explosion combinatoire!)
[ || ] [ && ] [ -- ] [ ~~ ]Opérations ensemblistes sur les classes de caractères :
Union, Intersection, Différence, et Différence symmétrique
Il s'agit de noms symboliques utilisables dans la définition des expressions régulières :
NOM = RegExpDéfinition dans la section "Options et déclarations"
{NOM}Utilisation
L'utilisation d'une définition régulière est permise dans la définition d'une autre mais toute récursivité est strictement interdite.
JFlex permet de définir un "super-automate" qui s'ajoute au dessus de la reconnaissance par expressions régulières. Ceci permet d'accéder directement au formalisme des automates finis quand l'écriture d'une expression régulière devient compliquée.
  • Les super-états sont déclarées sous la forme %state nom1 nom2 .. /* Définit des super-etats inclusives */ %xstate nom4 nom5 .. /* Définit des super-etats exclusives */
  • Au départ, l'automate est dans le super-état YYINITIAL ou 0
  • La méthode yybegin(etat) change le super-état de l'automate.
  • Une expression régulière préfixée <etat>expr ne s'applique que si l'automate est dans le super-état etat
  • Les expressions non préfixées s'appliquent pour l'état YYINITIAL et pour les super-états inclusives (%state) mais pas pour les super-états exclusives(%xstate)
Le préfixe d'une expression régulière peut contenir une liste d'états et les expressions peuvent être regroupées pour un même préfixe : <etat1, etat2> { r1 { /* action1*/ } r2 { /* action2*/ } }
Comment instrumenter une spécification JFlex pour réaliser diverses applications ?
L'outil JFlex produit une classe Yylex avec un constructeur Yylex(java.io.Reader in).

L'analyse lexicale sera réalisée par la méthode Yytoken yylex() (ou suivant la configuration : int yylex(), int next_token(), java_cup.runtime.Symbol next_token())

La méthode yylex()
  • lit les caractères en entrée jusqu'à reconnaître un fragment
  • exécute l'action correspondante
  • continue avec la lecture du prochain fragment. sauf si l'action contient une instruction return
Ainsi la méthode yylex() ne termine que sur la fin de fichier (EOF), ou sur une instruction return explicite dans une action.

Les variables et méthodes suivantes sont utilisables dans les actions :
String yytext()le dernier fragment reconnu
int yylength()yytext().length()
char yycharat(int pos)yytext().charAt(pos)
int yybegin(int state)change le super-état
int yystate()retourne le super-état courant
static final int YYINITIALle super-état initial
int yyreset(java.io.Reader in)réinitialise le scanner sur la nouvelle entrée.
void yypushback(int n)remet les n derniers caractères lus dans le flot d'entée (très sale mais parfois utile!)

Et avec Jflex*.include :
int yychar, yycolumn, yylinepositions courantes dans l'entrée
String WHERE()chaîne "yyline/yycolumn(yychar)"
void ECHO()imprime yytext()
void ECHO(String categorie)imprime "[categorie:yytext()]"
void WARN(String msg)imprime message d'erreur
public static void main(String[] args)main() avec lecture sur stdin ou args[0]
java_cup.runtime.Symbol TOKEN(int code)génère une valeur de retour pour CUP
java_cup.runtime.Symbol TOKEN(int code, Object value) idem avec valeur sémantique du token
  • un bloc %{ ... %} permet d'ajouter des variables ou des méthodes à la classe Yylex pour utilisation dans les actions
  • un bloc %init{ ... %init} permet d'ajouter du code exécuté initialement dans le constructeur de Yylex
  • un bloc %eof{ ... %eof} permet d'ajouter du code exécuté à la fin de l'entrée
Si la quantité de code utilisateur devient importante, il est rapidement préférable de développer ce code dans une classe séparée.

CSC 4536, TELECOM SudParis, P Hennequin, Last modified: Sept 2018