Langages
Analyse lexicale
Expressions régulières
Automates.
Postscript, PDF Didier Rémy Polytechnique, INRIA
En amont de la chaîne de compilation
Analyse en deux passes:
  1. Analyse lexicale: transforme une suite de caractères en une suite de lexèmes (mots).

  2. Analyse grammaticale: transforme une suite de lexèmes en une représentation arborescente (syntaxe abstraite).
Enjeux

Les analyses lexicales et grammaticales ont un domaine d'application bien plus large que celui de la compilation. On les retrouve comme première passe dans de nombreuses applications (analyses des commandes, des requêtes, etc,).

Ces deux analyses utilisent de façon essentielle les automates, mais on retrouve aussi les automates dans de nombreux domaines de l'informatique.

Les expressions régulières sont un langage de description d'automates; elles sont utilisées dans de nombreux outils Unix, et fournies en bibliothèque dans la plupart des langages de programmation.

Note

L'étude détaillée des automates et des grammaires formelles pourrait constituer un cours à part entière.

Nous nous contentons ici de la présentation formelle minimale, avec comme but:
    ·d'expliquer le fonctionnement des analyseurs de façon à pouvoir écrire soi-même des analyseurs lexicaux ou grammaticaux.
    ·de se familiariser aussi avec les expressions régulières et les automates, car on les retrouve ensuite fréquemment en informatique.
Le but du cours n'est pas d'écrire le moteur d'un analyseur, ni de répertorier toutes les techniques d'analyses.

Les langages formels

On se donne un ensemble S appelé alphabet, dont les éléments sont appelés caractères.

Un mot (sur S) est une séquence de caractères (de S).

On note e le mot vide, uv la concaténation des mots u et v (la concaténation est associative avec e pour élément neutre).

S * est l'ensemble des mots sur S

S + est l'ensemble des mots non vides.

Un langage sur S est un sous-ensemble L de S *.

Si U et V sont des langages sur S, on note U V l'ensemble des mots obtenus par la concaténation d'un mot de U et d'un mot de V; U * (resp. U +), l'ensemble des mots obtenus par la concaténation d'un nombre arbitraire, éventuellement nul (resp. non nul) de mots de U.

Exemples

  1. S1 est l'alphabet français et L1 l'ensemble des mots du dictionnaire français avec toutes leurs déclinaisons.

  2. S2 est L1 et L2 est l'ensemble des phrases grammaticalement correctes de la langue française.

    Ou bien L2' le sous-ensemble des palindromes de L2.

  3. S3 est l'ensemble des caractères ASCII, et L3 est composé de tous les mots clés de pseudo pascal, de l'ensemble des symboles, de l'ensemble des identificateurs et de l'ensemble des entiers.

  4. S4 est L3 et L4 est l'ensemble des programmes pseudo pascal.

  5. S est {a, b} et L est l'ensemble { a n b n | n Î IN} (sous ensemble des expressions bien parenthésées).
Expressions régulières

Les expressions régulières sont des opérateurs permettant de décrire certains langages (les langages réguliers) définis sur un même alphabet S.

On note a, b, etc. des lettres de S, M et N des expressions régulières, [[M]] le langage associé à M.
    ·Une lettre de l'alphabet a désigne le langage {a}.
    ·Epsilon: e désigne le langage {e}.
    ·Concaténation: M · N désigne le langage [[M]] [[N]].
    ·Alternative: M | N désigne le langage [[M]] È [[N]].
    ·Répétition: M* désigne le langage [[M]] *.
On ajoute également du sucre syntaxique (ie. sans changer l'expressivité):
    ·[abc] pour (a | b | c) et [a1-a2] pour {c Î S, a1 £ c Ù c £ a2}, (on suppose ici que l'alphabet est ordonné)
    ·M? pour M | e et M+ pour M M*.


Analyse lexicale

On veut couper une phrase (suite de caractères) en lexèmes.

On décrit les lexèmes par des expressions régulières. Exemple:
  1. Les mots clés: "let", "in"
  2. Les variables: ['a'-'z']+ ['0'-'9']*
  3. Les entiers: ['0'-'9']+
  4. Les symboles: '(', ')', '+', '*', '='
  5. Le lexème vide: (' ' | '\n')
On peut représenter les lexèmes par un type concret:
type token = 
    LET | IN | ..               (* mots clés *)
  | VAR of string               (* variables *)
  | INT of int                  (* entiers *)
  | LPAREN | RPAREN | PLUS | TIMES | EQUAL (* symboles *)

Analyse lexicale (suite)


Principe C'est un algorithme qui
    ·prend une suite de caractère
    ·la transforme en une suite de lexème, et retourne les caractères non reconnus.


Problème Il y a des ambiguités. Par exemple:
    ·let pourrait être reconnu comme une variable.
    ·lettre pourrait aussi être reconnu comme la séquence LET; VAR "tre" ou encore VAR "let"; VAR "tre"


Règles de priorité

On choisit par priorité:
  1. Le lexème le plus long,
  2. L'ordre de définition.
Ainsi la phrase let lettre = 3 in 1 + fin produit la suite de lexèmes:
LET; VAR "lettre"; EQUAL; IN; INT 1; PLUS; VAR "fin"

ocamllex

On écrit un fichier lexeur.mll qui est compilé en un fichier source lexeur.ml par le programme ocamllex.
    { (* prelude : code Ocaml reproduit verbatim *) }
    rule entree_1 = parse
      regexp_1  { (* code ocaml qui retourne un lexème *) }
    | regexp_2  { (* code ocaml qui retourne un lexème *) }
    | ...
    and entree_2
    ...
    { (* postlude : code Ocaml reproduit verbatim *) }

Pour construire les lexèmes, on récupére la chaîne reconnue par Lexing.lexeme lexbuf. Attention: le nom de la variable lexbuf est fixé par convention.
Exemple

Fichier essai.mll
{ open Lexing
  type token = IDENT of string | INT of int | LET | IN
      | PLUS | TIMES | EQUAL | LPAREN | RPAREN
  exception Eof  exception Illégal }
rule token = parse
   [' ' '\t' '\n']          { token lexbuf }  (* skip *)
|  "let"                    { LET }  
|  "in"                     { IN }
|  ['a'-'z'] + ['0'-'9'] *  { IDENT (lexeme lexbuf)}
|  ['0'-'9']+               { INT(int_of_string 
                                        (lexeme lexbuf)) }
|  '=' { EQUAL } | '+' { PLUS }  | '*' { TIMES }
|  eof { raise Eof }  | _ { raise Illégal }

Exemple (suite)

Fichier essai.mll
{ let lex buf = 
    let rec lex() =
      try let h = token buf in h :: lex() with Eof -> [] in
    lex()
  let lex_string s = lex (Lexing.from_string s)
  let lex_chan c = lex (Lexing.from_channel c) }

Compilation en deux étapes:
  1. Fabrication du fichier essai.ml
        ocamllex essai.mll
  2. Compilation normale du fichier essai.ml
        ocamlc -c essai.ml
Remarques

Utilisation de la récursion token lexbuf pour une production vide.

L'utilisation de plusieurs règles revient à combiner plusieurs lexeurs indépendants mais qui travaillent sur la même entrée. Application à l'analyse des chaînes de caractères (inefficace):
rule token = parse
    [' ' '\t' '\n']  { token lexbuf }  
 |  '"'        { STRING(String.concat "" (string lexbuf)) }
 |  ['0'-'9']+  { INT(int_of_string (lexeme lexbuf)) }
 |  eof         { raise EOF }
and string = parse
 |  '"'         { [] }
 |  '\\' '"'    { "\"" :: string lexbuf }
 |  eof         { raise Unterminated_string }
 |  _           { let c = lexeme_char lexbuf 0 in
                  String.make 1 c :: string lexbuf }

Récupération des erreurs

En cas d'erreur, il est nécessaire d'indiquer un minimum d'informations, telles que la position de l'erreur, et/ou la dernière séquence non reconnue:
    ·La position du dernier lexème dans le flux d'entrée est déterminée par Lexing.lexeme_start lexbuf et Lexing.lexeme_end lexbuf.
    ·La sous-chaîne correspondante est (Lexing.lexeme lexbuf).


Comment fonctionnne Ocamllex?

Un exemple de compilation:
  1. Chaque expression régulière est compilée en un automate,
  2. L'ensemble des automates sont fusionnés en un seul,
  3. L'automate résultant est determinisé.
  4. L'automate est minimisé.
Automates finis déterministes

Un automate fini déterministe M est un quintuple (Q, S, d, q0, F) où
    ·S est un alphabet;
    ·Q est un ensemble fini d'états;
    ·d : Q × S ® Q est la fonction (partielle) de transition;
    ·q0 est l'état initial;
    ·F est un ensemble d'états finaux.
On peut étendre d sur Q × S *® Q par
ì
í
î
d (q, e) = q
d (q, aw) = d (d (q, a), w)

Le langage L(M) reconnu par l'automate M est l'ensemble { w | d (q0, w) Î F} des mots permettant d'atteindre un état final à partir de l'état initial.

Exemple

Automate déterministe:
    ·S = {a,b}
    ·Q = {q0, q1, q2, q3, F}
    ·d = {(q0, a) |® q1, (q0, b) |® q2, (q1, a) |® q3, (q2, b) |® q3, (q3, b) |® F}
    ·État initial q0 et un seul état final F.
Quel est le langage reconnu? L = {aab, bbb}

Automates finis non-déterministes

Il existe plusieurs transitions avec la même étiquette, mais vers des états différents. On autorise aussi des e-transitions.

Formellement, comme ci-dessus, excepté d : Q × (S È {e}) ® 2Q.

On étend d sur Q × S *® Q par
ì
ï
í
ï
î
q Î d (q, e)      (en plus)
d (q, aw) =
 
È
q' Î d (q, a)
Î d (q', w)

Le langage L(M) reconnu par un automate non déterministe est {w | d (q0, w) Ç F ¹Ø}

Automate d'une expression régulière

L'alphabet S est fixé.

On associe à une expression régulière M un automate non déterministe (Q, d, s, F) défini récursivement par:

    ·[[a]] = ({s, f}, {s |®a f}, s, {f})
    ·[[e]]= ({s, f}, {s |®ef}, s, {f})
    ·[[M | M']] = (Q È Q' È {s''}, d È d' È { s'' |®es, s'' |®es' }, s'', F È F')
    ·[[M · M']] = (Q È Q', d È d' È {f |®es', f Î F}, s, F')
    ·[[M*]] = (Q, d È {f |®es, f Î F}, s, {s})


Exemple

Automate non-déterministe associé à l'expression régulière (a b)*.

Déterminisation de l'automate (egale à l'e-fermeture, ici):

Déterminisation d'un automate

Pour tout automate non déterministe M = (Q, S, d, q0, F), il existe un automate déterministe M' qui reconnaît le même langage.

Une solution est M' = (2Q, S, d', {q0}, {F}) où
d' (q', a) = fermeture  (
 
È
q Î q'
d (q, a))
où fermeture (q') est le plus petit ensemble contenant q' fermé par e-transition:
q Î fermeture (q') Þ d (q, e) Ì fermeture (q')
Se calcule par point fixe!

L'automate déterministe associé à Q a 2|Q| états, mais en général, seulement les états atteignables depuis {q0} nous intéressent. Heureusement, en pratique1, cet ensemble est relativement petit, souvent de l'ordre de |Q|.

Minimisation de l'automate

Tout automate admet un automate équivalent (qui reconnaît le même langage) avec un nombre d'états minimum.

Principe On peut le calculer à partir d'un automate déterministe par superposition d'états. Deux états sont équivalents si les suffixes de L reconnus par l'automate à partir de ces états sont égaux.

En particulier,
" q Î Q, " w Î S *, ì
í
î
q Î F Ù q' Ï F Þ q ¬ Rq'
d (q, w) ¬ Rd (q', w) Þ q ¬ Rq'

L'automate minimal est obtenu en prenant l'équivalence la plus large. C'est le plus grossier raffinement de la partition initiale P0 =def {F, Q \ F} qui soit stable par image inverse A |® d -1(A, a) pour tout AÎ P et aÎ S.

Calcul par une variation sur divide and conquer

Quelques indications

Étant donné un langage L sur S, on définit la relation d'équivalence R dans S * par x R y ssi " z Î S *, x z Î L Û y zÎ L. Cette relation est fermée par suffixe, ie. si x R y alors " z Î S *, x z R y z.

On montre que les trois propriétés suivantes sont équivalentes (par exemple, dans l'ordre (1) Þ (2)Þ (3)Þ (1)).
  1. Le langage L défini sur S est reconnaissable par un automate déterministe.
  2. L est une partition finie d'une relation d'équivalence fermée par suffixe.
  3. La partition de la relation R ci-dessus est finie.
Pour montrer (3) Þ (1) on considère l'automate dont les états sont les classes d'équivalence pour R, la fonction de transition est définie par d ( x,a) = xa, l'état initial est le mot vide et les états finaux sont { x, xÎ L}.

Cet automate est minimal, car la relation R ne peut pas avoir plus de classes qu'un automate reconnaissant L.

Exemple de minimisation

ß

Déterminisation + minimisation


Calcul de l'automate minimal

  1. On considère un raffinement P de la partition P0. Un élément A de P est dit stabilisé si P est stable par les images inverses d -1(A, a) pour tout a.

  2. On choisit un élément A non stabilisé de P.

  3. Pour chaque a Î S, on raffine la partition P afin qu'elle soit stable par les d -1 (A, a).

    Pour cela, il faut diviser chaque composante B Î P en B1 = B Ç d -1 (A, a) et B2 = B \ d -1 (A, a).

  4. Si B est non stabilisé, alors il faut stabiliser B1 et B2. Sinon, il suffit de stabiliser B1 pour que B2 le soit, ou inversement. On choisit de stabiliser la composante de plus petit cardinal.
Avec de (très) bonnes structures de donnée, la complexité est en m log (n) où m et n sont les nombres d'arcs et de noeuds de l'automate initial.

Représentation d'un automate

La fonction d de domaine fini Q × S peut être représentée par une matrice de dimension 2 dont les éléments sont les états (pour un automate déterministe) ou ensembles d'états (pour un automate non-déterministe) définissant d.

On peut choisir une représentation pleine (tableau de tableaux) ou creuse (tableau de listes) selon la situation. La première est bien sûr plus efficace en temps mais plus gourmande en espace.

Dans le cas d'une matrice creuse, on peut aussi économiser de l'espace en superposant les tableaux de domaines disjoints (astuce souvent utilisée en pratique qui a l'efficacité en temps de la représentation pleine et souvent l'efficacité en espace de la représentation creuse).

Plutôt que d'interpréter l'automate, on peut le représenter directement par une définition récursive avec filtrage.

Exemple

Automate minimal représentant l'expression régulière (a b)*:

Les états sont des entiers. Les étiquettes sont aussi des entiers 0 et 1 représentant les transitions a et b. Par convention, l'état initial est 0. Dans la table -1 représente une transition interdite.
let sigma = function 
    'a' -> 0 | 'b' -> 1 | _ -> failwith "sigma"
type automat= {final : bool array; delta : int array array}
let automat =
  { final =  [| true; false; |]; 
    delta =  [| (* étiquettes:     a    b   *)
                (* état 0 *)  [|   1;  -1   |];
                (* état 1 *)  [|  -1;   0   |]; |] }
exception Exit;;

Interprétation des tables

let run automat input =
  let i = ref 0 in
  let matched = ref (-1) in
  if automat.final.(0) then matched := 0;
  let q = ref 0 in
  (try while !i < String.length input do
    let a = sigma (input.[!i]) in
    let q' = automat.delta.(!q).(a) in
    if q' < 0 then raise Exit;
    q := q';
    incr i;
    if automat.final.(q') then matched := !i;
  done with Exit -> ());
  !matched;; (* retourne le dernier caractère reconnu *)
run automat "ababaabb";;  (* retourne 4 *)

Automate pour lex

La question n'est plus est-ce la chaîne est reconnaissable en entier par une expression régulière, mais trouver la chaîne la plus longue reconnue et la première règle (dans l'ordre de définition) la reconnaissant.

On veut construire le lexeur défini par les deux règles (ei {ai})i Î I (lire reconnaître l'expression régulière la plus longue parmi les ei et exécuter l'action ai en privilégiant l'ordre.)

Pour cela on enrichit on enrichie à la fois la construction de l'automate et son interprétation.

Fabrication de l'automate pour lex

On construit les automates non déterministes (Qi, S, di, qi, Fi)i Î I.

L'automate initial non déterministe pour lex (Q, S, d, q0, {qF}) est défini par:
Q =def Èi Î I Qi È q0 È {pi, i Î I}
d =def Èi Î I di È {q0 |®eqi | i Î I} È {q |®pi qF | q Î Fi, i Î I}
On déterminise cet automate, puis on retire, sur l'automate déterminisé, les transitions de sortie q |®pi qF lorsqu'il existe une transition q |®pj qF avec i > j.

En pratique, on représente les transitions de sortie à la place des états finaux, et on construit une structure de la forme:
type état = int (* on numérote les règles *)
type rule = int  (* on numérote les états  *)
type automat=  
  { final : rule option array; delta : état array array; };;

Interprétation de l'automate pour lex

On inteprète l'automate se souvenant de la dernière sortie possible

À chaque pas, on regarde s'il existe une transition possible vers la sortie, auquel cas, on indique la règle pi permettant cette transition, ainsi que le nombre de lettres lus depuis le début.

Lorsqu'on échoue (plus de transitions possibles) on retourne exécute l'action de la dernière sortie possible (en lui passant le nombre de caractères lus), sinon on échoue.

En Ocaml

Les états finaux sont les transitions
let run automat input =
  let i = ref 0 in
  let matched = ref None in
  let q = ref 0 in
  (try while !i < String.length input do
    let a = sigma (input.[!i]) in
    let q' = automat.delta.(!q).(a) in
    if q' < 0 then raise Exit;
    q := q';
    incr i;
    begin match automat.final.(q') with 
    | Some r -> matched := Some (r, !i)
    | None -> ()
    end;
  done with Exit -> ());
  match !matched with 
    Some (r, k) -> 
         Some (r, String.sub input 0 k), 
         String.sub input k (String.length input - k) 
  | None -> None, input;;

Langage reconnu par un automate

Le langage reconnu par un automate est rationnel (nombre fini de suffixes, voir aussi le cours suivant), en particulier, un automate ne peut pas reconnaître le langage composé des expressions bien parenthésées.

En effet un automate a un nombre fini d'états. Or la reconnaissance des expressions bien parenthésées demande de se souvenir du nombre de parenthèses déjà reconnues qui peut être arbitraire.

Pour définir un langage de programmation, il nous faut donc des outils plus puissants que les expressions régulières.

Ocamllex

Les actions sont des expressions arbitraires, donc Ocamllex est un langage complet, et la question du langage reconnu par Ocamllex n'as pas de sens si les actions peuvent interagir avec le flux d'entrée.

Toutefois avec une seule règle et sans interaction entre les actifs et le flux d'entrée, on reste à l'intérieur du formalisme précédent.

Reconnaissance des parenthèses On utilise simplement un compteur pour le nombre de parenthèses ouvertes.
{ let c = ref 0 }
rule token = parse
    '('  { incr c; token lexbuf } 
 |  ')'  { if !c > 0 then (decr c;token lexbuf) else false }
 |  eof  { (!c = 0) }
{ let test s = token (Lexing.from_string s) } 
Élimination des commentaires

Une variante toute simple devient un programme intéressant...
{ let depth = ref 0 } 
rule uncomment = parse
  |  "(*<*)"   { incr depth; uncomment lexbuf }
  |  "(*>*)"   { if !depth > 0 then decr depth else exit 1;
                 uncomment lexbuf }
  |  eof       { if !depth > 0 then exit 1 }
  |  _         { if !depth = 0 then
                    print_string (Lexing.lexeme lexbuf);
                 uncomment lexbuf; }
{ let lexbuf = Lexing.from_channel stdin in 
  uncomment lexbuf }

Exercice 1   Parser aussi les chaînes de caractères.

Exercices

Exercice 2   Écrire un lexeur pour le langage Pseudo-Pascal. Les lexèmes sont
    ·Les blancs (blanc, tabulation, retour à la ligne)
    ·Les mots clés: {} var, alloc, false, true, read, write , writeln, array, of, do, begin , end, if, then, else, while, type , function, procedure, integer, boolean, program.
    ·les entiers
    ·les identificateurs (composés de caractères alphabétiques (mininuscule ou majuscules et terminant éventellement par des chiffres.
    ·les lexèmes: ;;   :=   <>   <=   >=   <   >   ;    ~   :   =   -   +   *   /   (   )   [   ].
Réponse
La liste de mots clés, qui peut être assez longue, au risque de conduire à une explostion du nombre d'états de l'automate minimal. Pour éviter cela, on confond les mots clés avec les identificateurs au niveau du lexeur, et on les différencie dans le langage hôte. Écrire une nouvelle version du lexeur, équivalente à la précédente, qui procède ainsi.
Réponse

En travaux dirigé, suivre l'énoncé détaillé de Luc Maranget.


Extraire les URL d'un document HTML

Il s'agit d'écrire un lexeur qui extrait d'un document HTML une liste de chaîne de caractères, représentant l'ensemble des liens vers d'autres documents.

Un document HTML contient un ensemble de balises séparées par du texte. Les balises sont entre les caractères < et >). On pourra considérer que ces caractères n'apparaissent nulle part ailleurs.
  1. En s'inspirant du lexeur qui élimine les commentaires, écrire un lexeur qui ne retient que les balises HTML.

  2. Raffiner le lexeur pour n'imprimer que les URL des balises de type A.

  3. Pour simplifier on pourra d'abord considérer que
        ·Les chaînes ne contiennent pas la clé href.
        ·Les chaînes ne contiennent pas le caractère '"'.
  4. Relacher les contraintes précédentes.

  5. On pourra aussi considérer les liens "src" dans les ancres de type IMG.

Analyse des URL

Une URL est elle-même structurée: elle commmence par le nom d'un protocole (optionnel), l'adresse d'un serveur (optionnel), un chemin absolu ou relatif, et des suffixes (arguments ou étiquettes).

Déstructurer une URL en ses composantes de base.
    ·en utilisant un lexeur,
    ·en utilisant la librairie des str des expressions régulières.


This document was translated from LATEX by HEVEA and HACHA.