26.2 Syntaxdiagramme

Beispiel

Betrachten Sie folgende Abbildung:

Ein Syntaxdiagramm für arithmetische Ausdrücke (expr)

Mit Hilfe dieses Syntaxdiagramms kann man arithmetische Ausdrücke erzeugen.

Erzeugung einer einzelnen Zahl

Hier sehen Sie den "Weg", um eine Zahl wie 17 oder 3.14 zu erzeugen. Man startet am grünen Punkt, geht zum num-Kasten und von dort zum roten Punkt, also zum Ende.

Als Nächstes wollen wir einen Ausdruck wie "17 + radius" erzeugen, allgemein also "num + id". Dazu gehen wir folgendermaßen vor:

Erzeugung des Ausdrucks 17 + radius bzw. allgemein num + id

Zunächst folgen wir dem grünem Pfeil mit der Nummer 1. Vom Startpunkt aus landen wir direkt bei expr. Das heißt also: rekursiver Aufruf des Syntaxdiagramms.

In der zweiten Rekursionsebene folgen wir dem gelben Pfeil mit der Nummer 2.1. Wir landen bei num, bekommen also eine Zahl wie 17. Dann geht es zum roten Punkt, womit wir die zweite Rekursionsebene verlassen.

Jetzt sind wir wieder in der Rekursionsebene 1, den ersten expr-Ausdruck haben wir abgearbeitet, und jetzt kommt ein Plus-Zeichen. Danach kommt ein zweiter rekursiver Aufruf von expr.

Wir sind jetzt zum zweiten Mal in der Rekursionsebene 2 und folgen jetzt dem hellroten Pfeil mit der Nummer 2.2. Vom Startpunkt aus kommen wir zu id, also zu einem Bezeichner für eine Variable (identifier) wie "radius". Dann geht es wieder über den roten Punkt zurück zur ersten Rekursionsebene.

Mit der ersten Rekursionsebene sind wir jetzt fertig und kommen zum roten Punkt, der das Ende des Syntaxdiagramms andeutet.

Ableitungen

Schauen Sie sich nun das nächste Bild an.

Eine Ableitung

Auf diesem Bild sieht man eine sogenannte Ableitung. Eine solche Ableitung wird mit Hilfe eines Syntaxdiagramms erzeugt. Man startet mit dem Ausdruck expr. Dann erweitert man expr zu expr * expr. Das ist der zweitoberste Weg im Syntaxdiagramm. Im nächsten Schritt wird das linksstehende expr zu einer Zahl umgewandlet, aus expr wird also num. Das Gleiche macht man im nächsten Schritt, das rechts stehende expr wird ebenfalls in eine Zahl umgewandelt. Am Ende hat man einen fertigen arithmetischen Ausdruck stehen.

Ein Syntaxdiagramm für arithmetische Ausdrücke mit fünf Produktionsregeln

Diese Abbildung zeigt uns ein etwas erweitertes Syntaxdiagramm. An die blauen Pfeile wurde nun das Wort "Produktionsregel" geschrieben. Wir sehen hier fünf verschiedene Produktionsregeln, die man folgendermaßen in Worten beschreiben könnte:

P1: expr ===> expr + expr
P2: expr ===> expr - expr
P3: expr ===> num
P4: expr ===> id
P5: expr ===> ( expr )

Wie können wir nun den folgenden Ausdruck herleiten ?

num * num

Die Ableitung mit Angabe der Produktionen

• Zunächst wenden wir zunächst die Produktionsregel 2 an und erhalten aus dem Startsymbol expr den Ausdruck expr * expr.
• Auf das linke expr dieses Ausdrucks wenden wir die Produktion 3 an und erhalten den Ausdruck num * expr.
• Auf das rechte expr dieses Ausdrucks wenden wir abermals die Produktion 3 an und erhalten den Ausdruck num * num.

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu

Ein Java-Generator für arithmetische Ausdrücke

Sie wollen jetzt endlich wieder mal etwas Praktisches programmieren, das ist ja bekannt.

Hier ein paar Beispiele für auf diese Weise erzeugte Ausdrücke:

num+id+id*((id))
id+(id)
num
id
(id)*num
id
(id+(id))
(num+(num))+(id*num)
num+num*num+(num)*num*num+id
(num)
(num+num*id*num)+num+num
num+num

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu