Fraktale malen mit Lindemeyer- Grammatik · Sequentielle Programmierung mit JavaKara ? Kontrollstrukturen von JAVA ? Vertiefung in JavaScript und HTML-DOM Klasse 9 Wahlpflichtunterricht:

Virtuelle Lehrerfortbildung Informatik Niedersachsen

Hans Peter Schneider

Fraktale malen mit Lindemeyer-Grammatik

Ein Parser für einen Stack-Automaten zur Steuerung von Turtle-Grafiken

Eine virtuelle Unterrichtsreihe im Rahmen des

jahrgangsübergreifenden Informatikunterrichts der Oberstufe an Gymnasien

Virtuelle Lehrerfortbildung Informatik Niedersachsen Seite 2 Hans Peter Schneider Ampelschaltung – Logik löten

Inhalt

Einordnung..................................................................................................... 3

Die Unterrichtsinhalte ...................................................................................... 3

Grammatiken formaler Sprachen ................................................................................... 4 Lindemeyer-Grammatiken ............................................................................................. 4 Turtle-Grafik ................................................................................................................. 5 Fraktale........................................................................................................................ 5

Das Projekt ..................................................................................................... 6

Turtle-Befehlsinterpreter................................................................................................. 7 Parser für Lindemeyer-Grammatik .................................................................................. 8 Erweiterung um Stack-Befehle ...................................................................................... 11 Das Java-Programm LindeTurtle................................................................................... 12 Beispielprogramme ..................................................................................................... 13

Quellen ........................................................................................................ 13

Virtuelle Lehrerfortbildung Informatik Niedersachsen Hans Peter Schneider Ampelschaltung – Logik löten Seite 3

Einordnung

Das Informatikprofil gehört am Gymnasium Lüneburger Heide zu den Aushängeschildern. Nach dem für alle Schüler der 6. Klassen verpflichtenden PC-Führerschein, in dem den Schülern der Umgang mit dem Rechner, dem Schulnetzwerk, dem Internet und den üblichen Office-Anwendungen beigebracht wird, haben die Schüler die Möglichkeit, Informatik ab der 7. Klasse durchgehend bis zum Abitur als Unterrichts- und Prüfungsfach zu belegen. In der Mittelstufe wird Informatik im Rahmen des Profilunterrichts Klasse 7 bis 9 (bisher Wahlpflichtunterricht der Klassen 9 und 10) angeboten, in der Oberstufe als jahrgangsübergreifender Kurs, zur Zeit als Grundkurs P3/P4 für die Klassen 11 bis 13, zukünftig als Prüfungskurs mit normalen Anforderungen als Ersatz für eine zweite Naturwissenschaft. Die Abiturthemen werden in einem dreijährigen Zyklus wechselnd unterrichtet. Für die Teilnahme am Oberstufenkurs wird die Teilnahme an zwei Mittelstufenkursen vorausgesetzt. Schüler, die Informatik in Klasse 11 neu beginnen, nehmen am Unterricht der Klasse 9 teil. Der Grund für diese Einschränkung ist der, dass in der Mittelstufe drei Halbjahre JAVA-Programmierung unterrichtet wird und diese JAVA-Kenntnisse für den Oberstufenkurs notwendig für eine in ihren Leistungen einigermaßen homogene Schülerstruktur notwendig sind.

Der Aufbau und die Inhalte der Kurse im Einzelnen: Neue Richtlinien: Zentralabitur und Profilunterricht Alte Richtlinien: Schulabitur und Wahlpflichtunterricht Klasse 7 Profilunterricht: 3 Wochenstunden ? Tabellenkalkulation, Excel-Programmierung ? HTML und CSS, Webseitengestaltung ? Einführung in JavaScript

Klasse 8 Profilunterricht: 4 Wochenstunden ? Sequentielle Programmierung mit JavaKara ? Kontrollstrukturen von JAVA ? Vertiefung in JavaScript und HTML-DOM

Klasse 9 Wahlpflichtunterricht: 4 Wochenstunden ? HTML und CSS, Webseitengestaltung ? JAVA-Kontrollstrukturen mit JavaKara ? Einführung in JavaScript, HTML-DOM

Klasse 9 Profilunterricht: 4 Wochenstunden ? Objektorientierte Programmierung mit JAVA

Klasse 10 Profilunterricht: 4 Wochenstunden ? Objektorientierte Programmierung mit JAVA

Klasse 10 bis 12 NA-Kurs: 2+4+4 Wochenstunden Klasse 11 bis 13 Grundkurs: 3+3+3 Wochenstunden ? Datenbanken, ER-Modelle und SQL ? Informatik und Gesellschaft: Datenschutz, Urheberrecht, soziale Auswirkungen, Geschichte ? Algorithmen und Datenstrukturen I: Suchen und Sortieren auf Feldern ? Algorithmen und Datenstrukturen II: dynamische Listen und Bäume, Stack und Pipe ? Endliche Automaten und Parserbau: Zustandsgraphen, Touring-Maschinen, Parser und Interpreter ? Technische Informatik: Logik, Rechnerstrukturen

Die Unterrichtsinhalte

Für die Durchführung des Projektes gehen die Themen „Datenstrukturen“ und „endliche Automaten“ sowie die hier beschriebenen Unterrichtsinhalte voraus. Zusätzlich wird von den Schülern erwartet, dass sie Übung in der JAVA-Programmierung aus der Mittelstufe mitbringen und die formal entwickelten Lösungen wie hier als Beispiel beschrieben, weitgehend selbstständig in JAVA implementieren können. Die Unterrichtsinhalte werden aus Platzgründen nur kurz angerissen.


Grammatiken formaler Sprachen Eine formale Sprache L (etwa eine Programmiersprache) besteht aus einem Tupel L(T, N, P, S) der

Menge T der Terminalsymbole (Alphabet), der Menge N der Nichtterminalsymbole, der Menge P der Produktionen (Substitutionsregeln) und dem Startsymbol S. Die Menge P unter Verwendung der anderen drei nennt man gern auch die Grammatik der Sprache L. Zur Darstellung der der Regeln der Grammatik gibt es verschiedene Formen, von denen 1. die einfache, mathematisch-logische Darstellung, 2. das Syntaxdiagramm und 3. die Backus-Naur-Form (BNF) und ihre Erweiterung (EBNF). Hier ein Beispiel in drei Ausführungen. Definiert wird ein Satz als Folge von Wörtern, beendet mit einem Punkt. Die Wörter werden durch Leerzeichen _ getrennt. Das Startsymbol S ist Satz, die Menge der Nichtterminalsymbole ist {Satz, Wort, Zeichen} und die Menge der Terminalsymbole ist {a, b, … z, A, B, … Z}.

einfache Form, der mathematischen Logik entlehnt Satz = Wort . | Wort _ Satz

Wort = Zeichen | Zeichen Wort

Zeichen = a | b | … | z | A | B | … | Z

erweiterte Backus-Naur-Form (EBNF) <Satz> ::= <Wort> {'_' <Wort> } '.'

<Wort> ::= <Zeichen> { <Zeichen> }

<Zeichen> ::= 'a' | 'b' | … | 'z' | 'A' | 'B' | … | 'Z'

Syntaxdiagramm

Während bei der einfachen Darstellung Wiederholungen rekursiv definiert werden müssen, sind in den Backus-Naur-Formen Klammern für Option [] und Repetition {} und Vorrang () definiert.

Lindemeyer-Grammatiken

Lindemeyer-Grammatiken sind spezielle generative Grammatiken, die rekursiv die Ersetzung einzelner Zeichen durch Zeichenketten beschreiben. Im Unterschied zu den oben beschriebenen Grammatiken sind die Mengen T der Terminale und N der Nichtterminale identisch: Auf der linken Seite der Regeln stehen Terminale, die durch eine Folge von Terminalen ersetzt werden. Diese Eigenschaft ermöglicht rekursive Regeln. Mit Hilfe dieser Regeln wird eine gegebene Zeichenkette beliebig verlängert.

Durch die Struktur von Lindemeyer-Grammatiken fällt die Nähe zu fraktalen Strukturen, besonders zu Koch’schen Kurven auf, die durch sehr ähnliche Ersetzungsregeln erzeugt werden (siehe unten). Tatsächlich sind Lindemeyer-Grammatiken geradezu prädestiniert, um mit ihnen Koch’sche Kurven zu erzeugen, in dem man die Zeichenketten als Anweisungssequenzen für ein geeignetes Grafiksystem wie einen Turtle-Grafikkontext interpretiert. Dies ist der zentrale Punkt unseres Projektes.

Grammatik S ::= abuba a ::= dudu b ::= ikki u ::= ba

Ergebnisse nach Anwendung der Regeln 0.: abuba 1.: duduikkibaikkidudu 2.: dbadbaikkiikkiduduikkidbadba 3.: dikkidududikkiduduikkiikkidbadbaikkidikkidududikkidudu

Satz Wort .

_

Wort Zeichen

Zeichen

a b …


Turtle-Grafik Turtle-Grafik nennt man eine grafische Umgebung, in der die Position des „Zeichenstiftes“ nur

relativ verändert werden kann durch ein paar einfache Befehle. Dabei stellt man sich vor, der Zeichenpunkt sei eine Schildkröte, die im wesentlichen durch die beiden Befehle „gehe“ und „drehe“ an einen anderen Punkt gesteuert wird, dabei hinterlässt sie eine Spur auf der Zeichenfläche. Die Distanz des Befehls „gehe“ sowie der Winkel des Befehls „drehe“ sind festgelegte Werte. Ursprünglich wurde diese Grafikumgebung implementiert, um einfache Plotter zu steuern; die Schrittdistanz war abhängig von der Mechanik des Plotters und entsprach der minimalen Distanz, die die verwendeten Schrittmotoren bewegt werden konnten, der festgelegte Winkel war stets 90°. Danach verwendete man das Konzept in Robotern mit Zeichenstift, die sich frei auf einer Zeichenfläche bewegen konnte. Auch dabei waren Distanz und Winkel durch die Schrittmotoren des Antriebs festgelegt: Die Distanz entsprach der Länge, die die beiden Schrittmotoren der beiden Räder minimal in gleicher Richtung zurücklegten, der Winkel der, um den sich der Roboter drehte, wenn beide Schrittmotoren die Räder minimal in entgegen gesetzte Richtungen drehten. Alle alten Programmiersprachen (wie BASIC und PASCAL) und aus Tradition auch viele der modernen enthalten ein Paket mit einer Turtle-Grafikumgebung, in JAVA muss man sie jedoch selber schreiben, dies machen wir unter Anderem zum Gegenstand unseres Projektes.

Fraktale Fraktale tauschen zum ersten Mal 1875 auf, als Weierstrass eine stetige, in keinem Punkt

differenzierbare Funktion konstruiert, was zu einer fünfzigjährigen Krise der Mathematik führte. Dies machten ihm Mathematiker wie Cantor, Peano, Lebesgue, Hausdorff, Bolzano, Sierpinski und Koch nach. Schließlich prägte 1977 der Informatiker Mandelbrot1 beruhend auf den Arbeiten von Julia2 den Begriff des Fraktals und definierte eine neue, nicht auf die Analysis aufbauende Mathematik zu Beschreibung von Fraktalen, wobei er vor allem den Begriff der „fraktalen Dimension“ Df definierte, der alle positiven reellen Werte annehmen kann und nur bei analytischen Formen mit der normalen, ganzzahligen, sogenannten „topologischen“ Dimen-sion Dt übereinstimmt.

Eine der gängigsten Verfahren, ein Fraktal zu erzeugen, ist die unendlich häufige Anwendung eines Generators, in der ausgehend von einer geometrischen Grundfigur durch wiederholte Befolgung einer Bearbeitungsvorschrift diese immer komplexer wird und letztlich gegen das Fraktal konvergiert. Das von Koch3 implizierte Verfahren eines geometrischen Generators zur Erzeugung fraktaler Kurven aus Streckenzügen. Dabei wird eine Strecke ersetzt durch einen endlichen Polygonzug,

1 Benoît B. Mandelbrot (* 20. November 1924 in Warschau, Polen) 2 Gaston Maurice Julia (* 3. Februar 1893 in Sidi bel Abbès, Algerien; † 19. März 1978 in Paris) 3 Niels Fabian Helge von Koch (* 25. Januar 1870 in Stockholm, † 11. März 1924 ebenda)

N = 4 r = ½ Df = 2

Harter-Heightway-Drachen

N = 8 r = ¼ Df = 1,5

Koch-Mäander


bestehend aus lauter gleichlangen Teilstrecken. Im nächsten Schritt wird jede Teilstrecke des Polygonzugs wiederum ersetzt durch eine maßstäbliche Verkleinerung des Polygonzugs usw. Aus sehr einfachen Generatoren können so sehr komplexe fraktale Kurven entstehen. Die oben erwähnte fraktale Dimension Df dieser Koch’schen Kurven ist definiert als das Verhältnis der Polygonzuglänge zur Länge der ersetzten Strecke in folgender Weise:

Sei n die Zahl der Teilstücke des Polygonzugs und r die relative Länge der Teilstücke zu der zu

ersetzenden Strecke. So ist Df definiert als: )log()log(

1r

fn

D ?

Der Wert der Dimension Df ist ein Maß dafür, in wie weit die Kurve eine Fläche füllt, Eine Kurve mit Df = 2 hat also einen positiven Flächeninhalt. In den Kästen sieht man ein paar Beispiele.

Das Projekt

Im Folgenden wird beispielhaft die Entwicklung eines kleinen JAVA-Programms beschrieben, das einen Automaten enthält, der einen Parser darstellt, der Lindemeyer-Grammatiken analysiert und als Programme für Turtle-Grafiken interpretiert. Durch die Definition einer einfachen Lindemeyer-Grammatik kann ein komplexes Fraktal (etwa eine Koch’sche Kurve) von einer Turtle gezeichnet werden (siehe Kasten).

Das Projekt erinnert ein wenig an das Projekt „LOGO für Arme“4, nur dass Programme aus Lindemeyer-Grammatiken rekursiv aufgebaut sind und weder Entscheidungen noch Schleifen kennen. Jede Wiederholung muss also rekursiv formuliert werden. Ein weiterer Unterschied ist der, dass ein solches Programm nicht aus einer Folge von Anweisungen (mit einer Reihenfolge) besteht, sondern aus einer Menge von Regeln (ohne Reihenfolge, ähnlich einem PROLOG-Programm). Ein Parser kann daher nicht einfach im Code vorne Anfangen und sich nach hinten durcharbeiten und dabei schon den Interpreter anschmeißen, sondern muss sich an bestimmten Schlüsselzeichen orientieren und sich von diesen ausgehend die Regeln erfassen. Ein solcher Parser kann als eine Touring-Maschine mit einem großen Zeichensatz interpretiert werden, da der Parser sich im Code je nach Zustand vor und zurück bewegt.

4 siehe [1] E. Modrow „Einführung in die theoretische Informatik“, Kapitel 3.6 und 10.

N = 4 r = 1/3 Df = 1,26

Koch-Schneeflocke

#: 0F++4F++7F; F: +F--FF++F-;


Turtle-Befehlsinterpreter

Um Ein Turtle-Programm zu schreiben, muss jeder Turtle-Befehl als Zeichen (-kette) dargestellt werden. Übergibt man dieses Zeichen dem Interpreter der Turtle, so führt die Turtle den Befehl aus. Die typischen Turtle-Befehle und ihre Zeichendarstellung sind in der nebenstehenden Tabelle aufgelistet. Prinzipiell darf die übergebene Zeichenkette jedes beliebige Zeichen enthalten, aber nur die nebenstehenden Zeichen werden interpretiert, es gibt in dem Sinne also kein fehlerhaftes Programm.

Ein Turtle-Objekt muss den Standardwinkel und die Standardlänge seiner Bewegungen kennen, ebenso den Grafikkontext in dem es zeichnen soll und die Koordinaten und die Richtung seiner Ausgangsstellung. Für diesen Zweck braucht eine Turtle-Klasse entsprechende Set-Methoden. Ein Turtle-Objekt kennt jederzeit seine derzeitige Position und seine Ausrichtung. Zum Zeichnen verwendet das Turtle-Objekt die Methoden des zugewiesenen Grafikkontextes.

public class Turtle { static double c = Math.PI/180.; //Winkel-Radiant-Umrechnungskonstante static Color[] penCol = { Color.black, Color.darkGray, Color.gray, Color.red, Color.orange, Color.yellow, Color.green, Color.cyan, Color.blue, Color.magenta }; Graphics graph; // Grafik-Kontext der Turtle-Grafik double stpL = 10.; // Schrittlänge double stpA = c*60.; // Schrittwinkel double posX = 0.; // aktuelle Position: Ort(x,y), Winkel, Farbe double posY = 0.; double posDir = c*90.; int posCol = 0; // ------------ Konstruktoren --------------------------------------------------------------------------------------- public Turtle(Graphics g) { // Turtle mit Grafikkontext erzeugen graph = g; }; public Turtle() { // Turtle erzeugen }; // ----------- Einstellungen ----------------------------------------------------------------------------------------- public void setGraphics(Graphis g) { // Grafikkontext setzen graph = g; }; public void setPrms(double length, double angle) { // Initialisierung: Grundwerte stpL = length; stpA = correct(c*angle); }; // setPrms public void setStart(double x, double y, double dir) { // Initialisierung: Startwerte posX = x; posY = y; posDir = correct(c*dir); }; // setStart // ----------- Interpreter ------------------------------------------------------------------------------------------ public void draw(String code) { //------------------ Regel befolgen double actX; double actY; char c; for (int i = 0; i < code.length(); i++) { // code abarbeiten

eine Standardlänge gehen und zeichnen F eine Standardlänge gehen ohne zu zeichnen M um Standardwinkel nach rechts drehen + um Standardwinkel nach links drehen – umdrehen ! in Ausgangsstellung gehen # Farbe auswählen 0..9


c = code.charAt(i); // nächsten Befehl nehmen actX = posX; // alte Position merken actY = posY; switch (c) { case 'F': // male Schritt (forward) posX = actX+Math.cos(posDir)*stpL; posY = actY+Math.sin(posDir)*stpL; graph.setColor(penCol[posCol]); graph.drawLine((int)Math.round(actX), (int)Math.round(actY), (int)Math.round(posX), (int)Math.round(posY)); break; case 'M': // gehe Schritt ohne malen (muted forward) posX = actX+Math.cos(posDir)*stpL; posY = actY+Math.sin(posDir)*stpL; break; case '+': // drehe rechts posDir = correct(posDir+stpA); break; case '-': // drehe links posDir = correct(posDir-stpA); break; case '!': // drehe um posDir = correct(posDir+Math.PI); break; default: // Farbe auswählen if ((c >= '0')&&(c <= '9')) { posCol = (int)c - (int)'0'; }; }; }; }; // draw // ------- interne Methoden ------------------------------------------------------------------------------ public double correct(double a) { // Winkelkorrektor: -180°... +180° double z = 2*Math.PI; while (a >= Math.PI) { a = a - z; }; while (a < -Math.PI) { a = a + z; }; return a; }; // correct }; // class Turtle

Parser für Lindemeyer-Grammatik Eine Lindemeyer-Grammatik beinhaltet die rekursive Ersetzung von Zeichen durch Zeichenketten

und ermöglicht so erst die grafische Rekursion, die nötig ist, um Fraktale zu erzeugen. Diese Eigenschaften bürden wir nicht der Turtle auf (die kann ja nichts dafür), sondern überlassen sie dem vorgeschalteten Parser zur Auswertung: Der Parser ordnet zunächst die Ersetzungsregeln in eine Liste ein und führt dann die rekursiven Ersetzungen aus, wobei er Zeichen, für die keine Ersetzungsregel existiert, an den Turtle-Interpreter weiterreicht. Um keinen endlosen Automaten zu erzeugen, wird die endlose rekursive Tiefe und Selbstähnlichkeit der Fraktale dem Pragmatismus geopfert (wir müssen bei der Darstellung eh auf ganze Pixel runden) und lassen den Benutze bei jeder Anwendung eine Rekursionstiefe festlegen, über die hinaus keine Ersetzungen mehr vorgenommen werden. Quasi als Trost räumen wir dem Benutzer aber die Möglichkeit ein, bei Erreichen der Rekursionstiefe eine letzte, alternative Ersetzung vornehmen zu lassen. Der Parser analysiert also die Lindemeyer-Grammatik und nimmt nicht wahr, dass die Zeichen, die er verarbeitet, irgendwelche Bedeutungen haben. Erst wenn der Parser sein Ergebnis an den Interpreter der Turtle weiter gibt, werden aus den Zeichen Befehle. Hier die Syntax der Grammatik für den Parser in EBNF und als Syntaxdiagramm:


<Programm> ::= { <Anweisung> } <Startanweisung> { <Anweisung> } <Startanweisung> ::= '#' ':' <Zeichenfolge> [ ':' <Zeichenfolge> ] ';' <Anweisung> ::= <Zeichen> ':' <Zeichenfolge> [ ':' <Zeichenfolge> ] ';' <Zeichenfolge> ::= <Zeichen> { <Zeichen> } <Zeichen> ::= ? alle Unicode-Zeichen außer '#', ':', ';' und den Blanks ' ', \t und \n ?

Jede Anweisung wird als Regel formuliert, vergleichbar einem PROLOG-Programm. Die Reihenfolge der Regeln ist dabei uninteressant, irgendwo sollte es aber eine Startregel geben, die mit #: beginnt. Der Automat, der diese Regeln analysiert, muss also nicht von vorn nach hinten die Zeichen abarbeiten wie in einem sequentiellen Programm, sondern sucht nach Schlüsselzeichen und wandert von diesen je nach Zustand vorwärts oder rückwärts durch den Code wie eine Touring-Maschine. Die Schlüsselzeichen sind die in der Grammatik verwendeten Begrenzer ':' und ';' . Vor dem Parsen werden alle Blanks, die der Benutzer zur Formatierung verwenden darf, aus dem Code entfernt. Da es leichter ist, wenn sich der Parser bei seiner Arbeit die Positionen der Begrenzer merken kann, wird er besser als Stack-Automat implementiert. Es gibt höchstens drei Werte, die sich der Parser gleichzeitig merken muss, so kann der Stack einfach in Form von drei definierte Variablen realisiert werden.

Eine Anweisung besteht also mindestens aus einem Zeichen, gefolgt vom Doppelpunkt und einer Zeichenfolge, abgeschlossen mit einem Semikolon, zum Beispiel: A: ABGFAFR; Dies bedeutet, dass das Zeichen A in jeder Zeichenfolge des Programms ersetzt wird durch die angegebene Zeichenfolge ABGFAFR. Nach der ersten zwei Ersetzungsvorgängen sieht die Zeichenfolge ABGFAFR also so aus:

ABGFAFRBGFABGFAFRFRBGFABGFAFRBGFABGFAFRFRFR

Ein Programm kann aus beliebig vielen solchen Ersetzungsanweisungen bestehen.

Das Rautenzeichen '#' bezeichnet den Programmstart, also die Zeichenfolge mit der die Ersetzung anfangen soll. Findet der Parser keine Raute, so führt dies zu einem

:

:

; Anweisung Zeichenfolge

Zeichenfolge

Zeichen

Startanweisung :

:

; Zeichenfolge

Zeichenfolge

#

Programm

Anweisung Anweisung

Startanweisung

Zeichenfolge Zeichen

alle Unicode-Zeichen außer '#' ':' ';' ' ' \t \n Zeichen

S0

S1 ':', L, (1)

*, R, –

S2

S3

*, RR, (2) *, R, –

':', R, (3)

*, R, –

';', R, (4)

';', R, (3)

Start

* : alle anderen Eingaben R: Postion ein Zeichen nach rechts L: Position ein Zeichen nach links

(1) Position a merken; (2) Regelslot auswählen, Zeichen in Regelslot speichern; (3) Position b merken, Zeichenfolge zwischen a und b in Regelslot (normale Ersetzung) speichern; (4) Position c merken, Zeichenfolge zwischen b und c in Regelslot (finale Ersetzung) speichern; – keine Aktion


Syntaxfehler. Es ist jedoch egal, in welcher Reihenfolge die Ersetzungsanweisungen stehen. Steht in einer Anweisung eine zweite Zeichenfolge hinter einem zweiten Doppelpunkt, wird diese zweite Zeichenfolge in der letzten Ersetzung bei erreichen der vorgegebenen Rekursionstiefe an Stelle der ersten Zeichenfolge benutzt; diese Angabe ist jedoch optional.

Der vom Parser beachtete Bereich reicht vom Zeichen vor dem ersten Doppelpunkt bis zum nächsten Semikolon jeder Regel. Jedes Zeichen außerhalb dieser Bereiche wird ignoriert, eine Fehlermeldung ist auf Grund des Zusammenhangs nicht nötig. Auf diese weise kann man fast überall, also vor dem Programm, nach jeder Regel und am Ende des Programms ohne weitere Kennzeichnung Kommentare einfügen, ohne Einfluss auf die Syntax auszuüben.

Der Parser ist Bestandteil des Fensters, das die Zeichnung zeigt. Die Liste der Ersetzungsregeln wird vom Parser nur einmal erzeugt, wenn ein neues Programm eingegeben wurde. Die Ersetzungsrekursion wird dann von der paint-Methode des Fensters angestoßen. Während der Rekursion zeichnet die Turtle dann die codierte Grafik. Hier folgt der wesentliche Code des Parsers parse() und der Rekursionsmaschine run(). Der vollständige Code findet sich in den Anlagen.

class LindeScreen extends Frame implements MouseListener, MouseMotionListener { Turtle turtle; // Schildkröte String item = ""; // Liste der Symbole mit Ersetzungsregeln (0-tes ist Startanweisung) String[] subst; // Liste der zu den Symbolen gehörigen Ersetzungen String[] finst; // Liste der zu den Symbolen gehörigen finalen Ersetzungen

? public void parse() { // Parser unterteilt den Text des Editors String code = editTA.getText().trim(); // Regeltext holen item = "#"; // Zuordnungstabelle auf null subst = new String[40]; finst = new String[40]; int i = 0; // Aktuelle Position im Code int j; // Position des ersten ':' der gefundenen Regel int g; // Position des zweiten ':' der gefundenen Regel int k; // Position des ';' der gefundenen Regel int f; // Position des Endes der Standardersetzung ( g, wenn g existiert, sont k) int h; // Index der Ersetzungsregel im Regelfeld (item, subst, finst) while (i < code.length()) { // Scannen des Textes j = code.indexOf(':', i); // ersten ':' nach Position i erkennen if (j > -1) { g = code.indexOf(':', j+1); // zweiten ':' erkennen, bevor.. k = code.indexOf(';', j); // ';' erkennen if (k <= j) { // ... sonst Textende k = code.length(); }; if ((g > -1)&&(g < k)) { if ((j == 0)||("# ".indexOf(code.charAt(j-1)) > -1)) { // Startzeile mit # erkennen finst[0] = code.substring(g+1, k).trim(); } else if ((h = item.indexOf(code.charAt(j-1))) > -1) { // vorhandene Regel überschreiben finst[h] = code.substring(g+1, k).trim(); } else if((h = item.length()) < 40) { // neue Regel einfügen item = item+code.charAt(j-1); finst[h] = code.substring(g+1, k).trim(); }; f = g; } else { f = k; }; if ((j == 0)||("# ".indexOf(code.charAt(j-1)) > -1)) { // Startzeile erkennen subst[0] = code.substring(j+1, f).trim(); } else if ((h = item.indexOf(code.charAt(j-1))) > -1) { // vorhandene Regel überschreiben subst[h] = code.substring(j+1, f).trim(); } else if((h = item.length()) < 40) { // neue Regel einfügen item = item+code.charAt(j-1); subst[h] = code.substring(j+1, f).trim(); };


i = k; } else { // kein ':' mehr, also ignoriere Rest. i = code.length(); }; newTurtle = true; }; }; // parse public void run(String s, int d) { //---------- Rekursionsebene der Turtle-Aktivität int nr; char c; for (int i = 0; i < s.length(); i++) { // Regelzeile abarbeiten c = s.charAt(i); nr = item.indexOf(c); if (nr == -1) { // wenn Zeichen nicht in Ersetzungsliste turtle.draw(""+c); // ... dann gib's der Schildkröte } else if (d < tiefe) { // ist es in der Liste run(subst[nr], d+1); // ... dann mach das ganze mit der Ersetzungsregel (Rekursion) } else if (finst[nr] == null) { // ist aber die maximale Rekursionstiefe erreicht turtle.draw(subst[nr]); // .... dann füttere die Schildkröte mit der ganzen Regel } else { turtle.draw(finst[nr]); // .... bzw. mit der fialen Regel, wenn vorhanden }; }; }; // run public void run() { // ----------- Turtle-Aktivität starten turtle.setPrms(laenge, winkel); // Initialisierung turtle.setStart(startX, startY, startA); turtle.draw("0"); // Farbe auf schwarz setzen (mit dem Interpreter!) if (item.length() > 0) { // gibt es wenigstens eine Startregel? if (tiefe > 0) { // wenn Rekursionstiefe > 0 dann starte Rekursion run(subst[0], 1); } else if (finst[0] == null) { // sonst füttere die Schildkröte mit der Startregel turtle.draw(subst[0]); } else { turtle.draw(finst[0]); // .... bzw. mit der finalen Startregel, wenn vorhanden }; }; }; // run

? };

Erweiterung um Stack-Befehle Die Programmierungsmöglichkeiten der Turtle erweitern sich

beträchtlich, wenn man der Turtle einen Stack verpasst, der Interpreter lässt sich mit relativ wenig Aufwand diesbezüglich aufrüsten. Der Turtle erleichtert es, in ihren Grafiken Abzweigungen zu zeichnen, in dem die Position der Abzweigung gespeichert wird, erst der eine Zweig gezeichnet wird, dann die Position der Abzweigung restauriert wird, um dann den anderen Zweig zu zeichnen. Die Klasse Turtle wird wie folgt ergänzt:

public class Turtle {

? // ------------ Stack-Element ------------------------------------------------------------------------------ class StackEl { double pX; // Werte: Ort(x,y), Richtung, Farbe double pY; double pD; Color pC; StackEl nxt; // Zeiger auf nächstes Element StackEl() { // Konstruktor pX = posX; // Werte aus Turtle übernehmen pY = posY;

Turtle-Zustand auf den Stack legen (push) [ Turtle-Zustand vom Stack holen (pop) ]


pD = posDir; pC = posCol; }; }; // StackEl // --------------- Turtle-Variablen ------------------------------------------------------------------------------ StackEl stack; // leeren Stack erzeugen

? // ---------------- Stack-Methoden ----------------------------------------------------------------------------- public void push() { // Stack push StackEl ptr = new StackEl(); ptr.nxt = stack; // Element wird am Anfang der Liste eingefügt stack = ptr; }; // push public void pop() { // Stack pop if (stack != null) { posX = stack.pX; // Turtle-Werte restaurieren posY = stack.pY; posDir = stack.pD; posCol = stack.pC; stack = stack.nxt; // Element wird aus der Liste herausgenommen }; }; // pop

? // ------------ Interpreter ------------------------------------------------------------------------- public void draw(String code) { //------------------ Regel befolgen

? switch (c) {

? case '[': push(); // Turtle-Zustand auf den Stack legen break; case ']': pop(); // Turtle-Zustand vom Stack holen break;

?? };

? }; // draw };

Das Java-Programm LindeTurtle Das Hauptfenster enthält auf dem ersten Reiter den

Editor, in dem die Lindemeyer-Regeln definiert werden. Auf dem zweiten Reiter werden die Einstellungen für die Start- und Standardwerte vorgenommen. Der dritte Reiter enthält eine Übersicht über die Turtle-Befehle. Ein zweites Fenster, das über den Menüeintrag „Fenster – Leinwand“ geöffnet wird, enthält die grafische Fläche für die Turtle. Sobald es geöffnet wird, interpretiert es den Inhalt des Editors. Soll der Editor-Inhalt nach einer Änderung neu interpretiert werden, kann man dies durch den Menüeintrag „Schildkröte – starten“ auslösen.

Das Datei-Menü erlaubt es, die Lindemeyer-Regeln zusammen mit den Einstellungen in einer .ltf-Datei zu speichern oder wahlweise die Lindemeyer-Regeln allein als reine .txt-Datei.


Beispielprogramme ‚Delta Dragon’ (Df = 2) Hans Peter Schneider #: 0F++4F++7F; F: +F--FF++F-;

'Penta Plexity' (Df = 1.91) Roger Penrose #: 4F++7F++5F++9F++6F; F: F++F++F!F-F++F;

Winkel: 60° Länge: 1.25 Startpunkt: (150|200) Startrichtung: 0° Rekursionstiefe: 8


‚Sierpinski-Dreieck’ (Df=1.58) #: b; a: +b-a-b+ : F; b: -a+b+a- : F;

'Snowflake' (Df = 1.2618) Helge von Koch #: F--F--F; F: F+F--F+F;

Winkel: 60° Länge: 2 Startpunkt: (40|500) Startrichtung: 0° Rekursionstiefe: 8

Winkel: 60° Länge: 2 Startpunkt: (50|150) Startrichtung: 60° Rekursionstiefe: 5

‚Koch-Pyramide’ (Df = 1.46) #: F; F: F-F+F+F-F;

‚Rispen’ #: 4[+++a][---a]5Fba; a: Fb[+Fba][-Fba]Fba; b: Fb;


Winkel: 20° Länge: 5 Startpunkt: (300|400) Startrichtung: –90° Rekursionstiefe: 7

Quellen

[1] Eckard Modrow „Einführung in die theoretische Informatik“, VLIN

[2] Benoit B. Mandelbrot „Die fraktale Geometrie der Natur“, Birkhäuser, Basel 1987

[3] Nikolaus Wirth „Compilerbau“, Teubner Studienbücher Informatik, Stuttgart 1984

Documents

Fraktale malen mit Lindemeyer- Grammatik · Sequentielle Programmierung mit JavaKara ? Kontrollstrukturen von JAVA ? Vertiefung in JavaScript und HTML-DOM Klasse 9 Wahlpflichtunterricht: