Das Programmpaket kann mit folgenden Verfahren genutzt werden

In einem Delphi oder FreePascal Programm mit Hilfe der Bibliothek(Unit) Mysnobol

Dazu werden folgende Dateien benutzt mysnobol.pas mystring.pas myintarray.pas

Die Bibliotheken wurden getestet mit Delphi6, Delphi10 und Lazarus bzw. Freepascal.

Ferner können die Pattern mit der Anwendung SnobolIDE genutzt werden. Hier kann man ein Suchpattern eingeben, das dann durch das Ersetzungpattern ersetzt wird.

Diese Datei wird zweckmäßigerweise in ein Verzeichnis entpackt auf das auch Schreibzugriffe möglich sind, z.B <benutzer>\appdata\snobol

Zusammenfassung

Es werden Verfahren zur Texterkennung und --Bearbeitung mit Hilfe von an die Programmiersprache SNOBOL angelehnte Klassen zum Pattern-Matching beschrieben. Die Klassen sind gegenüber dem SNOBOL Vorbild zum Teil abgeändert, um eine größere Effizienz zu erzielen.

SNOBOL 4 (String Oriented symbolic Language number 4) ist die vierte und letzte Ausprägung einer Reihe von Programmiersprachen mit dem Zweck der Manipulation von Zeichenketten. Diese Sprachen wurden zwischen 1962 und 1967 in den Bell Laboratories von AT&T durch David J. Farber, Ralph E. Griswold und Ivan P. Polonsky entwickelt.

Ein wesentliches Unterscheidungsmerkmal zu den seinerzeit gebräuchlichen Programmiersprachen ist die Existenz von Mustern als "erstklassigem" Datentyp, d. h. einem Datentyp, dessen Wert in jeder Weise manipuliert werden kann wie in anderen Programmiersprachen, sowie von Operatoren zur Verkettung und Manipulation von Mustern. Zeichenketten, die zur Laufzeit erzeugt werden, können als Programm behandelt und ausgeführt werden. Ein Muster in SNOBOL 4 kann sehr einfach, aber auch sehr komplex aufgebaut sein. Ein einfaches Muster ist z. B. nur eine Zeichenkette wie "ABCD". Ein komplexes Muster kann hingegen eine große Struktur sein, die z. B. die vollständige Grammatik einer Computersprache beschreiben kann. (Wikipedia)

In den 1970er und 1980er Jahren war SNOBOL 4 als Sprache zur Manipulation von Texten weit verbreitet. In den vergangenen Jahren hat die Popularität allerdings abgenommen, weil neuere und effizientere Sprachen wie Awk und Perl zur Zeichenkettenbearbeitung mit regulären Ausdrücken beliebter wurden. Im Gegensatz zu Regex bei Perl erlaubt SNOBOL jedoch auch die Erkennung von Klammerstrukturen, die mit regulären Ausdrücken nicht zu beschreiben sind.

(1) Pattern-Matching

Beim Pattern-Matching in Texten beschäftigt man sich mit der Definition von Testmustern (Pattern), die durch Kombination in der Lage sind, frei vorkommende Teststrukturen zu beschreiben. Die Muster und ihre Kombinationen sollen durch geeignete Algorithmen erkannt werden können. Solche Patterns sind Bestandteile vieler Programmier-- und Skript-Sprachen. Die Sprache JAVA kennt z.B. die Klasse tokenizer, wo ein Text anhand von Trennzeichen in Teile zerlegt werden kann. Die Skriptsprache PERL hat mit ihren regulären Ausdrücken (regex: Perl regular expression) ebenfalls ein recht mächtiges Hilfsmittel Pattern zu beschreiben und zu erkennen. Eine der ersten Sprachen, gerade auf diese Art der Textverarbeitung ausgerichtet, war SNOBOL. Der im Folgenden beschriebene Ansatz benutzt im Wesentlichen die in SNOBOL definierten Patterns. Er definiert jedoch nicht eine neue Programmier - oder Skriptsprache, sondern die Implementation erfolgt über in einer vorhandenen Sprache (PASCAL-DELPHI ) geschriebene Klassen und Funktionen. Dadurch kann die Methodik in jedem Programm, das in diesen Sprachen geschrieben ist, genutzt werden. Eine Implementierung z.B. in Java oder C++ wäre ebenfalls möglich.

Patterns können u.a. sein:

• Strings einer vorgegebenen Länge

• alle Zeichenfolgen bis zu einem speziellen Zeichen

• die längste Folge von Blanks

• beliebige Wiederholungen eines Strings

• Strings balanciert bezüglich von vorgegeben Klammersymbolen

• beliebige Strings

Aus den Basis-Patterns können durch Alternativen (ALT) und Folgen (CAT) komplexere Pattern gebildet werden.

Beispiel:

p:=alt(['be','bea','bear']);

q:=alt(['ro','roo','roos']);

r:=alt(['ds','d']);

s:=alt(['ts','t']);

pa:=alt([pat([p,r]),pat([q,s])]);

pa match jeden der folgenden Strings:

beds rots

bed rot

beads roots

bead root

beards roosts

beard roost

Eine Prozedur zur Durchführung des Pattern-Matching ist:

function mat(var s:string;ab:integer;const pat:tpattern;var apos,alen:integer):boolean;

overload;

Es wird im String s ab der Position ab versucht das Pattern pat zu matchen. Ist dies erfolgreich wird die Position und die Länge des gematchten String auf apos und alen zurückgegeben. Bei Matching gibt es zwei Varianten:

Nach anchor(1) muss der Pattern im String exakt bereits ab der Position gematcht werden. Nach anchor(0) kann der Pattern irgendwo im String s ab der Position gematcht werden.

Das Pattern Matching kann man sich vorstellen, dass eine Nadel durch die passenden Patterns geführt wird. Kommt man an einer Stelle nicht mehr weiter, wird sie zurückgezogen und es wird bei dem vorangegangenen Pattern die nächste Alternative genommen. Existiert dort keine mehr, wird bei dem davor liegenden Pattern die nächste Alternative genommen. Entweder kann das gesamte Pattern gematcht werden oder beim ersten Pattern gibt es keine Alternative mehr.

Dies soll an folgendem Beispiel erläutert werden:

Das Pattern

br:=pat([alt(['b','r']),alt(['e','ea']),alt(['d','ds'])]);

soll getestet werden gegen den String: 'reads'

Testet man das obige Pattern pa gegen den String roosts so benötigt man 11 Schritte.

Der Aufwand kann also im ungünstigsten Fall exponentiell mit der Länge des String steigen. In vielen fällen kann man jedoch Pattern nutzen, die keine Alternativen haben, z.B. Suchen eines Pattern. Ferner wird für alle Pattern die Mindestlänge der matchenden String berechnet. Dadurch können Alternativen von vornherein ausgeschlossen werden. Auch wird versucht möglichst mit Klassen auszukommen, die keine oder nur wenige Alternativen haben. Am ungünstigsten ist das Pattern arb, das jeden String erkennt. Mit Hilfe des Patterns find (siehe weiter unten) kann hierauf meist verzichtet werden.

Implementiert wird der Suchalgorithmus, indem für jede Patternklasse eine Methode matchfirst existiert.

function matchfirst(astr:string;apos,arlen:integer;var alt,len:tobject ) :Boolean;

Die Funktion versucht den String astr ab der Position apos zu matchen. arlen gibt an, welche Länge die nachfolgenden Patterns mindestens haben. Auf den Parametern alt und len wird behalten welche Alternative erkannt wurde und wie lang der gematchte Teilstring ist. Dies wird benötigt zum Zurücksetzen und um die nächste Alternative auszuwählen.

Das Erkennen der nächsten Alternative erfolgt mit der Methode:

function matchnext(astr:string;apos,arlen:integer;var alt,len:tobject ) :Boolean;

Entsprechend dem Parameter alt wird versucht die nächste Alternative zu erkennen. Gibt es bei dem Pattern keine Alternative, so liefert matchnext immer false.

Eine Beschreibung der Pattern und ihre Benutzung in einigen Beispielen findet sich in snobol.pdf