Syntaxdiagramm
Ein Syntaxdiagramm zeigt die Regeln einer Sprache als Wegenetz. Jeder Weg vom Eingang zum Ausgang ergibt ein gültiges Wort.
Definition
Ein Syntaxdiagramm ist die grafische Darstellung einer Regel der Backus-Naur-Form. Für jedes Nichtterminal gibt es ein eigenes Diagramm, das nach dem Nichtterminal benannt ist. Jedes Diagramm hat einen Eingang und einen Ausgang. Das Diagramm des Startsymbols ist das Startdiagramm, dort beginnt jede Prüfung.
Ein Wort gehört zur Sprache, wenn ein Weg in Pfeilrichtung vom Eingang zum Ausgang des Startdiagramms genau die Zeichen des Wortes liefert. Trifft der Weg auf ein Nichtterminal, wird zuerst dessen Diagramm durchlaufen. Danach geht der Weg an dieser Stelle weiter.
Elemente

Der Weg beginnt am Eingang links und endet am Ausgang rechts. Pfeile geben die Richtung an. Ein Syntaxdiagramm besteht aus sechs Elementen:
- Terminal: ein Element mit runden Ecken. Es enthält ein Zeichen oder ein festes Wort, das wörtlich im Text steht.
- Nichtterminal: ein Rechteck. Es verweist auf das Diagramm dieses Nichtterminals. Das kann auch das eigene Diagramm sein, dann ist die Regel rekursiv.
- Folge: Elemente auf demselben Weg werden nacheinander durchlaufen.
- Alternative: Der Weg verzweigt. Genau ein Zweig wird gewählt.
- Wiederholung: Ein Rückweg führt hinter dem Element zurück an dessen Anfang. Das Element wird mindestens einmal durchlaufen und darf beliebig oft wiederholt werden.
- Option: Ein Weg führt am Element vorbei. Das Element darf entfallen.
Führt um eine Wiederholung zusätzlich ein Weg herum, darf das Element beliebig oft vorkommen, auch keinmal.
Von der Backus-Naur-Form zum Syntaxdiagramm
Jede Regel der BNF oder der erweiterten BNF ergibt ein Diagramm mit dem Namen des Nichtterminals auf der linken Seite. Die rechte Seite wird Element für Element übertragen. A und B stehen dabei für beliebige Teile der rechten Seite:
| Regel | Syntaxdiagramm |
|---|---|
Folge A B |
Kette: A und B hintereinander auf einem Weg |
Alternative A | B |
Verzweigung: ein Weg durch A, ein Weg durch B |
Option [ A ] (nur erweiterte BNF) |
ein Weg durch A und ein Weg an A vorbei |
Wiederholung { A } (nur erweiterte BNF) |
A mit Rückweg und zusätzlich ein Weg an A vorbei |
| Nichtterminal | Rechteck, das auf das Diagramm des Nichtterminals verweist |
| Terminal | Element mit runden Ecken |
{ A } erlaubt auch null Durchläufe. Ein Rückweg um ein Element bedeutet dagegen mindestens einen Durchlauf. Für { A } gehört deshalb zum Rückweg zusätzlich ein Weg an A vorbei, wie bei der Option. Die Folge A { A } dagegen ergibt ein einziges Element A mit Rückweg und ohne Weg daran vorbei: A kommt mindestens einmal vor.
Eine leere Alternative ε der BNF wird zu einem Weg ohne Element. Eine Regel der BNF, die sich selbst verwendet, um etwas zu wiederholen, wird im Diagramm zu einem Rückweg. Verwendet sich eine Regel selbst, um etwas zu verschachteln, bleibt im Diagramm das Rechteck mit dem eigenen Namen stehen.
Vom Syntaxdiagramm zur Backus-Naur-Form
Aus jedem Diagramm entsteht eine Regel:
- Der Name des Diagramms wird das Nichtterminal auf der linken Seite.
- Der Weg wird vom Eingang zum Ausgang verfolgt. Elemente hintereinander ergeben eine Folge. Terminale werden wörtlich notiert, in der erweiterten BNF in Anführungszeichen. Nichtterminale stehen in spitzen Klammern.
- Eine Verzweigung ergibt Alternativen, getrennt durch
|. - Ein Weg an einem Element vorbei ergibt in der erweiterten BNF eine Option
[ A ]. In der BNF ohne Erweiterungen entstehen zwei Alternativen, eine mit und eine ohne das Element. - Ein Rückweg um ein Element ergibt in der erweiterten BNF
A { A }. In der BNF ohne Erweiterungen übernimmt ein neues Nichtterminal die Wiederholung mit einer Regel, die sich selbst verwendet. - Ein Rückweg um ein Element zusammen mit einem Weg an ihm vorbei ergibt in der erweiterten BNF
{ A }. In der BNF ohne Erweiterungen hat das neue Nichtterminal dann die AlternativenεundAgefolgt vom neuen Nichtterminal.
Beispiele
Ganze Zahl als Syntaxdiagramm darstellen
Dargestellt wird die Regel für <zahl> aus dem Beispiel Ganze Zahl beschreiben, zusammen mit den beiden Regeln, auf die sie verweist:
<zahl> ::= [ <vorzeichen> ] <ziffer> { <ziffer> }
<vorzeichen> ::= "+" | "-"
<ziffer> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Es entstehen drei Diagramme:

- Diagramm Zahl: Die Option
[ <vorzeichen> ]ergibt einen Weg, der am Rechteck Vorzeichen vorbeiführt. Danach folgt<ziffer> { <ziffer> }: eine Ziffer, der beliebig viele Ziffern folgen dürfen. Das ist ein Rechteck Ziffer mit Rückweg, denn die Ziffer kommt mindestens einmal vor. - Diagramm Vorzeichen: Der Weg verzweigt in die Terminale
+und-. Im Diagramm stehen sie ohne Anführungszeichen, die runden Ecken kennzeichnen sie als Terminale. - Diagramm Ziffer: Der Weg verzweigt in die Terminale
0bis9. Das Bild kürzt mit … ab.
Wörter mit einem Syntaxdiagramm prüfen
Vier Wörter werden mit den Diagrammen der ganzen Zahl geprüft. Der Weg beginnt im Diagramm Zahl und folgt den Zeichen des Wortes von links nach rechts.
| Wort | Weg | Ergebnis |
|---|---|---|
-12 |
Der Weg führt durch das Rechteck Vorzeichen, sein Diagramm liefert -. Dann liefert Ziffer die 1. Der Rückweg führt noch einmal zu Ziffer, sie liefert die 2. Der Weg endet am Ausgang. |
passt |
7 |
Der Weg führt am Vorzeichen vorbei. Ziffer liefert die 7. Der Weg endet am Ausgang. |
passt |
12- |
Die Ziffern 1 und 2 führen zum Ausgang. Das - bleibt übrig. Ein Vorzeichen steht nur am Anfang. |
passt nicht |
+ |
Das Vorzeichen + ist lesbar. Danach müsste mindestens eine Ziffer folgen, sie fehlt. |
passt nicht |
Wiederholung mit Trennzeichen als Syntaxdiagramm darstellen

Dargestellt wird die Regel für eine Menge von Ziffern aus dem Beispiel Erweiterte Form in die Backus-Naur-Form überführen:
<menge> ::= "{" <ziffer> { ";" <ziffer> } "}"
- Die Terminale
{und}stehen am Anfang und am Ende des Weges, jeweils als Element mit runden Ecken. - Dazwischen folgt das Rechteck Ziffer.
- Die Wiederholung
{ ";" <ziffer> }darf auch keinmal vorkommen. Sie wird deshalb zu einem Rückweg um die Folge aus;und Ziffer und zusätzlich zu einem Weg, der an dieser Folge vorbeiführt.
Drei Zeichenfolgen werden geprüft:
{7}: Der Weg führt durch{und durch Ziffer, dann an der Wiederholung vorbei und durch}. Die Zeichenfolge passt.{4;0;7}: Nach der ersten Ziffer führt der Weg durch;und Ziffer, über den Rückweg noch einmal durch;und Ziffer und dann durch}. Die Zeichenfolge passt.{4;}: Nach dem Semikolon muss eine Ziffer folgen, es folgt aber}. Die Zeichenfolge passt nicht.
Rekursive Regel als Syntaxdiagramm darstellen

Die Regel für korrekt geklammerte Ausdrücke aus dem Beispiel Grammatik in die Backus-Naur-Form übertragen verwendet sich selbst:
<ausdruck> ::= ( <ausdruck> ) <ausdruck> | ε
Die leere Alternative ε wird zu einem Weg ohne Element. Die andere Alternative wird zu einem Weg mit vier Elementen: dem Terminal (, dem Rechteck Ausdruck, dem Terminal ) und noch einmal dem Rechteck Ausdruck. Beide Rechtecke verweisen auf das Diagramm selbst.
Ein Rückweg kann diese Rekursion nicht ersetzen: Zu jeder öffnenden Klammer muss später genau eine schließende folgen, und ein Rückweg zählt nicht mit, wie oft er durchlaufen wurde.
Zwei Wörter werden geprüft:
(): Der Weg führt durch(. Für das erste Rechteck wird das Diagramm erneut durchlaufen, und zwar auf dem Weg ohne Element. Danach führt der Weg durch). Auch für das zweite Rechteck wird das Diagramm auf dem Weg ohne Element durchlaufen.(()): Der Weg beginnt wieder mit(. Für das erste Rechteck wird das Diagramm jetzt auf dem Weg mit den Klammern durchlaufen, er liefert wie eben(). Danach folgen)und für das zweite Rechteck der Weg ohne Element.
Syntaxdiagramm in die Backus-Naur-Form überführen

Das Diagramm beschreibt Dezimalzahlen wie 3,14 oder 42. Das Rechteck Ziffer verweist auf das Diagramm Ziffer aus dem ersten Beispiel. Gesucht sind die Regeln in der erweiterten BNF und in der BNF ohne Erweiterungen.
Schritt 1: Weg verfolgen. Der Weg führt zuerst durch das Rechteck Ziffer mit Rückweg: eine oder mehrere Ziffern. Danach verzweigt er. Der obere Weg führt direkt zum Ausgang. Der untere Weg führt durch das Terminal , und noch einmal durch ein Rechteck Ziffer mit Rückweg. Der Teil hinter dem Komma ist also eine Option.
Schritt 2: Erweiterte BNF notieren. Der Rückweg wird zu <ziffer> { <ziffer> }, die Option steht in eckigen Klammern, das Komma als Terminal in Anführungszeichen:
<dezimalzahl> ::= <ziffer> { <ziffer> } [ "," <ziffer> { <ziffer> } ]
Schritt 3: BNF ohne Erweiterungen notieren. Das neue Nichtterminal <ziffern> übernimmt die Wiederholung. Aus der Option werden zwei Alternativen, eine ohne und eine mit Nachkommateil:
<dezimalzahl> ::= <ziffern> | <ziffern> , <ziffern>
<ziffern> ::= <ziffer> | <ziffer> <ziffern>
Schritt 4: Prüfen. Für 42 führt der Weg durch Ziffer, über den Rückweg noch einmal durch Ziffer und dann auf dem oberen Weg zum Ausgang. Für 3,14 führt er einmal durch Ziffer, dann auf dem unteren Weg durch das Komma und zweimal durch Ziffer. Beide Zahlen lassen sich auch mit beiden Fassungen der Regeln bilden. ,5 passt nicht, weil vor dem Komma mindestens eine Ziffer stehen muss. 7, passt nicht, weil hinter dem Komma mindestens eine Ziffer folgen muss.