Turbo Toolbox/Turbo_Toolbox.iso/spezial/01/pattern/pattern.doc

Text File | 1988-11-03 | 13.2 KB | 338 lines

Eine Pattern-Matching-Toolbox für Turbo Prolog

Im Englischen sind die Begriffe pattern und match vieldeutig und
flexibel: ein pattern ist ein Muster, ein Modell, eine Schablone;
match bedeutet vergleichen, gegenüberstellen oder passen. Pattern
Matching ist das Vergleichen eines Gegenstandes mit einem Muster
-zum Beispiel der Vergleich eines Stückes farbigen Stoffes mit
einem Muster der Farbe Kobaltblau. Im EDV-Kontext ist der mit
einem bestimmten zu vergleichende Gegenstand meist ein String,
also der Datentyp, der der menschlichen Schnittstelle am nähesten
steht. Eine typische Fragestellung ist: entspricht ein gegebener
String dem Muster einer Zahl? eines Bezeichners? eines Filenames?
einer Anweisung? eines logischen Ausdrucks? usw. Man begegnet
solchen Fragestelllungen meist bei der Verarbeitung von
Eingabestrings, natürlichsprachigen Texten sowie im Rahmen einer
Scanner- oder Parserumgebung.

Man halte sich vor Augen, wie ähnlich gelagerte Aufgaben durch
eine konventionelle prozedurale Programmiersprache, etwa Pascal,
gelöst werden. Wie kann beispielsweise ein String als
DOS-Filename identifiziert werden? Vermutlich schreibt man sich
hierzu eine kleine Funktion oder Prozedur, in der eine Schleife
jedes Zeichen des Strings abtastet und überprüft, ob es zum
zulässigen Zeichenbereich gehört. Das kann solange gehen, bis man
über acht Zeichen hinausgerät, oder an das Ende des Strings oder
auf einen Punkt stößt. Passiert letzteres, läßt man eine neue
Schleife laufen, die die jetzt mutmaßlich folgende Extension
Zeichen für Zeichen in ähnlicher Weise durchkontrolliert. Einige
Umsicht ist erforderlich, damit alle Fehlschlagsbedingungen auch
richtig erfaßt werden.

Der Mensch selbst denkt nicht so prozedural und atomistisch. Wir
haben wahrscheinlich ein allgemeines Muster eines DOS-Filenames
in unserem Kopf, das etwa folgendermaßen umschrieben werden
könnte:

    ein eins bis acht Zeichen langer String aus einem bestimmmten
    Zeichenbereich, dem ein Punkt und eine bis zu drei Zeichen
    lange Extension folgen kann.

Der Wunsch, solche Muster als besondere Datenstrukturen zu
formulieren und damit im Sinne einer einfachen und natürlicheren
Programmierung zu nutzen, liegt nahe. Das erste zusammenhängende
Konzept integrierter Pattern-Matching-Werkzeuge wurde Ende der
sechziger Jahre durch die Programmiersprache SNOBOL vorgestellt.
Wer einen kurzen Einblick in die Musterstrategien von SNOBOL
vermittelt haben will, kann James F: Gimpels Artikel "Text
Prozessing in SNOBOL4", in Byte 11.2(1986) nachlesen. Hier soll
im weiteren gezeigt werden, in welcher Weise einige der
SNOBOLschen Konzepte für die im ganzen leichter handhabbare und
übersichtlichere Sprache PROLOG praktisch genutzt werden.





Das match-Prädikat

Der TURBO-PROLOG-Code, der hier vorgestellt wird, bildet eine
Toolbox, die im wesentlichen nur ein Werkzeug enthält: das
Prädikat match. Aber dieses Prädikat ist ein Vielzweckwerkzeug: in
seinem zweiten Argument kann eine ganze Reihe der in SNOBOL
bekannten Muster-Grundbausteine("pattern primitives") für die
Erstellung komplexer Muster kombiniert werden.
match ist wie folgt definiert:

  match(SubjectString,PatternList,Matchedlist) (i,i,o)

Es wird weitgehend die Termonologie von SNOBOL beibehalten; daher
die Bezeichnung des zu vergleichenden Gegenstandes als
"SubjectString". Das Muster ist eine "PatternList", die sich aus
ein oder mehreren "pattern Primitives" zusammensetzt - dazu
gleich mehr. Die "MatchedList" enthält die Teile des
"SubjectStrings", die den in der "PatternList" genannten
Musterbausteinen entsprechen. Match vergleicht die
Subjekt-Zeichenkette mit einem als Liste formulierten Muster;
wenn es zu einer Entsprechung kommt, dann werden die passenden
Teile in Aufgabenliste eingereiht; ansonsten schlägt das Prädikat
fehl.
Hier ein Beispiel:

   match("if x<10 then stop := true;",[break([":="])],X).

Der Subjekt-String ist eine Zeile aus einem Pascal-Programm. das
Muster besteht aus dem einzelnen Grundbaustein "break", einem
Funktor, der eine Stringliste als Argument mit - in diesem Fall -
der einzelnen Konstante ":=" enthält. Dieses Muster paßt auf
beliebige Subjekt-Strings, die ein ":=" aufweisen. Paßt das
Muster (wie hier), so wird der vor dem Schlüsselstring ":="
liegende Teilstring in die "MatchedList" eingereiht. Läßt man
KIT.PRO laufen und gibt obige Goal, so erscheint die Lösung

   X = ["if x<0 then stop"]

Man kann break also benutzen, ein Muster zu konstruieren, zu dem
jeder Teilstring bis zu einer bestimmten Schlüsselsequenz paßt.
Werfen wir einen Blick auf ein paar weitere solcher Bausteine.


"any(Stringlist)" klärt die Frage, ob der Subjekt-String an der
gegenwärtigen Stelle einen der in "Stringlist" aufgeführten
Teilstrings enthält. Beispiel:

   match("if x<0 then stop := true;", [any(["<=",":="])], X)

(enthält der Subjekt-String am Anfang einen Substring der Form
"<=" oder ":=" ?) Die Antwort lautet nein, "No Solution", weder
:= noch <= steht am Anfang des Subjekt-Strings ( der
gegenwärtigen Stelle). Jetzt versucht man die Kombination von
break and any:

  match("if x<0 then stop := true;",
      [break([":=","<="]); any (["<=",":="])], [_,Operator]).

Operator = ":=" wird PROLOG auf dieses Goal hin melden und damit
eine Antwort auf die Fragen "Kommt einer der genannten Operatoren
vor? Welcher erscheint zuerst?" geben.


"notany(chartlist)" überprüft, ob bestimmte Zeichen an einer
bestimmten Stellle im Subjekt-String nicht vorkommen. Im folgenden
Beispiel wird eine Stelle identifiziert, an der kein Spatium
hinter einem Komma steht:

   match("alles rennet,rettet";[break([","], notany([' '])], X).


"span(Stringlist)" akzeptiert jede Zeichenkette, die aus den in
"Stringlist" enthaltenen Zeichen besteht. Die Musterüberprüfung
wird beim Erreichen eines Zeichens, das nicht in "Stringlist"
vertreten ist, oder beim erreichen des Endes vom Subjekt-String
erfolgreich abgeschlossen. Auszuprobierendes Beispiel:

   match("0110 xyz", [span(["0", "1"])], [Binärzahl]).


"len(N)" ist ein Grundmuster, das jeden Teilstring der Länge N
abdeckt:

    match("512.Anton"; [len(3)], [laufende Nummer]).


"rtab(0)"  deckt alles bis zum Ende des Subjekt-Strings ab:

    match(512.Anton", [len(5), rtab(0)], [Anfang,Rest]).


"rpos(0)" überprüft, ob das Muster den gesamten Subjekt-String
erfaßt:

    match("512.Anton", [len(10), rpos<(0)], _).


"lit(String)" überprüft, ob der Subjekt-String einen bestimmten
Teilstring an der gegenwärtigen Stelle enthält:

    match("Anton", [len(2), lit("ton")], _).


"bal" überprüft, ob ein ausgeglichenes Klammerverhältnis bis zu
einer bestimmten Stelle vorliegt. Das folgende Beispiel bricht
einen Klammerausdruck auf:

    match("f(g(h))", [break(["("]), lit("("), bal, lit(")"],
                   [Funktor, _, Argument, _]).






Arbeiten mit der Toolbox

Man beginnt gewöhnlich damit, daß man sich die Datei KIT.PRO in
den Work-File kopiert, umbennet und nn je nach Problemstellung
modifiziert. Man kann auch einfach KIT-PRO am Anfang des eigenen
Programms inkludieren (dies tun die Beispielprogramme BP1 und
BP2). KIT-PRO selbst inkludiert die drei eigentlichen
Toolbox-Dateien Match.1, Match.2 und Match.3 und wird damit zu
einem lauffertigen Programm, das ohne weitere Deklaration über
das match-Prädikat verfügen kann. Ein einzelnes
Dienstleistungsprädikat - literal(symbol,stringlist) - wird
explizit aufgeführt: es enthält in seinen Klauseln die üblichen
Unterteilungen des Zeichensatzes. Dies kann erhebliche Arbeit
sparen. Wenn es etwa darum geht, ein Muster für eine
alphanumerische Sequenz zu erstellen, dann könnte man sich zwar
die Mühe machen zu schreiben:

    match(string, span(["A", "B" <...etc., alle Buchstaben und
      Zahlen einzeln aufgeführt...>"8", "9"]), X)


Aber mit Hilfe von "literal" geht's auch so:

    literal(alfanums, A),
    match(String, [span(A)], X)


Um das Erscheinungsbild des match-Prädikats zu entlasten,
empfiehlt es sich besonders für komplexe Mustwer, ein eigens
Musterprädikat wie

    pattern(symbol, patternlist)

zu definieren. Eine mögliche pattern-Klausel mag dann so
 aussehen:

     pattern(integer, [span(Digits)]) :-
       literal(digits, Digits).

Dies ermöglicht überschaubare Subgoals wie

     pattern(integer, IntegerPattern),
     match(Eingabe, IntegerPattern, [Betrag]).

Gegebenenfalls lassen sich aufeinander aufbauende, komplexere
Muster erstellen:

     pattern(integer, [span(Digits)]):-
        literal(digits, Digits).
     pattern(real, [Int| X]) :-
        pattern(integer, [Int]) append([lit(".")], [Int], X).
     pattern(exponential, X):-
        pattern(real, R),
        pattern(integer, Exponent),
        append(R, [lit("E")| Exponent], X).


Die zusammmengesetzten Muster vom Typ real und exponential
greifen hier auf das/die vorher definierte(n) Muster zurück.



Anwendung: Ein simpler Scanner (BP1.PRO)

In seinem Buch Algorithmen und Datenstrukturen(Stuttgart, 1983,
S. 45-47) skizziert Niklaus Wirth einen in Pascal formulierten
Scanner, der aus einem Zeichenstrom Sprachsymbole wie Bezeichner,
Zahl, und die Operatoren :=, <= und >= identifiziert. BP1.PRO
löst die gleiche Aufgabe unter Zuhilfenahme der Pattern-Matching-
Toolbox.


Der Mini-Scanner verlangt eine beliebige Zeileneingabe des
Benutzers und identifiziert dann alle Sprachsymbole, die einem
der in den pattern-Klauseln definierten Muster entsprechen.
Anders als in Wirth's PASCAL-Code, in dem sich die Lösung mit
Hilfe des üblichen Geflechts von Bedinguns- und
Kontrollstrukturen gestaltet liegt im Prolog-Code der Schwerpunkt
eher statisch auf der Definition von vier Grundmustern. Das
komplexeste der vier Muster, das Bezeichner-Muster, soll zur
Erläuterung herausgegriffen werden:

   pattern(identifier,
      [span([""," "]) any(letter), span([""|Alfa]), rtab(0)]):-
      literal(letters,letter), literal(alfanums,Alfa).


Das Muster umfaßt nicht den eigentlichen Bezeichner, sondern auch
einen etwaigen linken und rechten Kontext. span([""," "]"
überbrückt alle etwaigen führenden Leerzeichen. Der Einsatz des
Nullstrings (der auch in any und break vorkommen kann) liefert
die Möglichkeit, ein Element als optional zu kennzeichnen. Wegen
des Nullstrings schlägt das obige span auch dann nicht fehl, wenn
die Zeile mit Leerzeichen beginnt. any(letter) erfaßt einen
einzelnen Buchstaben, der als erstes Zeichen eines Bezeichners
notwendig ist. span([""|alfa]) läßt sich lesen als "Null oder
alfa", also eine optionale alphnumerische Sequenz. rtab(0) wird
abschließend benutzt, um den Rest der Zeile für eine spätere
Variable zu erfassen. Der Bezeichner selbst läßt sich aus den
Gegenwerten für das zweite und dritte Element einer
"MatchedList" wieder zusammensetzen, und so wird das auch in den
entsprechenden classify-Klausel prakziziert.


Mehrdeutige Muster(BP2.PRO)

Die eigentliche Stärke der Toolbox wird aber erst deutlich, wenn
mit mehr oder komplexeren Mustern zu rechnen ist. Dann schwillt
ein vergleichbarer Pascal-Code überproportional an, während im
Prolog-Code eventuell lediglich die Zahl der pattern-Klauseln
zunimmt.

BP2.PRO soll demonstrieren, mit welcher Leichtigkeit
unterschiedlichste Muster zusammengestellt werden können. Statt
einer ganzen Zeile wird hier lediglich ein einzelnes mutmaßliches
Sprachsymbol angefordert, und die Idendifikation des
Eingabestrings erfolgt einfach über den Identifikator des
passenden pattern-Prädikats. Wird ein mehrdeutiges Sprachelement
eingegeben, so soll auch eine Mehrfachklassifikation erfolgen -
20 soll z.b. sowohl als Integer- wie als mögliche Hexzahl
identifiziert werden. Die folgende Übersicht zeigt ein
repräsentatives Korpus mit der jeweils gewünschten
Identifikation:

Sprachelement          verlangte Identifikation
-----------------------------------------------
var12                  identifier
+24                    integer
1F, 20H. $20           hex
1001b                  binaer
-100.45, 6.7E-6        real
'Jim Knopf'            literal
:=, <=                 operator
John                   name, identifier
20                     integer, hex
FF                     hex, identifier
1001                   integer, hex, binaer
!                      -


Diese Variationsvielfalt nähert sich Verhältnissen in
natürlichsprachigen Texten an und ist sicher nur mit äußerster
Geduld prozedural zu bewältigen. BP2.PRO zeigt demgegenüber, wie
die entsprechenden Muster mit Hilfe der Toolbox vergleichsweise
mühelos zu realisieren sind.




BP3.PRO (6 Prädikate/50 Zeilen) zeigt am Beispiel von
Dos-Zugriffspfaden und -Filenamen die Behandlung von Mustern mit
iterativen Bestandteilen. BP4.PRO (5 Prädikate/60 Zeilen) offeriert
eine Lösung des Standarsproblem "römische Zahlen" (beide
Richtungen) BP5.PRO (12 Prädikate/260 Zeilen) ist ein
Pretty-Printer, mit dem man versuchen kann, Pascal-Listings in
die richtige Form - einschließlich großgeschriebenen
Schlüsselwörtern und korrekt eingerückten Kontrollstrukturen - zu
bringen. BP6.PRO (12 Prädikate/180 Zeilen) schließlich
demonstriert einen Algorithmus zur Validierung propossitionaler
Formeln vom Typ "or(to be, not(to be))", ohne dabei auf eine
Wahrheitstabelle zurückzugreifen.



(Manfred Jahn)