Algorithmes fonctionnels en javascript sous la forme de cours et d'exercices. Utilisation de js dans un contexte de liste, de map, list_it. Inspiré de caml. A lire à l'envers...

samedi 3 octobre 2009

Les expressions régulières.

Expressions régulières.

Une petite digression sur les expressions régulières, aussi appelées expressions rationnelles ou regex..
Les expressions régulières correspondent à un mini langage bien spécifique qui est le langage des automates. Ici automate  est utilisé au sens mathématique  du terme. Dans un "automate fini déterministe", un mot u est reconnu si il fait passer l'automate d'un état initial à son état final.
Les expressions régulières sont utilisées en programmation pour reconnaître des motifs particuliers. Ainsi  les mots "unix" et "linux" sont reconnus par un automate dont le langage est  "*n.x" . "*n.x" est une expression régulière.

Construction d'expressions régulières:

en ligne: var regex = /test/igm ;
à l'aide d'un constructeur: var regex = new RegExp("test","igm");

En pratique 6 méthodes javascript permettent d'utiliser les expressions régulières

- 2 sont des méthodes de l'objet Regexp exec et test:
var regex = /t(r+)/ig ; // objet RegExp
regex.exec("Do it or not but there is no try"/* optionnel: , ig */);
regex.test("Try it or not");//true or false
- 4 sont des méthodes de l'objet String: match, search, replace, split.
str.match(regex);
str.search(regex);// retourne un entier
str.replace(regex,replacement ); // replacement un entier ou une fonction..
str.split(regex);// renvoi une liste.

En pratique de nombreux sites expliquent la formation d'une expression régulière, c'est un outil très puissant en programmation car il permet de selectionner rapidement et avec précision des éléments donnés dans un texte.

Ce qui est un peu plus intéressant est la notion d'alphabet et d'automate qui est à la base des moteurs d'expressions régulières. Bien sûr, il est probable que les implémentations de javascript utilisent une bibliothèque C d'expressions régulières.

Automate fini déterministe:


Un AFD définit sur un alphabet A de la manière suivante:
{Q, q0 , F, delta}
Q : est l'ensemble fini des états de l'automate.
q0: est l'état initial de l'automate.
F: est l'ensemble des états finals. F est inclus dans Q .
delta : est une fonction de transition de Q*A -> Q, telle que delta(q,c)-> q'
ou encore qui permet de passer d'un état q à un état q' lors de la lecture du caractère c.

Programmation d'un automate fini déterministe en javascript:



//Objet AFD, si on se contente de numéroter les états de l'automate:
var alpha ={ initial, final, transitions }
//où initial est un entier,
//final est la liste des états finaux,
//transitions est une liste de tableaux associatifs

Exemple de lecture d'un mot .

function calcul(alpha, q, mot){
var n= mot.length;
function avancer(q,i){
if(i==n)return q ;
if(typeof alpha.transitions[i])[mot[i]] =="undefined" ) throw "blocage";
avancer( (alpha.transitions[i])[mot[i]] , i+1);
}
}
//exemple automate à 3 états, 0->1->2
// alphabet a,b
var alpha ={
initial: 0,
finals: [2],
[{a:1, b:0},{a:0,b:2},{a:1, :b:2}]
}


Exercice: Tracez le schéma de cet automate et trouvez les mots qu'il reconnait en sachant que sont état final est l'état 2 et l'état initial l'état 0.

Réponse:
/b*a(aa)*b+(ab+)*/