====================================================================== Dokumentation zu "Patterns" Version 1.1 Autor: Nicolas Benezan, Postwiesenstr. 2, D7000 Stuttgart 60 ====================================================================== Übersicht ­­­­­­­­­ * Kopierrecht * Umfang des Projekts * Beschreibung * Demo- / Testprogramm Kopierrecht ­­­­­­­­­­­ Das komplette Projekt (Quelltext, Dokumentation und Objectcode) ist Public Domain Software. Es darf beliebig kopiert und verbreitet werden solange... * mein Name und dieser Kopierrechtshinweis erhalten bleiben, * die Vollständigkeit des ganzen Projekts gewährleistet ist, und * mit dem Vertrieb dieser Software kein Gewinn erwirtschaftet wird. Die Kommerzielle Nutzung ohne meine ausdrückliche schriftliche Genehmigung ist untersagt (über Gewinnbeteiligung läßt sich reden). W i c h t i g: Dies gilt insbesondere auch für "schwarze Schafe" der "PD"-Versandhäuser, die ganz offensichtlich Gewinn machen, was z.B. durch ganzseitige Anzeigen in Zeitschiften erkennbar ist. Verbesserungsvorschläge sind stets willkommen. Falls Sie Veränderungen am Programm vornehmen, dokumentieren Sie diese bitte gut verständlich. Es würde mich freuen, wenn Sie mich über größere Veränderungen oder Erweiterungen in Kenntnis setzen würden. (c) 1988 by Nicolas Benezan. Umfang des Projekts ­­­­­­­­­­­­­­­­­­­ Das komplette Projekt "Patterns" beinhaltet folgende Dateien: * Patterns.dok Diese Dokumentation * Patterns.def Quelltext der Definition * Patterns.mod Quelltext der Implementation * TestPatterns.mod Quelltext des Demoprogramms * TestPatterns Ausführbare Demo (Stand 02.Jan.1990) Beschreibung ­­­­­­­­­­­­ Das Modul exportiert eine Prozedur, die prüft, ob ein String (z.B. Dateiname) auf ein bestimmtes Muster paßt. Dabei wird Groß- und Kleinschreibung unterschieden. Ist dies nicht erwünscht, müssen alle Buchstaben des zu testenden Strings UND des Musters in Großbuchstaben gewandelt werden (z.B. mit Str.CapString). Die derzeitige Version beherrscht lediglich folgende Jokerzeichen: "?": steht für ein beliebiges Zeichen "*": steht für eine Folge von 0 oder mehr beliebigen Zeichen Dies entspricht nicht den AmigaDos- oder ARP-Befehlen, die auch Klammerung, Alternativen ("|") und Wiederholungen ("#") zulassen, ist aber in den meisten Fällen ausreichend. Die Joker dürfen ohne Einschränkungen auch beliebig gemischt verwendet werden. Beispiele: Muster: paßt auf: * alles ???? alle Strings mit 4 Zeichen ???* alle Strings mit 3 oder mehr Zeichen *.info alle Strings mit der Endung ".info" *x* alle Strings die mindestens ein "x" enthalten *x*x* alle Strings die mindestens zwei "x" enthalten *x?*x* wie oben, mit der Einschränkung, daß ein Zeichen Abstand dazwischen sein muß ???.* alle Strings mit 3 Zeichen und einer beliebigen Endung beginnend mit "." *???.def alle Strings mit 3 oder mehr Zeichen und der Endung ".def" Die Überprüfung erfolgt übrigens mit einem Backtracking-Algorithmus, auch wenn dies nicht sofort erkennbar ist. Das Backtracking steckt in der doppelten Rekursion im folgenden boolschen Ausdruck in der Prozedur Test: |"*": RETURN Test (PatPos + 1, StrPos) OR (StrPos < MaxStr) AND Test (PatPos, StrPos + 1) (doppelt rekursiv, weil die Prozedur sich zweimal selbst aufruft). Man beachte, daß die zweite Rekursion dabei jedoch nur auftritt, wenn die erste nicht erfolgreich war. Das zweite Argument eines boolschen "OR"-Ausdrucks wird nämlich nur ausgewertet, wenn das erste FALSE ist, während das zweite Argument eines boolschen "AND"-Ausdrucks nur ausgewertet wird, wenn das erste TRUE ist. Alles logo ?!?! Zur Veranschaulichung ein Beispiel: Muster: String: *TEST* PATTERNTEST.MOD Würde man lediglich Zeichen für Zeichen nacheinander prüfen, würde das "TE" des Musters bereits auf das "TE" von "PATTERN" passen. Dies führt jedoch in eine Sackgasse, da das folgende "S" des Musters nicht auf das "R" von "PATTERN" paßt. Jetzt könnte jemand sagen: Wo liegt das Problem? Man braucht doch nur mit der Prozedur Strings.Occurs nach "TEST" zu suchen! Aber was macht man, wenn das Muster "TE?T" lautet. Ok, man könnte sich eine Suchprozedur schreiben, die das "?" berücksichtigt, aber dann artet das ganze doch extrem ins Komplizierte aus. Im Prinzip programmiert man dann nichts anderes als ein iteratives Backtracking, und das ist bekanntlich kompliziert und unübersichtlich. Theoretisch könnte man die Prozedur noch optimieren, indem man die sogenannte "tail recursion", also Rekursion am Ende der Prozedur eliminiert. Da das ganze dann aber noch schwieriger zu durschauen wäre, überlasse ich dies jenen Leuten, die meinen, sich wegen 50ns Geschwindigkeitsvorteil einen Fuß ausreißen zu müssen. Demo- / Testprogramm ­­­­­­­­­­­­­­­­­­­­ Das Programm "TestPatterns" ist eine einfache Demo für die Benutzung von Patterns. Es erlaubt die Eingabe eines Musters und beliebig vieler Strings, die mit dem Muster verglichen werden. Beendet wird die Demo mit der eingabe eines leeren Strings, der übrigens auch noch mit dem Muster verglichen wird. Vorsicht mit Strings, die Leerzeichen enthalten (liegt an ReadString() )! Zum Schluß... ­­­­­­­­­­­­­ noch eine Anmerkung: Angeblich soll es jemand geschafft haben, eine Patternmatching-Prozedur zu schreiben, die unendlich viel UMSTÄNDLICHR, UNÜBERSICHTLICHER und LÄNGER ist, als die hier beschriebene und zu allem Überfluß auch noch die EINSCHRÄNKUNG hat, Wildcards NUR am ANFANG oder am ENDE des Musters zu erlauben. Gerüchten zufolge, soll derjenige es sogar geschafft haben, daß sein Programm, in dem diese Prozedur enthalten ist, auf einer der letzten Amok-Disks veröffentlicht wurde. Mein Rat: Kaufen Sie sich einen Strick und erschießen Sie sich, wo das Wasser am tiefsten ist.