Programmer avec des expressions régulières - [Site WWW de Laurent Bloch]

Corrigé de l’examen d’algorithmique de la biologie

Programmer avec des expressions régulières

Article mis en ligne le 19 février 2015

dernière modification le 1er mars 2015

par Laurent Bloch

Sommaire

Traitement des expressions régulières
Question 1
Question 2
Pour être vraiment juste
Petit rappel de syntaxe des expressions régulières

Traitement des expressions régulières

On s’intéresse à l’écriture des nombres conformes à la syntaxe du calculateur standard des systèmes Unix, bc, et on veut créer des expressions régulières qui vérifient la syntaxe de tels nombres (on trouvera à la fin de cet article un petit rappel de la syntaxe des expressions régulières). 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 :

(module number-parser
   (main get-number))
;;
(define (get-number args)
   (let* ((number (cadr args))
          (regexp
             "^(\\+|-)?([0-9]*)(\\.([0-9]*))?(\\^((\\+|-)?[0-9]+))?$")
          (number-elems (pregexp-match regexp number)))
      (print number-elems)))

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

./number-parser 123.8^-4
(123.8^-4 #f 123 .8 8 ^-4 -4 -)

– 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 ; il faut une double barre oblique inverse devant le signe +, parce que nous voulons bien dénoter le signe + lui-même, et non pas l’opérateur + de la syntaxe des expressions régulières ;
– 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

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 :

(module number-parser-2
   (main get-number-string))
;;
(define (get-number-string args)
   (let ((number-string (cadr args)))
      (print (parse2number number-string)) ))
;; On isole la procédure d'analyse proprement dite :
(define (parse2number number-string)
   (let* ((regexp
             "^(\\+|-)?([0-9]*)(\\.([0-9]*))?(\\^((\\+|-)?[0-9]+))?$")
          (number-elems (pregexp-match regexp number-string))
;; On localise les éléments qui seront utiles à la
;; construction du nombre et on leur donne des noms :
          (sign-num (cadr number-elems))
          (int-part (caddr number-elems))
          (point-part (cadddr number-elems))
          (exponent (caddr (cddddr number-elems)))
;; si un élément donne #f on le remplace par la chaîne vide
          (mantissa (string-append
                       (or sign-num "")
                       int-part
                       (or point-part ""))))
      (if exponent
          (list 'expt mantissa exponent)
          mantissa)))

Question 2

Nous souhaitons maintenant que notre programme accepte sur la ligne de commande un opérateur arithmétique tel que +, /, ou encore expt, deux opérandes, et calcule le résultat de l’opération.

On rappelle que la procédure string->number permet de convertir une chaîne de caractères en nombre, que string->symbol permet de convertir une chaîne de caractères en symbole, et que si ce symbole est le nom d’une procédure, (eval <symbol>) en réalise une double évaluation, ce qui permet d’utiliser <symbol> pour invoquer la procédure dont il est le nom.

(module number-parser-3
   (main get-number-string))
;; Comme le programme précédent, mais un opérateur et deux
;; nombres sur la ligne de commande. Si l'opérateur est aussi 
;; un opérateur du shell comme la multiplication, le mettre entre
;; quotes : '*'
(define (get-number-string args)
   (let ((op (eval (string->symbol (cadr args))))
         (n1 (parse2number (caddr args)))
         (n2 (parse2number (cadddr args))))
      (print (op n1 n2)) ))
;;
(define (parse2number number-string)
   (let* ((regexp
             "^(\\+|-)?([0-9]*)(\\.([0-9]*))?(\\^((\\+|-)?[0-9]+))?$")
          (number-elems (pregexp-match regexp number-string))
;; on décompose chaque nombre en éléments simples
          (sign-num (cadr number-elems))
          (int-part (caddr number-elems))
          (point-part (cadddr number-elems))
          (exponent (caddr (cddddr number-elems)))
;; si un élément donne #f on le remplace par la chaîne vide
          (mantissa (string-append
                       (or sign-num "")
                       int-part
                       (or point-part ""))))
      (if exponent
          (expt (string->number mantissa)
                (string->number exponent))
          (string->number mantissa))))

Pour être vraiment juste

Pour avoir un nombre variable d’opérandes, il suffit de mettre Scheme un peu plus
à contribution (une occasion de réviser map et apply, expliqués par exemple ici), en modifiant la procédure get-number-string ainsi :

(define (get-number-string args)
   (let ((op (string->symbol (cadr args)))
	 (Largs (map parse2number (cddr args))))
      (print (apply (eval op) Largs)) ))

Mon collègue Emmanuel Lazard me fait remarquer que mon expression régulière « attrape » des formes qui, bien que certaines soient acceptées par bc, ne sont pas vraiment des nombres, telles que ^6, .^6 ou -^8. L’expression vraiment juste est :

^(\\+|-)?((([0-9]+)(\\.([0-9]*))?)|\\.[0-9]+)(\\^((\\+|-)?[0-9]+))?$

Petit rappel de syntaxe des expressions régulières

– z? signifie que z doit exister en zéro ou un
exemplaire à cet endroit du texte examiné ; (xyz)? signifie que
xyz doit exister en zéro ou un exemplaire à cet endroit du texte
examiné (cette règle des parenthèses s’applique de la même façon aux
cas ci-dessous) ;
– z* signifie que z doit exister en un nombre
quelconque d’exemplaires à cet endroit du texte examiné,
éventuellement zéro ;
– z+ signifie que z doit exister en au moins un
exemplaire à cet endroit du texte examiné ;
– z|w signifie qu’à cet endroit du texte examiné il doit y avoir
z ou bien w ;
– l’accent circonflexe ^, lorsqu’il apparaît en
début d’expression régulière, dénote le début de ligne (ou de
chaîne de caractères), $, lorsqu’il apparaît en fin
d’expression régulière, la fin de ligne (ou de chaîne de
caractères) ;
– le point . dénote n’importe quel caractère ; l’expression régulière qui dénote le point est \.
– certains caractères, tels ? * + . ^ $ |, ont une signification particulière dans la syntaxe des expressions régulières ; lorsque l’on veut dénoter le caractère lui-même, en tant que tel, et non pas sa signification syntaxique, on le précède d’une barre oblique inverse, \ (backslash), ainsi \. signifie « ici je veux un point » ; si on veut une barre oblique inverse, on écrit \\ ; mais certains langages, tels Scheme ou Java, représentent les expressions régulières par des chaînes de caractères, où la barre oblique inverse possède aussi une signification syntaxique particulière, ce qui oblige à mettre deux barres obliques inverses là où il en faudrait une, et quatre là où il en faudrait deux (cf. les exemples ci-dessus).

Dans la même rubrique

Votre inscription a été enregistrée avec succès !