Compilation : De l'algorithme à la porte logique

Portail informatique

Mémento d'utilisation de JFlex

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 le fichier Jflex.include. Pour des informations plus complètes ou détaillées, on se reportera au manuel JFlex.

Exécution

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
--nobak pas de sauvegarde pour le fichier Yylex.java généré
--dump affichage textuel des automates générés
--dot écriture des automates générés dans des fichiers .dot pour Graphviz

Format d'une spécification

Trois sections séparées par "%%" Par exemple :
Les commentaires sont dans le style C/C++.

Reconnaissance de fragments

Fragments reconnus et Actions


  • 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 tous les fragments possibles (cf. règle balai).

Reconnaissance gloutonne sans recouvrement


  • 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 "gloutonne" (greedy) par opposition à d'autres outils permettant une reconnaissance dites "récalcitrante" (reluctant).
  • Une action n'est réalisée que sur un fragment qui ne peut être prolongé.

Ambiguïté, ordre des règles


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.

Règle-balai


L'entrée peut contenir des données erronées, ou sans utilité applicative, ou incorrectement traitées 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 "règle-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 débogage, 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 [^].

Action vide


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".

Expressions régulières JFlex

Échappement : "" et \


Les caractères suivants 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 mono-ligne
Dans une chaîne, seul " et \ sont des caractères réservés
\ Échappement du caractère suivant

Opérateurs fondamentaux, priorités et parenthèses : |,*, ()


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

Caractères et Classe de caractères : ., [ ], [^ ], [ - ]


Un caractère C dans une expression régulière peut être obtenu par :
C si C est imprimable et n'est pas un métacaractè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
Une classe de caractères 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 une 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’intérieur d'une classe
Pourquoi le caractère "." est t'il reconnu par [+*-/] ???
Réponse dans la table ASCII : 052 42 2A * 053 43 2B + 054 44 2C , 055 45 2D - 056 46 2E . 057 47 2F /

Répétitions : *, +, ?, {}


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

Spécification de contexte : ^, $, /


Pour une expression r, on a les reconnaissances :
^ r reconnaît r uniquement en début de ligne
r $ reconnaît r uniquement en fin de ligne
r / suite reconnaî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.

Autres expressions


Les éléments suivants sont plus spécifiques à l'outil JFlex et l'on évitera 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 POSIX [:digit:], [:space:], [:word:] et complémentaires
! r
~ r
Opérateur Négation (Danger explosion combinatoire !)
Opérateur UpTo (Danger explosion combinatoire !)
[ || ] [ && ] [ -- ] [ ~~ ] Opérations ensemblistes sur les classes de caractères :
Union, Intersection, Différence, et Différence symétrique

Définitions régulières

Il s'agit de noms symboliques utilisables dans la définition des expressions régulières :
NOM = RegExp Dé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.

Super-états (Bonus)

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-états inclusifs */ %xstate nom4 nom5... /* Définit des super-états exclusifs */
  • 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 inclusifs (%state), mais pas pour les super-états exclusifs (%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*/ } }

Instrumentation du code Java

Comment instrumenter une spécification JFlex pour réaliser diverses applications utiles ?

La classe Yylex


L'outil JFlex produit une classe Yylex.java 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 un return explicite dans une action.

API


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 YYINITIAL le 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'entrée (très sale mais parfois utile !)
Et avec les options du cours des fichiers Jflex*.include :
long yychar; int yycolumn, yyline positions 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 l'entrée standard ou sur le fichier 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

Codes utilisateur


  • 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.

CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Juillet 2022