7 octobre

Expressions régulières en C

J'ai déjà commis un article sur les expressions régulières en C++.

En C c'est un peu moins maniable.

Introduction

Pour utiliser les expressions régulières en C il faut d'abord inclure l'entête regex.h

#include <regex.h>

Nous utiliserons ici les fonctions regcomp et regexec. Voir le man de regex.

La première regcomp «compile» l'expression régulière, sous une forme nécessaire à la seconde.

Sa signature est :

int regcomp(regex_t *preg, const char *regex, int cflags);

La seconde regexec est celle qui nous permettra de trouver les champs du motif dans la cible.

Sa signature est :

int regexec(const regex_t *preg, const char *string, size_t nmatch,
                   regmatch_t pmatch[], int eflags);

où preg est l'adresse de l'expression régulière «compilée» et string est la cible.

Le nombre de champs trouvés par regexec est placé dans preg->re_nsub.

Les correspondances sont renvoyées dans pmatch.

pmatch[0] est le modèle en entier.

pmatch[k] contient les décalages par rapport au début de la cible du champ n° k.

Ainsi pmatch[k].rm_so est le décalage du début de la correspondance et pmatch[k].rm_eo celui de la fin. La longueur de ce champ est donc pmatch[k].rm_eo - pmatch[k].rm_so.

Les exemples ci-dessous font référence à ceux de l'article Regex en C++.

Exemple 1

Un classique : reconnaître les champs d'une URL.

Exemple : "http://arad.free.fr/regexc.html" est l'url de cet article et nous voudrions y identifier les champs "http", "arad", "free", "fr", "regexc.html".

L'expression régulière que nous utiliserons sera :

char *pattern = "(http|https|ftp|ftps)://(.*)\\.(.*)\\.(.*)/(.*)";

Voici le code d'un programme mettant en œuvre regex

Le source est ici : regex1.c.

/* regex1.c
:w | !gcc % -o .%<
:w | !gcc % -o .%< && ./.%<
*/
#include <stdio.h>
#include <string.h>
#include <regex.h>
#include <assert.h>
//
int main(int argc, char *argv[]) 
{
   char url[] = "http://arad.free.fr/index.html";
   char *pattern = "(http|https|ftp|ftps)://(.*)\\.(.*)\\.(.*)/(.*)";
 
   regex_t reg; 
   int err;
   // compile pattern
   err = regcomp(&reg, pattern, REG_EXTENDED);
   assert(!err);
   size_t nmatch = reg.re_nsub;
   regmatch_t pmatch[nmatch + 1];
   // exec regex
   err = regexec(&reg, url, nmatch + 1, pmatch, 0);
   assert(!err);
   // find domain i.e. free.fr
   char domain[256] = {0};
   size_t start = pmatch[3].rm_so;
   size_t len = pmatch[4].rm_eo - start;
   strncat(domain, url + start, len);
   // replace free.fr by pagesperso-orange.fr
   char rpl[256] = {0};
   strncat(rpl, url, start);
   strcat(rpl, "pagesperso-orange.fr");
   strcat(rpl, url + start + len);
   // prints
   printf("url: %s\n", url);
   printf("domain: %s\n", domain);
   printf("replace domain: %s\n", rpl);
}

Commentaires

J'utilise assert pour sortir du programme en cas d'erreur (lignes 19 et 24).

Ligne 18

Compilation du motif dans reg.

Ligne 23

Exécution de regex. Nous récupérerons les correspondances dans reg.

Lignes 26 à 29

Récupération du domaine "free.fr" dans domain. Il correspond aux champs 3 et 4. Il commence à start = pmatch[3].rm_so et finit à pamtch[4].rm_eo. Sa longueur est dans len.

Lignes 31 à 34

Remplacement du domaine "free.fr" par "pagesperso-orange.fr" : On copie le début de la chaine dans rpl (ligne 32), on y ajoute le nouveau nom de domaine (ligne 33), puis on copie le reste de la chaine (ligne 34).

Lignes 36 à 38

Affichage de l'url de départ, le domaine, et l'url modifiée.

Le code source est en téléchargement ici regex1.c.

Exemple 2

Il s'agit ici de reconnaître le motif de notation d'une note de musique utilisé par lilypond. L'expression régulière que nous utiliserons est :

char pattern[] = "([a-g]es?|is?)([',]{0,3})([0-9]{0,3})([.]?)";

Dans le code qui suit j'ai défini une fonction match qui renvoie une correspondance sous forme de chaine de caractères.

Le source est ici : regex2.c.

/* regex2.c
:w | !gcc % -o .%<
:w | !gcc % -o .%< && ./.%<
*/
#include <stdio.h>
#include <string.h>
#include <regex.h>
#include <assert.h>
  
char * match(char *dest, char *src, regmatch_t *m, int n)
{
   *dest = 0;
   size_t start = m[n].rm_so;
   size_t end = m[n].rm_eo;
   strncat(dest, src + start, end - start);
   return dest;
}
  
int main(int argc, char *argv[]) 
{
   char lily[] = " { aes4 c. }";
   char pattern[] = "([a-g]es?|is?)([',]{0,3})([0-9]{0,3})([.]?)";
   regex_t reg; 
   int err;
   // compile pattern
   err = regcomp(&reg, pattern, REG_EXTENDED);
   assert(!err);
   size_t nmatch = reg.re_nsub;
   regmatch_t m[nmatch + 1];
   // exec regex
   err = regexec(&reg, lily, nmatch + 1, m, 0);
   assert(!err);
   char tmp[24];
   for(int k=0; k<=nmatch; k++) {
      printf("field[%d]: %s\n", k, match(tmp, lily, m, k));
   }
}

Commentaires

Lignes 10 à 17

dest est la chaine de retour,

src est la chaine cible,

m est le tableau que construit regexec,

n est le numéro de champ, 0 pour la chaine correspondant au motif dans la cible.

Remarque : strncat est censée fermer la chaine avec un caractère nul.

Lignes 21 et 22

Données : lily est la chaine lilypond à analyser et pattern[] est le motif.

Ligne 26

Compilation du motif dans reg.

Ligne 28

Nombre de champs trouvés dans le motif

Ligne 29

Tableau de retour des correspondances.

Ligne 31

Recherche du motif pattern dans lily.

Lignes 34 et 35

Affichage des champs du motif.

Le code source est en téléchargement ici regex2.c.

Exemple 3

Dans cet exemple nous allons implémenter une fonction qui recherche dans un texte un modèle fourni par une expression régulière et remplacer toutes ses occurrences par une chaine de substitution fournie par une autre expression régulière. Voici le programme complet.

Lee source est ici : regex_replace.c.

/* regex_replace.c
:w | !gcc % -o .%<
./.%<
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <regex.h>
  
void  // *str MUST can be freed, i.e. obtainde by strdup, malloc, ...
regex_replace(char **str, const char *pattern, const char *replace) {
	regex_t reg;
	// when regex can't commpile pattern, abort
	if(regcomp(&reg, pattern, REG_EXTENDED)) {
		printf("Could not compile regex: %s\n", replace);
		return;
	}
	size_t nmatch = reg.re_nsub; 
	regmatch_t m[nmatch + 1];
	const char *rpl, *p;
	// count back references in replace
	int br = 0;
	p = replace;
	while(1) { 
		while(*++p > 31); 
		if(*p) br++; 
		else break;
	} // if br is not equal to nmatch, leave
	if(br != nmatch) return;
	// look for matches and replace
	char *new;
	while(!regexec(&reg, *str, nmatch + 1, m, REG_NOTBOL)) {
		// make enough room
		new = (char *)malloc(strlen(*str) + strlen(rpl));
		if(!new) exit(EXIT_FAILURE);
		*new = 0;
		p = rpl = replace;
		int c;
		strncat(new, *str, m[0].rm_so); // test before pattern
		for(int k=0; k<nmatch; k++) {
			while(*++p > 16); // skip printable char
			c = *p;  // back referenc (e.g. \1, \2, ...)
			strncat(new, rpl, p - rpl); // add head of rpl
			// concat match
			strncat(new, *str + m[c].rm_so, m[c].rm_eo - m[c].rm_so);
			rpl = p++; // skip back reference, next match
		}
		strcat(new, p ); // trailing of rpl
		strcat(new, *str + m[0].rm_eo); // trainling text in *str
		free(*str);
		*str = strdup(new);
		free(new);
	}
	// ajust size
	*str = (char *)realloc(*str, strlen(*str) + 1);
}
  
int main(int argc, char *argv[]) 
{
	char *pattern = "\\[([^-]+)->([^]]+)\\]";
	char *str = strdup("before [link->address] some text [link2->addr2] trail");
	char rpl[] = "<a href=\"\2\">\1</a>";
	puts(str);
	regex_replace(&str, pattern, rpl);
	puts(str);
	free(str);
}

Nous voudrions lui fournir un texte, par exemple

"préambule lien suite du texte".

L'expression régulière à rechercher est "(.+?)",

et l'expression régulière du remplacement est "<a href="\2">\1</a>".

les caractères \1 et \2 sont les références aux concordances trouvées.

La sortie du programme devrait être :

"préambule <a href="adresse">lien</a> suite du texte".

Il n'y a rien de nouveau sauf l'usage qui est fait du tableau et qu'il ne faut pas perdre le nord pour mettre les choses à leur place.

Le code source est disponible ici : regex_replace.c.

Remarques

Faiblesse de regex ?

POSIX regex du C ne comprend pas les motifs tels que (?:..) en dépit du drapeau REG_EXTENDED.

Une documentation assez complète POSIX Extended Regular Expression Syntax se trouve chez boost. Sinon il y a le info de regex.

Une connerie

Reprenons l'exemple 1.

Voici un programme qui recherche les correspondances avec le motif, et les affiche toutes.

Le source est ici : regex3.c.

/* regex3.c
:w | !gcc % -o .%<
:w | !gcc % -o .%< && ./.%<
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <regex.h>
#include <assert.h>
int main(int argc, char *argv[]) 
{
   char url[] = "ftp://arad.free.fr/regexc.html";
   char *pattern = "(http|https|ftp|ftps)://(.*)\\.(.*)\\.(.*)/(.*)";
   regex_t reg; 
   // compile pattern in reg
   assert(regcomp(&reg, pattern, REG_EXTENDED) == 0); 
   // number of matchs
   size_t nmatch = reg.re_nsub, mlen;
   // offsets
   regmatch_t match[nmatch + 1];
   // matchs
   assert(!regexec(&reg, url, nmatch + 1, match, 0));
   // list of matchs
   char words[256] = {0}, *ptr = words;
   for(int n=1; n<=nmatch; n++) {
      mlen = match[n].rm_eo - match[n].rm_so;
      ptr = strncpy(ptr, url + match[n].rm_so, mlen) + mlen + 1;
   }
   // prints
   puts(url);
   for(ptr=words; *ptr!=0; ptr += strlen(ptr) + 1) 
      printf("\"%s\" ", ptr);
   puts("");
}

Jusqu'à la ligne 22, rien de plus banal.

Ensuite, la variable words est dimensionnée suffisamment et initialisée avec des '\0'.

Ma coquetterie est dans les lignes 25 à 28, et particulièrement la ligne 27.

Ici je simule une liste de chaines de caractères. Dans la variable words, j'enchaine les portions trouvées en les séparant par des caractères '\0'. C'est pourquoi dans la ligne 27 j'ajoute mlen + 1 au pointeur renvoyé par strncpy.

Le résultat dans words est ftp,arad,free,fr,regexc.html,, où les virgules représentent le caractère '\0'. Le seul intérêt est de ne consommer aucun caractère imprimable comme délimiteur.

Ainsi pour l'affichage, (ligne 31) il suffit d'enjamber ces carctères nuls, d'où le + 1 à la fin du for. Ça s'arrête lorsque deux caractères nuls se suivent.

On s'amuse comme on peut.

Le code source est en téléchargement ici regex3.c.