ruby-mine

von WoNáDo

Hier nun die Fortsetzung von Teil 0.0. Offen blieben noch zwei Fragen im Zusammenhang mit der Strukturbeschreibung: "In welcher Form kann man so etwas beschreiben?" und "Wie kann ich überprüfen, ob ein Text der Beschreibung genügt?".

Teil 0.1 versucht Antworten auf die erste Frage zu geben, ohne dabei zu sehr ins Detail zu gehen. Diese Themen werden umfangreich in der Literatur zur Theoretischen Informatik und zum Thema Compilerbau behandelt.

Also los...

Frage 2: In welcher Form kann man so etwas beschreiben?

Eine Form habe ich schon benutzt - die Umgangssprache. Diese Beschreibungssprache hat zwar den Vorteil, dass sie ohne zusätzlichen Lernaufwand verständlich ist, aber die Nachteile überwiegen. Zuerst einmal ist jede natürliche Sprache zu ungenau. Das haben Mathematiker schon vor langer Zeit erkannt. Hinzu kommt noch, dass eine Beschreibung komplexerer Strukturen sehr lang werden kann und damit unübersichtlich wird. Ein weiterer Nachteil besteht darin, dass natürliche Sprachen normalerweise keine Klammerstrukturen enthalten. Iterationen lassen sich daher nur sehr umständlich durch Satzkonstruktionen wie "Die in den letzten vier Sätzen beschriebenen Elemente dürfen in dieser Reihenfolge beliebig oft auftreten." ausdrücken. Der in der Praxis entscheidende Nachteil ist jedoch, dass man bei natürlichsprachlichen Strukturbeschreibungen nur in ganz einfachen Fällen ein Programm einsetzen kann, welches automatisch überprüft, ob vorgegebene Texte der Beschreibung entsprechen. Es gibt also gute Gründe formale Sprachen und Methoden zu suchen, die sich für derartige Strukturbeschreibungen eignen.

Schon in den 1960er Jahren wurde eine derartige Sprache entwickelt, die sowohl Beschreibungskonstruktionen, als auch eine Auswertungmaschinerie beinhaltete - Snobol, bis heute als Snobol4 noch immer benutzt (Ende der 1980er Jahre erlebte diese Sprache eine richtige Renaissance im PC-Umfeld). Die Beschreibungssprache bestand aus Musterfunktionen, die aneinandergefügt, durch Klammern gruppiert und als Alternativen dargestellt werden konnten. Ich will hier nicht auf die Details eingehen, sondern verweise auf die Snobol4-Seite, das PDF of "Green Book" (THE SNOBOL4 PROGRAMMING LANGUAGE) und auf Manuals - das SPITBOL Manual (PDF), sowie das Vanilla SNOBOL4 Reference Manual und das Vanilla SNOBOL4 Tutorial. Ein Beispiel, welches das über die Snobol4-Seite verfügbare Free 16-bit SNOBOL4+ for DOS in der interaktiven Form benutzt, möchte ich jedoch zeigen (welches Snobol4 für Linux existiert, weiß ich nicht).

>snobol4 code.sno

SNOBOL4+          Version 2.24.    8087 present.
(c) Copyright 1984,1998 Catspaw, Inc., Salida, Colo.  All Rights Reserved.

No errors

Enter SNOBOL4 statements:
?     alpha = "abcdefghijklmnopqrstuvwxyz"
Success
?     num   = "0123456789"
Success
?     int   = ("+" | "-" | "") span(num)
Success
?     var   = any(alpha "_") (span(alpha num "_") | "")
Success
?     optbl = span(" ") | ""
Success
?     ass   = pos(0) optbl var optbl "=" optbl int optbl rpos(0)
Success
?     "v235=567" ass
Success
?     "v45_pq77 = -2345" ass
Success
?     "no-var = 666" ass
Failure

Ich definiere hier ein paar Muster, welche Zahlen (int), Variablen (var) und Zuweisungen (ass) erkennen. Anschließend wende ich diese Muster an. Wer alle Details wissen will, sollte in den angegebenen Links nachschauen. Da Snobol4 hier nur eine Randbemerkung ist, möchte ich nicht weiter darauf eingehen.

Bevor wir nun langsam das Ziel - reguläre Ausdrücke - ansteuern können, will ich noch auf einige Strukturarten zu sprechen kommen. Ich nehme die zwei Texte "Eine Schlange lebt von Erdbeereis." und "Peter (der ältere (23 Jahre) Bruder) und Karla (die fünfte Frau des Vaters) gehen spazieren." und mache mir Gedanken über mögliche Strukturbeschreibungen. Wenn ich mal jede Semantik außer lasse, könnte der erste Fall durch "Eine Folge von durch Leerzeichen getrennten Worten, die mit einem Punkt abgeschlossen wird." beschrieben werden. Der zweite Fall ist unangenehmer, weil es offensichtlich auf die Klammern ankommt. Ich will ja nur dann einen Text als korrekt akzeptieren, wenn die Zahl der öffnenden Klammern gleich der Zahl der schließenden ist. Wer Spaß daran hat, kann mal versuchen eine umgangssprachliche Strukturbeschreibung für derartige Sätze zu finden.

Hier kümmern wir uns aber nicht weiter um diese Strukturen, weil sie mit echten regulären Ausdrücken nicht beschrieben werden können. Dafür werden mächtigere Beschreibungsmittel benötigt, wie kontextfreie Grammatiken, die nicht Gegenstand dieser Reihe sind.

Ich habe im letzten Absatz etwas von echten regulären Ausdrücken geschrieben. In den meisten Programmiersprachen werden erweiterte reguläre Ausdrücke benutzt, weil die erheblich ausdrucksstärker sind. Diese Ausdrucksmächtigkeit gibt es jedoch leider nicht geschenkt. Dazu später mehr in Teil 0.2 bei der Beantwortung der Frage "Wie kann ich überprüfen, ob ein Text der Beschreibung genügt?".

Wir definieren jetzt erst einmal die echten regulären Ausdrücke als Strukturbeschreibungssprache. Ich orientiere mich hier sofort an der auch in Ruby üblichen Schreibweise, ohne näher auf die mathematischen Grundlagen einzugehen (um die leere Menge als gültigen regulären Ausdruck kümmere ich mich auch nicht). Reguläre Ausdrücke können folgendermassen definiert werden:

• Das leere Wort ist ein regulärer Ausdruck.
  Bitte beachten - ich rede vom leeren Wort, nicht von der leeren Menge. Dieses leere Wort entsteht dadurch, dass ich nichts hinschreibe. Das mag seltsam klingen, es geht jedoch auch in Ruby.

  "abc".match(//)
  "abc".match(/5|/)

  Der zweite Fall beschreibt sogar eine manchmal benutzte Variante um optionales Vorkommen zu beschreiben. Was hier steht heisst umgangssprachlich "Die Ziffer 5 oder nichts". In Teil 6 dieser Reihe taucht dieser Fall auch auf, und zwar im Zusammenhang mit regulären Ausdrücken, die versehentlich immer erfolgreich anwendbar sind, weil sie auch den Leerstring erkennen.


• Jedes Zeichen des zugrunde liegenden Alphabets ist ein regulärer Ausdruck.
  Das ist wohl klar, wobei natürlich nur Zeichen vorkommen dürfen, die im Rahmen der eingestellten Codierung zugelassen sind. Das muss ab Ruby 1.9 immer beachtet werden, weil viele verschiedene Codierungen zugelassen sind.


• Wenn A und B reguläre Ausdrücke sind, dann ist auch AB ein regulärer Ausdruck.
  Hiermit wird beschrieben, dass hintereinander geschriebene reguläre Ausdrücke einen neuen gültigen regulären Ausdruck ergeben. Semantisch bedeutet es, dass erst der erste reguläre Ausdruck, und anschliessend der zweite passen muss. Da dies eine rekursive Definition ist, können auf diese Art und Weise beliebig viele reguläre Ausdrücke aneinandergefügt werden.


• Wenn A und B reguläre Ausdrücke sind, dann ist auch A|B ein regulärer Ausdruck.
  Hiermit wird beschrieben, dass durch das Zeichen "|" getrennte hintereinander geschriebene reguläre Ausdrücke einen neuen gültigen regulären Ausdruck ergeben. Semantisch bedeutet es, dass der erste reguläre Ausdruck oder der zweite passen muss. Da dies eine rekursive Definition ist, können auf diese Art und Weise beliebig viele reguläre Ausdrücke aneinandergefügt werden.


• Wenn A ein regulärer Ausdruck ist, dann ist auch A* ein regulärer Ausdruck.
  Hiermit wird beschrieben, dass hinter einem regulären Ausdruck ein "*" angefügt werden darf, und sich dadurch ein neuer gültiger regulärer Ausdruck ergibt. Semantisch bedeutet es, dass der reguläre Ausdruck beliebig oft hintereinander passen darf, gegebenenfalls auch keinmal. Da dies eine rekursive Definition ist, kann "*" beliebig oft an einen regulären Ausdruck angefügt werden.


• Wenn A ein regulärer Ausdruck ist, dann ist auch (A) ein regulärer Ausdruck.
  Hiermit wird beschrieben, dass ein regulärer Ausdruck in Klammern eingeschlossen werden darf und sich dadurch ein neuer gültiger regulärer Ausdruck ergibt. Semantisch hat das nur eine Bedeutung im Zusammenhang mit den Prioritäten, wie auch im Zusammenhang mit üblichen arithmetischen Ausdrücken. Da dies eine rekursive Definition ist, kann jeder reguläre Ausdruck beliebig oft geklammert werden.
  Achtung! Diese Klammerung hat hier nichts mit in Variablen zu speichernden Teilstrings zu tun. Diese Fähigkeit gehört zu erweiterten regulären Ausdrücken. Bei dieser Definition geht es ausschließlich um eine Gruppierung im Zusammenhang mit Prioritäten.


• Wenn in einem regulären Ausdruck mehrere der aufgeführten Konstruktionen vorkommen, gelten die folgenden Prioritäten:
  1. Klammerung
  2. Stern-Operator "*"
  3. Aneinandereihung
  4. Alternative (Operator "|")
  Konstruktionen mit gleicher Priorität sind linksassoziativ. An einem Beispiel gezeigt ist a|b|c|d identisch mit ((a|b)|c)|d.

Im Prinzip haben wir damit schon eine vollständige Beschreibungssprache. Leider ist sie oft recht unhandlich, so dass etwas syntaktischer Zucker eingefügt wurde, der die Leistungsfähigkeit nicht erweitert, aber die Lesbarkeit. Die betrifft beispielsweise die [...]-Gruppierung und den "+"-Operator, die nur abkürzende Schreibweisen sind. Darauf gehe ich an dieser Stelle nicht ein, weil das Thema später im Zusammenhang mit den Elementen von Ruby's erweiterten regulären Ausdrücken intensiv angegangen wird.

im nächsten Teil geht es dann um die Beantwortung der dritten Frage. Bis dahin erst einmal viel Spass beim lesen.