Fachkonzept - Syntaxdiagramm

Beispiel: Rechenausdrücke

Rechenausdrücke wie z. B. x*(y+2) oder (2*x+3*y)*(4*y-z) sind sprachliche Ausdrücke, in denen Zahlen, Variablen, Rechenzeichen und Klammern vorkommen können und die nach bestimmten Regeln gebildet werden.

Die Sprache der Rechenausdrücke kann man formal wie folgt beschreiben: Der Sprache der Rechenausdrücke liegt das Alphabet

Σ = {0, 1, ..., 9, x, y, z, +, -, *, /, (, )}

zu Grunde. Über diesem Alphabet lassen sich eine Vielzahl von Wörtern bilden, z. B. (), x++ oder 2*x+3. Die Sprache L_RA der korekt gebildeten Rechenausdrücke ist eine bestimmte Teilmenge der Gesamtheit Σ^* aller Wörter über Σ:

LRA = {0, 1, ..., x, y, z, ..., x+0, x+1, ...}

Welche Wörter über Σ zu L_RA gehören, ist einer Mengendarstellung mit ... nicht genau zu entnehmen.

Eine präzise und konstruktive Beschreibung der Sprache L_RA kann man z.B. mit Hilfe von Syntaxdiagrammen erstellen.

Ausdruck:

Summand:

Faktor:

Variable:

Zahl:

Ziffer:

Jeder Weg durch diese Diagramme - beginnend im Diagramm Ausdruck - liefert einen korrekt gebildeten Rechenausdruck:

Ausdruck ->
Summand + Summand ->
Faktor + Summand ->
Variable + Summand ->
x + Summand ->
x + Faktor * Faktor ->
x + Zahl * Faktor ->
x + Ziffer Fiffer * Faktor ->
x + 2 Ziffer * Faktor ->
x + 2 0 * Faktor ->
x + 2 0 * Variable ->
x + 2 0 * y

Dabei dürfen nur noch die Symbole in den abgerundeten Kästen vorkommen. Symbole in eckigen Kästen stehen für Teilwege, die in separaten Diagrammen festgelegt sind. Diese müssen passend zu den entsprechenden Diagrammen ersetzt werden.

Bei der Ableitung eines Weges wird eine Symbolfolge schrittweise umgeformt. Wir starten mit dem Symbol Ausdruck. Das Diagramm Ausdruck legt fest, wie dieses Symbol ersetzt werden kann. Wir wählen einen Weg, der zur Symbolfolge Summand + Summand führt. Das erste Symbol Summand lässt sich jetzt mit dem entsprechenden Diagramm Summand ersetzen. Wir wählen hier einen Weg, der dieses Symbol durch das Symbol Faktor ersetzt. Es ergibt sich die neue Symbolfolge Faktor + Summand, usw.. Nach einer Reihe weiterer Umformungen erhält man schließlich die Symbolfolge x + 2 0 * y bzw. das Wort x+20*y.

Umgekehrt lässt sich auch jeder korrekt gebildete Rechenausdruck durch einen Weg durch die Diagramme erzeugen. Für den Rechenausdruck (x+y)*(x-y) könnte man folgende Wegbeschreibung benutzen:

Ausdruck ->
Summand ->
Faktor * Faktor ->
( Ausdruck ) * Faktor ->
( Summand + Summand ) * Faktor ->
( Faktor + Summand ) * Faktor ->
( Variable + Summand ) * Faktor ->
( x + Summand ) * Faktor ->
( x + Faktor ) * Faktor ->
( x + Variable ) * Faktor ->
( x + y ) * Faktor ->
( x + y ) * ( Ausdruck ) ->
( x + y ) * ( Summand - Summand ) ->
( x + y ) * ( Faktor - Summand ) ->
( x + y ) * ( Variable - Summand ) ->
( x + y ) * ( x - Summand ) ->
( x + y ) * ( x - Faktor ) ->
( x + y ) * ( x - Variable ) ->
( x + y ) * ( x - y )

Aufbau von Syntaxdiagrammen

Im Folgenden soll das Fachkonzept "Syntaxdiagramm" präzisiert werden.

Im Beispiel oben sind Ausdruck, Summand, Faktor, Variable, Zahl, Ziffer die benutzten Nichtterminalsymbole und 0, 1, ..., 9, x, y, z, +, -, *, /, (, ) die Terminalsymbole.

Mit Hilfe von Syntaxdiagrammen lassen sich Wörter über dem Alphabet der Terminalsymbole ableiten. Eine Ableitung besteht dabei aus einer Folge von Umformungen einer Symbolfolge entlang der Wege durch die Syntaxdiagramme mit dem Ziel, die Nichtterminalsymbole letztlich alle durch Terminalsymbole zu ersetzen. Zwei solche Herleitungen sind oben im Beispiel dargestellt.

Die Verbindung von Terminal- und Nichtterminalsymbolen mit Hilfe von Pfeilen lässt folgende Konstruktionsmuster erkennen:

Sequenz:

A

Alternative:

A

Iteration:

A

Rekursion:

A