Aufbaudiagramme

Aufbaudiagramme können verwendet werden, um den Aufbau von Programmteilen, wie Literalen, zu beschreiben (daher die Bezeichnung „Aufbaudiagramm“). Ein Aufbaudiagramm wird einfach nur als „Diagramm“ bezeichnet, wenn dadurch keine Mißverständnisse zu befürchten sind.

Aufbaudiagramme erlauben eine präzise und verständliche Darstellung von Regeln zum Aufbau von Programmen. Ihr Erlernen bereitet das Erlernen von Notationen wie EBNF und regulären Ausdrücken vor.

Da Aufbaudiagramme Bilder sind, können sie nicht so leicht wie die Alternative EBNF mit Quelltext verwechselt werden. Während der Quelltext und EBNF textorientierte Lerntypen anspricht, sprechen die Aufbaudiagramme bildorientierte Lerntypen an und sorgen so für einen gewissen Ausgleich bei Erlernen der textbasierten Programmiersprachen.

Das Erlernen von Aufbaudiagrammen bereitet die Lektüre von Fachliteratur und Sprachspezifikationen vor, in denen oft Aufbaudiagramme (oder ähnliche Notationen, wie EBNF) verwendet werden. (Beispielsweise: in „Das Beste an JavaScript“ von Douglas Crockford, „Programmieren in Java 1.5“ von Gregor Fischer und Jürgen Wolff von Gudenberg, „Grundlegende Elemente des Programmierens“ von Kaiser)

Das Erlernen von Aufbaudiagramme bereitet auch das spätere Erlernen von EBNF und Grammatiken sowie der programmatischen Analyse von Eingaben oder Texten vor, zu deren Beschreibung Aufbaudiagramme oder ähnliche Notationen verwendet werden.

Zur Verwendung von Aufbaudiagrammen

Aufbaudiagramme sind kein  Teil des Quelltextes, sie werden also nicht  in Programme hineingeschrieben!

Aufbaudiagramme geben Regeln  zum Aufbau des Quelltexts wieder.

Es ist nicht nötig, daß Leser selber Aufbaudiagramme schreiben  können, es reicht, wenn sie diese lesen  können, und selbst das ist zum Verständnis des Kurses nicht unbedingt nötig, sondern wird hier in der Hoffnung behandelt, daß es das Verständnis des Aufbaus von Programmteilen erleichtert, indem es die einschlägigen Regeln als Bild wiedergibt.

Lernhinweis Obwohl Aufbaudiagramm zu Verständnis des Aufbaus von Programmiersprachen hilfreich sind, können auch Leser, die zunächst noch Schwierigkeiten beim Verständnis von Aufbaudiagrammen haben, dem Kurs weiterhin weitgehend folgen, da die Informationen der Aufbaudiagramme oft noch einmal näherungsweise durch Erklärungen in Textform und durch Beispiele gegeben werden.

Kategorien und ihre Exemplare

Ein Exemplar  einer Kategorie ist ein spezieller Fall (ein konkretes Exemplar) dieser Kategorie, beispielsweise ist das Vorzeichen »+« eine Exemplar der Kategorie „Vorzeichen“.

Kategorie und Exemplar (Beispiel)

.------------.
| Vorzeichen |    Kategorie
'------------'
      ^
      |
.------------.
|     +      |    Exemplar
'------------'

Aufbaudiagramme

Ein Aufbaudiagramm  gibt an, wie ein Exemplar einer bestimmten Kategorien  hergestellt wird („aufgebaut“ ist).

Das folgende Aufbaudiagramm beschreibt beispielsweise das ein Wort der Kategorie „Vorzeichen“ ein Plus »+« oder ein Minus »-« sein kann.

Aufbaudiagramm mit der Kategorie »Vorzeichen«

Vorzeichen
            .-.    
|-|---.--->( + )---.--->|-|
      |     '-'    ^
      |     .-.    |
      '--->( - )---'
            '-'

auf deutsch

Ein ›Vorzeichen‹ ist ein »+« oder ein »-«.

Beispiele für Vorzeichen

»+«

»-«

Aufbaudiagramme geben an, wie solche Kategorien aus einzelnen Schriftzeichen  aufgebaut werden.

Die Kategorie eines Aufbaudiagramms (wie ›Vorzeichen‹ in dem obigen Beispiel) sagt, was  durch das Diagramm beschrieben wird. Die Kategorie steht links oben (beispielsweise „Vorzeichen“).

Die Beschreibung der Kategorie folgt dann mit Kästchen, welche durch Linien verbunden sind.

Eine Wort einer Kategorie erhält man, indem man dem Diagramm der Kategorie vom linken Eingang bis zum rechten Ausgang entlang der Pfeile folgt und alle Zeichen aus gerundeten Kästchen hintereinanderschreibt, die man dabei überstreicht.

Das gezeigte Aufbaudiagramm besagt beispielsweise, daß ein ›Vorzeichen‹ ein Pluszeichen »+« oder ein Minuszeichen »-« ist. Es erlaubt uns also, ganz genau festzulegen, was ein Vorzeichen ist.

Wie sagen auch, »+« oder »-« sei ein Exemplar  oder eine Realisierung  der Kategorie „Vorzeichen“, oder einfach »+« oder »-« sei ein  Vorzeichen.

Beispiel „Dezimalziffer“ ⃗

Das folgende Diagramm besagt beispielsweise, daß eine Dezimalziffer eines der Ziffern von »0« bis »9« ist. Es erlaubt uns also, ganz genau festzulegen, was eine Dezimalziffer ist.

Diagramm mit der Kategorie ›Dezimalziffer‹

Dezimalziffer
            .-.
|-|---.--->( 0 )---.--->|-|
      |     '-'    ^
      |     .-.    |
      '--->( 1 )---'
      |     '-'    ^
      |     .-.    |
      '--->( 2 )---'
      |     '-'    ^
      |     .-.    |
      '--->( 3 )---'
      |     '-'    ^
      |     .-.    |
      '--->( 4 )---'
      |     '-'    ^
      |     .-.    |
      '--->( 5 )---'
      |     '-'    ^
      |     .-.    |
      '--->( 6 )---'
      |     '-'    ^
      |     .-.    |
      '--->( 7 )---'
      |     '-'    ^
      |     .-.    |
      '--->( 8 )---'
      |     '-'    ^
      |     .-.    |
      '--->( 9 )---'
            '-'

auf deutsch

Eine ›Dezimalziffer‹ ist »0«, »1«, »2«, »3«, »4«, »5«, »6«, »7«, »8« oder »9«.

Beispiele für Dezimalziffern (also für Exemplare der Kategorie „Dezimalziffer“)

»4«

»7«

Anfangs- und Endpunkt ⃗

Ein Aufbaudiagramm wird von seinem links stehenden Eingang »|-|« bis zu seinem rechts stehenden Ausgang »|-|« gelesen.

Eingang und Ausgang eines Aufbaudiagramms

|-|

Wörtliche Zeichenwiedergabe ⃗

Zeichen in gerundeten Kästchen  sind wörtlich  zu verstehen. Ein Minuszeichen »-« in einem gerundeten Kästchen steht beispielsweise für ein Minuszeichen »-«.

gerundetes Kästchen mit dem Zeichen Minus »-«

 .-.
( - )
 '-'

auf deutsch

Das Zeichen »-«.

Pfeile ⃗

Ein Aufbaudiagramm enthält Linien mit Pfeilen und wird zum Finden eines erlaubten Exemplars seiner Kategorie vom Eingang bis zum Ausgang in Richtung seiner Pfeile durchlaufen, dazwischen darf auch von rechts nach links gegangen werden, solange dabei der Richtung der Pfeile gefolgt wird.

Wegen der Pfeilrichtung steht das folgende Diagramm für »xy«, nicht aber für »yx«.

Aufbaudiagramm für »xy«

xy
        .-.      .-.
|-|--->( x )--->( y )--->|-|
        '-'      '-'

auf deutsch

Das Zeichen »x« gefolgt vom Zeichen »y«.

Pfeile

       |   ^
--->   |   |   <---
       v   |        

Alternativen ⃗

An einer Verzweigung  einer Linie darf ein beliebiger Abzweig  gewählt werden.

Verzweigung (Beispiel)

    
---.--->
   |
   '--->
   |
   '--->

Das folgende Aufbaudiagramm besagt beispielsweise, daß die Kategorie „Vorzeichen“ entweder durch das Zeichen »+« oder durch das Zeichen »-« realisiert werden kann.

Aufbaudiagramm für ›Vorzeichen‹

Vorzeichen
            .-.
|-|---.--->( + )---.--->|-|
      |     '-'    ^
      |     .-.    |
      '--->( - )---'
            '-'

auf deutsch

Ein ›Vorzeichen‹ ist ein »+« oder ein »-«.

Exemplare der Kategorie Vorzeichen

»+«

»-«

Produktionsregeln

Die einzelnen Teile eines Diagramme mit jeweils einem Eingang und Ausgang nennt man auch Produktionsregeln. Das folgende Diagramm enthält zwei Produktionsregeln, eine für ›Alpha‹ und eine für ›Gamma‹.

Aufbaudiagramm

Alpha
        .-.     
|-|--->( x )--->|-|
        '-'     
Gamma
        .-.
|-|--->( y )--->|-|
        '-'

Eine Produkt  ist das Ergebnis der Verwendung einer Produktionsregel, also ist »x« beispielsweise ein Produkt der Produktionsregel ›Alpha‹.

In manchen Texten werden die Produktionsregeln selber als „Produktionen“ bezeichnet.

Die Bildung von Exemplaren einer Kategorie wird auch als Inkarnation  der Kategorie bezeichnet. Entsprechend nennt man Exemplare auch Inkarnationen. Beispielsweise ist »x« eine Inkarnation der Kategorie ›Alpha‹.

Mehrere Produktionsregeln zu einer Kategorie

Gibt es mehrere Produktionsregeln zu einer Kategorie, so kann eine davon frei ausgewählt werden.

Aufbaudiagramm

Alpha
        .-.
|-|--->( x )--->|-|
        '-'
Alpha
        .-.
|-|--->( y )--->|-|
        '-'

auf deutsch

Ein ›Alpha‹ kann als ein »x« realisiert werden.

Ein ›Alpha‹ kann als ein »y« realisiert werden.

Das voranstehende Diagramm mit zwei Produktionsregeln ist also dem folgenden mit nur einer Produktionsregel gleichwertig.

Aufbaudiagramm

Alpha
            .-.
|-|---.--->( x )---.--->|-|
      |     '-'    ^
      |     .-.    |
      '--->( y )---'
            '-'

auf deutsch

Ein ›Alpha‹ kann als ein »x« oder als ein »y« realisiert werden.

Auf diese Weise ist es auch möglich, die Definition einer Kategorie (wie ›Alpha‹) zunächst durch eine Produktionsregel teilweise anzugeben und später durch eine weitere Produktionsregel zu erweitern.

Falls es zu einer Kategorie mehrere  Produktionsregeln gibt, so muß man dann die Exemplare der Kategorie aber als Produktionen der Produktionsregeln  („Produktionsregeln“ im Plural!) bezeichnen.

Vollständigkeit ⃗

Wenn nichts anderes gesagt wird, so enthält ein Diagramm in dieser Lektion hier alle  relevanten Produktionsregeln. Daher können wir in dieser Lektion hier aus dem folgenden Diagramm folgern, daß ein »z« kein  ›Alpha‹ sein kann, denn sonst müßte es eine entsprechende Produktionsregeln in dem Diagramm geben.

Aufbaudiagramm

Alpha
        .-.
|-|--->( x )--->|-|
        '-'
Alpha
        .-.
|-|--->( y )--->|-|
        '-'

In anderen Lektionen sind Diagramme manchmal als Erweiterung früherer Diagramme zu verstehen.

Wenn in einem Text mehrere Produktionsregeln für eine Kategorie angegeben werden, so kann man normalerweise davon ausgehen, daß es keine anderen Produktionsregeln für diese Kategorie gibt. So kann man in diesem Abschnitt dann schließen, daß ein »z« kein Alpha ist, da es keine Produktionsregeln dafür gibt. Auch ohne diese Annahme kann man beim Fehlen einer Produktionsregel, die besagt, daß ein »z« ein Alpha ist, zumindests feststellen, daß man nicht zeigen kann, daß »z« ein Alpha ist. Im besten Falle sollte in einem Text ausdrücklich stehen, daß es keine anderen Produktionsregeln als die angegebenen gibt. Sinngemäß also: „»x« und »y« sind jeweils ein Alpha, und alles andere ist kein Alpha.“

Referenzierung

Angaben in eckigen Kästchen  sind nicht  wörtlich, sondern beschreibend  zu verstehen. Sie können den Namen einer Kategorie  enthalten, die an ihrer Stelle realisiert werden soll und ihrerseits durch ein weitere Produktionsregel angegeben werden kann.

Angabe in einem eckigen Kästchen

.-------.
| Gamma |
'-------'

Beispiel zur Referenzierung

Aufbaudiagramm

Alpha
        .-.     .-------.
|-|--->( x )--->| Gamma |--->|-|
        '-'     '-------'
Gamma
        .-.
|-|--->( y )--->|-|
        '-'

auf deutsch

Ein ›Alpha‹ besteht aus dem Zeichen »x« gefolgt von einem ›Gamma‹.

Ein ›Gamma‹ besteht aus dem Zeichen »y«.

Ein Text ist ein Alpha, wenn es einen Weg vom Eingang zum Ausgang des Diagramms unter der Überschrift »Alpha« gibt, welcher der Pfeilrichtung folgt und dabei über Zeichen kommt, welche zusammengesetzt diesen Text ergeben. Wir nennen solch einen Text auch eine Exemplar der Kategorie Alpha  oder eine Realisierung der Kategorie Alpha  oder einfach ein Alpha.

Exemplar der Kategorie „Gamma“

»y«

Exemplar der Kategorie „Alpha“

»xy«

Kombination der beiden obigen Produktionsregeln

Alpha           .-------------.
                | Gamma       |
        .-.     |     .-.     |
|-|--->( x )--->|--->( y )--->|--->|-|
        '-'     |     '-'     |
                |             |
                '-------------'

Wiederholte Referenzierung

Wenn eine Kategorie mehrfach referenziert wird, so muß sie nicht jedes Mal auf die gleiche Weise realisiert werden.

Aufbaudiagramm

Alpha
       .-------.    .-------.
|-|--->| Gamma |--->| Gamma |--->|-|
       '-------'    '-------'
Gamma
            .-.
|-|---.--->( y )---.--->|-|
      |     '-'    ^
      |     .-.    |
      '--->( z )---'
            '-'

»yz« ist beispielsweise ein ›Alpha‹. (Hier wurde für das erste ›Gamma‹ ein »y« und für das zweite ein »z« eingesetzt.)

Kommentare ⃗

In diesem Kurs werden unter Kästchen manchmal Kommentare  zu den Kästchen geschrieben. Diese haben ändern die Bedeutung des Diagramm nicht, sondern geben nur Hinweise zur Bedeutung des Kästchens.

Aufbaudiagramm

Alpha
        .-.     .-------------.
|-|--->( x )--->| Gamma       |--->|-|
        '-'     '-------------'
                  Anfangswert

Symbole ⃗

Die Kästchen werden manchmal auch „Symbole“ genannt. Eine Kategorie, also ein eckiges Kästchen wird dann auch ein „Nichtterminalsymbol “ genannt, während wörtlich zu verstehende Zeichen in einem gerundeten Kästchen auch „Terminalsymbole “ genannt werden.

Ein Terminalsymbol

 .-.
( x )
 '-'

Ein Nichtterminalsymbol

.-------.
| Gamma |
'-------'

Weiteres Beispiel zur Referenzierung *

Aufbaudiagramm

Alpha
        .-.     .-------.     .-.
|-|--->( x )--->| Gamma |--->( y )--->|-|
        '-'     '-------'     '-'
Gamma
        .-.      .-.
|-|--->( v )--->( w )--->|-|
        '-'      '-'

auf deutsch

Ein ›Alpha‹ besteht aus dem Zeichen »x« gefolgt von einem ›Gamma‹ gefolgt von dem Zeichen »y«.

Ein ›Gamma‹ besteht aus dem Zeichen »v« gefolgt von dem Zeichen »w«.

Exemplar der Kategorie Gamma

»vw«

Exemplar der Kategorie Alpha

»xvwy«

Kombination der beiden obigen Produktionsregeln

Alpha
                .----------------------.
                | Gamma                |
        .-.     |     .-.      .-.     |     .-.
|-|--->( x )--->|--->( v )--->( w )--->|--->( y )--->|-|
        '-'     |     '-'      '-'     |     '-'
                |                      |
                '----------------------'

Weiteres Beispiel zur Referenzierung *

Aufbaudiagramm

Alpha
       .-------.    .-------.
|-|--->| Gamma |--->| Gamma |--->|-|
       '-------'    '-------'
Gamma
            .-.
|-|---.--->( v )---.--->|-|
      |     '-'    ^
      |     .-.    |
      '--->( w )---'
            '-'

auf deutsch

Ein ›Alpha‹ besteht aus einer Folge zweier ›Gamma‹.

Ein ›Gamma‹ besteht aus dem Zeichen »v« oder dem Zeichen »w«.

Exemplar der Kategorie Gamma

»v«
»w«

Exemplar der Kategorie Alpha

»vv«
»vw«
»wv«
»ww«

Kombination der beiden obigen Produktionsregeln

Alpha  .---------------------.    .---------------------.
       | Gamma               |    | Gamma               |
       |                     |    |                     |
       |                     |    |                     |
       |         .-.         |    |         .-.         |
|-|--->|---.--->( v )---.--->|--->|---.--->( v )---.--->|--->|-|
       |   |     '-'    ^    |    |   |     '-'    ^    |
       |   |     .-.    |    |    |   |     .-.    |    |
       |   '--->( w )---'    |    |   '--->( w )---'    |
       |         '-'         |    |         '-'         |
       '---------------------'    '---------------------'

Da das wörtliche mehrfache Einsetzen einer Produktionsregel in eine andere eine stark vergrößerte Produktionsregel ergeben kann, dient die Aufteilung in mehrere Produktionsregel auch dem Zweck, die Diagramme klein zu halten.

Undefinierte Kategorien

Manchmal werden Kategorien referenziert, die nicht durch Produktionsregeln definiert werden. In diesem Fall, soll an Hand der Bezeichnung der Kategorie geraten werden, was diese beschreibt. Man kann sagen, daß die Bezeichnung der Kategorie in solch einem Fall ihre normale Bedeutung in der deutschen Sprache haben soll. Ein undefinierte Kategorie ›Ziffer‹ steht also beispielsweise für eine Ziffer (normale Bedeutung des Wortes „Ziffer“ in der deutschen Sprache, also eines der Zeichen von »0« bis »9«).

Eine Verwendung der Kategorie »Ziffer«

.--------.
| Ziffer |
'--------'

Optionalität ⃗

Etwas, das verwendet werden kann, aber nicht verwendet werden muß, wird als optional  bezeichnet. Beispielsweise ist das „e“ im Genitiv „Wortes“ optional. Durch entsprechende Verzweigungen kann solch eine Wahlmöglichkeit auch in einem Aufbaudiagramm ausgedrückt werden.

Auszug aus einem Wörterbuch

das Wort; Genitiv: des Wort[e]s, Plural: die Wörter und Worte

Aufbaudiagramm

Genitiv von "Wort"                        .------------.
                                          |            |
        .-.      .-.      .-.      .-.    |     .-.    v     .-.
|-|--->( W )--->( o )--->( r )--->( t )---'--->( e )---'--->( s )--->|-|
        '-'      '-'      '-'      '-'          '-'          '-'

auf deutsch

Ein ›Genitiv von "Wort"‹ besteht aus dem Zeichen »W« gefolgt vom Zeichen »o« gefolgt vom Zeichen »r« gefolgt vom Zeichen »t«, dem dann entweder ein »s« oder eine Folge aus den Zeichen »e« und »s« (in dieser Reihenfolge) folgen muß.

Einen Pfeil, der es erlaubt etwas (wie oben das »e«) zu umgehen, nennen wir auch einen Umgehungspfeil.

Etwas, das verwendet werden muß, wird als obligatorisch  bezeichnet. Beispielsweise ist das „W“ am Anfang des Genitivs „Wortes“ obligatorisch. Es führt im Diagramm also kein Weg um das „W“ herum.

Übungsfragen

?   Übungsfrage 0 ⃗

Welcher der folgenden Texte ist ein ›Alpha‹ gemäß dem folgenden Aufbaudiagramm? (Hier und bei den folgenden Übungsfragen kann angenommen werden, daß es keine anderen Möglichkeiten der Exemplarbildung zu einer Kategorie gibt als die durch die vorliegenden Aufbaudiagramme angegebene gibt.)

Aufbaudiagramm

Alpha
        .-.      .-.
|-|--->( x )--->( y )--->|-|
        '-'      '-' 
Gamma
        .-.      .-.
|-|--->( y )--->( x )--->|-|
        '-'      '-' 

• Anton: »x«
• Berta: »xy«
• Cäsar: »yx«
• Dora: »y«

?   Übungsfrage 1

Welcher der folgenden Texte ist ein ›Gamma‹ gemäß dem folgenden Aufbaudiagramm?

Aufbaudiagramm

Gamma
        .-.          .-.
|-|--->( x )---.--->( y )---.--->|-|
        '-'    |     '-'    ^
               |     .-.    |
               '--->( z )---'
                     '-'

• Anton: »x«
• Berta: »xy«
• Cäsar: »xz«
• Dora: »yx«

?   Übungsfrage 2

Welcher der folgenden Texte ist ein ›Delta‹ gemäß dem folgenden Aufbaudiagramm?

Aufbaudiagramm

Delta
        .-.     .---------.     .-.
|-|--->( x )--->| Epsilon |--->( y )--->|-|
        '-'     '---------'     '-'
Epsilon
        .-.
|-|--->( z )--->|-|
        '-'

• Anton: »x«
• Berta: »xy«
• Cäsar: »xz«
• Dora: »yzx«
• Emil: »xzy«
• Friedrich: »xzzy«

?   Übungsfrage 3

Welcher der folgenden Texte ist ein ›Eta‹ gemäß dem folgenden Aufbaudiagramm?

Aufbaudiagramm

Eta
        .-.          .-.
|-|--->( x )---.--->( y )---.--->|-|
        '-'    |     '-'    ^
               |            |
               '------------'

• Anton: »x«
• Berta: »xyy«
• Cäsar: »yx«
• Dora: »xy«
• Emil: »yxx«

?   Übungsfrage 4

Welcher der folgenden Texte ist ein ›Zeta‹ gemäß dem folgenden Aufbaudiagramm?

Aufbaudiagramm

Zeta
        .-.          .-.
|-|--->( x )---.--->( y )---.--->|-|
        '-'    ^     '-'    |
               |            |
               '------------'
       

• Anton: »x«
• Berta: »xyyy«
• Cäsar: »yx«
• Dora: »xy«
• Emil: »yxx«

?   Übungsfrage 5

Welcher der folgenden Texte ist ein ›Iota‹ gemäß dem folgenden Aufbaudiagramm?

Aufbaudiagramm

Iota
        .-.         .------.
|-|--->( x )---.--->| Iota |---.--->|-|
        '-'    |    '------'   ^
               |               |
               '---------------'

• Anton: »x«
• Berta: »xyy«
• Cäsar: »yx«
• Dora: »xx«
• Emil: »yxx«

?   Übungsfrage 6

Welcher der folgenden Texte ist ein ›Kappa‹ gemäß dem folgenden Aufbaudiagramm?

(Das Zeichen im obersten Kästchen des Diagramms ist eine Null.)

Aufbaudiagramm

Kappa
                       .-.
|-|---.-------------->( 0 )--------------.--->|-|
      |                '-'               ^
      |    .-------.     .-.      .-.    |
      '--->| Kappa |--->( * )--->( 0 )---'
           '-------'     '-'      '-'

• Anton: »0«
• Berta: »0*0«
• Cäsar: »0*0*0«
• Dora: »0*0*0*0«
• Emil: »*0«

?   Übungsfrage 7

Welcher der folgenden Texte ist ein ›My‹ gemäß dem folgenden Aufbaudiagramm?

(Das Zeichen im obersten Kästchen des Diagramms ist eine Null.)

Aufbaudiagramm

Kappa
                       .-.
|-|---.-------------->( 0 )--------------.--->|-|
      |                '-'               ^
      |    .-------.     .-.      .-.    |
      '--->| Kappa |--->( * )--->( 0 )---'
           '-------'     '-'      '-'
My
                       .-----.
|-|---.-------------->( Kappa )--------------.--->|-|
      |                '-----'               ^
      |    .-------.     .-.      .-----.    |
      '--->| My    |--->( + )--->( Kappa )---'
           '-------'     '-'      '-----'

• Anton: »0«
• Berta: »0*0«
• Cäsar: »0+0«
• Dora: »0+0*0«
• Emil: »0+0*0+0«

?   Übungsfrage 8 _

Können Sie genau ein Beispiel für eine Exemplar der Kategorie ›Kappa‹ nennen? („Genau ein“ heißt: „ein und nur ein“, es sollen also nicht mehrere Beispiele genannt werden.)

Aufbaudiagramm

Kappa
        .-.          .-.
|-|--->( k )---.--->( b )---.--->|-|
        '-'    |     '-'    ^
               |     .-.    |
               '--->( l )---'
               |     '-'    |
               |     .-.    |
               '--->( q )---'
                     '-'

Übungsaufgaben ⃗

/   Übungsaufgabe ⃗

Schreiben Sie genau ein Exemplar der Kategorie ›Anton‹ des folgenden Aufbaudiagramms.

(„Genau eine“ heißt: „ein und nur ein“, es sollen also nicht  mehrere Exemplare aufgeschrieben werden.)

Anton (Aufbaudiagramm)

Anton
        .-------.      .-.
|-|---->| Berta |---->( g )---->|-|
        '-------'      '-'
Berta
             .-.
|-|--->.--->( x )---.--->|-|
       |     '-'    ^
       |     .-.    |
       '--->( o )---'
       |     '-'    |
       |     .-.    |
       '--->( m )---'
             '-'

Die Lösung soll auf einer von Leerzeilen umgebenden Zeile für sich stehen.

Endlichkeit

Alle Produkte von Produktionsregeln sollen endlich  lang sein.

Produktionsregeln gelten also nicht  für Zeichenfolgen mit unendlich vielen  Zeichen.

Allgemeine Prinzipien der Programmierung *

Anhand der Aufbaudiagramme können wir auch einige wichtige Prinzipien  illustrieren, die beim Programmieren oft vorkommen.

Prinzip Regeln *

Es ist im allgemeinen nicht  möglich, eine Regel auf eindeutige Weise aus einer Sammlung von Beispiele herzuleiten, insbesondere sind auch Implementationen von Programmiersprachen dazu nicht in der Lage.

Ein Programm ist eine  Regel, beispielsweise zur Verarbeitung von Eingaben, zur Reaktion auf Ereignisse, zur Ermittlung einer Ausgabe oder zur Steuerung von Geräten.

Es ist also die Aufgabe des Programmierers, allgemeine Regeln zu formulieren. Die Aufbaudiagramme sind Beispiele  solcher Regeln. Sie machen uns daher mit der Grundidee des Programmierens  vertraut: Etwas wird nicht durch Beispiele oder auf vage Weise sondern durch genau formulierte Regeln  beschrieben, wie sie beispielsweise die Aufbaudiagramme darstellen.

Der Nichtprogrammierer (Kunde) drückt sich durch Beispiele  aus, der Programmierer übersetzt diese in sprachlich formulierte Regeln. Aufbaudiagramme erlauben es eine Programmiersprache durch Regeln zu beschreiben. Eine Auflistung von Beispiele könnte dies nicht in so eindeutiger und umfassender Weise gewähren.

Prinzip Abstraktion *

Bei der Abstraktion wird eine Information entfernt.

Wenn man von einem Minuszeichen »-« zur Kategorie »Vorzeichen« übergeht, verliert man die Information, um welches  Vorzeichen es genau geht. Vorher wußte man, daß es ein Minuszeichen »-«, hinterher nur noch, daß es ein Pluszeichen »+« oder  ein Minuszeichen »-« ist, aber nicht mehr, welches davon.

Vor der Abstraktion

»-«

Nach der Abstraktion

Vorzeichen

Prinzip Exemplare (Realisierung) *

Bei der Exemplarbildung wird eine Information hinzugefügt.

Wenn man die Kategorie »Vorzeichen« durch ein Minuszeichen »-« realisiert, so fügt man eine Information hinzu (nämlich, welches  Vorzeichen man ausgewählt hat).

Eine Kategorie

Vorzeichen

Ein Exemplar der Kategorie »Vorzeichen«

»-«

Ein Exemplar enthält mehr  Informationen als ihre Kategorie: Wenn man weiß, daß ein Zeichen ein »-« ist, dann weiß man mehr  über das Zeichen, als wenn man nur weiß, daß es ein Vorzeichen ist (dann könnte es auch ein »+« sein).

Prinzip Referenzierung *

Bei der Referenzierung (auch „Verwendung“ genannt) steht ein Text A nicht für sich selbst, sondern für einen anderen Text B. Für welchen Text B der Text A steht, wird dann an einer anderen Stelle festgelegt, die man „Definition“ nennt. Diese Referenzierung wird auch als Umleitung (“indirection ”) bezeichnet.

Verwendung von »Gamma«

Alpha
        .-.     .-------.
|-|--->( x )--->| Gamma |--->|-|
        '-'     '-------'

Definition von ›Gamma‹

Gamma
        .-.
|-|--->( y )--->|-|
        '-'

Prinzip Zusammenfassung *

Mehrere Dinge werden zu einer neuen Einheit zusammengefaßt. Beispielsweise kann eine Produktionsregel zwei Zeichen »x« und »y« zu einer neuen Kategorie ›Zeta‹ zusammenfassen.

Verwendung von ›Gamma‹

Zeta
        .-.      .-.
|-|--->( x )--->( y )--->|-|
        '-'      '-'

Prinzip Rekursion *

Die Referenzierung eröffnet die Möglichkeit zur Rekursion, die darin besteht, daß etwas sich selbst  referenziert.

Selbstbezug (Rekursion) durch die Produktionsregel für ›Iota‹

Iota
        .-.          .------.
|-|--->( x )--->.--->| Iota |--->.--->|-|
        '-'     |    '------'    ^
                |                |
                '----------------'

Aufbaudiagramm nach einfachem Einsetzen der Rekursion

Iota
        .-.           .-.          .------.
|-|--->( x )--->.--->( x )--->.--->| Iota |--->.--->
        '-'     |     '-'     |    '------'    ^
                |             |                |
                |             '--------------->'
                |                              |
                '----------------------------->'

Aufbaudiagramm nach zwiefachem Einsetzen der Rekursion

Iota
        .-.           .-.           .-.          .------.
|-|--->( x )--->.--->( x )--->.--->( x )--->.--->| Iota |--->.--->
        '-'     |     '-'     |     '-'     |    '------'    ^
                |             |             |                |
                |             |             '--------------->'
                |             |                              |
                |             '----------------------------->'
                |                                            |
                '------------------------------------------->'

Aufbaudiagramm nach dreifachem Einsetzen der Rekursion

Iota
        .-.           .-.           .-.           .-.          .------.
|-|--->( x )--->.--->( x )--->.--->( x )--->.--->( x )--->.--->| Iota |--->.--->
        '-'     |     '-'     |     '-'     |     '-'     |    '------'    ^
                |             |             |             |                |
                |             |             |             '--------------->'
                |             |             |                              |
                |             |             '----------------------------->'
                |             |                                            |
                |             '------------------------------------------->'
                |                                                          |
                '--------------------------------------------------------->'

Durch das mehrfache Einsetzen erkennt man, daß die Rekursion hier das Prinzip der Möglichkeit einer Hintereinanderschreibung von beliebig vielen »x« ausdrückt.

Analysediagramme

Kappa

Aufbaudiagramm

Kappa
                       .-.
|-|---.-------------->( 0 )--------------.--->|-|    R0
      |                '-'               ^
      |    .-------.     .-.      .-.    |
      '--->| Kappa |--->( * )--->( 0 )---'           R1
           '-------'     '-'      '-'

ein Kappa

0*0*0

Analyse von »0*0*0«

                  Kappa
                    |
            .-------'-------. R1
            |       |       |
          Kappa     *       0
            |
    .-------'-------. R1
    |       |       |
  Kappa     *       0
    | R0
    0

Die Null in der Mitte von »0*0*0« wird dem linken  Stern »*« zugeordnet, entsprechend sagt man auch, der Stern sei „linksassoziativ“.

My

Aufbaudiagramm

Kappa
                       .-.
|-|---.-------------->( 0 )--------------.--->|-|       R0
      |                '-'               ^
      |    .-------.     .-.      .-.    |
      '--->| Kappa |--->( * )--->( 0 )---'              R1
           '-------'     '-'      '-'
My
                       .-----.
|-|---.-------------->( Kappa )--------------.--->|-|   R2
      |                '-----'               ^
      |    .-------.     .-.      .-----.    |
      '--->| My    |--->( + )--->( Kappa )---'          R3
           '-------'     '-'      '-----'

ein My

0+0*0

Analyse von »0+0*0«

                My
                |
        .-------'-------. R3
        |       |       |
        My      +     Kappa
        | R2            |
      Kappa     .-------'-------. R1
        | R0    |       |       |
        0     Kappa     *       0
                | R0
                0

Die Null in der Mitte von »0+0*0« wird dem Stern »*« zugeordnet, entsprechend sagt man auch, daß der Stern eine höhere Priorität  als das Kreuz »+« habe.