Comment puis-je écrire une fonction simple d'appariement de motifs d'expression régulière en C ou C ++?

Brian Kernighan un court article sur Une Expression Régulière Matcher que Rob Pike écrit comme un programme de démonstration pour un livre qu'ils ont à travailler sur. L'article est une très belle lecture expliquer un peu sur le code et les expressions régulières en général.

J'ai joué avec ce code, en faisant quelques changements à expérimenter avec des extensions comme aussi de retourner là d'où dans la chaîne de la répétition des matchs, de sorte que la sous-chaîne correspondant au modèle peut être copié à partir du texte original.

De l'article:

J'ai suggéré à Rob qu'il nous fallait trouver le plus petit réguliers
expression paquet qui illustrent les idées de base tout en encore
la reconnaissance d'un utile et non négligeable de la classe de modèles. Idéalement, l'
code sur une seule page.

Rob disparu dans son bureau, et à moins que je m'en souviens maintenant,
apparut de nouveau dans pas plus d'une heure ou deux avec les 30 lignes de C
le code qui est apparu par la suite dans le Chapitre 9 de TPOP. Ce code
implémente une expression régulière matcher qui s'occupe de ces constructions:

c    matches any literal character c
.    matches any single character
^    matches the beginning of the input string
$    matches the end of the input string
*    matches zero or more occurrences of the previous character

C'est très utile de classe; dans ma propre expérience de l'utilisation régulière
expressions sur un jour le jour base, il est facile de comptes pour 95 pour cent
de toutes les instances. Dans de nombreuses situations, de résoudre le problème en question est un
grande étape sur la route pour un beau programme. Rob mérite le plus grand respect
pour le choix de justesse, parmi un large éventail d'options, une très petite
pourtant important, bien définie et extensible ensemble de fonctionnalités.

Rob mise en œuvre est un exemple superbe de beau code:
compact, élégant, efficace et utile. C'est l'un des meilleurs exemples
de la récursivité que j'ai jamais vu, et il montre la puissance de C
les pointeurs. Bien qu'à l'époque, nous étions plus intéressés dans la transmission de l'
le rôle important d'une bonne notation dans la réalisation d'un programme plus facile à
utiliser et peut-être plus facile d'écrire ainsi, l'expression régulière code
a également été un excellent moyen d'illustrer les algorithmes, les données
les structures, les tests, amélioration de la performance, et d'autres
sujets.

Le réel de code source C de l'article est très très agréable.

/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
if (regexp[0] == '^')
return matchhere(regexp+1, text);
do {    /* must look even if string is empty */
if (matchhere(regexp, text))
return 1;
} while (*text++ != '\0');
return 0;
}
/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
{
if (regexp[0] == '\0')
return 1;
if (regexp[1] == '*')
return matchstar(regexp[0], regexp+2, text);
if (regexp[0] == '$' && regexp[1] == '\0')
return *text == '\0';
if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
return matchhere(regexp+1, text+1);
return 0;
}
/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
do {    /* a * matches zero or more instances */
if (matchhere(regexp, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}

N'ai pas tester, en fait le code, ou de débogage, mais cela pourrait vous obtenir un début...

for each character in the pattern
if pattern character after the current one is *
//enter * state
while current character from target == current pattern char, and not at end
get next character from target
skip a char from the pattern
else if pattern character after the current one is ?
//enter ? state
if current character from target == current pattern char
get next char from target
skip a char from the pattern
else
//enter character state
if current character from target == current pattern character
get next character from target
else
return false
return true

Toute la puissance des expressions régulières, et des machines à états finis ne sont pas nécessaires pour résoudre ce problème. Comme alternative, il est relativement simple de programmation dynamique de la solution.

Laissez match(i, j) 1 si il est possible de faire correspondre la sous-chaîne chaîne[i..n-1] avec le sous-modèle modèle[j, m - 1], où n et m sont les longueurs des chaîne et modèle respectivement. Sinon, laissez-match(i, j) 0.

La base de cas sont les suivants:

• match(n, m) = 1, on peut faire correspondre une chaîne vide avec un pattern vide;

• match(i, m) = 0, vous ne pouvez pas correspondre à une chaîne non vide avec un pattern vide;

La transition est divisé en 3 cas selon que le sous-modèle commence avec un caractère suivi par un '*', ou un caractère, suivi par un '?' ou juste commence avec un personnage qui n'a aucune symbole spécial après.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int is_match(char* pattern, char* string)
{
int n = strlen(string);
int m = strlen(pattern);
int i, j;
int **match;
match = (int **) malloc((n + 1) * sizeof(int *));
for(i = 0; i <= n; i++) {
match[i] = (int *) malloc((m + 1) * sizeof(int));
}
for(i = n; i >= 0; i--) {
for(j = m; j >= 0; j--) {
if(i == n && j == m) {
match[i][j] = 1;
}
else if(i < n && j == m) {
match[i][j] = 0;
}
else {
match[i][j] = 0;
if(pattern[j + 1] == '*') {
if(match[i][j + 2]) match[i][j] = 1;
if(i < n && pattern[j] == string[i] && match[i + 1][j]) match[i][j] = 1;
}
else if(pattern[j + 1] == '?') {
if(match[i][j + 2]) match[i][j] = 1;
if(i < n && pattern[j] == string[i] && match[i + 1][j + 2]) match[i][j] = 1;
}
else if(i < n && pattern[j] == string[i] && match[i + 1][j + 1]) {
match[i][j] = 1;
}
}
}
}
int result = match[0][0];
for(i = 0; i <= n; i++) {
free(match[i]);
}
free(match);
return result;
}
int main(void)
{
printf("is_match(dummy, dummy)  = %d\n", is_match("dummy","dummy"));
printf("is_match(dumm?y, dummy) = %d\n", is_match("dumm?y","dummy"));
printf("is_match(dum?y, dummy)  = %d\n", is_match("dum?y","dummy"));
printf("is_match(dum*y, dummy)  = %d\n", is_match("dum*y","dummy")); 
system("pause");
return 0;
}

Le temps de la complexité de cette approche est de O(n * m). La mémoire de la complexité est également en O(n * m), mais avec une simple modification peut être réduite à O(m).

Un programme C pour trouver l'indice,d'où le sous-chaîne dans la chaîne principale va commencer.
entrez le code ici

#include<stdio.h>
int mystrstr (const char *,const char *);
int mystrcmp(char *,char *);
int main()
{
char *s1,*s2;//enter the strings, s1 is main string and s2 is substring.
printf("Index is %d\n",mystrstr(s1,s2));
//print the index of the string if string is found
}
//search for the sub-string in the main string
int mystrstr (const char *ps1,const char *ps2) 
{
int i=0,j=0,c=0,l,m;char *x,*y;
x=ps1;
y=ps2;
while(*ps1++)i++;
while(*ps2++)j++;
ps1=x;
ps2=y;
char z[j];
for(l=0;l<i-j;l++)
{
for(m=l;m<j+l;m++)
//store the sub-string of similar size from main string
z[c++]=ps1[m];
z[c]='\0'
c=0;
if(mystrcmp(z,ps2)==0)
break;
}
return l;
}
int mystrcmp(char *ps3,char *ps4) //compare two strings
{
int i=0;char *x,*y;
x=ps3;y=ps4;
while((*ps3!=0)&&(*ps3++==*ps4++))i++;      
ps3=x;ps4=y;
if(ps3[i]==ps4[i])
return 0;
if(ps3[i]>ps4[i])
return +1;
else
return -1;
}