Corrigé de l’examen d’algorithmique de la biologie, juin 2012
Programmation des expressions régulières
Article mis en ligne le 24 juin 2021

par Laurent Bloch

 Traitement des expressions régulières

On s’intéresse à l’écriture des nombres conformes à la syntaxe de la calculette standard des systèmes Unix, bc, et on veut créer des expressions régulières qui vérifient la syntaxe de tels nombres. Par exemple, si j’écris -1.23^-5 cela dénote le nombre -1,23^{-5} (l’accent circonflexe est l’opérateur d’élévation à la puissance, et conformément à l’usage anglo-saxon c’est un point qui sépare la partie entière de la partie décimale du nombre).

Les expressions régulières peuvent être traitées par un programme Scheme, et les textes reconnus peuvent être décomposés en leurs parties élémentaires ; ainsi, pour un nombre écrit selon la syntaxe de bc, il sera possible de séparer l’exposant de la mantisse (le nombre auquel est appliqué l’exposant) pour ensuite les utiliser dans des expressions Scheme ordinaires.

On rappelle qu’en mettant entre parenthèses une sous-expression d’une expression régulière, il est possible de distinguer les parties du texte reconnues par chaque sous-expression régulière. Ces parties de texte sont placées, par la procédure pregexp-match à la ligne 8 du programme ci-dessous, dans une liste, dans l’ordre des parenthèses ouvrantes auxquelles elles correspondent. Le premier élément de la liste (numéro 0) sera le texte entier reconnu par l’expression régulière, le second élément (numéro 1) sera la partie de texte reconnue par la première sous-expression entre parenthèses, et ainsi de suite. Par exemple, soit le programme suivant :

  1. (module number-parser
  2.    (main get-number))
  3.  
  4. (define (get-number args)
  5.    (let* ((number (cadr args))
  6.           (regexp
  7.              "^(+|-)?([0-9]*)?(\\.([0-9]*))?(\\^((+|-)?[0-9]+))?$")
  8.           (number-elems (pregexp-match regexp number)))
  9.       (print number-elems)))

Télécharger

Son invocation avec un nombre tel que décrit ci-dessus donnera :

 Le premier élément de la liste est le nombre en entier : 123.8^-4 ;
 le second élément est #f : en effet le groupe de la première paire de parenthèses (+|-) reconnaît le signe du nombre, qui ne figure pas dans notre cas ;
 le troisème élément, 123, est la partie entière, reconnue par ([0-9]*) ;
 le quatrième élément reconnu par (\\.([0-9]*)) (attention aux doubles barres obliques inversées !) est la partie décimale, précédée du point, .8 ;
 le cinquième élément reconnu par ([0-9]*) est la partie décimale ;
 le sixième élément est l’exposant précédé de l’opérateur d’élévation à la puissance, soit ^-4, reconnu par (\\^((+|-)?[0-9]+)) ;
 le septième élément, reconnu par ((+|-)?[0-9]+), est l’exposant muni de son signe ;
 le dernier élément est le signe de l’exposant.

 Question 1

On rappelle que la procédure string->number permet de convertir une chaîne de caractères en nombre.

Modifiez le programme ci-dessus pour afficher, non plus la liste des sous-chaînes reconnues par des sous-expressions, mais le texte d’une expression Scheme qui dénote le nombre.

Réponse :

  1. (module number-parser
  2.    (main get-number-string))
  3.  
  4. (define (get-number-string args)
  5.    (let ((number-string (cadr args)))
  6.       (print (parse2number number-string))
  7. ))
  8.  
  9. ;; On isole la procédure d'analyse proprement dite :
  10.  
  11. (define (parse2number number-string)
  12.    (let* (
  13.           (regexp
  14.              "^(+|-)?([0-9]*)?(\\.([0-9]*))?(\\^((+|-)?[0-9]+))?$")
  15.           (number-elems (pregexp-match regexp number-string))
  16.  
  17. ;; On localise les éléments qui seront utiles à la
  18. ;; construction du nombre et on leur donne des noms :
  19.  
  20.           (sign-num (cadr number-elems))
  21.           (int-part (caddr number-elems))
  22.           (point-part (cadddr number-elems))
  23.           (exponent (caddr (cddddr number-elems)))
  24.  
  25. ;; Construction du nombre :
  26.  
  27.           (number-list (append
  28.                          (if exponent (list 'expt) '())
  29.                          (list (string-append
  30.                                   (if sign-num sign-num "")
  31.                                   int-part
  32.                                   (if point-part point-part "")))
  33.                          (if exponent (list exponent) '())))
  34.           (the-number (if exponent number-list (car number-list))))
  35.    the-number))

Télécharger