c systems notebook
C-Dokumentation

Pattern-Matching

Beim Verarbeiten von Text reicht ein direkter Vergleich mit strcmp() oft nicht aus. Statt exakter Gleichheit prüft man häufig, ob ein String einem bestimmten Muster folgt oder ob sich Teile daraus extrahieren lassen.

Muster (engl. pattern) erlauben, dass an bestimmten Stellen beliebige Zeichenfolgen oder genau ein Zeichen stehen. So lässt sich eine Form beschreiben, ohne den vollständigen String zu kennen.

Typische Anwendungsfälle sind:

  • Dateinamen nach Endungen oder Präfixen filtern
  • Eingaben grob validieren (z. B. E-Mails, IDs, Versionsnummern)
  • Textstellen extrahieren, z. B. den Nutzerteil aus name@example.com
  • Logzeilen nach Mustern durchsuchen (›enthält Datum, dann Level, dann Nachricht‹)

Solche Muster haben eine lange Tradition: Schon in den 1960er-Jahren boten Systeme wie CTSS und später Multics erste Möglichkeiten, Dateinamen mit Platzhaltern zu filtern. Diese frühen Mechanismen prägten das Unix-Design, das die heute verbreiteten Wildcards übernahm.

Dieses Unterkapitel zeigt zwei Ansätze, wie man Muster explizit beschreiben kann: einfache Wildcards für alltägliche Filter und reguläre Ausdrücke für komplexere Regeln und Extraktionen.

Einfaches Wildcard-Matching

Für einfache Muster genügen oft zwei Platzhalter, sogenannte Wildcards:

  • * steht für beliebig viele Zeichen
  • ? steht für genau ein Zeichen

Diese Symbole stammen historisch aus dem Unix-Umfeld: Die frühe Thompson-Shell der 1970er führte das sogenannte ›glob‹-System ein, das Dateimuster erlaubte. Dieses einfache Pattern-Matching wurde später in andere Shells übernommen und ist bis heute Standard.

Beispiele:

  • *.txt trifft auf alle Dateien mit .txt.
  • test?.c passt auf test1.c oder testA.c, aber nicht auf test12.c.
  • backup-????-??.tar.gz beschreibt Backups mit Datumsanteil.

Solche Wildcards eignen sich gut für einfache Filter, etwa beim Durchsuchen von Verzeichnissen oder beim Erkennen von Dateinamenmustern wie error*.log oder img_??.png.

Die Implementierung eines Wildcard-Matchers ist überschaubar. Ein rekursiver Ansatz gleicht Muster und Eingabe zeichenweise ab. Der folgende Code zeigt eine einfache Variante:

#include <stdio.h>
#include <stdbool.h>

bool wildcard_match(const char *pattern, const char *str) {
    if (*pattern == '\0' && *str == '\0') return true;
    if (*pattern == '*') {
        if (*(pattern + 1) == '\0') return true;
        while (*str != '\0') {
            if (wildcard_match(pattern + 1, str)) return true;
            str++;
        }
        return wildcard_match(pattern + 1, str);
    }
    if (*str != '\0' && (*pattern == '?' || *pattern == *str)) {
        return wildcard_match(pattern + 1, str + 1);
    }
    return false;
}

int main() {
    puts(wildcard_match("*.txt", "test.txt") ? "Match" : "Kein Match");
    // 📣 Match
    puts(wildcard_match("test?.c", "test1.c") ? "Match" : "Kein Match");
    // 📣 Match
    puts(wildcard_match("test?.c", "test12.c") ? "Match" : "Kein Match");
    // 📣 Kein Match
}

Die Funktion arbeitet rekursiv:

  • Ist das Muster leer, gibt es nur dann einen Match, wenn auch die Eingabe leer ist.
  • Ein * versucht, null oder mehr Zeichen zu konsumieren und probiert dafür mehrere Varianten aus.
  • Ein ? steht genau für ein Zeichen.
  • Passen die aktuellen Zeichen, wird mit den Resten weitergemacht.

Der Ansatz kann bei Mustern mit vielen * langsam werden, weil viele Kombinationen geprüft werden (Backtracking). Für typische Dateinamenfilter ist die Geschwindigkeit in der Regel ausreichend. Iterative Varianten oder Memoization können beschleunigen, erhöhen aber die Komplexität.

POSIX Funktion fnmatch()

Auf POSIX-Systemen bietet die Bibliothek <fnmatch.h> eine fertige, standardisierte Lösung. Die Funktion hat die Signatur:

  • int fnmatch(const char *pattern, const char *string, int flags);

Bedeutung der Parameter:

  • pattern: Das Wildcard-Muster.
  • string: Der zu prüfende Text.
  • flags: Steuert Optionen, z. B. 0 für Standardverhalten oder FNM_CASEFOLD für case-insensitive Matching (ignoriert Groß-/Kleinschreibung, nützlich für plattformübergreifende Anwendungen).

Ein Rückgabewert von 0 bedeutet ›Match‹. Ein Beispiel:

#include <stdio.h>
#include <fnmatch.h>

int main() {
    if (fnmatch("*.txt", "test.txt", 0) == 0) {
        puts("Match");  // 📣 Match
    }
    if (fnmatch("test?.c", "test12.c", 0) == 0) {
        puts("Match");
    } else {
        puts("Kein Match");  // 📣 Kein Match
    }
    // Case-insensitive Beispiel:
    if (fnmatch("*.TXT", "test.txt", FNM_CASEFOLD) == 0) {
        puts("Case-insensitive Match");  // 📣 Case-insensitive Match
    }
}

Für Fälle, die mehr als einfache Platzhalter brauchen -- etwa verschachtelte Muster, Alternativen oder strukturelle Regeln --, eignen sich reguläre Ausdrücke ...

Reguläre Ausdrücke mit POSIX (<regex.h>)

Reguläre Ausdrücke (kurz: Regex) ermöglichen es, Zeichenketten auf Basis von Mustern wie ›beginnt mit A, gefolgt von einer beliebigen Anzahl Ziffern, endet mit .txt‹ zu prüfen oder Teile daraus zu extrahieren.

Geschichte Der theoretische Ursprung geht auf Stephen Kleene zurück, der in den 1950er-Jahren reguläre Sprachen und ihre Notation definierte. Eine der ersten praktischen Implementierungen entwickelte Ken Thompson in den späten 1960ern für das Textwerkzeug QED; später wurden Regex zu einem festen Bestandteil von Unix-Werkzeugen wie ed, grep und sed.

Der POSIX-Standard definiert eine C-Schnittstelle dafür in <regex.h>, die auf Unix-ähnlichen Systemen verfügbar ist. Unter Windows fehlt diese Bibliothek standardmäßig, aber Ports bieten ähnliche Funktionalität.

Die POSIX-Regex-API umfasst drei Hauptfunktionen:

  • regcomp() kompiliert einen regulären Ausdruck in eine interne Struktur,
  • regexec() führt den Match gegen eine Zeichenkette aus, und
  • regfree() gibt die Ressourcen frei.

Das folgende Beispiel prüft, ob eine Zeichenkette dem Muster einer einfachen E-Mail-Adresse entspricht:

#include <stdio.h>
#include <regex.h>

int main() {
    regex_t regex;
    const char *pattern =
        "^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}$";
    const char *email = "test@example.com";

    int result = regcomp(&regex, pattern, REG_EXTENDED | REG_NOSUB);
    if (result != 0) {
        char errbuf[128];
        regerror(result, &regex, errbuf, sizeof(errbuf));
        puts("Regex-Kompilierung fehlgeschlagen");
        return 1;
    }

    result = regexec(&regex, email, 0, nullptr, 0);
    if (result == 0) {
        puts("E-Mail-Adresse gültig"); // 📣 E-Mail-Adresse gültig
    } else if (result == REG_NOMATCH) {
        puts("E-Mail-Adresse ungültig");
    }

    regfree(&regex);
}

Das Flag REG_EXTENDED aktiviert erweiterte Syntax (z. B. + für ›ein oder mehr‹ ohne Escaping). REG_NOSUB deaktiviert Submatch-Extraktion, was den Aufruf von regexec() vereinfacht, wenn man nur wissen will, ob ein Match existiert. Weitere nützliche Flags sind z. B. REG_ICASE für case-insensitive Vergleiche.

Die wichtigsten Elemente regulärer Ausdrücke sind:

  • Zeichenklassen und Metazeichen:

    • . für ein beliebiges Zeichen,
    • [abc] für eines von a, b oder c,
    • [^abc] für jedes Zeichen außer a, b, c.
    • In POSIX: [0-9] für Ziffern (PCRE bietet zusätzlich \d), außerdem Klassen wie [[:digit:]] oder [[:alpha:]].
    • ^ markiert den String-Anfang, $ das String-Ende.

  • Quantifizierer:

    • * für null oder mehr,
    • + für eine oder mehr,
    • ? für null oder eine Wiederholung.
    • {n} für exakt n, {n,m} für n bis m, {n,} für mindestens n.

  • Gruppierung und Alternativen:

    • (...) für Gruppen,
    • | für Oder.
    • Beispiel: (cat|dog)s? matcht ›cat‹, ›cats‹, ›dog‹ und ›dogs‹.

  • Escaping:

    • Sonderzeichen wie . oder * müssen mit Backslash maskiert werden; in C-Strings doppelt: \\. für einen literalen Punkt.

Submatches mit regexec

Bei Erfolg liefert regexec() (ohne REG_NOSUB) Submatch-Informationen über ein regmatch_t-Array. Damit kann man Teilstrings bequem aus dem Originalstring ausschneiden, z. B. den Benutzerteil aus einer E-Mail-Adresse:

#include <stdio.h>
#include <regex.h>

int main() {
    regex_t regex;
    regmatch_t matches[2];
    const char *pattern = "^\\([^@]+\\)@.*$";
    const char *email = "user@example.com";

    if (regcomp(&regex, pattern, 0) != 0) {
        return 1;
    }

    if (regexec(&regex, email, 2, matches, 0) == 0) {
        int start = matches[1].rm_so;
        int end   = matches[1].rm_eo;
        printf("User: %.*s\n", end - start, email + start); // 📣 User: user
    }

    regfree(&regex);
}

matches[0] beschreibt das gesamte Match, matches[1] die erste Klammergruppe. rm_so und rm_eo enthalten Start- und Endindex im Originalstring.

Das E-Mail-Beispiel ist bewusst vereinfacht; für eine vollständige RFC-5322-Konformität sollte man spezialisierte Bibliotheken verwenden. Für Windows oder Systeme ohne POSIX-Support eignen sich PCRE2 oder leichte Header-only-Engines. In jedem Fall gilt: Lizenz und Kompatibilität prüfen und Muster gründlich testen.

Regex sind flexibel, aber fehleranfällig. Ein unpassendes Muster führt zu unerwarteten Treffern oder verpassten Matches. Komplexe Quantifizierer in Kombination mit ungünstigen Mustern können zu sehr langsamen Laufzeiten durch starkes Backtracking führen.