Analyse Lexicale

rappels sur les langages rationnels
exemple OcamlLex
extensions pour analyseurs lexicaux:
- rappel du dernier l'état final
- longest match, first defined
Utilisation de OcamlLex
Exemples

Rappels sur les langages rationnels

expressions rationnelles (regular expressions): : epsilon, +, *, .
automates finis non deterministes: : (Q,I,T,F)
automates finis deterministes: :
(Q,I,T,F) avec F fonctionnelle et I singleton
determinisation: : construction de l'ensemble puissance
minimalisation: : construction de Moore
propriétés: : lemme de l'étoile, complémentation, intersection, union

Exemple OcamlLex Voici un exemple de fichier de définition OcamlLex:

{
exception Eof;;
let count = ref 0;;
}
let alphanum = [^ ' ' '\t' '\n']
let mot = alphanum alphanum*

rule token = parse
         mot   {count := !count + 1;}
       | _     {}
       | eof   {raise Eof}
{
let _ = try let lexbuf = Lexing.from_channel stdin in
            while true do token lexbuf; done
        with Eof -> print_int !count; print_newline(); exit 0
}

Extensions pour analyseurs lexicaux

Un analyseur lexical doit séparer un flot de caractères en une série de tokens'' (unités lexicales), chacune définie par une expression régulière. Cela est légèrement différent du problème de la reconnaissance d'un langage rationnel: <UL><LI> on recherche le plus long prefixe de l'entrée qui corresponde à une des définitions d'unités lexicales, on n'échoue pas s'il reste qque chose après, et on doit pouvoir returner à la fois ce prefixe et identifier quelle définition a été trouvée, donc... <LI> on augmente l'automate fini avec une information supplémentaire sur les états finaux (la règle qui corresponde à l'état, et en cas de ambiguité, on choisit la prémière en ordre de définition). <LI> on mantient deux variables supplémentaires: <TT>dernierEtatFinal</TT> et <TT>positionEntreeAuDernierEtatFinal</TT>, qu'il faut mantenir à jour. <LI> on retourne <TT>dernierEtatFinal</TT> quand l'automate se trouve bloqué. </UL> Utilisation de OcamlLex Un fichier source pour OcamlLex a extension <TT>.mll</TT> et a cette structure: <PRE>{ prologue } let ident = regexp ... rule etatinitial = parse regexp { action } | ... | regexp { action } and etatinitial = parse ... and ... { epilogue }</PRE> Les commentaires sont délimités par <code>(*</code> et <code>*)</code> comme en OCaml. Prologue et epilogue sont des sections optionnelles qui contiennent du code Ocaml arbitraire (typiquement, prologue définit des fonctions nécéssaires dans les actions, alors que épilogue est plus souvent utilis', comme dans l'exemple précédent, pour réaliser un programmestand-alone'').

Utilisation de OcamlLex: expressions rationnelles

' char '	le caractère dénoté par char .
_	un caractère quelconque.
eof	la fin du flot de caractères.
" string "	une chaîne de caractères.
[ ens-char ]	filtre tout caractère dans l'ensemble ens-char, qui peut être
	une constante 'c', un intervalle 'c1' - 'c2'
	ou l'union de deux ensembles (ex: 'a' - 'z' 'A' - 'Z')
[ ^ ens-char ]	tout caractère qui n'est pas dans ens-char
exp *	étoile de Kleene
exp +	1 ou plus occurrences de exp
exp ?	1 ou 0 occurrences de exp
exp1 \| exp2	une occurrence de exp1 ou une de exp2
exp1 exp2	une occurrence de exp1, puis une de exp2
( exp )	la même chose que exp
ident	l'expression abregée de nom ident (voir plus bas)

Précédences: * et + precèdent ?, qui precède la concatenation, et enfin |

Utilisation de OcamlLex: abbréviations

Il est possible de donner un nom à des expressions rationnelle qui apparaissent souvent, en écrivant:

let ident = regexp

entre le prologue et les régles.

Bien entendu, ces definitions ne peuvent être récursives.

Utilisation de OcamlLex: états initiaux

Dans rule token = parse, token est un identificateur Ocaml valide (qui commence par une minuscule), et définit un état initial de l'automate, que l'on peut invoquer sur un flot de caractères. Par exemple:

let lexbuf = Lexing.from_channel stdin in
token lexbuf;

Construit un flot à partir de l'entrée standard et appelle l'automate sur le flot avec l'état initial token''. La possibilité d'avoir plusieurs états initiaux est fort pratique pourchanger de mode'', ce qui permet de traiter par exemple de façon simple les commentaires imbriqués.

Commentaires Imbriqués

{ exception Eof;;
   let level = ref 0;; }
let ouvrecomm = "/*"
let fermecomm = "*/"

rule token = parse
            ouvrecomm {level:=1; comment lexbuf;}
       | _ {print_string(Lexing.lexeme lexbuf);}
       | eof {raise Eof}
and comment = parse
          fermecomm {level := !level -1; 
                     if !level=0 then token lexbuf else comment lexbuf; }
        | ouvrecomm {level := !level + 1; comment lexbuf;}
        | _ {comment lexbuf; (* glob comments *)}
        | eof   { raise Eof;}

{let _ = try let lexbuf = Lexing.from_channel stdin in
           while true do token lexbuf; done
         with Eof -> exit 0 }

Compilation

écrire un fichier lexer.mll avec les définitions OcamlLex
appeler OcamlLex: ocamllex lexer.mll
cela produit le fichier lexer.ml
compiler lexer.ml:
- s'il est un programme standalone: ocamlc -o lexer lexer.ml
  et ensuite on peut l'exécuter en tapant ./lexer
- s'il est un module: ocamlc -c lexer.ml

Exemples

Regardez ici

About this document ...

The command line arguments were:
latex2html -ascii_mode -split 0 Slides01.tex.

The translation was initiated by Roberto Di Cosmo on Mon Oct 25 16:27:25 MET 1999

Roberto Di Cosmo
Mon Oct 25 16:27:25 MET 1999