ein Kapitel zurück                                           ein Kapitel weiter

Jeder der mit einer Unix/Linux-Maschine zu tun kennt wohl die Regulären Ausdrücke. Reguläre Ausdrücke ist auch ein Suche nach Zeichenketten wie beim String Matching, nur erheblich komfortabler und komplexer.

Der Begriff Regulärer Ausdruck wurde von dem Sprachwissenschaftler Noam Chomsky erfunden und wird in der Informatik verwendet. Es gibt zwar mehrere Varianten von regulären Ausdrücken, doch laufen alle auf das selbe Ziel hinaus.

Bei einem regulären Ausdruck geht es darum Muster aus Buchstaben zu beschreiben. Dies Zusammen mit Wiederholungen, Alternativen und Abkürzungen für Zeichenklassifizierungen wie Ziffern oder Buchstaben. Das bekannteste Beispiel, womit sogar M$-Dos klar kommt und jeder kennen dürfte wäre die "Wildcard" (*).... 

dir t*.txt
...oder Unix...
ls -l t*.txt

Damit werden alle Textdateien ausgegeben die mit t beginnen. Beispielsweise.... 

text.txt
test.txt
total.txt

Beachten sie das M$-Dos hier nicht von Groß/Kleinschreibung Unterscheidet im Gegensatz zu Unix/Linux.

Ich möchte darauf hinweisen, dass es sich bei Regulären Ausdrücken nicht um eine Funktion handelt, sondern um eine echte Sprache mit formaler Grammatik, wo jeder Ausdruck eine präzise Bedeutung besitzt.

Wir wollen nun einige Funktionen schreiben, wo diejenigen, die mit den regulären Ausdrücken überhaupt nicht vertraut sind einen kleinen Einblick bekommen. Und Leute die damit vertraut sind, werden sehen wie man reguläre Ausdrücke in C schreiben kann.

Ich möchte darauf hinweisen, das es sich dabei nicht um ein komplettes Tutorial zu den regulären Ausdrücken handelt, sondern nur um einen kleinen Überblick. Mehr zu den regulären Ausdrücken finden sie Abschließend ein paar Links dazu.

Unser Programm ließt Dateien Zeile für Zeile aus. Unsere erste Funktion, die das Pattern Matching einleitet....... 

int pmatch(char *ausdruck, char *text)
{
 if(ausdruck[0] == '^')
   return match(ausdruck+1, text);
 for( ; *text != '\0'; *text++)
   if(match(ausdruck, text))
     return 1;
 return 0;
}

Zuerst überprüfen wir ob unser zu matchender Ausdruck am Anfang eines Textes vorkommen muss. Dies ist gegeben wenn unser Ausdruck mit dem Zeichen '^' beginnt. Beispielsweise der Ausdruck lautet.... 

^hallo

Somit müssen die ersten 4 Zeichen in text mit hallo übereinstimmen. Beispielsweise.... 

hallo welt wie gehts (Gefunden)
 hallo welt wie gehts (Mismatch -> nicht gefunden)

Im Falle des Zeichens '^' müssen wir unseren zu matchenden Ausdruck inkrementieren, damit diese Zeichen nicht mit Verglichen wird.

Falls nicht das Zeichen '^' angeben wird unsere Matching-Funktion ganz normal Zeichen für Zeichen aufgerufen.

Nun wollen wir uns die Matching-Funktion match ansehen........ 

int match(char *ausdruck, char *text)
{
 if(ausdruck[0] == '\0')
  return 1;
 if(ausdruck[1] == '*')
  return wildcard(ausdruck[0], ausdruck+2, text);
 if(ausdruck[0] == '$' && ausdruck[1] == '\0')
  return *text == '\0';
 if(*text != '\0' && ( ausdruck[0] == '.' || ausdruck[0] == *text))
  return match(ausdruck+1, text+1);
 return 0;
}

Zuerst überprüfen wir ob wir schon am Ende des Pattern sind ('\0'). Als nächstes schauen wir ob eine Wildcard (*) angegeben wurde. Falls ja wird entsprechende Funktion aufgerufen wozu wir gleich noch kommen. Das Zeichen '$' bedeutet beim Matching Stringende. Beispielsweise.... 

match und$ *.txt

Damit werden alle Ausdrücke gefunden bei denen die Zeilen mit und Enden..... 

asdfasdfasdfasdfsdfassdfsdfund             /*Gefunden*/
asdfasdfsdffdasdfsdfasdfasdffaseiasdund    /*Gefunden*/
qwerasdf asdf asdf asdf  und               /*Gefunden*/
und was jetzt                              /*Missmatch*/

Und das zu Überprüfen das wir nicht nach dem Zeichen '$' suchen ,sondern das es auch wirklich das ist was es bedeuten soll, testen wir gleich ob das nächste Zeichen unseres Ausdrucks das Endzeichen '\0' ist.

Die nächste Überprüfung....... 

if(*text != '\0' && ( ausdruck[0] == '.' || ausdruck[0] == *text))

..testet ob wir nicht schon am Ende sind UND entweder das nächste Zeichen ein beliebiges sein darf (.) oder das Zeichen im Ausdruck mit dem im Text übereinstimmt. Falls ja wird diese Funktion rekursiv erneut mit mit den nächsten Zeichen Aufgerufen. Der rekursive Aufruf erfolgt solange bis eine der Bedingungen in dieser Funktion einen return Wert (0 oder 1) zurückliefert.

Jetzt wollen wir uns noch schnell die Wildcardfunktion ansehen........ 

int wildcard(int c, char *ausdruck, char *text)
{
  for( ;*text != '\0' && (*text == c || c == '.'); *text++)
    if(match(ausdruck, text))
      return 1;
  return 0;
}

Zugegeben dies ist eine schwache Wildcard-Funktion aber sie funktioniert. Sie finden anschließend bei den Links mehr dazu.

Nun wollen wir uns den Kompletten Quellcode dazu ansehen......

/*Download:match.c*/

#include <stdio.h>
#include <stdlib.h>
#define BUF 4096

int pmatch(char *ausdruck, char *text)
{
 if(ausdruck[0] == '^')
   return match(ausdruck+1, text);
 for( ; *text != '\0'; *text++)
   if(match(ausdruck, text))
     return 1;
 return 0;
}

int match(char *ausdruck, char *text)
{
 if(ausdruck[0] == '\0')
  return 1;
 if(ausdruck[1] == '*')
  return wildcard(ausdruck[0], ausdruck+2, text);
 if(ausdruck[0] == '$' && ausdruck[1] == '\0')
  return *text == '\0';
 if(*text != '\0' && ( ausdruck[0] == '.' || ausdruck[0] == *text))
  return match(ausdruck+1, text+1);
 return 0;
}

int wildcard(int c, char *ausdruck, char *text)
{
  for( ;*text != '\0' && (*text == c || c == '.'); *text++)
    if(match(ausdruck, text))
      return 1;
  return 0;
}

int my_grep(char *ausdruck, FILE *f, char *name)
{
 int n, nmatch=0;
 int line=0;
 char buffer[BUF];
 while(fgets(buffer, sizeof(buffer), f) != NULL)
  {
    line++;
    n = strlen(buffer);
    if(n > 0 && buffer[n-1] == '\n')
      buffer[n-1] = '\0';
    if(pmatch(ausdruck, buffer))
     {
      nmatch++;
      if(name != NULL)
       printf("%d. ",line);
     }
   }
  if(nmatch!=0)
   printf("Zeile in der Datei %s (insg.%d)\n\n",name,nmatch);
  return nmatch;
}



int main(int argc, char **argv)
{
 int i, nmatch=0;
 FILE *f;

 if(argc <= 2)
  {
   fprintf(stderr, "Verwendung des Programms : %s pattern quelle\n\n",*argv);
   exit(0);
  }
 else
  {
   for(i = 2; i<argc; i++)
    {
     f = fopen(argv[i], "r");
     if(NULL == f)
      {
        fprintf(stderr, "Konnte %s nicht öffnen\n",argv[i]);
        continue;
      }
     if(my_grep(argv[1],f, argv[i]) > 0)
      nmatch++;
     fclose(f);
    }
  }
 printf("%d Dateien mit passenden Pattern %s gefunden\n",nmatch,argv[1]);
 return 0;
}

Nun wollen wir uns doch ein paar Matching Beispiele zu unserem Programm ansehen...... 

match ^\#include.*$ *.c

(Matcht alle am Anfang einer Zeile stehenden Stringfolge
'#include' in C-Dateien des selben Verzeichnisses bis zum Ende
der Zeile ($). Unter M$ entfernen sie bitte das Zeichen \ vor
dem Zeichen #, da dies unter Unix eine andere Bedeutung hat.
beliebiger Länge (*.) bis zum Ende der Zeile ($))

match Was.* *.txt

(Matcht aus allen Textdateien die Stringfolge 'Was'
beispielsweise:
Was ist...? Wasserbehälter. Wassermann.............


match \<p\> *.html

(Matcht alle Absätz in HTML - Dateien. Auch hier bei M$-Systemen
das Zeichen \ entfernen.

Nun haben sie eine wenig erfahren wie sie Reguläre Ausdrücke in C schreiben können. Dies war aber nur ein Bruchteil von dem was man mit Regulären Ausdrücken alles machen kann. Daher für weiterführende Informationen nun folgende Links........



Reguläre Sprachen, reguläre Ausdrücke
http://www.lrz-muenchen.de/services/schulung/unterlagen/regul/


Reguläre Ausdrücke
http://www.infodrom.north.de/~joey/Linux/Toolbox/RegExp.html


Wildcards Pattern Matching Algorithm
http://user.cs.tu-berlin.de/~schintke/references/wildcards/

Regular Expressions in C and Linux (mit der Library regex.h)
http://www.linuxgazette.com/issue55/tindale.html

Regular Expression Matching (Zeitvergleiche Verschiedener Programmiersprachen)
http://www.bagley.org/~doug/shootout/bench/regexmatch/?cpu-s

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf