Lexique

Lexique

L'analyse lexicale est le préalable indispensable à tout traitement des suites de caractères : elle découpe cette suite en une suite de mots dits aussi d'unités lexicales, ou lexèmes.

Le module `Genlex`

Ce module fournit une primitive simple permettant d'analyser une suite de caractères selon plusieurs catégories d'unités lexicales prédéfinies. Ces catégories sont distinguées par le type :


# type token =
    Kwd of string
  | Ident of string
  | Int of int
  | Float of float
  | String of string
  | Char of char ;;

On pourra ainsi reconnaître dans une suite de caractères un entier (constructeur Int) et récupérer la valeur représentée (argument du constructeur de type int) Les chaînes et les caractères reconnus obéissent aux conventions usuelles : une chaîne est délimitée par deux (") et un caractère par deux ('). Un flottant est représenté soit en utilisant la notation pointée (par exemple 0.01) soit la notation en mantisse et exposant (par exemple 1E-2). Restent les deux constructeurs Kwd et Ident.

Le constructeur Ident désigne la catégorie des identificateurs. Ce sont les noms de variables ou de fonctions des langages de programmation, par exemple. Ils correspondent à n'importe quelle suite de lettres et de chiffres pouvant inclure le caractère souligné (_) ou l'apostrophe ('). Cette suite ne doit pas commencer par un chiffre. On considère également comme identificateur (pour ce module, du moins) toute suite de symboles d'opérations ou de relations tels +, *, > ou =. Enfin, le constructeur Kwd définit la catégorie des mots clés qui contient des identificateurs distingués ou des caractères spéciaux.

La seule catégorie paramétrable de cet ensemble d'unités prédéfinies est celle des mots clés. La primitive suivante permet de créer un analyseur lexical en prenant comme ensemble de mots clés la liste passée en premier argument.


# Genlex.make_lexer ;;
- : string list -> char Stream.t -> Genlex.token Stream.t = <fun>

On obtient alors une fonction qui prend en entrée un flot de caractères et retourne un flot d'unités lexicales (type token).

On peut ainsi obtenir facilement un analyseur lexical pour notre BASIC. On déclare l'ensemble des mots clés :


# let keywords =
  [ "REM"; "GOTO"; "LET"; "PRINT"; "INPUT"; "IF"; "THEN";
    "-"; "!"; "+"; "-"; "*"; "/"; "%"; 
    "="; "<"; ">"; "<="; ">="; "<>";
    "&"; "|" ] ;;

On fabrique, avec cet ensemble, la fonction d'analyse lexicale :


# let line_lexer l = Genlex.make_lexer keywords (Stream.of_string l) ;;
val line_lexer : string -> Genlex.token Stream.t = <fun>
# line_lexer "LET x = x + y * 3" ;;
- : Genlex.token Stream.t = <abstr>

Le fonction line_lexer prend en entrée une chaîne de caractères et produit le flot de lexèmes correspondants.

Utilisation des flots

On peut procéder << à la main >> à l'analyse lexicale en manipulant directement des flots.

L'exemple suivant est un analyseur lexical pour les expressions arithmétiques. La fonction lexer prend un flot de caractères et construit un flot d'unités lexicales de type lexeme Stream.t¹. Les espaces, tabulations et sauts de lignes sont éliminés. Pour simplifier, nous ne traitons pas les variables ni les entiers négatifs.


# let rec spaces s =
   match s with parser
     [<'' '  ; rest  >] -> spaces rest
   | [<''\t' ; rest  >] -> spaces rest
   | [<''\n' ; rest  >] -> spaces rest
   | [<>] -> ();;
val spaces : char Stream.t -> unit = <fun>
# let rec lexer s =
   spaces s;
   match s with parser
     [< ''('  >] -> [< 'Lsymbol "(" ; lexer s >]
   | [< '')'  >] -> [< 'Lsymbol ")" ; lexer s >]
   | [< ''+'  >] -> [< 'Lsymbol "+" ; lexer s >]
   | [< ''-'  >] -> [< 'Lsymbol "-" ; lexer s >]
   | [< ''*'  >] -> [< 'Lsymbol "*" ; lexer s >]
   | [< ''/'  >] -> [< 'Lsymbol "/" ; lexer s >]
   | [< ''0'..'9' as c; 
        i,v = lexint (Char.code c - Char.code('0')) >] 
       -> [<'Lint i ; lexer v>]
 and lexint r s =
   match s with parser  
     [< ''0'..'9' as c >] 
     -> let u = (Char.code c) - (Char.code '0') in  lexint (10*r + u) s
   | [<>] -> r,s
 ;;
val lexer : char Stream.t -> lexeme Stream.t = <fun>
val lexint : int -> char Stream.t -> int * char Stream.t = <fun>

La fonction lexint est dédiée à l'analyse du morceau de flot de caractères correspondant à une constante entière. Elle est appelée par la fonction lexer lorsque celle-ci rencontre un caractère codant un chiffre. La fonction lexint consomme alors tous les chiffres consécutifs pour donner la valeur de l'entier correspondant.

Expressions rationnelles

Prenons un peu de hauteur et considérons le problème des unités lexicales d'un point de vue plus théorique.

De ce point de vue, une unité lexicale est un mot. Un mot est formé par la concaténation d'éléments d'un alphabet. Pour ce qui nous concerne, l'alphabet considéré est pris dans l'ensemble des caractères ASCII. Théoriquement, un mot peut ne contenir aucun caractère (le mot vide²) ou ne contenir qu'un seul caractère. L'étude théorique de l'assemblage d'éléments de l'alphabet pour former des éléments du lexique (les lexèmes) a abouti à un formalisme simple connu sous le nom d'expressions rationnelles.

Définition

Une expression rationnelle permet de définir des ensembles de mots. Par exemple : l'ensemble des identificateurs. Son mode de définition est basé sur un certain nombre d'opérations ensemblistes. Soient M et N deux ensembles de mots, on peut former :

l'union de M et N que l'on note M | N.
le complément de M que l'on note ^M. C'est l'ensemble de tous les mots sauf ceux de M.
la concaténation de M et N qui est l'ensemble des mots construits en mettant bout à bout un mot de M et un mot de N. On note simplement MN cet ensemble.
on peut itérer l'opération de concaténation sur les mots de l'ensemble M pour obtenir l'ensemble des mots formés d'une suite finie, mais de longueur quelconque, des mots de M. On note M+ cet ensemble. Il contient tous les mots de M, puis tous les mots formés par la concaténation de deux mots de M, puis de trois mots, etc... Si l'on désire en plus que cet ensemble contienne le mot vide, on note M*.
Comme cela s'avère utile, on se donne la construction M? qui désigne l'ensemble des mots de M plus le mot vide.

On assimile un caractère au singleton ne contenant que ce seul caractère. L'expression a | b | c désigne alors l'ensemble contenant les trois mots a, b et c. On utilisera la syntaxe plus compacte : [abc] pour définir cet ensemble. Comme notre alphabet est ordonné (par l'ordre des codes ASCII) on peut également définir un intervalle. Par exemple, l'ensemble des chiffres s'écrit : [0-9]. On peut se servir des parenthèses pour grouper des expressions.

Si l'on veut utiliser, pour lui même, un des caractères représentant un opérateur, on le fait précéder du caractère d'échappement . Par exemple (*)* désigne l'ensemble des suites d'étoiles.

Exemple

Considérons l'alphabet comprenant les chiffres (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) les symboles plus (+) et moins (-), le point (.) et la lettre E. On peut définir l'ensemble num des mots représentant les nombres. Appelons entiers l'ensemble défini par [0-9]+. On définit unum, l'ensemble des nombres non signés, par :

entiers?(.entier)?(E(+|-)?entiers)?

L'ensemble des nombres signés num est alors défini par :

unum | -unum ou par -?unum

Reconnaissance

Une fois défini un ensemble d'expressions, reste le problème de savoir si une chaîne de caractères ou une de ses sous-chaînes appartient ou non à cet ensemble. Pour cela, il faut traduire la définition formelle de l'ensemble en un programme de reconnaissance et de traitement des expressions. Dans le cas des expressions rationnelles, cette traduction peut être automatisée. De telles techniques de traduction sont mises en oeuvre par le module Genlex, dans la bibliothèque Str et dans l'outil ocamllex que nous présentons dans les deux prochains paragraphes.

La bibliothèque `Str`

Ce module contient un type abstrait regexp représentant les expressions rationnelles ainsi qu'une fonction regexp qui prend une chaîne de caractères décrivant une expression rationnelle, plus ou moins selon la syntaxe décrite ci-dessus, et qui la transforme en sa représentation abstraite.

Ce module contient également un certain nombre de fonctions exploitant les expressions rationnelles et manipulant des chaînes de caractères. La syntaxe des expressions rationnelles pour la bibliothèque Str est donnée figure 11.1.

. n'importe quel caractère sauf \n

* zéro ou plusieurs occurrences de l'expression précédente

+ au moins une occurrence de l'expression précédente

? zéro ou une occurrence de l'expression précédente

[..] ensemble de caractères

l'intervalle est noté - (exemple [0-9])

le complémentaire est noté ^ (exemple [^A-Z])

^ début de ligne

à ne pas confondre avec l'utilisation de ^ comme complémentaire d'un ensemble

$ fin de ligne

| alternative

(..) regroupement en une expression composée

on pourra alors nommer cette expression composée

i avec i constante entière, texte filtré par la i-ième expression composée

\ caractère d'échappement

on l'utilise lorsque l'on veut filtrer l'un des caractères réservés des expressions rationnelles.

Figure 11.1 : Expressions rationnelles

Exemple

Nous voulons écrire une fonction traduisant des dates au format anglo-saxon en des dates françaises dans un fichier de données. On suppose que le fichier est organisé en lignes de champs et que les composants d'une date anglo-saxonne sont séparés par un point. Nous définissons une fonction qui prend en argument une chaîne (i.e. une ligne du fichier), qui isole la date, la décompose, la traduit et la remplace par cette traduction.


# let french_date_of d =
  match d with
   [mm; jj; yy] -> jj^"/"^mm^"/"^yy
  | _ -> failwith "Bad date format" ;;
val french_date_of : string list -> string = <fun>

# let english_date_format = Str.regexp "[0-9]+\.[0-9]+\.[0-9]+" ;;
val english_date_format : Str.regexp = <abstr>

# let trans_date l = 
  try
   let i=Str.search_forward english_date_format l 0 in
   let d1 = Str.matched_string l in
   let d2 = french_date_of (Str.split (Str.regexp "\.") d1) in
     Str.global_replace english_date_format d2 l
  with Not_found -> l ;;
val trans_date : string -> string = <fun>

# trans_date "..............06.13.99............" ;;
- : string = "..............13/06/99............"

L'outil `ocamllex`

L'outil ocamllex est un générateur d'analyseur lexical construit pour Objective CAML sur le modèle de l'outil lex dédié au langage C. Il produit un fichier source Objective CAML à partir d'un fichier contenant la description des éléments du lexique à reconnaître sous forme d'ensembles d'expressions rationnelles. À la description de chacun des éléments lexicaux, le programmeur peut attacher une action de traitement dite action sémantique. Le code engendré manipule un type abstrait lexbuf défini dans le module Lexing. Ce module contient quelques fonctions de manipulation des buffers lexicaux que le programmeur peut utiliser pour définir ses traitements.

L'usage est de donner aux fichiers de description lexicale l'extension .mll. Pour obtenir un source Objective CAML à partir d'un fichier lex_file.mll on tape la commande

ocamllex lex_file.mll

On obtient un fichier lex_file.ml contenant le code de l'analyseur correspondant. Ce fichier peut alors être intégré dans une application Objective CAML. À chaque ensemble de règles d'analyse lexicale correspond une fonction prenant en entrée un buffer lexical (type Lexing.lexbuf) et retournant la valeur définie par les actions sémantiques. Par conséquent, toutes les actions d'une même règle doivent produire une valeur du même type.

Le format général d'un fichier pour ocamllex est

`{`
	en-tête
`}`

let ident `=` regexp
	...
rule ruleset1 `=` parse
		regexp `{` action `}`
		`\|` ...
		`\|` regexp `{` action `}`
and ruleset2 `=` `parse`
		...
and ...
`{`

	suite-et-fin
`}`

Les deux sections << en-tête >> et << suite-et-fin >> sont facultatives. Elles contiennent du code Objective CAML définissant types, fonctions, etc. nécessaires au traitement. La dernière section peut définir des fonctions utilisant les règles d'analyse d'ensemble lexicaux données dans la section médiane. La série de déclarations précédant la définition des règles permet de nommer certaines expressions rationnelles. On utilisera alors leur nom dans la définition des règles.

Exemple

Reprenons notre exemple du BASIC. Nous allons pouvoir y affiner le type des unités lexicales retournées. De surcroît, nous pourrons retrouver la fonction lexer définie page ?? avec le même type de sortie (lexeme), mais qui prendra en entrée un buffer de type Lexing.lexbuf.


{
 let string_chars s =
  String.sub s 1 ((String.length s)-2) ;;
}

let op_ar = ['-' '+' '*' '%' '/']
let op_bool = ['!' '&' '|'] 
let rel = ['=' '<' '>']

rule lexer = parse
   [' ']   { lexer lexbuf }

 | op_ar   { Lsymbol (Lexing.lexeme lexbuf) }
 | op_bool { Lsymbol (Lexing.lexeme lexbuf) }

 | "<="    { Lsymbol (Lexing.lexeme lexbuf) }
 | ">="    { Lsymbol (Lexing.lexeme lexbuf) }
 | "<>"    { Lsymbol (Lexing.lexeme lexbuf) }
 | rel     { Lsymbol (Lexing.lexeme lexbuf) }

 | "REM"   { Lsymbol (Lexing.lexeme lexbuf) }
 | "LET"   { Lsymbol (Lexing.lexeme lexbuf) }
 | "PRINT" { Lsymbol (Lexing.lexeme lexbuf) }
 | "INPUT" { Lsymbol (Lexing.lexeme lexbuf) }
 | "IF"    { Lsymbol (Lexing.lexeme lexbuf) }
 | "THEN"  { Lsymbol (Lexing.lexeme lexbuf) }
 
 | '-'? ['0'-'9']+   { Lint (int_of_string (Lexing.lexeme lexbuf)) }
 | ['A'-'z']+        { Lident (Lexing.lexeme lexbuf) }
 | '"' [^ '"']* '"'  { Lstring (string_chars (Lexing.lexeme lexbuf)) }

La traduction de ce fichier par ocamllex fournit la fonction lexer de type Lexing.lexbuf -> lexeme. Nous verrons plus loin comment une telle fonction s'utilise en corrélation avec l'analyse syntaxique (voir page ??).

`.`	n'importe quel caractère sauf `\n`
`*`	zéro ou plusieurs occurrences de l'expression précédente
`+`	au moins une occurrence de l'expression précédente
`?`	zéro ou une occurrence de l'expression précédente
`[`..`]`	ensemble de caractères
	l'intervalle est noté `-` (exemple `[0-9]`)
	le complémentaire est noté `^` (exemple `[^A-Z]`)
`^`	début de ligne
	à ne pas confondre avec l'utilisation de `^` comme complémentaire d'un ensemble
`$`	fin de ligne
`\|`	alternative
`(`..`)`	regroupement en une expression composée
	on pourra alors nommer cette expression composée
i	avec i constante entière, texte filtré par la i-ième expression composée
`\`	caractère d'échappement
	on l'utilise lorsque l'on veut filtrer l'un des caractères réservés des expressions rationnelles.

Lexique

Le module Genlex

Utilisation des flots

Expressions rationnelles

Définition

Exemple

Reconnaissance

La bibliothèque Str

Exemple

L'outil ocamllex

Exemple

Le module `Genlex`

La bibliothèque `Str`

L'outil `ocamllex`