Visualisierung limitierter Lindenmayer

Studienarbeit
Visualisierung limitierter
Lindenmayer-Systeme
Technische Universität
Carolo-Wilhelmina zu Braunschweig
Institut für Theoretische Informatik
Prof. Dr. Adámek
Prof. Dr. Wätjen
Betreuer: Prof. Dr. Wätjen
Vorgelegt von
Frank Böhmer
Matr.-Nr. 2582133
Braunschweig, Dezember 2002
Inhaltsverzeichnis
1
2
3
4
5
6
7
Einleitung ........................................................................................................................... 4
Lindenmayer-Systeme........................................................................................................ 5
2.1
0L-Systeme................................................................................................................. 5
2.2
Limitierungen ............................................................................................................. 6
2.3
Parametrische L-Systeme ........................................................................................... 6
2.4
Kontextsensitivität...................................................................................................... 6
Vergleich limitierter mit nicht limitierten Systemen.......................................................... 8
3.1
Mögliche Anwendungen .......................................................................................... 10
Bedienung von 0L ............................................................................................................ 11
4.1
Voraussetzungen ...................................................................................................... 11
4.2
Installation................................................................................................................ 11
4.3
Programmoberfläche ................................................................................................ 11
Beschreibungssprache ...................................................................................................... 14
5.1
Formatfreiheit........................................................................................................... 14
5.2
Kommentare ............................................................................................................. 14
5.3
Programmstruktur..................................................................................................... 14
5.4
Konstantendefinition ................................................................................................ 14
5.5
Symboldefinition...................................................................................................... 15
5.6
Axiomdefinition ....................................................................................................... 15
5.7
Substitutionen........................................................................................................... 16
5.8
Limitierungen ........................................................................................................... 17
5.9
Interpretation ............................................................................................................ 17
5.9.1
Interpretation „turtle2d“ ................................................................................... 18
5.9.2
Interpretation „turtle3d“ ................................................................................... 19
5.10 Mathematische Funktionen ...................................................................................... 20
5.11 Mathematische Konstanten ...................................................................................... 21
5.12 Boolesche Ausdrücke............................................................................................... 21
5.13 Formale Syntax ........................................................................................................ 22
Architektur ....................................................................................................................... 26
6.1
Parser........................................................................................................................ 26
6.2
Interpretation ............................................................................................................ 26
6.3
Klassendiagramme ................................................................................................... 27
6.3.1
System .............................................................................................................. 27
6.3.2
Substitutionen................................................................................................... 27
6.3.3
Worte und Symbole.......................................................................................... 28
6.3.4
Arithmetische Ausdrücke ................................................................................. 28
6.3.5
Boolesche Ausdrücke....................................................................................... 29
6.3.6
Interpretation .................................................................................................... 29
Anhang ............................................................................................................................. 30
2
7.1
Beispiel für ein Lindenmayer-System...................................................................... 30
8
Abbildungsverzeichnis ..................................................................................................... 32
9
Literaturverzeichnis.......................................................................................................... 33
3
1 Einleitung
Zurückgehend auf den Biologen Aristid Lindenmayer haben Lindenmayer-Systeme eine
vielseitige Entwicklung durchgemacht. Eingeführt als System zur Beschreibung der parallelen
Zellteilungsprozesse einfacher Organismen (z.B. Algen) wurde bald das Interesse sowohl von
der theoretischen Informatik [5] als auch der Computergraphik [4] geweckt.
In der theoretischen Informatik wurde und wird die Einordnung von Lindenmayer-Systemen
in die Chomsky-Hierarchie der formalen Sprachen sowie die Abgeschlossenheit unter
verschiedenen Operationen (insbesondere der AFL-Operationen) betrachtet. D. Wätjen führte
in [8] und [9] Limitierungen von Lindenmayer-Systemen ein, die das Wachstum beschränken.
Zur Generierung natürlich anmutender Pflanzen oder zur Erzeugung abstrakter, aber
ästhetischer Graphiken werden in der Computergraphik u.a. Lindenmayer-Systeme eingesetzt.
Dazu wurden die Systeme um reellwertige Parameter und bedingte Produktionen erweitert.
Zur Interpretation kommt in der Regel das Turtle-Modell zum Einsatz.
In der vorliegenden Arbeit sollen limitierte Lindenmayer-Systeme und diese der
Computergraphik zusammengeführt werden. Dabei steht der praktische Teil im Vordergrund,
auf die theoretische Untermauerung soll lediglich verwiesen werden. Im Rahmen dieser
Arbeit ist eine Applikation – namentlich „0L“ – entstanden [1], die die Berechnung und
Interpretation von Lindenmayer-Systemen mittels zwei- und dreidimensionaler TurtleGraphik erlaubt.
4
2 Lindenmayer-Systeme
Im folgenden sollen die in 0L verwendeten Eigenschaften und Erweiterungen von
Lindenmayer-Systemen formal definiert werden.
2.1
0L-Systeme
Definition 3.1: Ein Tripel G = (Σ, h, ω) heißt 0L-System, wenn gilt:
(1) Σ ist eine endliche Menge,
(2) h : Σ → ℘(Σ*) ist eine nichtleere endliche Substitution,
(3) ω ∈ Σ*.
Dann bezeichnen wir Σ als das Alphabet, die Elemente von Σ als Symbole und Elemente aus
Σ* als Wörter über Σ. Das leere Wort bezeichnen wir mit ε.
Definition 3.2: Sei G = (Σ, h, ω) ein 0L-System
p: a → w ist genau dann eine Produktion in G, wenn w ∈ h(a) gilt.
h beschreibt also eine Menge von Produktionen.
Definition 3.3: Es sei G = (Σ, h, ω) ein 0L-System, w ∈ Σ* und i ∈ ù, i > 0. Dann sei
L0 (G, w) := {w} und
Li (G, w) := {v ∈ Σ * | v ∈ h i ( w)} .
Damit folgt
∞
L(G ) = U Li (G, ω ) .
i =0
Definition 3.4:
(1) Es sei G ein 0L-System. v leitet w direkt (in G) ab (bezeichnet mit v ⇒ G w ), wenn
w ∈ L1 (G, v) gilt.
(2) w leitet v in n Schritten (in G) ab (bezeichnet mit v ⇒ Gn w ), wenn w ∈ Ln (G, v) gilt.
(3) w leitet v (in G) ab (bezeichnet mit v ⇒ *G w ), wenn w ∈ Ln (G, v) für ein beliebiges
n ∈ ù gilt.
Definition 3.5: Ein 0L-System G = (Σ, h, ω) heißt propagierend, wenn gilt:
∀ a ∈ Σ : ε ∉ h(a).
Ein solches System bezeichnen wir auch als P0L-System. Es ist leicht ersichtlich, dass die
Wortlänge in einem P0L-System mit jedem Ableitungsschritt wächst oder wenigstens
konstant bleibt.
Definition 3.6: Ein 0L-System G = (Σ, h, ω) heißt deterministisch, wenn gilt:
∀ a ∈ Σ : |h(a)| = 1.
Somit ist für jedes Wort nur genau eine Ableitung möglich. Ein deterministisches 0L-System
bezeichnen wir als D0L-System.
Ist ein 0L-System deterministisch und propagierend, so bezeichnen wir es als PD0L-System.
Beispiel 3.1: Sei G = (Σ, h, ω) ein 0L-System mit Σ = {a, b, c}, ω = a,
h(a) = bac, h(b) = a, h(c) = a.
Dann ist G propagierend und deterministisch mit folgender Ableitung:
a ⇒ bac ⇒ abaca ⇒ bacabacabac ⇒ ...
5
2.2
Limitierungen
Limitierte 0L-Systeme werden in [7], [8] und [9] betrachtet. Die Idee ist, dass die vollständige
parallele Ersetzung bei 0L-Systemen nicht ausreicht, um natürliche Wachstumsprozesse zu
beschreiben, da diese durch Ressourcenknappheit und andere äußere Einflüsse beschränkt
sind. Die Limitierung eines L-Systems bedeutet eine Einschränkung der Substitution: in
einem Ableitungsschritt werden nicht mehr alle möglichen Ersetzungen vorgenommen,
sondern nur eine Teilmenge.
Definition: Sei k ∈ ù, k > 0, weiterhin sei h: Σ →℘(Σ*) eine endliche Substitution.
hk(w): Σ* →℘(Σ*) ist eine k-Limitierung von h, wenn hk(w) genau die Menge der Wörter ist,
die sich erzeugen lassen, indem für jedes Symbol a ∈ Σ genau min{#aw, k} Vorkommen in w
ersetzt werden.
Definition: Sei k ∈ ù, k > 0, weiterhin sei h: Σ →℘(Σ*) eine endliche Substitution.
hk(w): Σ* →℘(Σ*) ist eine uniforme k-Limitierung von h, wenn hk(w) genau die Menge der
Wörter ist, die sich erzeugen lassen, indem genau min{|w|, k} Symbole in w ersetzt werden.
2.3
Parametrische L-Systeme
Parametrische L-Systeme werden in [3], Kapitel 3.1 betrachtet. Die Erweiterung bezüglich
normaler L-Systeme besteht darin, dass die Symbole des Alphabets mit reellwertigen
Parametern ausgestattet werden, diese werden als Moduln bezeichnet. Ein Modul mit
Buchstaben A ∈ Σ und den Parametern a1, a2, ..., an ∈ R wird bezeichnet mit A(a1, a2, ..., an).
Die Menge der Moduln nennen wir M := (Σ × R*). Parametrische Wörter sind Wörter über die
Moduln.
Gegenüber den reellwertigen Parametern stehen die formalen Parameter, die benötigt werden,
um die Substitution des L-Systems zu spezifizieren. Für eine Menge Φ formaler Parameter
soll C(Φ) die Menge der logischen Ausdrücke und E(Φ) die Menge der arithmetischen
Ausdrücke über Φ sein.
Definition: Ein Quadrupel G = (Σ, Φ, h, ω) ist ein parametrisches L-System, wenn gilt:
(1) Σ ist eine endliche Menge, das Alphabet des Systems,
(2) Φ ist eine Menge formaler Parameter,
(3) ω ∈ (Σ × R*)+ ist das Axiom des Systems,
(4) h: (Σ × Φ*) × C(Φ) → (Σ × E(Φ)*)* ist eine endliche Menge von Produktionen.
Die durch h beschriebenen Produktionen schreiben wir auch als p: a | φ → w, wobei
*
* *
a ∈ (Σ × Φ ), φ ∈ C(Φ) und w ∈ (Σ × E(Φ) ) ist.
Eine Produktion p: a | φ → w wird dann auf ein Modul b angewandt, wenn a und b das selbe
Symbol s ∈ Σ tragen, die Zahl der formalen Parameter in a mit der Zahl der reellwertigen
Parameter in b übereinstimmt und der durch die reellwertigen Parameter von b bewertete
logische Ausdruck φ erfüllt ist. b wird dann durch die Bewertung von w ersetzt.
2.4
Kontextsensitivität
Die bisher betrachteten Produktionen sind kontextfrei. Wir wollen nun parametrische LSysteme noch um kontextsensitive Produktionen erweitern. Im Gegensatz zu 0L-Systemen
werden L-Systeme, deren Produktionen kontextsensitiv sind 2L-Systeme genannt, als
Spezialfall dieser ergeben sich noch die 1L-Systeme, bei denen der Kontext jeweils nur auf der
linken oder nur auf der rechten Seite des zu ersetzenden Symbols auftaucht. Diese
Differenzierung soll im folgenden nicht betrachtet werden.
6
Um Kontextsensitivität einzuführen, muss im Wesentlichen nur die Substitution erweitert
werden:
Definition: Ein Quadrupel G = (Σ, Φ, h, ω) ist ein kontextsensitives, parametrisches LSystem, wenn gilt:
(1) Σ ist eine endliche Menge, das Alphabet des Systems
(2) Φ ist eine Menge formaler Parameter
(3) ω ∈ (Σ × R*)+ ist das Axiom des Systems
(4) h: (Σ × Φ*)* × (Σ × Φ*) × (Σ × Φ*)* × C(Φ) → (Σ × E(Φ)*)* ist eine endliche Menge von
Produktionen
Die durch h beschriebenen Produktionen schreiben wir auch als
p: v1 < a > v2 | φ → w
*
* *
* *
wobei a ∈ (Σ × Φ ), v1, v2 ∈ (Σ × Φ ) , φ ∈ C(Φ) und w ∈ (Σ × E(Φ) ) ist.
Sein p eine Produktion v1 < a > v2 | φ → w und sei u1bu2 ein Teilwort mit u1, u2 ∈ (Σ × R*)*
und b ∈ (Σ × R*). p wird dann auf u1bu2 angewandt, wenn gilt:
(1) v1av2 = x1x2...xn passt auf u1bu2 = y1y2...ym, d.h. m = n, die Moduln xi und yi tragen
jeweils das selbe Symbol und die Zahl der formalen Parameter von xi stimmt mit der
Zahl der reellwertigen Parameter von yi überein (für alle i ∈ {1, 2, ..., n}).
(2) Der durch die reellwertigen Parameter von u1bu2 bewertete logische Ausdruck φ ist
erfüllt.
b wird dann durch die Bewertung von w ersetzt.
7
3 Vergleich limitierter mit nicht limitierten Systemen
Es kann gezeigt werden, dass die Erzeugungsmächtigkeit limitierter Lindenmayer-Systeme
größer ist als die von nicht limitierten – siehe [7], Satz 14.11:
∀ k ∈ N: L(ET0L) ⊂ L(klET0L)).
Daraus ergibt sich die Frage, inwieweit dies von praktischer Bedeutung sein kann, also ob
Wachstumsprozesse besser beschrieben werden.
Im Folgenden soll demonstriert werden, wie limitierte System zumindest subjektiv ein
„natürlicheres“ Wachstum aufzeigen. Dazu sollen zunächst zwei Bäume betrachtet werden,
die mit 0L generiert wurden. Das zugrundeliegende System (siehe 7.1) ist identisch, mit der
einzigen Ausnahme, dass bei dem rechten Baum eine konstante, uniforme Limitierung (k =
10) verwendet wurde.
Abbildung 1 Baum ohne Limitierung
Abbildung 2 Baum mit Limitierung
Da das zugrundeliegende Lindenmayer-System deterministisch ist, führt eine Berechnung
ohne Limitierung immer zum gleichen Ergebnis; durch Einführung einer Limitierung wird das
System jedoch nichtdeterministisch (Es ist leicht einzusehen, dass die Ableitung für ein
beliebiges Lindenmayer-System nichtdeterministisch ist, sobald das Wachstum die
Limitierung überschreitet.). Das heißt, dass der Baum in Abbildung 1 nur ein Wort einer
möglichen Ableitung repräsentiert. Um dies zu verdeutlichen seien vier weitere Ableitungen
gezeigt (alle in der selben Ableitungstiefe, berechnet mit jeweils anderen Startwerten in 0L):
8
Ableitung 1
Ableitung 2
Ableitung 3
Ableitung 4
Abbildung 3 Nichtdeterministische Ableitung
Die Zahl der möglichen Ableitungen einer bestimmten Tiefe t wächst abhängig vom System
zum Teil sehr stark mit t. Dies soll exemplarisch verdeutlicht werden:
Sei G = (Σ, h, ω) ein 0L-System mit Σ := {a, b, c, d}, ω := a und
h(a) = bcd, h(b) = acd, h(c) = abd, h(d) = abc.
Das System ist offenbar deterministisch, die (einzige) Ableitungsfolge lautet:
a ⇒ bcd ⇒ acd abd abc ⇒ bcd abd abc bcd acd abc bcd acd abd ⇒ ...
Die Wortlänge wächst mit 3t.
Betrachten wir nun das gleiche System mit uniformer Limitierung von k := 3. Eine mögliche
Ableitung ist (mit rein linkslastigen Ersetzungen):
a ⇒ bcd ⇒ acd abd abc ⇒ bcd abd abc abd abc ⇒ acd abd abc abd abc abd abc ⇒ ...
Die Länge eines Wortes w der Ableitungstiefe t beträgt |wt| = 6t – 3 für t ≥ 1. Es können in
jedem Ableitungsschritt nur 3 Symbole zur Ersetzung ausgewählt werden, dies ergibt
9
 | w |   6t − 3 

mt :=  t  = 
 3   3 
verschiedene Ableitungswege im Schritt t. Damit ergibt sich die Zahl der möglichen
Ableitungen einer Tiefe t zu:
t −1
t −1 6i − 3



Mt = ∑ mi = ∑ 
3 
i =1 
i =1
t −1
=
1
∑ 6 (6i − 3)(6i − 4)(6i − 5)
i =1
t −1
≥
∑ (i − 1)
i =1
3
t −2
=
∑i
i =0
3
=
1
(t − 2) 2 (t − 1) 2
4
Es ergibt sich zwar lediglich polynomiales Wachstum der Ableitungsmöglichkeiten, dabei ist
aber zu beachten, dass die Wortlänge nur linear wächst, die Zahl der
Ableitungsmöglichkeiten wächst also erheblich stärker als die Wortlänge. Wenn das
Wachstum des unlimitierten Systems auf das beschränkte Wachstum abgebildet wird (das ist
durchaus sinnvoll, da der Sinn der Limitierung ja nicht darin liegt, kürzere Wörter zu
erzeugen), ergibt sich folgender Zusammenhang:
1
3t1 = 6t 2 − 3 ⇔ t 2 = 3t1 + 3
6
Damit ist die Zahl der Ableitungsmöglichkeiten für ein Wort der Länge 3t
1 1
1
1 1 4t
M t1 ≥ ( 3t1 + 1) 2 ( 3t1 + 2) 2 ≥
3
4 6
6
4 64
3.1
Mögliche Anwendungen
Lindenmayer-Systeme stellen eine ausgesprochen effiziente Komprimierung von PflanzenModellen dar. Durch den inhärenten Nichtdeterminismus limitierter Lindenmayer-Systeme
lassen sich fast beliebig viele verschiedene – jedoch einander ähnelnde – Pflanzen-Modelle
aus einem System ableiten. Zudem erfordert die Berechnung eines statisch implementierten
Systems vergleichsweise wenig Aufwand. Es liegt also eine Anwendung nahe, in der große
Pflanzenbestände generiert werden müssen. Zum Beispiel bei der Simulation eines Waldes in
Computerspielen oder in Applikationen zur Landschaftsplanung könnten limitierte
Lindenmayer-Systeme zum Einsatz kommen, bei denen die Bäume in Echtzeit nur für den
gerade sichtbaren Ausschnitt berechnet werden. Es ergäbe sich daraus eine erheblich größere
Vielfalt, ohne dass die Speicheranforderungen erhöht würden. Da sich zudem noch das Alter
jedes Baumes kontrollieren ließe würde dies zu einem natürlicheren Gesamteindruck führen
und zugleich den Aufwand für das Design der Bäume einsparen.
Durch Limitierungen ergibt sich noch ein weiterer Vorteil: Das Wachstum wird linear
beschränkt und lässt sich somit besser kontrollieren, während es bei nicht-limitierten
Systemen nur exponentiell beschränkt ist. So werden im obigen Beispiel ohne Limitierung
lediglich elf Ableitungsschritte benötigt, um einen bereits sehr komplexen, ausgewachsenen
Baum zu erzeugen. In der limitierten Version hingegen benötigt ein ähnliches Ergebnis,
abhängig von der Limitierung, mehrere hundert bis tausend Schritte. Dadurch wird ein
feingranulierter Wachstumsprozess möglich, der eine realistische Simulation erlaubt.
10
4 Bedienung von 0L
4.1
Voraussetzungen
Um 0L starten zu können, muss auf dem System eine Java Runtime Environment (JRE) ab
Java Version 1.3 sowie das zusätzliche Paket Java 3D installiert sein. Beides ist für
verschiedene Plattformen (Linux, Solaris, Windows etc.) erhältlich; unter [6] sind weitere
Informationen und die genauen Links zu finden.
4.2
Installation
Eine Installation ist nicht notwendig. Das Programm 0L besteht einzig aus der Datei
„lindenmayer.jar“, die durch folgenden Aufruf gestartet werden kann:
> java –jar lindenmayer.jar
Voraussetzung ist dabei, dass „java“ sich im Pfad befindet. Windows-Benutzer können die
Applikation alternativ durch Doppelklick starten.
4.3
Programmoberfläche
Abbildung 4 Programmoberfläche
Nach dem Start präsentiert 0L zunächst ein leeres Projekt. Im Menü „Project“ kann mit „New
Window“ ein weiteres leeres Projektfenster geöffnet werden. „Open...“ lädt eine Datei in das
aktuelle Projektfenster, sofern dieses leer ist, oder erzeugt ein neues Projektfenster. „Save“
speichert das aktuelle Projekt. Ist dieses noch nicht betitelt, so wird ein Dateidialog geöffnet
mit der Aufforderung, einen Dateinamen zu wählen. Mit „Save As...“ kann ein Projekt unter
einem neuen Dateinamen gespeichert werden.
Im oberen Fensterbereich sind drei Registerkarten zu sehen. „Editor“ enthält den
Projekteditor, in dem das zu berechnende Lindenmayer-System in der Beschreibungssprache
(siehe Kapitel 5) spezifiziert wird. Unter „Derivation“ ist die aktuelle Ableitungsfolge zu
sehen, Worte werden ab einer Länge von 255 Symbolen (nicht dargestellter Zeichen)
abgeschnitten. „Selected Word“ zeigt das unter „Derivation“ gewählte Wort vollständig an.
Im rechten Fensterbereich sind die Kontrollelemente untergebracht. Da die Ableitung in
vielen Fällen nicht deterministisch ist, kann unter „Seed for randomizer“ ein Startwert für den
Zufallsgenerator eingegeben werden, der bestimmt, auf welche Weise ein Wort abgeleitet
11
wird. Wird der gleiche Startwert für zwei Ableitungen des selben Systems genutzt, so ist auch
die Ableitung die gleiche. Mittels eingeschaltetem „Random seed“ wird vor jeder AbleitungsBerechnung ein neuer Startwert eingetragen. Die Ableitungsberechnung lässt sich anhand
zweier Parameter beschränken: „Maximal depth“ gibt den Maximalwert für die Tiefe der
Ableitung an, bei einem Wert von n werden maximal n+1 Worte erzeugt (n abgeleitete Wörter
und das Axiom). „Maximal word length“ beschränkt die maximale Länge der abgeleiteten
Wörter. Wird diese überschritten, so stoppt der Ableitungsprozess. Es werden folglich so viele
Ableitungsschritte berechnet, bis eines der Beschränkungskriterien erfüllt ist.
Der Ableitungsprozess kann mit „Start Derivation“ gestartet und mit „Stop Derivation“
vorzeitig abgebrochen werden. „Star Derivation“ aktiviert außerdem die Registerkarte
„Derivation“, in der der Ableitungsprozess mitverfolgt werden kann.
Abbildung 5 Der Ableitungsprozess
Wird ein Wort in der Ableitungsfolge ausgewählt, so kann dieses unter „Selected Word“
betrachtet werden. Die Interpretation dieses Wortes wird mit „Interpretation“ gestartet: Ein
neues Fenster öffnet sich und zeigt – je nach Beschreibung – die zweidimensionale bzw.
dreidimensionale graphische Darstellung an.
12
Abbildung 6 Interpretation 3D
Abbildung 7 Interpretation 2D
Die Navigation in der dreidimensionalen Darstellung erfolgt im Wesentlichen über die Maus.
Bei gedrückter linker Maustaste kann die Kamera um den Nullpunkt rotiert werden. (Der
Nullpunkt ist die Startposition des Turtles bei der Interpretation, also in der obigen Abbildung
z.B. das untere Ende das Baumstammes.) Mit gedrückter rechter Maustaste kann die Kamera
geschwenkt werden (das Entspricht subjektiv dem Verschieben der Darstellung). Schließlich
kann mittels gedrückter mittlerer Maustaste (alternativ „Alt“ und linke Maustaste) in die
Szene hinein- bzw. herausgezoomt werden. Wird das Fenster vergrößert, so vergrößert sich
entsprechend auch die Darstellung.
In der zweidimensionalen Ansicht ist keine Navigation möglich, die Darstellung wird so
gestreckt, dass sie optimal im Fenster Platz findet.
13
5 Beschreibungssprache
Lindenmayer-Systeme werden in 0L mit Hilfe einer speziellen Sprache beschrieben, die ein
höheres Maß an Flexibilität bietet, als dies durch eine statische Eingabemaske zu erreichen
wäre. Die Notation weicht zwangsläufig von der üblichen formalen Notation ab.
5.1
Formatfreiheit
Die Beschreibungssprache von 0L ist formatfrei, d.h. Whitespace, also Leerzeichen,
Tabulatoren und Zeilenumbrüche, kann beliebig zur Strukturierung genutzt werden.
5.2
Kommentare
Kommentare dürfen an beliebiger Stelle im Quelltext auftreten. Die Syntax ist die aus C++
und Java bekannte:
// Kommentar
für einzeilige Kommentare, d.h. der Rest der Zeile wird ignoriert bzw.
/* Kommentar ... */
für Kommentarblöcke, also auch mehrzeilig.
5.3
Programmstruktur
Der generelle Aufbau einer Lindenmayer-System-Beschreibung sieht folgendermaßen aus:
constants = (<constant-definition>);
symbols = (<symbol-definition>);
axiom = <word >;
substitution = (
table = (
<substitution>*
);
);
limitation:<type>[ = <function>];
interpretation:<type> = (
<symbol-interpretation>*
);
Keiner dieser Abschnitte darf fehlen.
5.4
Konstantendefinition
Um das Experimentieren mit verschiedenen Parametern zu erleichtern, können Konstanten
definiert werden. Dies geschieht im Abschnitt constants. Konstantenbezeichner
(<identifier>) beginnen mit einem Buchstaben gefolgt von einer beliebigen
Kombination aus Buchstaben und Zahlen. Sonderzeichen bzw. Umlaute sind nicht erlaubt.
Bezeichner werden in 0L generell Case-Sensitive behandelt, d.h. Groß- und Kleinschreibung
ist relevant.
Erlaubt sind folgende Ausdrücke innerhalb von <constant-definition>:
<identifier> = <value>;
<identifier> = <expression>;
14
Wobei <value> ein beliebiger numerischer Wert in Dezimalschreibweise (z.B. „0.1“, „5“,
eine Null vor dem Dezimalpunkt darf nicht ausgelassen werden) sein kann. <expression>
kann ein arithmetischer Ausdruck sein, erlaubt sind Addition „+“, Subtraktion „-“,
Multiplikation „*“ sowie Division „/“ als Operationen, weiterhin mathematische Funktionen
(siehe 5.10) sowie mathematische Konstanten (siehe 5.11) und in vorhergehenden
Anweisungen definierte Konstanten als Operanden
Beispiel:
constants = (
q = 0.40;
leafMin = 50;
leafScale = 1.5;
// Berechnungen, e ist eine mathematische Konstante
q1 = pow(q, e);
q2 = pow(1-q, e);
);
5.5
Symboldefinition
Alle Symbole des Lindenmayer-Systems müssen im Abschnitt symbols definiert werden.
Dies geschieht durch Aneinanderreihung der Symboldefinitionen, Whitespace kann zur
Trennung der Symboldefinitionen genutzt werden, dies ist aber nicht zwingend.
Eine Symboldefinition besteht aus einem Symbolbezeichner sowie eine optionalen
Symbolsignatur, wenn es sich um ein parametrisiertes Symbol handelt.
Symbolbezeichner beginnen mit einem Buchstaben oder einem der folgenden Sonderzeichen:
[ ] ? # ~ ^ & % $ " + - _
Auf das erste Zeichen kann eine beliebig lange Kombination von Ziffern folgen.
Die optionale Signatur ist die in runden Klammer eingeschlossene, durch Kommata getrennte
Aufzählung der Parametertypen. Zur Zeit ist nur der Typ real für „reelle“ Zahlen (In der
Implementierung werden Fließkommazahlen doppelter Genauigkeit verwendet.).
Beispiel:
symbols = (
aAX0X1 y(real, real) z(real)
);
Es werden somit sechs Symbole definiert: a, A, X0, X1, y, z. Das Symbol y ist mit zwei
reellwertigen und das Symbol z einem reellwertigen Parameter ausgestattet. Zu beachten ist,
dass die hier definierte Signatur bei allen folgenden Symbolverwendungen eingehalten
werden muss. Beispielsweise würde y(1) eine Fehlermeldung verursachen.
5.6
Axiomdefinition
Das Axiom wird im Abschnitt axiom definiert. Erlaubt ist ein beliebiges Wort (auch das
leere, wenngleich wenig sinnvoll) über die in symbols definierten Symbole. Bei
parametrischen Symbolen müssen die einzelnen Parameter mit Werten belegt werden. Dies
können numerische Werte sein, aber auch arithmetische Ausdrücke unter der Verwendung der
allgemeinen mathematischen sowie der in constants definierten Konstanten. Näheres ist
im Kapitel 5.4 unter der Definition von <value> und <expression> zu finden.
Beispiel:
axiom = X0y(1, pow(q2, e) * leafMin)z(leafScale);
15
5.7
Substitutionen
Innerhalb des substitution-Blocks werden die Tafeln mittels table-Blöcken definiert.
Wird nur eine Tafel angegeben, so kann der umschließende substitution-Block auch
weggelassen werden. Innerhalb eines table-Blocks werden die eigentlichen
Ersetzungsregeln angegeben.
Eine Ersetzungsregel besteht aus einem optionalen linken Kontext, dem zu ersetzenden
Symbol, einem optionalen rechten Kontext, einer optionalen Bedingung sowie dem
Ersetzungswort. Linker und rechter Kontext werden dabei in spitzen Klammern („<>“)
angegeben, die Bedingung durch einen senkrechten Strich („|“) abgetrennt, das
Ersetzungswort durch ein Gleichheitszeichen („=“).
Die Parameter der Symbole des linken und rechten Kontexts beziehungsweise des zu
ersetzenden Symbols müssen mit Variablen belegt werden. Diese Variablen können in der
Bedingung als auch auf der rechten Seite der Substitution verwendet werden. Die Bedingung
ist ein beliebiger boolescher Ausdruck (siehe 5.12); ist die Bedingung nicht erfüllt, so wird
die Substitution nicht angewandt.
Die Parameter der Symbole des Ersetzungswortes müssen mit Werten belegt werden. Dies
können numerische Werte und arithmetische Ausdrücke sein, die von den allgemeinen
mathematischen und den in constants definierten Konstanten sowie von den Variablen der
linken Seite der Substitution abhängen (siehe Kapitel 5.4, Definition von <value> und
<expression>).
Beispiel:
<X0z(x0)> y(x1, x2) <X1> | x0 >= x1*x2 = X0y(x0*x1, x0+x2)X1;
Innerhalb einer Tafel können beliebig viele Ersetzungsregeln angegeben werden, sind sie
hinsichtlich Ersetzungssymbol, Kontext und Bedingung nicht disjunkt, so führt dies zu
nichtdeterministischen Ableitungen.
Ist keine der Regeln auf ein Symbol anwendbar, so impliziert dies die identische Ersetzung
für dieses Symbol.
Bei Angabe mehrerer Tafeln wird vor jedem Ableitungsschritt zufällig eine Tafel gewählt, die
Symbole des Wortes werden dann nach den Regeln der gewählten Tafel abgeleitet.
Beispiel:
substitution = (
table = (
a = y(0, 0);
y(a, b) = y(a*b, b+1);
<y(a, b)> z(c) | c < a*b = z(c*1.1);
);
table = (
a = A;
y(a, b) = X0;
z(a) = X1 ;
);
);
16
5.8
Limitierungen
Soll das System nicht beschränkt sein, so ist dies mit
limitation:none;
anzugeben. Uniforme und normale Limitierungen werden durch einen arithmetische
Ausdruck bestimmt, der von der Variable n abhängen kann, die die Ableitungstiefe
repräsentiert. Ist das Ergebnis nicht ganzzahlig, so wird die nächstkleinere ganze Zahl
angenommen. Ein Ergebnis kleiner Null hat den gleichen Effekt wie Null: Es wird keine
Ersetzung vorgenommen.
Beispiel:
limitation:normal = 5;
limitation:uniformly = pow(2, n);
5.9
Interpretation
Im Abschnitt interpretation wird die Interpretation der Symbole definiert, das heißt die
Zuordnung von Symbol zu einer Folge von Anweisungen an die Visualisierung.
Hinter dem Schüsselwort interpretation wird durch Doppelpunkt getrennt der Typ der
Visualisierung festgelegt.
Visualisierungstypen:
Bezeichnung
Beschreibung
turtle2d
zweidimensionale Turtle-Interpretation
turtle3d
dreidimensionale Turtle-Interpretation
Innerhalb des interpretation-Blocks kann für jedes Symbol eine Reihe von
Anweisungen (statements) angegeben werden. Die Visualisierung stellt sowohl Variablen
als auch Methoden zur Verfügung, die in den Anweisungen genutzt werden können,
genaueres dazu in den Kapiteln 5.9.1 und 5.9.2.
Eine Anweisung ist entweder eine Zuweisung in der Form
<variable> = <expression>;
oder ein Methodenaufruf (ohne Auswertung des Ergebnisses):
<method>(<parameter_list>);
wobei die durch Kommata separierten Parameter in <parameter_list> wieder
arithmetische Ausdrücke (<expression>) sind.
17
Beispiel:
interpretation:turtle3d = (
y(a, b) = (
rotateX(a);
rotateY(b);
);
z(l) = (
draw(l);
);
X0 = (
push();
);
X1 = (
pop();
);
a = (
setMaterial(green);
);
);
5.9.1 Interpretation „turtle2d“
Der 2D-Turtle bewegt sich auf einer Ebene, seine Orientierung ist durch die Rotation um den
die aktuelle Position gegeben.
y
x
Abbildung 8 Orientierung des 2D-Turtles
Der Turtle verfügt über eine Stack, auf dem der aktuelle Zustand gespeichert werden kann.
Ein Zustand des Turtles besteht aus Rotationswinkel, Position, Liniendicke sowie Linienfarbe.
Methoden:
Methode
move(l)
Beschreibung
draw(l)
Zeichnet eine Linie
Bewegungsrichtung
rotate(alpha)
Rotiert den Turtle um alpha.
stroke(d)
Erhöht die Liniendicke um d.
setRotation(alpha)
Setzt die absolute Rotation auf alpha.
getRotation()
Gibt die absolute Rotation zurück
setStroke(d)
Setzt die Liniendicke auf d.
Bewegt den Turtle um l nach vorne ohne zu
zeichnen.
der
Länge
l
in
18
getStroke()
Gibt die Liniendicke zurück.
setColorRed(x)
Setzt den Rot-Anteil der Linienfarbe auf x.
getColorRed()
Gibt den Rot-Anteil der Linienfarbe zurück.
setColorGreen(x)
Setzt den Grün-Anteil der Linienfarbe auf x.
getColorGreen()
Gibt den Grün-Anteil der Linienfarbe zurück.
setColorBlue(x)
Setzt den Blau-Anteil der Linienfarbe auf x.
getColorBlue()
Gibt den Blau-Anteil der Linienfarbe zurück.
red()
Setzt die Linienfarbe auf Rot.
green()
Setzt die Linienfarbe auf Grün.
blue()
Setzt die Linienfarbe auf Blau.
push()
Speichert den Zustand des Turtles auf dem
Stack.
pop()
Lädt einen Turtle-Zustand vom Stack.
Es werden keine Variablen bereitgestellt.
5.9.2 Interpretation „turtle3d“
Der 3D-Turtle bewegt sich in einem dreidimensionalen Raum mit rechtshändigem
Inertialsystem. Der Turtle kann dabei um alle drei Achsen rotiert und in Richtung des durch
die Rotation bestimmten Normalenvektors bewegt werden. Rotationen beziehen sich immer
auf die aktuelle Ausrichtung des Turtles im Raum.
y
x
z
Abbildung 9 Orientierung des 3D-Turtles
Ebenso wie der 2D-Turtle verfügt der 3D-Turtle über einen Stack, auf dem der vollständige
Zustand gespeichert werden kann, also Orientierung, Position, Liniendicke und Materialfarbe.
Methoden:
Methode
move(l)
Beschreibung
draw(l)
Zeichnet einen Zylinder der Länge l.
drawSphere(d)
Zeichnet eine Kugel mit Durchmesser d.
setLineWidth(d)
Setzt den Durchmesser der mit draw
Bewegt den Turtle um l nach vorne, ohne zu
zeichnen.
19
erzeugten Zylinder auf d.
incLineWidth(delta)
Erhöht den Zylinderdurchmesser um delta.
setMaterial(material)
Setzt das Material, siehe Tabelle „Variablen“.
rotateX(alpha)
Rotiert den Turtle um die X-Achse.
rotateY(alpha)
Rotiert den Turtle um die Y-Achse.
rotateZ(alpha)
Rotiert den Turtle um die Z-Achse.
rotate(alpha)
Äquivalent zu rotateZ(alpha).
push()
Speichert den Zustand des Turtles auf dem
Stack.
pop()
Lädt einen Turtle-Zustand vom Stack.
Variablen:
Variable
brown
Beschreibung
green
Materialfarbe grün.
blue
Materialfarbe blau.
Materialfarbe braun.
5.10 Mathematische Funktionen
Die folgenden mathematischen Funktionen können in allen arithmetischen Ausdrücken
verwendet werden:
Funktion
pow(x, y)
Ergebnis
exp(x)
ex
sqr(x)
x2
sqrt(x)
x1/2
root(x, y)
y1/x
sin(a)
sin(a), a im 360°-Maß
cos(a)
cos(a), a im 360°-Maß
tan(a)
tan(a), a im 360°-Maß
max(x, y)
max{x, y}
min(x, y)
min{x, y}
abs(x)
|x|
xy
20
5.11 Mathematische Konstanten
Als mathematische Konstanten stehen zur Verfügung:
Variable
Wert
e
e
pi
π
5.12 Boolesche Ausdrücke
Boolesche Ausdrücke werden in den Bedingungen von Substitutionsregeln benutzt. Erlaubt
sind die binären Operatoren and sowie or und der unäre Operator not. Als Operanden sind
true und false sowie arithmetische Vergleiche zulässig. Um die Schreibweise zu
vereinfachen, unterliegen die Operatoren der üblichen Rangordnung: not bindet stärker als
and, and bindet stärker als or. Zur Gruppierung können runde Klammern eingesetzt
werden.
Ein arithmetischer Vergleich besteht aus einem linken arithmetischen Ausdruck, dem
Vergleichsoperator und einem rechten arithmetischen Ausdruck. Die Tabelle der
Vergleichsoperatoren:
Operator
a == b
Bedeutung
a <= b
a≤b
a >= b
a≥b
a < b
a<b
a > b
a>b
a != b
a≠b
a=b
Beispiel:
x > 2 and not (x != 3 or false)
21
5.13 Formale Syntax
Im folgenden wird die formale Syntax der Beschreibungssprache in EBNF angegeben,
Whitespaces und Kommentare werden dabei nicht berücksichtigt:
SYSTEM =
CONSTANTS_SECTION
SYMBOLS_SECTION
AXIOM_SECTION
SUBSTITUTION_SECTION
LIMITATION_SECTION
INTERPRETATION_SECTION.
CONSTANTS_SECTION =
CONSTANTS
ASSIGN
LPAREN
{ CONSTANT_DEFINITION }
RPAREN
SEMICOLON.
CONSTANT_DEFINITION =
VARIABLE
ASSIGN
EXPRESSION_ARITHMETIC.
SYMBOLS_SECTION =
SYMBOLS
ASSIGN
LPAREN
{ SYMBOL_DEFINITION }
RPAREN
SEMICOLON.
AXIOM_SECTION =
AXIOM
ASSIGN
WORD_EXPRESSION
SEMICOLON.
SUBSTITUTION_SECTION =
TABLE_DEFINITION
| SUBSTITUTION
ASSIGN
LPAREN
{ TABLE_DEFINITION }
RPAREN
SEMICOLON.
TABLE_DEFINITION =
TABLE
ASSIGN
LPAREN
{ RULE }
RPAREN
SEMICOLON.
22
RULE =
[ LT WORD_CONSTANT GT ]
SYMBOL_VARIABLE
[ LT WORD_CONSTANT GT ]
[ PIPE EXPRESSION_BOOLEAN ]
ASSIGN
WORD_EXPRESSION
SEMICOLON.
LIMITATION_SECTION =
LIMITATION
COLON
LIMITATION_TYPE
[ ASSIGN EXPRESSION_ARITHMETIC ]
SEMICOLON.
LIMITATION_TYPE = NONE | NORMAL | UNIFORMLY.
INTERPRETATION_SECTION =
INTERPRETATION
COLON
INTERPRETATION_TYPE
ASSIGN
LPAREN
{ SYMBOL_INTERPRETATION }
RPAREN
SEMICOLON.
SYMBOL_INTERPRETATION =
SYMBOL_VARIABLE
ASSIGN
LPAREN
{ STATEMENT }
RPAREN
SEMICOLON.
STATEMENT = ( ASSIGNMENT | METHOD_CALL ) SEMICOLON.
ASSIGNMENT =
VARIABLE
ASSIGN
EXPRESSION_ARITHMETIC.
SYMBOL_DEFINITION =
SYMBOL_IDENTIFIER
[ LPAREN
[ PARAMETER_TYPE { COMMA PARAMETER_TYPE } ]
RPAREN ].
SYMBOL_VARIABLE =
SYMBOL_IDENTIFIER
[ LPAREN
[ VARIABLE { COMMA VARIABLE } ]
RPAREN ].
SYMBOL_EXPRESSION =
SYMBOL_IDENTIFIER
[ LPAREN
[ EXPRESSION_ARITHMETIC { COMMA EXPRESSION_ARITHMETIC } ]
RPAREN ].
WORD_VARIABLE = { SYMBOL_VARIABLE }.
23
WORD_EXPRESSION = { SYMBOL_EXPRESSION }.
PARAMETER_TYPE = REAL.
EXPRESSION_ARITHMETIC =
NUMBER
| VARIABLE
| LPAREN EXPRESSION_ARITHMETIC RPAREN
| EXPRESSION_ARITHMETIC OPERAND_ARITHMETIC EXPRESSION_ARITHMETIC
| METHOD_CALL.
VARIABLE = IDENTIFIER.
METHOD_CALL =
IDENTIFIER
LPAREN
[EXPRESSION_ARITHMETIC {COMMA EXPRESSION_ARITHMETIC}]
RPAREN.
OPERAND_ARITHMETIC = PLUS | MINUS | STAR | SLASH.
EXPRESSION_BOOLEAN =
TRUE
| FALSE
| LPAREN EXPRESSION_BOOLEAN RPAREN
| OPERAND_BOOLEAN_UNARY EXPRESSION_BOOLEAN
| EXPRESSION_BOOLEAN OPERAND_BOOLEAN_BINARY EXPRESSION_BOOLEAN
| COMPERATION_ARITHMETIC.
OPERAND_BOOLEAN_UNARY = NOT.
OPERAND_BOOLEAN_BINARY = AND | OR.
COMPARATION_ARITHMETIC =
EXPRESSION_ARITHMETIC
COMPERATOR_ARITHMETIC
EXPRESSION_ARITHMETIC.
COMPERATOR_ARITHMETIC = GT | LT | GE | LE | NE | EQ.
NUMBER = DIGIT+ [ COMMA DIGIT+ ].
IDENTIFIER = LITERAL (DIGIT | LITERAL)*.
DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
LPAREN = "(".
RPAREN = ")".
SEMICOLON = ";".
COLON = ":".
COMMA = ",".
ASSIGN = "=".
PLUS = "+".
MINUS = "-".
STAR = "*".
SLASH = "/".
GT = ">".
LT = "<".
GE = ">=".
LE = "<=".
NE = "!=".
EQ = "==".
PIPE = "|".
TRUE = "true".
FALSE = "false".
24
CONSTANTS = "constants".
SYMBOLS = "symbols".
AXIOM = "axiom".
SUBSTITUTION = "substitution".
TABLE = "table".
LIMITATION = "limitation".
NONE = "none".
NORMAL = "normal".
UNIFORMLY = "uniformly".
INTERPRETATION = "interpretation".
TURTLE2D = "turtle2d".
TURTLE3D = "turtle3d".
REAL = "real".
25
6 Architektur
0L ist vollständig in Java implementiert, für die dreidimensionale Darstellung wurde auf das
Paket Java 3D zurückgegriffen. Kernstück der Architektur ist die Klasse System, die ein
Lindenmayer-System vollständig repräsentiert. Der Parser (siehe 6.1) übernimmt die
Transformation eines in der Beschreibungssprache beschriebenen Lindenmayer-Systems in
eine Instanz der Klasse System.
6.1
Parser
Der Parser wurde mit Hilfe von antlr [2] erstellt, einem Tool zum Erzeugen von LL(k)Lexern und -Parsern aus regulären Grammatiken, die um semantische und syntaktische
Prädikate erweitert werden können. Die Grammatik ist in der Datei „LindenmayerParser.g“
angegeben, antlr generiert daraus mit dem Aufruf
> java antlr.Tool LindenmayerParser.g
die folgenden Java-Klassen-Quellcodes:
LindenmayerParser.java
LindenmayerParserTokenTypes.java
LindenmayerLexer.java
LindenmayerLexerTokenTypes.java
Der generierte Parser kann folgendermaßen genutzt werden, um eine Instanz der Klasse
System zu erzeugen:
LindenmayerLexer lexer = new LindenmayerLexer(Reader);
LindenmayerParser parser = new LindenmayerParser(lexer);
System system = parser.definition_system();
6.2
Interpretation
Grundgedanke beim Entwurf war eine Separierung der graphischen Darstellung von der
Modell-Ebene. Das Ergebnis ist eine sehr lose Kopplung zwischen System und Darstellung:
Die darstellenden Klassen (namentlich Turtle2D sowie Turtle3D) werden als
Provider bei der interpretierenden Klasse Interpretation registriert. Ein Provider
kann beliebig viele Funktionen und Variablen anbieten, die in den Statements der
Interpretation genutzt werden können. Die Zuordnung wird anhand von Bezeichnern
vollzogen. Aus dieser Trennung ergibt sich die Möglichkeit grundverschiedene
Darstellungsformen zu implementieren, die zudem keine Kenntnis davon haben müssen, dass
sie von einem Lindenmayer-System bedient werden, also auch keine entsprechende Logik
implementieren müssen. Als nachteilig erweist sich hingegen, dass eine
„Rückwertsauflösung“, also z.B. die Zuordnung von Graphikelementen zu Teilwörtern des
interpretierten Wortes, nicht möglich ist.
26
6.3
Klassendiagramme
Im folgenden werden die wichtigsten Beziehungen zwischen den Klassen angegeben. Diese
Darstellung stellt keinen Anspruch auf Vollständigkeit, sondern soll vielmehr dem
Verständnis der Architektur helfen.
6.3.1 System
Provider {interface}
+ getMethods(): Methdo[]
+ getVariables(): Variable[]
1
System
1
1
axiom 1
1
1
1
<<implements>>
MathProvider
ConstantDefinition
SymbolsDefinition
WordConstant
Substitution
<<implements>>
Limitation {interface}
LimitationNone
+ getLimitationCount(depth: int)
LimitationNormal
Interpretation
LimitationUniformly
Abbildung 10 Die Klasse System
6.3.2 Substitutionen
Substitution
*
Table
*
Rule
leftContext
1
rightContext
1
symbol
1
condition
1
substitute
1
WordVariable
WordVariable
SymbolVariable
ExpressionBoolean
WordExpression
Abbildung 11 Die Klasse Substitution
27
6.3.3 Worte und Symbole
*
WordConstant
SymbolConstant
parameters
SymbolsDefinition
*
ExpressionArithmetic
*
WordVariable
1
SymbolVariable
*
SymbolDefinition
id: String
parameterCount: int
parameters
*
Variable
*
WordExpression
SymbolExpression
parameters
*
ExpressionArithmetic
Abbildung 12 Beziehungen zwischen Worten und Symbolen
6.3.4 Arithmetische Ausdrücke
ExpressionArithmetic {abstract}
2
Addition
2
Subtraction
2
Multiplication
2
Division
ExpressionArithmetic {abstract}
ExpressionArithmetic {abstract}
ExpressionArithmetic {abstract}
ExpressionArithmetic {abstract}
NumberDouble
value: double
1
Reference
id: String
*
Function
id: String
Variable
ExpressionArithmetic {abstract}
Statement {abstract}
Assignment
1
1
MethodCall
id: String
1
*
Reference
ExpressionArithmetic {abstract}
Method {interface}
ExpressionArithmetic {abstract}
Abbildung 13 Klassendiagramm arithmetischer Ausdrücke
28
6.3.5 Boolesche Ausdrücke
ExpressionBoolean {abstract}
+ evaluateBoolean()
+ assignVariables(variableMap: Map)
+ assignMethods(methodMap: Map)
True
False
2
Conjunction
2
Disjunction
1
Negation
2
Equal
2
GreaterThan
2
GreaterOrEqual
2
LessThan
2
LessOrEqual
2
Unequal
ExpressionBoolean {abstract}
ExpressionBoolean {abstract}
ExpressionBoolean {abstract}
ExpressionArithmetic {abstract}
ExpressionArithmetic {abstract}
ExpressionArithmetic {abstract}
ExpressionArithmetic {abstract}
ExpressionArithmetic {abstract}
ExpressionArithmetic {abstract}
Abbildung 14 Klassendiagramm boolescher Ausdrücke
6.3.6 Interpretation
Interpretation
+ setProvider(p: Provider)
*
SymbolInterpretation
1
*
SymbolVariable
Statement
interpretationProvider
Provider {interface}
<<implements>>
Turtle2D
Turtle3D
Abbildung 15 Klassendiagramm Interpretation
29
7 Anhang
7.1
/*
*/
Beispiel für ein Lindenmayer-System
tree3d.lms
Uncomment one of the lines (a) - (i) in the
constants section
constants = (
r1 = 0.80;
r2 = 0.80;
alpha1 = 30;
alpha2 = -30;
phi1 = 137;
phi2 = 137;
w0 = 30;
q = 0.50;
e = 0.50;
min = 0.0;
// Minimal value for s to generate Leafs
leafMin = 50;
leafScale = 1.5;
// Some calculation
q1 = pow(q, e);
q2 = pow(1-q, e);
);
symbols = A(real,real) F(real) l(real) +(real) #(real) [] L;
axiom = A(100, w0);
table = (
A(s,w) | s > leafMin && s >= min
=
l(w)F(s) [ +(alpha1) #(phi1) A(s * r1, w * q1) ]
[ +(alpha2) #(phi2) A(s * r2, w * q2) ];
A(s,w) | s <= leafMin && s >= min
=
l(w) LF(s)L [ +(alpha1) #(phi1) A(s * r1, w * q1) ]
[ +(alpha2) #(phi2) A(s * r2, w * q2) ];
);
limitation:none;
//limitation:uniformly = 3;
interpretation:turtle3d = (
F(s) = (
draw(s/100);
);
l(w) = (
30
);
setLineWidth(w/300);
+(r) = (
rotateX(r);
);
#(r) = (
rotateY(r);
);
[ = (
);
] = (
);
L = (
);
push();
pop();
push();
rotateZ(90);
setMaterial(green);
setLineWidth(0.005*leafScale);
draw(0.05*leafScale);
rotateX(90);
setLineWidth(0.025*leafScale);
draw(0.005*leafScale);
pop();
);
31
8 Abbildungsverzeichnis
Abbildung 1 Baum ohne Limitierung ........................................................................................ 8
Abbildung 2 Baum mit Limitierung........................................................................................... 8
Abbildung 3 Nichtdeterministische Ableitung........................................................................... 9
Abbildung 4 Programmoberfläche ........................................................................................... 11
Abbildung 5 Der Ableitungsprozess ........................................................................................ 12
Abbildung 6 Interpretation 3D ................................................................................................. 13
Abbildung 7 Interpretation 2D ................................................................................................. 13
Abbildung 8 Orientierung des 2D-Turtles ............................................................................... 18
Abbildung 9 Orientierung des 3D-Turtles ............................................................................... 19
Abbildung 10 Die Klasse System............................................................................................. 27
Abbildung 11 Die Klasse Substitution ..................................................................................... 27
Abbildung 12 Beziehungen zwischen Worten und Symbolen................................................. 28
Abbildung 13 Klassendiagramm arithmetischer Ausdrücke.................................................... 28
Abbildung 14 Klassendiagramm boolescher Ausdrücke ......................................................... 29
Abbildung 15 Klassendiagramm Interpretation ....................................................................... 29
32
9 Literaturverzeichnis
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
F. Böhmer: Internetseite zu 0L http://www.lindenmayer.innercitylife.net.
T. Parr: Internetseite zu antlr http://www.antlr.org.
P. Prusinkiewicz, Jim Hanan, Mark Hammel, Radomír Mêch: L-systems: from the
theory to visual models of plants.
P. Prusinkiewicz, A. Lindenmayer: The Algorithmic Beauty of Plants. Springer,
Berlin 1990.
G. Rozenberg, A. Salomaa: The Mathematical Theory of L Systems. Academic Press,
New York 1980.
Sun Microsystems: Sun Java Internetseite http://www.java.sun.com.
D. Wätjen: Automatentheorie und Formale Sprachen. Vorlesungsskript (1999),
196-252.
D. Wätjen: k-Limited 0L-Systems and Languages. J. Inf. Process. Cybernet. EIK 24
(1988), 267-285.
D. Wätjen: On k-uniformly-limited T0L Systems and Languages. J. Inf. Process.
Cybernet. EIK 26 (1990), 229-238.
33