G.Heyer Digitale Informationsverarbeitung1

9. Syntaxdiagramme und Backus-Naur-Form (BNF)

Programmiersprachen häufig definiert durch kontextfreie Grammatiken in BNF mit gewissen Zusatzbedingungen

BNF statt

A -> w1 | w2 | ... | wn

A -> w1A -> w2...A -> wn

A -> x(y)z A -> xzA -> xyz

A -> x{y}zA -> xzA -> xBzB -> yBB -> y

G.Heyer Digitale Informationsverarbeitung2

Symbol Bedeutung Beispiel

= ist äquivalent zu A = B + C

+ Sequenz

(impliziert keine Ordnung) X = X1 + X2 + X3

[ ] Auswahl (entweder ... oder) A = [B | C]

{ } Wiederholung A = { B }

M{ }N Wiederholung von M bis N A = 1 { B } 10

( ) Option = 0 { }1 A = B + ( C )

* * Kommentar A = X + Y * Kommentar *

G.Heyer Digitale Informationsverarbeitung3

While-Berechenbarkeit

Ein While-Programm besteht aus folgenden Komponenten:

Variablen: x0, x1, x2, ...Konstanten: 0, 1, 2, ...Trennsymbole: ; :=

Operationszeichen: + - ?Schlüsselwörter: WHILE DO END

1. Eine Wertzuweisung der Form xi := xj + c oder xi := xj - c (c Konstante) ist ein While-Programm2. Falls P1 und P2 While-Programme sind, so auch P1;P23. Falls P While-Programm ist, so ist auch WHILE xi ≠ 0 DO P END ein While-Programm4. Nur die durch 1-3 beschiebenen Konstrukte sind While-Programme

Syntax von While-Programmen, induktive Definition:

G.Heyer Digitale Informationsverarbeitung4

Beispiel

WHILE x1 ≠ 0 DO x3 := x2; WHILE x3 ≠ 0 DO x0 := x0 + 1; x3 := x3 - 1 END; x1 := x1 - 1END

Multiplikation: Eingabe: x1, x2, Ausgabe: x0

G.Heyer Digitale Informationsverarbeitung5

Syntax von WHILE-Programmen in BNF

<Programm> <Zuweisung> | <Programm>; <Programm> | WHILE <Test> DO <Programm> END

<Zuweisung> <Variable> := <Variable> + <Konstante> |<Variable> := <Variable> - <Konstante>

<Variable> x0 | x1 | x2 | ...

<Konstante> 0 | 1 | 2 | ...

<Test> <Variable> ≠ 0

Konvention:Variablen in < >-Klammern, alle anderen Symbole Terminalsymbole

->

->

->

->

->

G.Heyer Digitale Informationsverarbeitung6

Die Kundendatei

besteht aus keinem, einem oder beliebig vielen Kundeneinträgen.

Der Kundeneintrag setzt sich zusammen aus der

Personal-Nr., dem Namen, der Adresse und dem Umsatz (Muß-Angaben).

Optional können noch das

Geburtsdatum und die Funktion (im Unternehmen) angegeben sein (Kann-Angaben).

Bei der Adresse

wird entweder die Straße und die Haus-Nr. oder die Postfachnummer angegeben, gefolgt vom optionalen Länderkennzeichen, PLZ, Ort und den optionalen Angaben Telefon und Fax.

G.Heyer Digitale Informationsverarbeitung7

Seminaranmeldung

Als Teilnehmer zu nachfolgenden Seminaren wird angemeldet:

Titel Vorname Name

vom bis

Anmeldebestätigung und Rechnung erbeten an:Titel Vorname Name

Firma Straße / Postfach LKZ

ORTPLZ Telefon

Veranstaltungs-Nr. Seminarbezeichnung

G.Heyer Digitale Informationsverarbeitung8

Syntaxdiagramme• Graphische Repräsentation kontextfreier Grammatiken.

• Pfeilrichtung gibt an, wie Diagramme zu durchlaufen sind.• Alternative Durchläufe sind möglich.• Rechtecke entsprechen Variablen, werden beim Durchlauf ersetzt durch

Syntaxdiagramm gleichen Namens.• Ovale geben jeweils produzierte Terminalzeichen an.• Die Folge von Terminalzeichen, die bei einem vollständigen Durchlauf

produziert wird, ist ein Element der erzeugten Sprache.

Beispiel:

X

Y

Z

0

1

erzeugte Sprache: X0, Y0, Z0, X1, Y1, Z1, X00, Y00, Z00, X01, Y01, Z01, ...

G.Heyer Digitale Informationsverarbeitung9

Syntaxdiagramme für Katzenbeispiel

Satz: Subjekt Objekt

Subjekt:

der

die

das

Adjektiv

jagt

Hund

Katze

Objekt: wie Subjekt

Adjektiv: kleine

bissige

große

G.Heyer Digitale Informationsverarbeitung10

Bemerkungen

• Beschreibung von Programmiersprachen oft in Form von Syntaxdiagrammen

• Nicht in allen Fällen möglich bzw. praktisch (Kontextabhängigkeit)• Oft werden auch Mischformen aus Syntaxdiagrammen und zusätzlichen

Kontextbedingungen angegeben, etwa:

Bezeichner: Buchstabe

Buchstabe

Ziffer

Kontextbedingungen: unzulässig als Bezeichner sind:BEGIN, END, WHILE, ...

G.Heyer Digitale Informationsverarbeitung11

Ablaufsteuerung

Zur Ausführung eines Algorithmus benötigt man verschiedene Arten von Kontrollstrukturen, v. a.

- Sequenz

- Selektion

- Iteration

Sequenz, Selektion und Iteration genügen,

um jeden Algorithmus auszudrücken !

G.Heyer Digitale Informationsverarbeitung12

Sequenz (Folge von Anweisungen)

1. Zu einem Zeitpunkt wird nur ein Schritt ausgeführt.

2. Jeder Schritt wird genau einmal ausgeführt: keiner wird wiederholt,

keiner wird ausgelassen.

3. Die Reihenfolge, in der die Schritte ausgeführt werden, ist die gleiche

Folge, in der sie niedergeschrieben sind (d. h. nacheinander).

4. Mit der Beendigung des letzten Schrittes endet der gesamte Algorithmus.

Die Ausführung eines Algorithmus ist sehr starr, wenn nur die Sequenz als Kontrollstruktur eingesetzt wird.

G.Heyer Digitale Informationsverarbeitung13

Selektion (Auswahl, bedingte Anweisung)

a) Einfache Form

IF Bedingung

THEN Anweisung(en)

b) Bedingte Anweisung mit Alternative (allgemeine Form):

IF Bedingung

THEN Anweisung 1

ELSE Anweisung 2

Die einfache Form ist ein Spezialfall der allgemeinen Form, bei der Anweisung 2 die leere Anweisung ist („tue nichts“)

G.Heyer Digitale Informationsverarbeitung14

c) Mehrfachauswahl

CASE

Bedingung 1: Anweisung 1

Bedingung 2: Anweisung 2

...

Bedingung n: Anweisung n

ELSE

Anweisung n + 1

Die Bedingungen 1 bis n müssen sich gegenseitig ausschließen; d. h. es dürfen nicht zwei Bedingungen gleichzeitig erfüllt sein.

G.Heyer Digitale Informationsverarbeitung15

Iteration (Wiederholung, Schleife)

a) Solange-bis-Schleife

Wiederholte Ausführung einer Anweisung (oder einer Folge von

Anweisungen), bis eine Abbruchbedingung erfüllt ist.

REPEAT

Anweisung(en)

UNTIL Bedingung {Abbruchbedingung}

G.Heyer Digitale Informationsverarbeitung16

b) Solange-noch-SchleifeDie Anweisungen in der Schleife werden ausgeführt, solange die

Bedingung erfüllt ist:

WHILE Bedingung DOAnweisung 1 ... ... {Rumpf der Schleife}Anweisung n

Anweisung n + 1 {nicht mehr in der Schleife}

• Unterschied zur ersten Form: Die Bedingung wird vor der Ausführung des

Schleifenrumpfes geprüft.

• Vorteilhaft, wenn damit gerechnet werden muß, daß in manchen Fällen bereits

beim erstmaligen Eintritt in die Schleife die Abbruchbedingung erfüllt ist, der

Schleifenrumpf also nicht ausgeführt werden soll.

• Die beiden Formen der Iteration sind äquivalent, sie lassen sich (unter Verwendung der bedingten Anweisung) ineinander überführen.

G.Heyer Digitale Informationsverarbeitung17

Symbole für Struktogramme (1)

Aktion

nicht erfüllterfülltBedingung

Aktion 1 Aktion 2

Strukturblock

Verzweigung

Fallunterscheidung

Fallauswahl

Aktion n

... n21

Aktion 2Aktion 1 ...

G.Heyer Digitale Informationsverarbeitung18

Symbole für Struktogramme 2

Solange-noch-Schleife

Solange-bis-Schleife

Aktion

Aktion

UNTIL-Bedingung

WHILE-Bedingung

G.Heyer Digitale Informationsverarbeitung19

Euklidischer Algorithmus (1)

Struktogramm

G.Heyer Digitale Informationsverarbeitung20

Darstellungsmittel für Programmablaufpläne (1)

Aktion für Aktionen

für Verzweigungen

für Eingaben und Ausgaben

JNBedingung

Eingabe X

G.Heyer Digitale Informationsverarbeitung21

Darstellungsmittel für Programmablaufpläne (2)

AAÜbergangsstellen zwischen mehreren Diagrammen

für Anfang und Ende

Ablauflinie und Zusammenführung

Unterprogramm

Anfang Ende

vollständige Aufstellung: Norm DIN 66 01

(Sinnbilder für Datenfluß- und Programmablaufpläne)

G.Heyer Digitale Informationsverarbeitung22

Euklidischer Algorithmus (2)

Programmablaufplan

G.Heyer Digitale Informationsverarbeitung23

Euklidischer Algorithmus (3)

ausgeführte Aktion

Programmprotokoll