Programmer’s Toolbox - Dateien, Teil 9: Eine Einführung in Textdateien

Mit der heutigen Folge beginnt der zweite thematische Block der Programmer's Toolbox. Hier wird ausschließlich eine spezielle Dateiart behandelt: die Textdatei. Es werden Kommandos zum Ansehen, Sortieren und Durchsuchen von Text eingeführt.

Text

Der zweite thematische Block umfaßt insgesamt vier Serienteile. An dieser Stelle soll zunächst wieder eine kurze Übersicht gegeben werden. In der heutigen Folge (9. Teil) beginnen wir mit einigen allgemeinen Hilfsfunktionen, die genau wie im ersten Block in einem Modul zusammengefaßt sind (Modul ATOM2). Dazu kommt das Makefile für den kompletten zweiten Block und ein erstes Kommando (ECHO-Ausgabe der Argumente auf der Standardausgabe). Die nächste Folge (10. Teil) enthält einige Kommandos, die sich mit unterschiedlichen Aspekten der Bearbeitung von Textdateien beschäftigen:

CAT - Verschmelzen und Anzeigen von Dateien
MORE - Anzeigen von Textdateien
GREP - Durchsuchen von Textdateien nach Textmustern

Die letzten beiden Teile des Blocks (11. und 12. Teil) befassen sich mit einem sehr umfangreichen Kommando:

SORT - Die Sortierung von Textdateien

Mit dem Kommando SORT wird das Sortieren von Textdateien auf einer sehr breiten Basis gelöst. SORT erlaubt unter anderem das Sortieren mit mehreren Sortierfeldern und/oder Sortierrelationen.

Weitere Hilfsfunktionen

Doch zurück zur heutigen Folge. Hier steht zunächst die Implementierung eines Moduls an (ATOM2). Das Modul ATOM2 beinhaltet eine recht bunte Sammlung von Funktionen, die jedoch alle eine Gemeinsamkeit besitzen: Sie erzeugen/bearbeiten/verarbeiten Strings. Verwundern dürfte das nicht. Das Thema dieses Blocks ist nun einmal Text und von Text bis zu Strings ist es nicht weit.

Die meisten der Funktionen des Moduls ATOM2 sind sehr einfach. Ich werde daher zunächst nur eine kurze Wirkungsbeschreibung aller Routinen geben und mich dann dem Funktionspaar strcompare/patmat (Listing 2.1. Zeilen 61-107) zuwenden. Ich denke der hier angewendete Algorithmus verdient einen nähere Betrachtung. da er ein gutes Beispiel für eine mehrgliedrige Rekursion ist. Doch zunächst die übrigen Funktionen in der Reihenfolge ihres Auftretens.

Die Funktion onlyws (Zeilen 30-38) untersucht den String str darauf, ob er ausschließlich aus Leerzeichen (SPACE und TAB) besteht. Sie wird von den Kommandos CAT und MORE benutzt, um derartige Zeilen zu erkennen. Die nächste einfache Funktion ist outline (Zeilen 123-134). outline wird vom Kommando MORE benötigt, um die Ausgabe der Zeichenkette string in einer Zeile vorzunehmen. Bei Überlänge der Zeile entscheidet der Parameter fold darüber, ob die Zeile abgeknickt wird (fold == TRUE), oder ob sie abgeschnitten werden soll (fold == FALSE). filter_dict (Zeilen 149-164) wird vom Kommando SORT benötigt. Diese Funktion entfernt alle Zeichen aus der Zeichenkette string, bei denen es sich weder um alphanumerische Zeichen (Ziffern und Buchstaben) noch um Leerzeichen handelt. Auch die drei letzten Funktionen des Moduls ATOM2 werden im Zusammenhang mit SORT benötigt. Bei random_number, random_alpha und random_month (Zeilen 188-250) handelt es sich um Funktionen, die Zufallsstrings unterschiedlicher Art erzeugen. random_number erzeugt einen Zufallsstring aus Ziffern: random_alpha erzeugt den String aus Großbuchstaben und random_month erzeugt einen drei Zeichen langen Zufallsstring. dessen Komponenten den anglikanischen Konventionen für die Abkürzung von Monatsnamen entsprechen:

JAN FEB MAR APR MAY JUN JUL AUG
SEP OCT NOV DEC

Diese Funktionen werden benötigt, um hinreichend komplexe Textdateien zum Test von SORT zu erstellen. Zur Erzeugung der Zufallszeichen werden entsprechende Transformationen der XBIOS-Funktion Random vorgenommen. Random liefert dabei eine 24-Bit Pseudo-Zufallszahl. die durch Anwendung des Modulus (Rest der ganzzahligen Division) auf entsprechende Ziffern abgebildet wird (Zeilen 194, 204, 212).

Kommen wir nun zu dem Funktionspaar strcompare/patmat. Diese beiden Funktionen enthalten einen einfachen Mustererkennungsalgorithmus, wie er in zweien der nachfolgenden Kommandos (MORE und GREP) zur Erkennung von Zeilen mit bestimmten Eigenschaften benutzt wird.

Zunächst zum Begriff des Musters. Aus dem Betriebssystem des ST sind Ihnen sicherlich Dinge wie Fragezeichen (?) und Sternchen (*) innerhalb von Suchanfragen zum Auffinden von Dateien bekannt. Innerhalb von Mustern steht ein Fragezeichen für einen beliebigen Buchstaben ein Sternchen für eine Folge von beliebigen Buchstaben (die Folge kann auch leer sein). Solche Muster werden eingesetzt, um Wörter (beliebige Folgen von Zeichen) mit bestimmten Eigenschaften zu erkennen. Nachfolgend finden Sie einige Muster zur Erkennung bestimmter Wörter.

• "" - alle Wörter
  "A" - Wörter mit Anfang 'A'
  "??" - Wörter mit zwei Zeichen
  "?" - Wörter mit mindestens einem Zeichen
  "ATARI"" - Wörter die irgendwo "ATARI" enthalten
  ".C" - Wörter die C-Programmnamen sind

Soweit zur Motivation für die Mustererkennung. Ihre Realisierung geschieht nach einem Algorithmus, der jede Muster-Wort-Kombination auf einen der beiden folgenden. einfachen Fälle reduziert:

1. "Muster ist leer“ und “Wort ist leer" ==> “Wort entspricht dem Muster“
2. "Muster ist leer" und "Wort ist nicht leer" ==> "Wort entspricht nicht dem Muster“

Die Reduktion geschieht nach drei Regeln. In der Implementierung erfolgt sie innerhalb der Funktion strcompare.

1. Besitzen Muster und Wort in erster Position das gleiche Zeichen, werden Muster und Wort um das erste Zeichen verkleinert und die verkürzten Wörter werden untersucht (Zeilen 86-87).

2. Besitzt das Muster in erster Position das Zeichen '?' und das Wort ist nicht leer, werden Muster und Wort um das erste Zeichen verkleinert und die verkürzten Wörter werden untersucht (Zeilen 82-83).

3. Besitzt das Muster in erster Position das Zeichen '*' sind zwei Regeln hintereinander anwendbar:

3.1. Zunächst kann eine Reduktion des Wortes erfolgen, da auch auf ein verkürztes Wort anwendbar ist (Zeilen 74-77).

3.2. Nach erfolgter Reduktion kann zusätzlich noch entfernt werden und auf ein unverändertes Wort angewendet werden (Zeilen 78-79).

Die Realisierung ist dabei um einiges kompakter formuliert als die obige umgangssprachliche Fassung. Gut zu beobachten ist dabei die Anwendung von Rekursion (Zeilen 75, 79, 83, 87). Zur Verdeutlichung betrachten Sie bitte Abb. 2.1. Hier sind zwei Beispiele für die parameterisierte Abfolge von rekursiven strcompare-Funktionsaufrufen dargestellt. (Der Ergebnisparameter erg wurde dabei weggelassen.) Die rechte Abfolge steht für eine erfolgreiche Mustererkennung. Die linke Abfolge führt dagegen zum Abbruch des Vergleichs beim Auftauchen von unterschiedlichen Zeichen in Muster und String. Insbesondere erkennt man. daß das Zeichen immer gleich zu einer ganzen Kaskade von rekursiven Einschachtelungen führt.

Die Hauptfunktion patmat (Zeilen 92-107) besitzt eigentlich keine andere Aufgabe. als strcompare geeignet zu parameterisieren. Da patmat einen beliebigen Teilstring innerhalb einer Zeile erkennen soll, wird zunächst das Muster von patmat auf der rechten und linken Seite um ein Sternchen erweitert. Erst dann kann ein Aufruf von strcompare erfolgen, wo dann die eigentliche Vergleichsarbeit durchgeführt wird.

Und damit endet auch schon die Betrachtung des Moduls ATOM2. Nachgereicht sei nur noch der zugehörige C-Header. Ihn finden Sie in Listing 2.2.

Abb. 2.1: Beispiele für die rekursive Mustererkennung

Das Kommando ECHO

Das Kommando ECHO ist bereits einmal in etwas einfacherer Form zu Beginn des ersten Blocks verwendet worden, um die Parameterübergabe des Betriebssystems zu verdeutlichen (Kommando ECHOSIMP, Listing 1.2). Nun wird ein erweitertes ECHO vorgestellt, daß die meisten C-Ersatzdarstellungen erkennt.

Name
ECHO - Ausgabe der Argumente auf der Standardausgabe

Anwendung
ECHO [ -N ] [ Argument... ]

Beschreibung
ECHO gibt sämtliche Argumente auf dem Standardausgabekanal aus. Die Ausgabe wird mit einem NEWLINE abgeschlossen. ECHO erkennt dabei folgende C-Ersatzdarstellungen:

\b Zeilenvorschub
\t Tabulator
\b Rückschritt
\r Wagenrücklauf
\f Seitenvorschub
" Doppelte Anführungszeichen
' Einfache Anführungszeichen
\nnn Zeichen mit Oktalwert nnn

Optionen
-N Die Ausgabe wird nicht mit einem NEWLINE abgeschlossen.

Programmierung
Das Kommando ECHO finden Sie in Listing 2.3 programmiert. Es unterscheidet sich von der bereits früher betrachteten, einfachen Ausgabe der Argumente (Kommando ECHOSIMP. Listing 1.2) durch eine zusätzliche Funktion (print, Zeilen 29-82). print übernimmt die Aufgabe der Standardfunktion printf innerhalb von ECHOSIMP. Der Hintergrund für diesen Austausch besteht darin, daß ECHO, wie unter Beschreibung aufgeführt, die C-Ersatzdarstellungen beherrschen soll. Entsprechend muß dafür gesorgt werden, daß die übergebenen Argumente auf C-Ersatzdarstellungen untersucht werden. Diese Aufgabe wird von einer switch-Anweisung innerhalb von print (Zeilen 40-76) übernommen. Die Ausgabe erfolgt dann zeichenweise durch wiederholten Aufruf der Standardfunktion putchar.

Das Makefile für den zweiten Block

Genau wie bei dem letzten Block der Programmer's Toolbox, soll auch dieses Mal ein Makefile angegeben werden, daß darüber Aufschluß gibt, wie die einzelnen Moduln und Kommandos übersetzt werden, bzw. welche Abhängigkeiten zwischen den Kommandos bestehen. Innerhalb dieses Artikels finden Sie eine entsprechende Datei abgedruckt. Zu beachten ist dabei, daß die Module EXPAND und ATOM aus dem letzten Block zur Übersetzung einiger Kommandos benötigt werden.

Vorausschau

In der nächsten Folge der Programmer’s Toolbox befassen wir uns mit unterschiedlichen Aspekten der Bearbeitung von Textdateien. Folgende Kommandos werden dabei realisiert.

CAT - Verschmelzen und Anzeigen von Dateien
MORE - Anzeigen von Textdateien
GREP - Durchsuchen von Textdateien nach Textmustern

Bei MORE und GREP wird dabei das heute betrachtete Mustererkennungsverfahren angewendet.

/*
 * Listing 2.1, Datei : atom2.c
 * Modul              : ATOM2 - ATOMare Manipulationen,
 *                      2.Teil
 * Modifikationsdatum : 04-Mär-90
 * Abhängigkeiten     : stdio.h, string.h, ctype.h,
 *                      osbind.h, local.h
 */

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <osbind.h>
#include "local.h"

/*
 * Funktion     : onlyws
 *
 * Parameter    : isonlyws = onlyws(str);
 *                BOOLEAN isonlyws;
 *                char *str;
 *
 * Aufgabe      :
 *
 * Der String <str> wird daraufhin untersucht,
 * ob er nur Leerzeichen (SPACE und TAB) enthält.
 * Es wird ein entsprechender Wahrheitswert zurückgegeben.
 */

BOOLEAN onlyws(str) 
char *str;
{   short i;

    for (i =0; i < strlen(str); i++)
        if (!(str[i] == ' ' || str[i] == '\t'))
            return(FALSE); 
    return(TRUE);
}

/*
 * Funktion     : patmat
 *
 * Parameter    : ismatching — patmat(pattern,string);
 *                BOOLEAN ismatching;
 *                char    *pattern,
 *                        *string;
 *
 * Aufgabe      :
 *
 * Die Funktion <patmat> (Pattern Matching) vergleicht
 * das Muster <pattern> mit der Zeichenkette <string>
 * und liefert einen Wahrheitswert, der dem Ergebnis des
 * Vergleichs entspricht. <pattern> darf dabei das Zeichen
 * '?' zur Kennzeichnung eines unbekannten Buchstaben und
 * das Zeichen '*' zur Kennzeichnung eines unbekannten
 * Teilstrings enthalten. <patmat> ergänzt dabei das
 * übergebene Muster rechts und links mit dem Zeichen '*',
 * um <pattern> an beliebiger Stelle im <string> zu erkennen.
 */

static void strcompare (string, pattern, erg) 
char    *string,
        *pattern;
BOOLEAN *erg;
{   char *str = string,
         *pat = pattern;

    if (!(*erg)) {
        if (strlen(pat) == 0)
            *erg = strlen(str) == 0;
        else
            switch(pat[0]) {
                case '*':
                    if (strlen(str) > 0) {
                        strcompare(++str,pat,erg);
                        -str;
                    }
                    if (!(*erg))
                        strcompare(str,++pat,erg);
                    break; 
                case '?':
                    if (strlen(str) != 0)
                        strcompare(++str,++pat,erg);
                    break; 
                default:
                    if (pat[0] == str[0])
                        strcompare(++str,++pat,erg);
            }
    }
}

BOOLEAN patmat(pattern, string) 
char *pattern,
     *string;
{   BOOLEAN erg = 0;
    char    *w1 = malloc(strlen(string) + 1),
            *w2 = malloc(strlen(pattern) + 3);

    strcpy(w1, string); 
    strcpy(w2, "*"); 
    strcat(w2, pattern); 
    strcat(w2, "*"); 
    strcompare(w1, w2, &erg); 
    free(w1); 
    free(w2);
    return (erg);
}

/*
 * Funktion     : outline
 *
 * Parameter    : outline(string, fold);
 *                char *string;
 *                BOOLEAN fold;
 *
 * Aufgabe      :
 *
 * Ausgabe einer Zeile unter Berücksichtigung des
 * Parameters <fold>. <fold> gibt an ob die Zeile beim Zeilenende "abgeschnitten" oder
 * "abgeknickt" wird.
 */

void outline(string, fold) 
char    *string;
BOOLEAN fold;
{   short i = 1;

    for (i = 0; i < strlen(string); i++) {
        if (fold && (i + 1) % 80 == 0) 
            printf("\n"); 
        putchar(string[i]);
    }
    printf("\n");
}

/*
 * Funktion     : filter_dict
 *
 * Parameter    : filter_dict(string)
 *                char *string;
 *
 * Aufgabe
 *
 * <filter_dict> entfernt alle Zeichen aus einem String, die weder Leerzeichen noch
 * alphanumerische Zeichen
 * sind.
 */

void filter_dict(string) 
char *string;
{   short i,
          j,
          l;

    j = 0;
    l = strlen(string); 
    for (i = 0; i < 1; i++)
        if (isspace(string[i]) || isalnum(string[i])) 
            string[i - j] = string[i];
        else
            j++;
    string[l - j] = 0;
}

/*
 * Funktion     : random_number, random_alpha,
 *                random_month
 *
 * Parameter    : random_number(string, count);
 *                random_alpha(string, count);
 *                random_month(string);
 *                char *string;
 *                short count;
 *
 * Aufgabe      :
 *
 * Erzeugen von Zufallsstrings. <random_number>
 * und <random_alpha> erzeugen Zufallsstrings 
 * der Länge <count> an der Adresse <string>.
 * <random_nunber> erzeugt dabei
 * Ziffern; <random_alpha> Großbuchstaben. <random__month>
 * erzeugt einen drei Zeichen langen Zufallsstring, der
 * einem der zwölf folgenden Monatskürzel entspricht:
 *
 * JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC
 */

void random_number(string, count) 
char    *string; 
short   count;
{   short i;

    for (i = 0; i < count; i++)
        string[i] = Random() % 10 + '0';
    string[count] = 0;
}

void random_alpha(string, count) 
char    *string; 
short   count;
{   short i;

    for (i = 0; i < count; i++)
        string[i] = Random() % 26 + 'A';
    string[count] = 0;
}

void random_month(string) 
char *string;
{   short i;

    switch (Random() % 12) {
        case 0:
            strcpy(string, "JAN"); 
            break; 
        case 1:
            strcpy(string, "FEB"); 
            break; 
        case 2:
            strcpy(string, "MAR"); 
            break; 
        case 3:
            strcpy(string, "APR"); 
            break; 
        case 4:
            strcpy(string, "MAY"); 
            break; 
        case 5:
            strcpy(string, "JUN"); 
            break; 
        case 6:
            strcpy(string, "JUL"); 
            break; 
        case 7:
            strcpy(string, "AUG"); 
            break; 
        case 8:
            strcpy(string, "SEP"); 
            break; 
        case 9:
            strcpy(string, "OCT"); 
            break; 
        case 10:
            strcpy(string, "NOV"); 
            break; 
        case 11:
            strcpy(string, "DEC"); 
            break;
    }
}

/*
 * Listing 2.2, Datei : atom2.h
 * Modul              : ATOM - ATOMare Manipulationen,
 *                      2.Teil
 * Modifikationsdatum : 04-Mär-90
 * Abhängigkeiten     : local.h
 */

extern BOOLEAN onlyws(), 
               patmat(); 
extern void    outline(),
               filter_dict(), 
               random_number(), 
               random_alpha(), 
               random_month();

/*
 * Listing 2.3, Datei : echo.c
 * Programm           : ECHO - Ausgabe der Argumente
 *                      auf der Standardausgabe
 * Modifikationsdatum : 17-Dez-89
 * Abhängigkeiten     : ctype.h, stdio.h, string.h,
 *                      local.h 
 */

#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include "local.h"

/*
 * Funktion         : print
 *
 * Parameter        : print(line);
 *                    char *line;
 *
 * Aufgabe          :
 *
 * Die Zeile <line> wird auf dem Standardausgabekanal
 * ausgegeben. Dabei sind die C-Ersatzdarstellungen
 * zu berücksichtigen und innerhalb von <print>
 * entsprechend zu interpretieren.
 */

void print(line) 
char *line;
{   short i = 0,
          len = strlen(line);

    while (i < len) {
        if (line[i] == '\\' ) 
            if (i + 1 == len) 
                return ; 
            else { 
                i++;
                switch(line[i]) {
                    case 'n' :
                        putchar('\n'); 
                        break; 
                    case 't' :
                        putchar('\t'); 
                        break; 
                    case 'b' :
                        putchar('\b'); 
                        break; 
                    case 'r' :
                        putchar('\r'); 
                        break; 
                    case 'f' :
                        putchar('\f'); 
                        break; 
                    case '\"' :
                        putchar('\"'); 
                        break; 
                    case '\'' :
                        putchar('\''); 
                        break; 
                    default:
                        if (isoctal(line[i])) {
                            if (i + 2 < len && isoctal(line[i+1]) && isoctal(line[i+2])) {
                                putchar(todigit(line[i + 1])*8 + todigit(line[i + 2])); 
                                i += 2;
                            }
                        }
                        else
                            putchar(line[i]); 
                        break;
                }
            }
        else if (line[i] != '\"')
            putchar(line[i]);
        i++;
    }
}

/*
 * Funktion     : echo
 *
 * Parameter    : echo(argc, argv);
 *                short argc;
 *                char *argv[];
 *
 * Aufgabe      :
 *
 * Interpretation der durch <argc> und <argv>
 * spezifizierten Parameterliste gemäß den Fest-
 * legungen des Kommandos ECHO.
 */

void echo(argc, argv) 
short argc; 
char  *argv[];
{   short i,
          start = 1;
    BOOLEAN newline = TRUE;

    if (argc > 1) {
        if (strcmp(argv[1], "-N") == 0 || strcmp(argv[1], "-n") == 0) { 
            newline = FALSE; 
            start = 2;
        }
        for (i = start; i < argc; i++) 
            print(argv[i]);
    }
    if (newline)
        printf("\n");
}

short main(argc, argv) 
short argc; 
char  *argv[];
{   echo(arge, argv); 
    exit(0);
}

###############################################
# Listing MAKE, Datei: MAKE_2                 #
# Modifikationsdatum : 04-Mär-90              #
# Abhängigkeiten     : -                      #
###############################################

COMPILER  = \megamax\ccom.ttp -I\megamax\headers 
LINKER    = \megamax\ld.ttp \megamax\init.o 
PROGRAMM2 = cat.ttp echo.ttp grep.ttp more.ttp \ 
            random.ttp sort.ttp 
MODUL2    = atom.o atom2.o expand.o

make_2 : $(PROGRAMM2) $(MODUL2)

###############################################
# Teil 2 - Text                               #
###############################################

cat.ttp : cat.c atom.h atom.o atom2.h atom2.o \ 
          expand.h expand.o 
        $(COMPILER) cat.c
        $(LINKER) cat.o atom.o atom2.o expand.o - lc \
                  -o cat.ttp

echo.ttp : echo.c
        $(COMPILER) echo.c 
        $(LINKER) echo.o -lc -o echo.ttp

grep.ttp : grep.c atom.h atom.o atom2.h atom2.o \ 
           expand.h expand.o 
        $(COMPILER) grep.c
        $(LINKER) grep.o atom.o atom2.o expand.o -lc \
                  -o grep.ttp

more.ttp : more.c atom.h atom.o atom2.h atom2.o \ 
           expand.h expand.o 
        $(COMPILER) more.c
        $(LINKER) more.o atom.o atom2.o expand.o -lc \
                  -o more.ttp

random.ttp : random.c atom2.h atom2.o 
        $(COMPILER) random.c 
        $(LINKER) random.o atom2.o -lc -o random.ttp

sort.ttp : sort.c atom.h atom.o atom2.h atom2.o \ 
           expand.h expand.o
        $(COMPILER) sort.c
        $(LINKER) sort.o atom.o atom2.o expand.o -lc \
                  -o sort.ttp

expand.o : expand.c
        $(COMPILER) expand.c

atom.o : atom.c
        $(COMPILER) atom.c

atom2.o : atom2.c
        $(COMPILER) atom2.c

Dirk Brockhaus

---

---